RSA暗号のアルゴリズム

　RSA暗号のアルゴリズムをいかに示す。

1. ある大きな２つの素数 p,q を選んで n = p * q とする。
2. (p-1) * (q-1) 以下で (p-1) * (q-1) と互いに素の数　e を選ぶ。
3. e * d mod (p-1) * (q-1) = 1 となる整数 d を求めると (e, n)が公開鍵, (d,n)が秘密鍵となる。

このとき、平文 M を暗号化するには C = M^e mod nとし、暗号文 C を複合化するには　M = C^d mod n　とすればよい。

RSA暗号の鍵生成編　-----------------------------------------------------------------------------------------------------------

　p=5, q=7の場合
　p=5, q=7とすると、n=35, (p-1) * (q-1) = 24
　24以下で、24と互いに素となる数e=5を決める。
　(5*d) mod 24 = 1となる d は　29 ( d=5では可だが、公開鍵とおなじになってしまう。)

　(5, 35)が公開鍵, (29,35)が秘密鍵となる。

RSA暗号の解読編 --------------------------------------------------------------------------------------------------------------

　公開鍵(e,n)が与えられているとする。nを因数分解して n = p * qを満足するp,qを決める。
　ここで、e * d mod (p-1) * (q-1) = 1をなる整数を求めると(d , n)が秘密鍵となる。
　つまり、n を因数分解することができれば容易に秘密鍵を求めることができる。

　実際に計算してみる。

　公開鍵(7, 33)
　33 を因数分解して 33 = 11 * 3　すなわちp=11,q=3となる。
　(11 - 1) * (3 - 1) = 20であるので (7 * d) mod 20 = 1　となる d は
　d = 21/7　= 3　となる。
　したがって、秘密鍵は(3, 33)である。

　実際に確認してみる。

　5を暗号化 5^7 mod 33 = 78125 mod 33 = 14
　14を複合化 14^3 mod 33 = 2744 mod 33 = 5　

　５を暗号化したら１４になり、１４を複合化したら５になった。