RSA暗号の簡単な解説

これまで何となくの理解で使ってきた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$、$q$ を生成する。
• $(p-1)(q-1)$ と互いに素な整数 $e$ を用意する。
• 拡張ユークリッド互除法で $d e \equiv 1 \ (\mathrm{mod}\ (p-1)(q-1))$ となる $d$ を求める。
• $n \ (=pq)$ と $e$ を公開鍵、$d$ を秘密鍵とする。

暗号化

• メッセージ $m (0 \geq m \geq n)$ から公開鍵を使って暗号文 $C$ を求める。
• $C = m^{e} \ (\mathrm{mod}\ n)$

メッセージの復号

• 暗号文 $C$ と秘密鍵 $d$ を用いて、復号する
• $C^{k_2} = m^{k_1 k_2} \equiv m \ (\mathrm{mod}\ n)$

参考

• http://www.maitou.gr.jp/rsa/
• http://tsujimotter.hatenablog.com/entry/euler-function
• https://mathtrain.jp/rsaango