セキュリティ
RSA暗号で素数 p=11、q=13 を選んだとき、公開鍵 e=7 に対応する秘密鍵 d の値として正しいものはどれか。ただし d は 7d ≡ 1 (mod 120) を満たす最小の正の整数とする。
ア.103正解
イ.17
ウ.51
エ.77
解説
RSA秘密鍵の計算は「モジュラ逆数を求める」こと。7×d を120で割ると余りが1になるdを探す——7の「120の世界での逆数」がdです。拡張ユークリッド法か地道な探索で求める。
なぜ ア が正解か
アが正解。n=p×q=11×13=143。φ(n)=(p-1)(q-1)=10×12=120。d≡e⁻¹(mod φ(n))、つまり7d≡1(mod 120)を満たすd。確認：7×103=721。721÷120=6余1（120×6=720、721-720=1）。7×103≡1(mod 120)✓。よってd=103。検証：7×17=119≡-1(mod 120)≠1。7×51=357=2×120+117≡117≠1。7×77=539=4×120+59≡59≠1。
出典: AI生成問題（学習用）