Why is "schoolbook" RSA vulnerable to a codebook (table look-up) attack, and what makes it possible?
Schoolbook RSA is deterministic — the same plaintext always encrypts to the same ciphertext — so an attacker can pre-encrypt every likely message under the public key, store the results as a look-up table, and read off plaintexts by matching intercepted ciphertexts.
* Because encryption is repeatable, the attacker precomputes every likely (m, c) pair and inverts intercepts by lookup — no factoring needed. *
RSA on its own is not a probabilistic algorithm: with the public key $(N, e)$ fixed, $c = m^e \bmod N$ is a fixed function of $m$. That determinism is fatal whenever the message space is small or guessable — a yes/no vote, a price from a short list, a PIN, a database field with few values. The attacker knows $(N, e)$, so she simply:
- Enumerates every candidate plaintext $m$.
- Computes $c = m^e \bmod N$ for each and stores the pairs $(m, c)$ — the "codebook".
- Later inverts any captured ciphertext by looking it up in the table.
No factoring of $N$, no knowledge of $d$ — the confidentiality is broken purely because encryption is repeatable. The cure is to destroy the determinism: pad the message with fresh randomness before encrypting (OAEP — Optimal Asymmetric Encryption Padding), so the same plaintext maps to a different ciphertext every time and no finite table can ever cover it. The same padding also kills RSA's multiplicative malleability. (This is an attack on RSA encryption; RSA signing has its own separate weakness — existential forgery, next.)
Go deeper:
Deterministic encryption — why it leaks — the "build a dictionary of plaintext/ciphertext pairs" attack, stated generally.- Optimal Asymmetric Encryption Padding (OAEP) — the randomised padding that turns deterministic RSA probabilistic.