Why does 'textbook RSA' — computing c = m^e mod n directly without padding — fail to achieve semantic security?
Think about your answer, then reveal below.
Model answer: Textbook RSA is deterministic: the same plaintext always produces the same ciphertext. An adversary who wants to distinguish encryptions of m0 vs m1 simply computes m0^e mod n and compares with the ciphertext. Additionally, textbook RSA is multiplicatively homomorphic (E(m1) * E(m2) = E(m1*m2)), enabling chosen-ciphertext attacks. RSA-OAEP adds randomized padding before encryption, making it probabilistic and provably CCA-secure under the RSA assumption.
Semantic security (IND-CPA) requires that encryptions of different messages be indistinguishable. Any deterministic encryption fails this — the attacker can always check their guess by encrypting it. Padding schemes like OAEP introduce randomness and structure that eliminate these weaknesses. No one should ever use textbook RSA in practice.
Question 2 Multiple Choice
RSA key generation requires finding two large primes p and q. Primality testing algorithms like Miller-Rabin are probabilistic. A student worries: what if the algorithm falsely certifies a composite as prime?
AThis cannot happen — Miller-Rabin is deterministic for numbers used in RSA
BIf n = pq where p or q is composite, RSA decryption may fail on some messages and the key is functionally broken. However, the probability of Miller-Rabin giving a false positive after k rounds is at most 4^(-k), so with k = 64 rounds the risk is negligible (less than 2^(-128))
CComposite factors actually make RSA more secure because factoring becomes harder
DThe Chinese Remainder Theorem corrects for any composite factors during decryption
RSA's correctness depends on Euler's theorem, which requires p and q to be prime. If either is composite, phi(n) is computed incorrectly, and decryption fails for some messages. Miller-Rabin's false-positive rate of 4^(-k) means that 64 iterations give a false-positive probability below 2^(-128) — astronomically unlikely. In practice, this probabilistic guarantee is more than sufficient; the risk is far smaller than hardware errors.
Question 3 True / False
An attacker knows the RSA public key (n, e) and wants to compute the private key d. Finding d is computationally equivalent to factoring n.
TTrue
FFalse
Answer: True
This equivalence goes both ways. Given the factorization n = pq, computing d = e^(-1) mod phi(n) is straightforward. Conversely, if an attacker knows d (and e), they can efficiently factor n using a probabilistic algorithm that exploits the relationship ed - 1 = k*phi(n). So computing d without factoring n is exactly as hard as factoring n. This is why RSA's security reduces to the factoring assumption.
Question 4 Multiple Choice
RSA with a 2048-bit modulus n is considered secure today. Why is doubling the key length to 4096 bits more than doubling the security?
ALonger keys use more rounds of encryption, adding security multiplicatively
BThe best known factoring algorithm (General Number Field Sieve) has sub-exponential but super-polynomial runtime in the bit length of n. Doubling the bit length more than doubles the exponent in the runtime expression, providing a super-linear security increase
C4096-bit keys are exactly twice as secure as 2048-bit keys
DLonger keys enable more padding, which adds independent security
GNFS runs in time exp(O(n^{1/3} * (log n)^{2/3})) where n is the bit length. This is sub-exponential — faster than brute force but slower than polynomial. Because the exponent grows as n^{1/3}, doubling n multiplies the exponent by 2^{1/3} ≈ 1.26, which roughly squares the runtime (or more). The security increase is super-linear in key length, which is why RSA key sizes are measured in thousands of bits while symmetric key sizes are measured in hundreds.
Question 5 Short Answer
For RSA signatures, the signer computes s = H(m)^d mod n and the verifier checks that s^e mod n equals H(m). Why is hashing the message before signing essential?
Think about your answer, then reveal below.
Model answer: Without hashing, an attacker can forge signatures using RSA's multiplicative homomorphism: given signatures s1 = m1^d and s2 = m2^d on messages m1 and m2, the attacker computes s1 * s2 = (m1 * m2)^d mod n, which is a valid signature on m1 * m2. Hashing prevents this because H(m1 * m2) != H(m1) * H(m2) — the hash function is not homomorphic, so the algebraic attack fails. Additionally, hashing allows signing messages of any length with a fixed-size RSA operation.
The hash function acts as a barrier against algebraic manipulation. It converts the multiplicative structure of RSA — which an attacker could exploit — into an unstructured computation that the attacker cannot predict or control. Formal signature schemes (RSA-PSS) add randomized padding to the hash for additional security guarantees.