RSA暗号の仕組みを小さな数で確かめる。素数 p = 5、q = 11 から n = pq を作り、公開指数を e = 3 とする。φ(n) = (p − 1)(q − 1) として、e × d ≡ 1 (mod φ(n)) を満たす秘密指数 d(0 < d < φ(n))はどれか。

正解：B. 27

n = 5 × 11 = 55、φ(n) = 4 × 10 = 40 です。3 × d を40で割った余りが1になる d を探すと、3 × 27 = 81 = 2 × 40 + 1 なので、d = 27 です。公開鍵は (n, e) = (55, 3)、秘密鍵は d = 27 で、p と q を知らないと φ(n) が分からず、d を求められないことが安全性の根拠になります。実際のRSA暗号では、p と q はそれぞれ1000ビットを超える大きな素数で、e には65537がよく使われます。

• A. 5は、φ(n) を (p − 1) + (q − 1) = 14 と取り違えて、3 × 5 = 15 ≡ 1 (mod 14) から求めた値です。
• B. 正しい。3 × 27 = 81 ≡ 1 (mod 40) です。
• C. 37は、φ(n) の代わりに n = 55 を使って、3 × 37 = 111 ≡ 1 (mod 55) から求めた値です。