RSA暗号化方式を紐解くその(1)

感覚をつかむため、まずは実際の数値での例を見てみましょう。

RSAの秘密鍵、公開鍵のペアを16bitの長さで生成してみました。
16bitを指定するとmodulusの大きさが16bitになります。

modulus:29353 秘密鍵
exponentE:65537 秘密鍵(通常65537固定なのであまり秘密ではない)
exponentD:15825 公開鍵
primeP:197
primeQ:149

ここでprivateキーがmodulesとexponentEであり、publicキーがexponentDです。
primePとprimeQは暗号化、復号化の際には使わず必要ありませんので、当面気にしなくて良いです。

modulusをn、exponentEをe、exponentDをdで表すことにします。
任意の平文m ( $0 \leq m$ < nとなる整数)を暗号化して暗号文c(整数)を作成してみましょう。
$c = {m} ^ {e} \mod n$
計算はpythonで行います。m=1234とすると、

>>> (1234 ** 65537) % 29353
13474L

暗号文c = 13474を復号化してみましょう。
$m = {c} ^ {d} \mod n$

>>> (13474 ** 15825) % 29353
1234L

元に戻りましたね。
なぜベキ乗とモジュロ演算を使うとうまく動作し安全な暗号が作れるのでしょうか。
徐々に見ていこうと思います。

次回に続く。