An adversary has RSA's public key (n, e) and wants to find the private key d. What information do they need that they cannot easily obtain?
AThe value of the ciphertext c = mᵉ mod n
BThe factorization of n into its prime factors p and q
CThe value of the modular inverse of e in ℤ
DThe bit-length of the modulus n
To find d, the attacker must compute d ≡ e⁻¹ (mod φ(n)). But computing φ(n) = (p−1)(q−1) requires knowing p and q — which requires factoring n. With a 2048-bit modulus, no known classical algorithm can factor n in feasible time. Options A and D give no useful information; option C is impossible to compute without φ(n).
Question 2 Multiple Choice
Textbook RSA without padding allows an attacker who intercepts ciphertexts c₁ = m₁ᵉ mod n and c₂ = m₂ᵉ mod n to compute the ciphertext of m₁·m₂ without knowing the messages. This attack works because:
AThe encryption exponent e is publicly known, so anyone can re-encrypt
CModular exponentiation can be reversed with two ciphertext samples
DThe product m₁·m₂ is always smaller than n
Textbook RSA preserves multiplicative structure: (m₁m₂)ᵉ mod n equals (m₁ᵉ mod n)·(m₂ᵉ mod n) mod n. So c₁·c₂ mod n is a valid ciphertext for m₁m₂. This algebraic leakage is why padding schemes like OAEP are mandatory in practice — they destroy the clean algebraic structure that makes such manipulation possible.
Question 3 True / False
RSA's security rests on the difficulty of computing discrete logarithms — recovering the exponent from a modular power.
TTrue
FFalse
Answer: False
RSA's security rests on the hardness of *integer factorization*, not discrete logarithm. An attacker who can factor n = pq immediately recovers φ(n) = (p−1)(q−1) and then d = e⁻¹ mod φ(n). Discrete logarithm hardness underlies different cryptographic schemes such as Diffie-Hellman and elliptic curve cryptography.
Question 4 True / False
If you know the two primes p and q used to generate an RSA key with public exponent e, you can compute the private key d.
TTrue
FFalse
Answer: True
Yes. Knowing p and q lets you compute φ(n) = (p−1)(q−1), and then d = e⁻¹ mod φ(n) via the extended Euclidean algorithm. This is exactly why keeping p and q secret is the foundation of RSA security — the public key (n, e) reveals n but not its factors.
Question 5 Short Answer
Why does RSA decryption correctly recover the original message m? Explain the mathematical reason, citing the key theorem involved.
Think about your answer, then reveal below.
Model answer: Decryption works because ed ≡ 1 (mod φ(n)), so ed = 1 + k·φ(n) for some integer k. Then (mᵉ)ᵈ = m^(ed) = m^(1+k·φ(n)) = m · (m^φ(n))^k ≡ m · 1 = m (mod n) by Euler's theorem, which states m^φ(n) ≡ 1 (mod n) when gcd(m, n) = 1. The choice of e and d as modular inverses mod φ(n) is precisely what makes encryption and decryption inverse operations.
The key is Euler's theorem. The exponents e (encrypt) and d (decrypt) are chosen to be multiplicative inverses mod φ(n), so raising m to the ed power mod n cycles back to m. Without knowing φ(n) — which requires factoring n — an attacker cannot find the right d, even though they know e and n.