RSAの実装を頼まれたので差し支えない範囲で書きたいと思う。

数学的な理論は置いておくとして、RSAの暗復号方式については、RFC8017に書かれている。

暗号化は、c = m^e mod n、復号は、m = c^d mod n とある。

この計算を試してみたいと思う。

まず、

openssl genrsa -out key.pem

で鍵を作る。

openssl rsa -in key.pem -text

で内容を見ることができる。

modulus が上の式の n で、public exponent が e、private exponent が d だろう。

このままだと、

modulus:
     00:c6:33:df:6c:04:ed:38:7e:ae:67:22:a4:17:aa:
     8b:f7:ae:1e:c5:f1:b0:dd:84:b9:f1:95:84:1a:2e:
     17:c1:5e:9e:4c:d7:00:91:13:39:a8:1a:87:ea:4c:
     60:3c:85:c5:3d:87:49:f1:43:b7:7c:35:08:79:4c: 
                          :

のような形式で、python に貼り付けづらいので、

openssl asn1parse -in key.pem

で 3 行目の値を n に、4 行目の値を e に、5行目の値を d にセットする。

python3 では、長い整数を扱えるので、n=0xC633DF6C…. のようにして変数に代入する。e、d も同様に。

c = m^e mod n の計算だが、python3 だと、pow(m, e, n) で暗号化できる。復号は pow(c,d,n)

m=0x123456など(n未満の数字)を入れて試してみてほしい。

実際には、平文を推測しづらくするよう、padding 等の方法が決められている。

参考になる本

C言語で実装してみて、あまりにも遅く、事前に以下の本を読んでおけばよかった・・・と後悔した。

Knuth先生によるアルゴリズムの本。長い整数の演算方法、特に割り算方法は非常に参考になる。

暗号化で使われる効率的な計算方法について書かれている。(実装してみて演算速度が遅く、参考にPython3のソースを見て、コメントからこの書籍を知った。)

この本には、Squaring という章があるので、二乗計算の効率的な計算方法があるのだろう。例えば、各桁を a b c と見たとして、(a+b+c)^2 = a^2 + b^2 + c^2 + 2ab + 2bc + 2cb なので、計算速度を劇的に減らせるかもしれない。

あわせてどうぞ。