RSA暗号方式

原理

p,q を素数とすると その積 N (p*q) を法とする世界では、任意の整数 n についてある数の n(p-1)(q-1) + 1 乗は元の数と一致する。
つまり n(p-1)(q-1) + 1回、その数を掛けると元に戻る。

鍵の生成

  1. 無作為に２つの素数 P, Q を選ぶ
  2. N = P*Q として法を求める。この N が公開鍵の一部となる
  3. φ(N) と互いに素となる(最大公約数が１である)整数eを選択する。オイラー関数φ(N)は次の式で表される φ(N) = (P-1)(Q-1)
    計算を簡単にするために、eには3とか65537がよく用いられる。この e も公開鍵の一部となる
  4. ここで d*e≡1(mod(φ(N) ) つまり d*e mod (φ(N) ) = 1 となる ｄ を選ぶ。このdは拡張ユークリッド互除法を用いると求まる。これが秘密鍵となる。

暗号化処理と復号処理

こうして求まった N, e, d が鍵となり以下のように暗号化および復号化が可能である。

元の平文をＭと、暗号文をＣとすると

暗号化 C = Me mod Ｎ
復号化 M = Cd mod Ｎ

例１

  1. P=47, Q=71 とする
  2. N=3337である
  3. φ(3337)=(47-1)(71-1)=3220と互いに素である整数として e=79を選択する
  4. (79*d) % 3220 = 1 となる d として 1019を選択する。

例２

  1. P=17, Q=23, e=3とする
  2. N=PQ=391
  3. φ(N) = (P-1)(Q-1) = 16*22 = 352
  4. 3*d mod 352 = 1 となる。d として 235 を選ぶ

法としてのNが公開されてしまうと、PとQが求められ、それを元に秘密鍵が計算できるのではないかと思われるが、Nを非常に大きな数にすると、大きな数の素因数分解は効率的な解を求める方法がまだ見つかっていない。

非常にわかりやすいサイト：http://www.maitou.gr.jp/rsa/