Textbook RSA encrypts m as m^e mod n with no padding. Give three separate attacks it permits, including one that works when the same message is sent to three recipients with e = 3, and say what…

Question

Textbook RSA encrypts m as m^e mod n with no padding. Give three separate attacks it permits, including one that works when the same message is sent to three recipients with e = 3, and say what padding scheme fixes each.

Accepted Answer

Textbook RSA is deterministic, malleable, and breakable outright by the small exponent attack, and OAEP padding fixes all three. First, determinism: encryption has no randomness, so identical plaintexts give identical ciphertexts and an attacker with a small message space, such as a price level or a yes or no field, simply encrypts every candidate and compares. Second, malleability: because (m1 * m2)^e = m1^e * m2^e mod n, an attacker multiplies a ciphertext by 2^e and the recipient decrypts twice the original value, so a signed amount can be doubled without the key. The same identity gives a blinding attack against a decryption oracle. Third, the small exponent attack with e = 3: if the same m is sent to three recipients with moduli n1, n2, n3, the attacker takes the three ciphertexts and applies the Chinese remainder theorem to recover m^3 mod n1n2n3. Since m is smaller than every modulus, m^3 is smaller than the product, so the value recovered is the exact integer m^3 and an ordinary integer cube root gives m with no factoring at all. OAEP fixes these by mixing the message with a fresh random value through two hash-based rounds, so encryption is randomised, the padded value fills the modulus, and any manipulation of the ciphertext produces a padding failure on decryption. Signatures need PSS for the same reasons.