In 1949, one year after unveiling information theory, Claude Shannon published another declassified masterpiece in the Bell System Technical Journal titled “Communication Theory of Secrecy Systems.” This single paper transformed cryptography from an esoteric, empirical dark art of cipher wheels and frequency counts into a rigorous branch of mathematics. While military cryptographers historically judged ciphers by how long they resisted human codebreakers, Shannon proved that there exists an absolute mathematical ceiling: Perfect Secrecy. He proved that Gilbert Vernam’s 1917 One-Time Pad (OTP) is mathematically unbreakable by any adversary regardless of computational power, while simultaneously proving the sobering converse: achieving perfect secrecy requires a truly random key that is at least as long as the message itself.
1. The Mathematical Formalism of a Cipher System
Shannon formalized a secrecy system through three random variables defined on finite probability spaces:
- Plaintext Message Space $mathcal{M}$: Message $M$ with prior probability distribution $p(m)$ and entropy $H(M)$.
- Key Space $mathcal{K}$: Secret key $K$ chosen independently of $M$ with distribution $p(k)$ and entropy $H(K)$.
- Ciphertext Space $mathcal{C}$: Transmitted ciphertext $C = E_K(M)$ produced by an invertible encryption function $E: mathcal{M} times mathcal{K} to mathcal{C}$.
Decryption is deterministic: $D_K(E_K(M)) = M$. Kerckhoffs’ Principle (1883)—that the security of a cryptosystem must reside entirely in the secrecy of the key, not in the secrecy of the algorithm—was elevated by Shannon to a foundational axiom: the adversary knows the encryption function $E$ and the probability distribution $p(m)$ perfectly.
2. The Definition and Proof of Perfect Secrecy
When does an encrypted transmission protect a message completely? Shannon defined Perfect Secrecy as the condition where the observed ciphertext $C$ reveals zero information about the underlying plaintext message $M$:
[
p(M = m | C = c) = p(M = m) quad forall m in mathcal{M}, c in mathcal{C}
]
In the language of information theory, observing the ciphertext must result in zero mutual information between plaintext and ciphertext:
[
I(M; C) = 0 iff H(M|C) = H(M)
]
The conditional entropy $H(M|C)$—which Shannon termed the equivocation—remains identical to the original message uncertainty. Even an adversary possessing infinite supercomputing power, alien quantum architectures, or infinite time learns nothing upon intercepting ciphertext $c$ except that a message was sent.
3. Shannon’s Fundamental Cipher Theorem: $H(K) ge H(M)$
Can a short 128-bit key provide perfect secrecy for a 1-megabyte document? Shannon proved the definitive negative theorem:
[
text{If a cipher achieves perfect secrecy, then } H(K) ge H(M)
]
Shannon’s Elegant Proof:
- By definition of mutual information and the properties of entropy:
[
H(M|C) le H(M, K | C) = H(K|C) + H(M | C, K)
] - Because the message is uniquely determined by the ciphertext and the key, the remaining uncertainty $H(M | C, K) = 0$. Therefore:
[
H(M|C) le H(K|C)
] - Conditioning never increases entropy ($H(K|C) le H(K)$). Combining these inequalities:
[
H(M|C) le H(K)
] - For perfect secrecy, we require $H(M|C) = H(M)$. Substituting this requirement yields:
[
H(M) le H(K) implies |mathcal{K}| ge |mathcal{M}|
]
Shannon’s Pessimistic Reality: Perfect information-theoretic secrecy is physically expensive. You cannot achieve unbreakability without consuming a volume of key entropy equal to or greater than the message itself. This proof established the mathematical supremacy of the One-Time Pad ($C = M oplus K$, where $K$ is uniformly random and never reused), which was used on the Moscow-Washington hotline during the Cold War.
4. The Unicity Distance and Computational Cryptography
If the key is shorter than the message ($H(K) < H(M)$), the cipher is imperfect. As the intercepted ciphertext length $N$ increases, the adversary can eliminate spurious keys until only the true key remains.
Shannon defined the Unicity Distance ($U$) as the minimum length of ciphertext required for an adversary with unbounded computational power to determine the key uniquely:
[
U = frac{H(K)}{D} = frac{H(K)}{R_0 – H(L)}
]
where $D = R_0 – H(L)$ is the redundancy of the source natural language (for English, $R_0 = log_2(26) approx 4.7$ bits/char, while entropy $H(L) approx 1.5$ bits/char, yielding redundancy $D approx 3.2$ bits/char). For a classical DES cipher with a 56-bit key, the unicity distance is merely $U approx 56 / 3.2 approx 17.5$ characters!
Because physical keys cannot be as long as all planetary data traffic, modern cryptography abandoned information-theoretic perfection in favor of Computational Security (Diffie, Hellman, Rivest, Shamir, Adleman), where ciphers are breakable in principle, but require computational resources exceeding the physical capacity of the universe.
