The Unicity Distance of Secrecy

Classified Cryptanalysis, the SIGSALY Voice Scrambler, and Proof of the One-Time Pad

Locked inside a fortified room at the Pentagon and a basement vault at Selfridges department store in London during 1943 stood two fifty-five-ton speech scramblers designated SIGSALY. Built by Bell Telephone Laboratories engineers led by A. B. Clark and Ralph Bown, the system protected transatlantic telephone conferences between President Franklin D. Roosevelt and Prime Minister Winston Churchill. Each terminal consisted of forty equipment racks drawing thirty kilowatts of electric power. Earlier analog voice scramblers simply inverted audio frequencies. That flaw had allowed German listening posts on the Dutch coast to descramble transatlantic conversations in real time using optical spectrographs.

SIGSALY abandoned analog inversion for digital pulse-code modulation. A vocoder sliced the speaker's voice into ten narrow frequency bands plus two pitch parameters every twenty milliseconds. It then quantized the amplitudes into discrete six-level steps. To encrypt those digital steps, turntables at Washington and London played synchronized sixteen-inch vinyl phonograph records stamped with pure thermal noise generated by mercury-vapor vacuum tubes. When the random noise values were added modulo six to the quantized voice levels at the transmitter and subtracted at the receiver, the intercepted radio wave sounded like featureless white hiss.

Tasked with auditing the mathematical security of SIGSALY and other wartime ciphers at Bell Labs, Claude Shannon realized a striking gap in scientific knowledge. Thousands of years of cryptography had operated as an intuitive craft without a single rigorous theorem. On September 1, 1945, he completed a classified Bell Labs memorandum titled A Mathematical Theory of Cryptography. The report was declassified and published in 1949 in the Bell System Technical Journal as Communication Theory of Secrecy Systems.

Shannon defined a secrecy system probabilistically. A message source selects a plaintext $M$ with prior probability $P(M)$, and a key source selects a secret key $K$ to transform $M$ into an intercepted ciphertext $C = T_K(M)$. An enemy cryptanalyst with unlimited computing power intercepts $C$ and calculates the posterior probabilities $P(M \mid C)$ of every possible message. Perfect secrecy occurs if and only if intercepting the ciphertext gives the eavesdropper zero statistical information about the plaintext. In mathematical terms, the posterior probability must equal the prior probability, $P(M \mid C) = P(M)$, or equivalently the mutual information vanishes, $I(M; C) = 0$.

Using that definition, Shannon proved mathematically that the one-time pad invented in 1917 by AT&T engineer Gilbert Vernam—and implemented inside SIGSALY's vinyl noise disks—is unconditionally unbreakable. That guarantee holds as long as the random key is never reused and contains at least as much uncertainty $H(K)$ as the message $H(M)$. Why, then, do all ordinary substitution and rotor ciphers with short keys eventually break as an eavesdropper intercepts a longer message of $N$ letters?

Shannon answered that question by deriving the unicity distance $N_0$:

Here $H(K)$ is the key entropy measured in bits, such as $\log_2(26!) \approx 88.4$ bits for a monoalphabetic substitution cipher. The denominator $D = R_0 - R$ is the redundancy of the plaintext language per character. For English, $D$ is the difference between the maximum twenty-six-letter rate $R_0 = \log_2(26) \approx 4.70$ bits per letter and the true entropy rate $R \approx 1.5$ bits per letter, giving $D \approx 3.2$ bits per letter.

When an intercepted cryptogram is shorter than $N_0$, many different false keys decode the ciphertext into plausible English phrases. The cryptanalyst cannot tell which key is real. Once the message length $N$ exceeds $N_0 = 88.4 / 3.2 \approx 28$ letters, language redundancy eliminates almost every spurious key and fixes a unique solution. Because a true one-time pad supplies as many bits of fresh key entropy as the message itself contains, its unicity distance is infinite and no amount of intercepted ciphertext or computing power can ever narrow the set of possible plaintexts.