カテゴリー: メモ

RSA暗号化についてメモ

日本語より式の方がわかりやすいと思うので式で
x , y　　　　　　　　　　　　　　　　　　　　　　　　　　 ( xとyは任意の素数)
n * ( x – 1 ) * ( y – 1 ) + 1 = p*q 　( nは任意の自然数)
x * y
(p , x * y)　と (q, x* y) のセットが鍵
どちらが秘密鍵でも公開鍵でもおｋです。

えらく複雑なことしてるのかと思いきや、
数字を(p * q)乗して、mod (x * y)すると元の数字に戻るという、数字の不思議を利用した暗号化でした。

試しにx = 3, y = 11 とすると、p * q = 21となり p = 3, q = 7となります。
適当に 5 を 21 乗して、mod (x * y)すると (476837158203125 mod 33) = 5 となり復号できます。不思議だ！

一気に21乗すると、いきなり元の値に戻っていまうので、２１を３と７に分割します。
つまり、今回の５を暗号化した結果は、 5^3 mod (x * y) = 26となります。
復号するには、26 ^ 7 mode (x * y) = 5となり復号できました。

この性質を利用して、
鍵Aで暗号化したけど鍵Aでは復号できない、鍵Bでは複合できる
鍵Bで暗号化したけど鍵Bでは復号できない、鍵Aでは複合できる
っていう奇妙な仕組みが実現してるみたい。(公開鍵、秘密鍵)

今回、素数 3 と 11 を使って切りの良い、鍵 3 と 7 が出来たけど、
素数が 5 と 11とかだと、 p * q = 41 となり二つに分割できません。。 41が素数なので無理です。（整数じゃないのもおｋなのかな？
さらに、p * q = 29962177 だと p と q が想像できない！ （ x = 8287 y = 3617
これは上手いこと考えないとプログラムに出来ない！実際どうやって作ってるんだろう。