The One-Time Pad and Shannon: The Only Cipher Proven "Absolutely Secure"

This article has three layers:

1. The intuition: why "anything is possible" means "you know nothing"
2. Real-world use: the Washington–Moscow hotline, the Venona project and why modern encryption doesn't use it
3. The mathematics: the definition and proof of perfect secrecy, the lower bound on key length, the collapse of the two-time pad and a worked example

Layer 1: The Intuition

1.1 Encryption by addition

Turn letters into numbers (A=0, B=1, …, Z=25), and add each plaintext letter to the key letter at the same position, modulo 26:

Decryption just subtracts it back. Computers usually work in binary, where "adding" is XOR.

1.2 Why it can't be broken

Someone holding the ciphertext EQNVZ can try any 5-letter key:

• Key XMCKL → plaintext HELLO
• Key TQURI → plaintext LATER
• Key RCRVB → plaintext NOWAY

Every 5-letter word corresponds to exactly one key. The key was chosen completely at random, so every plaintext is equally possible. No amount of computing power helps: the problem isn't "it can't be computed" but "the answer simply isn't determined".

1.3 All three conditions are required

1. Truly random: it can't be pseudorandom, or an attacker can go after the generator;
2. As long as the message: the key can't be cycled;
3. Used only once: using it twice brings the whole thing down (see sections 2.2 and 3.4).

Layer 2: Real-World Use

2.1 Real uses

• 1917: Vernam at AT&T invented XOR encryption on the teleprinter; Mauborgne then proposed that the key must be random and used only once.
• The Cold War hotline: the Washington–Moscow hotline, set up in 1963 after the Cuban Missile Crisis, was initially encrypted with one-time paper tape.
• Spy codebooks: agents carried small notebooks full of random digits, tearing off each page after use (which is how the name "one-time pad" came about).

2.2 The Venona project: used twice and it's over

During World War II, under wartime production pressure, the Soviet Union printed some codebook pages more than once. The US Army's Venona project (1943–1980) exploited these reused keys to decrypt thousands of Soviet intelligence cables, exposing spies in the Manhattan Project (such as Klaus Fuchs and the Rosenbergs).

2.3 Why modern encryption doesn't use it

So in practice we use stream ciphers (ChaCha20, AES-CTR): a short key generates a long, "random-looking" keystream, which is then XORed in. Security drops from "information-theoretic" to "computational", in exchange for practicality. See "Linear Feedback Shift Registers".

Layer 3: The Mathematics

3.1 The definition of perfect secrecy

Shannon's definition: for any plaintext distribution, any plaintext $m$ and any ciphertext $c$,

$$\Pr[M = m \mid C = c] = \Pr[M = m].$$

Seeing the ciphertext changes nothing at all about what you believe of the plaintext. Equivalently, the distribution of the ciphertext doesn't depend on the plaintext.

3.2 The proof: translation in a group

Let messages, keys and ciphertexts all live in a finite group $(G, +)$ (such as $\mathbb{Z}_{26}^n$ or $\mathbb{F}_2^n$), with the key $K$ uniformly random on $G$, independent of $M$, and $C = M + K$.

For any $m, c \in G$, there is exactly one key $k = c - m$ with $m + k = c$. Therefore

$$\Pr[C = c \mid M = m] = \Pr[K = c - m] = \frac{1}{|G|},$$

which doesn't depend on $m$. Perfect secrecy follows from Bayes' rule.

In abstract algebra terms: for each fixed $m$, the translation $k \mapsto m + k$ is a bijection from $G$ to itself, and a uniform distribution stays uniform under a bijection.

This proof works for any finite group, and "$k-1$ shares reveal nothing" in "Shamir's Secret Sharing" is essentially the same argument.

3.3 The key must be at least as long as the message

Shannon also proved that perfect secrecy requires a key space with $|\mathcal{K}| \ge |\mathcal{M}|$.

The reason: fix a possible ciphertext $c$. If there are fewer keys than plaintexts, then decrypting $c$ with every key gives at most $|\mathcal{K}| < |\mathcal{M}|$ different plaintexts, so some plaintext $m$ can never correspond to $c$, meaning $\Pr[M = m \mid C = c] = 0 \neq \Pr[M = m]$.

So "short key + perfect secrecy" is impossible. This is a theorem of information theory, not an engineering problem yet to be solved.

3.4 A worked example: the two-time pad

Summary