Why raw (textbook) RSA is not enough

We assume RSA is known here: n = p × q, a public exponent e, a private exponent d, and encryption c = m^e mod n. This course starts from an uncomfortable observation: applied as is, RSA is dangerous.

Textbook RSA

We call textbook RSA (or raw RSA) the scheme presented in manuals: you take the message, view it as a number m, and directly compute c = m^e mod n. Nothing else. No processing of the message before encryption.

It is perfect for understanding the principle. It is catastrophic in practice, for three reasons.

Flaw no. 1: it is deterministic

The same message always gives the same ciphertext. The function m -> m^e mod n has no element of randomness.

message "OUI"  --chiffrer-->  c = 8F2A...   (toujours identique)
message "NON"  --chiffrer-->  c = 51CD...   (toujours identique)

Consequence: an eavesdropper watching the channel can recognise a previously seen message. If the possible messages are few in number ("yes" / "no", a vote, a 4-digit PIN code), they encrypt each possibility themselves with the public key and compare. This is a dictionary attack: the private key is never touched.

Flaw no. 2: it is malleable

RSA is homomorphic for multiplication. By multiplying two ciphertexts, you multiply the corresponding plaintexts:

c1 = m1^e mod n
c2 = m2^e mod n
c1 × c2 = (m1^e)(m2^e) = (m1 × m2)^e mod n

The product c1 × c2 is therefore the valid ciphertext of m1 × m2. An attacker can forge the ciphertext of a message they were never able to encrypt themselves, or transform an intercepted message without reading it. They "tamper with" the plaintext remotely.

Flaw no. 3: small messages

If the message is small and the exponent is small, m^e may not exceed n. In that case there is no reduction modulo n, and recovering m amounts to a simple root. That is the subject of the next lesson.

The countermeasure: random padding

The common solution is to add randomness and structure to the message before encrypting it: this is padding. The safe standard for RSA encryption is called OAEP.

• The message is mixed with random bytes, so that encrypting "OUI" twice gives two different ciphertexts: no more determinism and no more dictionary.
• The imposed structure means that a "tampered" ciphertext (product of two ciphertexts) yields, once decrypted, an invalid padding that is rejected: no more malleability.

In summary

Textbook RSA is deterministic (thus vulnerable to a dictionary attack), malleable (c1 × c2 encrypts m1 × m2) and fragile on small messages. Random OAEP padding fixes these flaws by making encryption unpredictable and verifiable. You never encrypt with raw RSA.