In RSA, the plaintext is M = 5 and p = 3, q = 11, d = 7. What ciphertext C is…
2012
In RSA, the plaintext is M = 5 and p = 3, q = 11, d = 7. What ciphertext C is obtained?
Answer: D. 26 — ConceptRSA works with the modulus n = pq and Euler's totient φ(n) = (p − 1)(q − 1). The public exponent e and private exponent d satisfy ed ≡ 1 (mod φ(n)).…
- A.
33
- B.
5
- C.
25
- D.
26
Attempted by 21 students.
Show answer & explanation
Correct answer: D
Concept
RSA works with the modulus n = pq and Euler's totient φ(n) = (p − 1)(q − 1). The public exponent e and private exponent d satisfy ed ≡ 1 (mod φ(n)).
Encryption uses C ≡ Me (mod n), while decryption uses M ≡ Cd (mod n). When d is supplied, e is found as its modular inverse modulo φ(n).
Application
Compute the modulus: n = pq = 3 × 11 = 33.
Compute the totient: φ(n) = (3 − 1)(11 − 1) = 2 × 10 = 20.
Find e from 7e ≡ 1 (mod 20). Since 7 × 3 = 21 ≡ 1 (mod 20), e = 3.
Encrypt M = 5: C ≡ 53 (mod 33) = 125 mod 33 = 26.
Cross-check
Decrypt the computed ciphertext with d = 7. Using repeated squaring, 262 ≡ 16 (mod 33) and 264 ≡ 25 (mod 33).
Thus 267 ≡ 264 × 262 × 26 ≡ 25 × 16 × 26 ≡ 5 (mod 33), which recovers the original plaintext.
Therefore, the ciphertext is C = 26.