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이 자주 쓰입니다.