Unicity Distance

Shannon published this in "Communication Theory of Secrecy Systems" in the Bell System Technical Journal in 1949, the paper that made cryptography a mathematical subject rather than a craft. The question it answers is not "when does the cipher break" but "when does the answer become unique". Below the unicity distance, several different keys decrypt the ciphertext into plausible plaintexts, and the message is genuinely ambiguous — no amount of cleverness can single out the right one, because the information is not there. Above it, exactly one key produces sense, and the cryptanalyst's problem becomes one of effort rather than of information.

The derivation is a bookkeeping argument. Each character of ciphertext narrows the set of surviving keys by the language's redundancy $D$ — the gap between the bits a character could carry and the bits it actually carries. Ordinary English written in 26 letters has $\log_2 26 = 4.70$ bits available per letter, and Shannon's own experiments put its actual entropy at roughly 1.0 to 1.5 bits, so $D$ is about 3.2 to 3.7 bits per character. The key starts with $H(K)$ bits of uncertainty, each character eats $D$ of them, and the uncertainty reaches zero at $U = H(K)/D$.

Shannon's own example is the simple substitution cipher. Its key is a permutation of the alphabet, so $H(K) = \log_2(26!) = 88.4$ bits — a respectable-looking figure — and $U = 88.4/3.2 \approx 28$ letters. Twenty-eight letters of English is about five words. That is the whole indictment of classical ciphers: an 88-bit key that surrenders after five words, because the plaintext leaks 3.2 bits per character and no key size can outrun a leak that scales with message length.

Two things this figure does not say, and both matter. It does not say the cipher falls at $U$ characters — only that the answer becomes unique there. Finding it may still be infeasible, and for a modern block cipher it emphatically is: AES-128's unicity distance over English is about 40 characters, and nobody has ever recovered an AES key from 40 characters of ciphertext, or from forty million. The bound is about how much information is present, never about the work of extracting it. And it does not say that a shorter message is safe. It says a shorter message is ambiguous, which is a real property — a one-time pad has infinite unicity distance and that is exactly why it is unbreakable — but a fragile one, since any external context that rules out the decoy plaintexts collapses the ambiguity immediately.

The practical descendant of this result is Shannon's own remedy: compress the plaintext first. Compression removes redundancy, $D$ falls toward zero, and $U$ grows without bound. That is genuinely sound information theory, and it is also where modern practice diverges — compressing attacker-influenced plaintext before encrypting leaks information through the ciphertext length, which is what the CRIME and BREACH attacks against TLS exploited. Shannon's advice was correct about the quantity he was measuring and silent about a channel that did not exist in 1949.