これまで何となくの理解で使ってきたRSA暗号について理解を深めるために、数学的な理論を調べて（自分なりに）わかりやすくまとめてみました。
基本理論
- $p$ 、$q$ が素数であるとき、$x \equiv 1 \ (\mathrm{mod}\ (p-1)(q-1))$ を満たす $x$ について、$a^x \equiv a \ (\mathrm{mod}\ pq)$ が成り立つ。
- 例えば、$p=3$、$q=5$ とすると、$x = 9, 17, \cdots$ となり、$3^9 = 19683 \equiv 3 \ (\mathrm{mod}\ 15)$、$2^{17} = 131072 \equiv 2 \ (\mathrm{mod}\ 15)$ となる。
- この式はオイラーの定理から導出できる。導出方法の簡単な説明は※1を参照。
- $x = de \equiv 1 \ (\mathrm{mod}\ (p-1)(q-1))$ となるような整数 $d$、$e$ を用意し、$d$、$pq$ を公開鍵、$e$ を秘密鍵とする。
- 送信者はメッセージ $a$ を $e$（公開鍵）乗することで暗号文 $a^e \ (\mathrm{mod}\ pq)$ を作成し、受信者は暗号文を $d$（秘密鍵）乗することで復号：$(a^e)^d = a^x \equiv a \ (\mathrm{mod}\ pq)$ して元のメッセージ $a$ を取り出せる。
- ここで、公開鍵 $pq$ から $p$、$q$ を求めること（素因数分解）は現実的な時間で計算できないため、$(p-1)(q-1)$ を求めて $x$ を割り出し、$d$（秘密鍵）を求めることも困難となる。
※1 式の導出の簡単な説明
- $a$ と $n$ が互いに疎な正の整数であるとき、$a^{\phi(n)} \equiv 1 \ (\mathrm{mod}\ n)$ が成り立つ。（オイラーの定理）
- ここで、オイラー関数 $\phi(n)$ は $n$ と互いに疎な数の個数を表すが、$n$ が素数 $p$、$q$ の積（$n = pq$）である場合を考える。
- $n$ が素数であったとすると、$\phi = n-1$ となる（フェルマーの小定理）が、今回は $p$ と $q$ の倍数がそれぞれ$(q-1)$、$(p-1)$ 個ずつ含まれるので、$\phi(n) = (pq-1) - (q-1) - (p-1) = (p-1)(q-1)$ となる。
- よって、$x \equiv 1 \ (\mathrm{mod}\ (p-1)(q-1))$ を満たす $x$ について、$x = 1 + k(p-1)(q-1) = 1+ k\phi(n)$ と置くことができ、$a^x = a^{1 + k\phi(n)} = a \cdot (a^{\phi(n)})^k \equiv a \cdot 1^k =a \ (\mathrm{mod}\ pq)$ となる。
鍵生成・暗号化・復号の手順
鍵生成
- 大きな素数 $p$ (prime1) 、$q$ (prime2) を生成する。
- $(p-1)(q-1)$ と互いに素な整数 $e$ (public exponent) を用意する。
- 一般的に $e$ には $65537$ が使われる。（参考）
- 拡張ユークリッド互除法で $d e \equiv 1 \ (\mathrm{mod}\ (p-1)(q-1))$ となる $d$ (private exponent) を求める。
- $n \ (=pq)$ (modulus) と $e$ を公開鍵、$d$ を秘密鍵とする。
暗号化
- メッセージ $m (0 \geq m \geq n)$ から公開鍵を使って暗号文 $C$ を求める。
- $C = m^{e} \ (\mathrm{mod}\ n)$
メッセージの復号
- 暗号文 $C$ と秘密鍵 $d$ を用いて、復号する。
- $C^{d} = m^{e d} \equiv m \ (\mathrm{mod}\ n)$