現代のセキュリティの基礎であるRSA暗号、その仕組みと計算原理を知っている人は多いと思いますが、実際に計算した人はあまりいないと思います。また、無味乾燥な演習では味気ないので、後半ではそれを活用して AI に秘密のラブレターを送っていきたいと思います。
という訳で、やっていきましょう。
なお、説明のために実用上ありえない小さい素数を用いています。
公開鍵と秘密鍵のつくりかた
素数のペアp,qを決める
適当な素数 $p,q$ を決めます。ここでは適当に、
- $p=3$
- $q=11$
とします。なお、現実の暗号化でこんな小さな数をつかってはいけません（一瞬で素因数分解されるので）。
pq=N を定める
それらをかけあわせて新しい数を作ります。$N$ とします。
- $N=p\times q=33$
(p-1)(q-1) を計算する
オイラーのトーシェント関数というものを計算します。本来はもっと複雑ですが、素数同士なら $(p-1)(q-1)$ で計算できます。$\phi$ とします。
- $\phi=(3-1)(11-1)=20$
ある公開鍵を決める
$\phi$ と互いに素な数をひとつ適当に決めます。これは互いに素なら何でもよいです。ここでは $3$ とします。これと $N$ のペアが公開鍵になります。
- $(e,N)=(3,33)$
これは世界に公開してもよい情報です。
公開鍵から秘密鍵が定まる
$\mod \phi$ における $e$ の逆元（かけたらあまり $1$ になるような数）が秘密鍵となります。
-
$3 \times d \equiv 1 \mod 20$
-
$d \equiv 7 \mod 20$
-
$(d,N)=(7,33)$
これが秘密鍵になります。これは他人に知られてはいけません。
暗号を用いた会話をAIと行う
秘密の連絡をしてもらう
素数が小さすぎてなぜか秘密鍵まで漏れていますが（本来は逆算不可能です）、AI が暗号を伝えてくれます。
復号する
from string import ascii_lowercase
cipher = []
for c in cipher:
idx = (c**7)%33
print(ascii_lowercase[idx])
秘密の連絡をする
暗号化する
from string import ascii_lowercase
word = ""
for w in word:
idx = ascii_lowercase.index(w)
c = (idx**7)%253
print(c)
驚きの結末とは……！？
こうしてふたりの機密性は保たれたのであった。めでたしめでたし。
（実際はこの秘密鍵も余裕で推測可能なので復元できますが、大きい素数を用いた場合は、これだけの情報では復元は困難です）