The mechanism of RSA is checked with small numbers. From the primes p = 5 and q = 11, n = pq is formed, and the public exponent is e = 3. With φ(n) = (p − 1)(q − 1), which of the following is the private exponent d (0 < d < φ(n)) that satisfies e × d ≡ 1 (mod φ(n))?

Answer: B. 27

n = 5 × 11 = 55 and φ(n) = 4 × 10 = 40. Looking for d such that 3 × d leaves a remainder of 1 when divided by 40, 3 × 27 = 81 = 2 × 40 + 1, so d = 27. The public key is (n, e) = (55, 3) and the private key is d = 27; the security rests on the fact that without knowing p and q one cannot find φ(n), and so cannot find d. In real RSA, p and q are each large primes of more than 1000 bits, and e is commonly 65537.

• A. 5 is the value obtained by mistaking φ(n) for (p − 1) + (q − 1) = 14, from 3 × 5 = 15 ≡ 1 (mod 14).
• B. Correct. 3 × 27 = 81 ≡ 1 (mod 40).
• C. 37 is the value obtained by using n = 55 instead of φ(n), from 3 × 37 = 111 ≡ 1 (mod 55).