RSA
#素数
https://amzn.to/3mauwqK https://gyazo.com/4d585025fa3d714cedb8d708ff46452a
上記の本の中から、他にもいろいろ良い説明がおおい。
暗号化
暗号文 = 平文^E mod N
復号化
平文 = 暗号文^D mod N
手順
Nを求める
大きな素数を２つ(p,q)用意して、掛ける 17x19=323
L を求める
Lは作成途中のみに使う
L = lcm(p-1, q-1): least common multiple, lcm(16,18) = 144
Eを求める
gcd(E, L) = 1を満たす E. Eの候補で(相対的な)素数をみて？ 5
Dを求める
E x D mod L = 1 29は.... 5x29 mod 144 = 1になる
公開鍵(E:5, N:323), 秘密鍵(D:29, N:323)
平文を123とすると、
暗号化する
123^5 mode 323 = 225
225に暗号化
225を復号すると
225^29 mod 323 = 123
123に復号化
225から平文を推測する?
E:5, N:323は分かってる。
225 = X^5 mod 323 で、X を求める
modがあると計算が難しい...らしい。なければ、対数を取るだけだが...