What is OAEP, and how does it fix the problems of textbook RSA?

OAEP (Optimal Asymmetric Encryption Padding) adds random padding to the plaintext before RSA encryption, making it probabilistic and destroying the homomorphic property.

* Adding structured randomness before the RSA step turns the deterministic, malleable schoolbook scheme into a probabilistic, tamper-evident one. *

Problems of "schoolbook" RSA that OAEP fixes:

1. Deterministic encryption — same plaintext → same ciphertext (allows table lookup)
2. Small exponent attacks — with $e = 3$, three intercepted ciphertexts can recover the message
3. Fixed points — $m = 0, 1, N-1$ encrypt to themselves
4. Homomorphic property — ciphertext can be manipulated meaningfully

How OAEP works (PKCS#1 v2.1):

• Before encryption, the message M is padded with random data using a specific structure
• The padded message is then encrypted: $c = \text{pad}(M, \text{random})^e \mod N$
• Decryption reverses: decrypt, then remove and verify padding
• $k$ = length of modulus N in bytes, $M$ = message to encrypt

Result: RSA with OAEP becomes:

• Probabilistic — same message, different ciphertext each time
• No longer homomorphic — multiplying ciphertexts produces garbage
• Provably secure under the RSA assumption (in the random oracle model)

Tip: Think of OAEP as a "format check" turned security mechanism — it adds structure that gets verified on decryption, so any tampering is detected.

Go deeper:

• RFC 3447 — PKCS #1 v2.1 (RSA + OAEP spec) — the primary standard defining RSAES-OAEP.
• Optimal asymmetric encryption padding (Wikipedia) — the Feistel-like padding construction, explained.