Why is "schoolbook" RSA deterministic, and why is this a security problem?

In textbook RSA, the same plaintext always produces the same ciphertext — this allows table-lookup attacks and leaks statistical patterns. OAEP padding solves this.

* Because the mapping is fixed, an attacker with a small message space can precompute every ciphertext and simply look up the intercept — no key needed. *

The problem: $c \equiv m^e \mod N$ is a deterministic function. Given the same key and message, you always get the same ciphertext.

Consequences:

1. Table lookup attack: For small message spaces (like 4-digit PINs), an attacker can precompute all 10,000 possible ciphertexts and look up any intercepted one
2. Statistical patterns: If certain plaintexts are more common, this frequency is visible in the ciphertext
3. Known-plaintext matching: If you suspect a message was sent, encrypt it yourself with the public key and compare

Special "ugly" cases:

• $m = 0$ → $c = 0^e = 0$
• $m = 1$ → $c = 1^e = 1$
• $m = -1 = N-1$ → $c = (N-1)^e \mod N = N - 1$

The solution: OAEP (Optimal Asymmetric Encryption Padding)

• Add random padding to the plaintext before encrypting
• Specified in PKCS#1 v2.1
• Makes RSA probabilistic — same plaintext produces different ciphertext each time
• Destroys the homomorphic property and the deterministic mapping

Contrast: ElGamal and ECC are inherently probabilistic — ciphertexts change every time even for the same plaintext.

Go deeper:

• RSA — attacks on "textbook" RSA (Wikipedia) — why deterministic RSA is never used raw.
• Optimal asymmetric encryption padding (Wikipedia) — the randomised padding that fixes it.