1.2 A Brief History of Ciphers

The best single account of this history is David Kahn’s The Codebreakers, which runs from Babylonian scribes to the Cold War. What follows is a compressed tour: each cipher below was broken by an attack that carries its own lesson, and it is those lessons that the security definitions of Chapter 2 are built to rule out.

Before the tour, we fix the characters and the notation. Alice and Bob want to communicate; an attacker listens. They share a secret key $k\in \mathcal{K}$ about which the attacker knows nothing. A cipher is a pair of algorithms

$$E:\mathcal{K}\times \mathcal{M}\to \mathcal{C},D:\mathcal{K}\times \mathcal{C}\to \mathcal{M},D(k,E(k,m))=m,$$

where the ciphertext $c:=E(k,m)$ crosses the hostile network. Both sides use the same key $k$, so these are symmetric ciphers. Two quantities matter for every historical example:

• the key space $\mathcal{K}$: how many possible keys exist, and
• what the attacker is given. The weakest model, a ciphertext-only attack, hands the attacker nothing but ciphertexts; a cipher that falls in this model is broken outright.

1.2.1 The substitution cipher

A substitution cipher hides a message by relabeling its alphabet. A key is a permutation $\pi$ of the 26 letters; encryption applies $\pi$ letter by letter. For instance, the beginning of one key might be

plaintext	A	B	C	⋯	Z
ciphertext	C	W	N	⋯	A

Under this table the message BCZA encrypts to WNAC, and decryption is applying ${\pi }^{-1}$.

A key is a permutation of the 26 letters.

Quiz: What is the size of the key space of the substitution cipher, assuming 26 letters?

A key is a permutation of all 26 letters, and there are $26!$ of those, so $|\mathcal{K}|=26!\approx 2^{88}$, about 88 bits. That is a respectable key size; AES uses 128.

The substitution cipher is nonetheless easy to break, which gives the first lesson: a large key space is necessary but not sufficient.

1.2.2 The Caesar cipher: not even a key

The Roman-era Caesar cipher is the special case where $\pi$ is the fixed shift by three: $A\mapsto D$, $B\mapsto E$, $\dots$, $X\mapsto A$, $Y\mapsto B$, $Z\mapsto C$. There is no random choice at all: the “key” is written into the design. Anyone who knows the scheme can undo it instantly, and the design of a cipher is assumed public. This is not a cipher in the modern sense; it is a fixed, public function. It survives here only as a cautionary tale about confusing secrecy of the design with secrecy of the key.

1.2.3 Breaking the substitution cipher: frequency analysis

Quiz: What is the most common letter in English text?

E, at roughly $12.7\mathrm{\%}$, far ahead of T ($9.1\mathrm{\%}$) and A ($8.1\mathrm{\%}$). Rare letters like Q and X sit near zero.

English text is not uniform over its alphabet, and a substitution cipher permutes letters, so it preserves each letter’s frequency. Hence a ciphertext-only attack on a long message:

1. Count the frequency of each ciphertext letter. The most frequent ciphertext letter is almost certainly the encryption of E; one entry of the secret table is now known.
2. Repeat for T, then A. Three entries recovered without touching the plaintext.
3. When letter frequencies alone stall (the remaining letters have similar frequencies), escalate to digrams (letter pairs): the most common English pairs (TH, HE, IN, AN) impose consistency constraints on candidate tables. Then trigrams (THE, ING, …) pin down the rest. With a few trials per level, the entire permutation $\pi$ falls, and with it every past and future message.

This is exactly a ciphertext-only attack: given only ciphertexts, the attacker recovers the key. The substitution cipher satisfies no meaningful security definition against even the weakest adversary. Chapter 2 turns “the attacker cannot recover $k$” into an experiment with a precise success probability; for the substitution cipher that probability is essentially one.

1.2.4 The Vigenère cipher: a good idea, badly executed

The Renaissance (16th century) brought a genuine idea: what if the substitution changes as you go? In the Vigenère cipher the key is a short word (say $k=\mathtt{\text{CRYPTO}}$, of period $6$) written repeatedly under the message, and encryption is letterwise addition mod 26:

$$c_i=(m_i+k_{imod6})mod26.$$

Now the plaintext letter E is not encrypted to a single ciphertext letter: it is shifted by whatever key letter sits above it, so the peak at E is smeared across six positions and the letter frequencies of the ciphertext look flat. That was the point.

The execution, however, repeats the weakness of the substitution cipher: the key is periodic. Recover it, and the scheme collapses. The break, assuming the key length $\ell$ is known:

1. Split the ciphertext into $\ell$ interleaved subsequences: position $1,1+\ell ,1+2\ell ,\dots$ form one subsequence.
2. Each subsequence was encrypted by a single Caesar shift (one fixed key letter). Apply frequency analysis independently to each subsequence. The most common letter of subsequence 1 is $E$ shifted by $k_1$, so $k_1=(\text{that letter}-\mathtt{\text{E}})mod26$. Repeat for $k_2,\dots ,k_{\ell }$.
3. If $\ell$ is unknown, run the procedure for $\ell =1,2,3,\dots$ until the recovered plaintext makes sense.

Vigenère’s addition mod 26 is the right operation, and later chapters build on exactly that; what failed was reusing a short key. With a truly random key as long as the message, never reused, the same operation becomes the one-time pad, which Chapter 2 proves perfectly secret. What breaks a periodic cipher is the period: a short key, reused over a long text.

1.2.5 Rotor machines and the Enigma

The nineteenth century made ciphers electric. A rotor machine passes current through rotating wired substitution rotors, so each keypress applies a different substitution. The Hebern machine (one rotor) is the archetype: the rotor is the secret key, wired as a substitution table, and it advances one notch per letter: pressing C three times might emit T, S, K. For a single rotor this is just a Vigenère-style period the size of the alphabet, and it was broken, soon after being advertised, by the same frequency/digram/trigram machinery.

A Hebern machine at the National Cryptologic Museum; the substitution table is wired into the drum. Image source: Roger Brown, CC BY-SA 3.0, via Wikimedia Commons

Rotors then multiplied in an arms race against statistics, culminating in the Enigma: three to five rotors, each stepping at a different rate, plus a plugboard that swapped letter pairs. With four rotors the rotor positions alone give ${26}^4\approx 2^{18}$ keys; the plugboard raises the figure to about $2^{36}$, which is small by the standards of what came next.

An Enigma machine with its lid open. Image source: Robert-brook, CC0 1.0, via Wikimedia Commons

It was nevertheless broken: the British cryptographers at Bletchley Park mounted ciphertext-only attacks on Enigma traffic and decrypted German ciphers in World War II, an effort that played an important role in many battles.

1.2.6 DES, AES, and the block cipher

The mechanical age ended with the war and computers took over. The US government was buying large amounts of digital equipment from industry, and it wanted that equipment to ship with a decent cipher; so it issued a request for proposals for a federal Data Encryption Standard. The design submitted by IBM in 1974 became DES: a 56-bit key, and encryption of 64 bits at a time (eight characters at once) rather than one character, a conceptual jump from everything above. Chapter 3 explains why that jump matters.

DES became a federal standard, but its key space of only $2^{56}$, large in 1974, is small today: a brute-force search is practical, so DES is considered insecure and must not be used in new systems. Legacy systems still use it.

Its successor, standardized in 2001 and built like DES but with 128-bit keys, is AES; alongside the block ciphers, Salsa20 (2008) offers a stream-cipher alternative for high-speed software use, and there are many, many other types of ciphers. Chapter 3 dissects the block-cipher design and explains why “encrypt 128 bits at a time with a 128-bit key” is the right shape of object for proofs; Chapter 2 treats the stream-cipher alternative.

One more tool is needed before any of this can be made precise: probability.