unhurried

コンピュータ関連ネタがほとんど、ときどき趣味も…

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)}

参考