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 なので、計算速度を劇的に減らせるかもしれません。
あわせてどうぞ。