Classical ciphers: Hiding letters: from Caesar to Vigenère

The oldest known “encrypted” text is a tomb inscription in Menet Khufu, Egypt, from around 1900 BC, whose scribe used unusual hieroglyphs, probably to give the text dignity rather than to hide it. Real secrecy shows up a little later: a Mesopotamian clay tablet of about 1500 BC hides a recipe for pottery glaze by writing its words with rare signs, and Spartan generals wound a strip of leather around a staff of fixed thickness, the scytale, wrote along it and sent the strip: unwound, the letters were a jumble; wound on a staff of the same thickness, they lined up again. The scytale transposes letters, changing their order. Most of this chapter is about the other great family: ciphers that substitute letters.

Caesar's shift

Suetonius tells us that Julius Caesar wrote confidential letters “by so changing the order of the letters of the alphabet that not a word could be made out”, and that whoever wanted to read them had to “substitute the fourth letter of the alphabet, namely D, for A, and so with the others”. Number the letters $A = 0, B = 1, \dots, Z = 25$ . Caesar's cipher with key $k$ is

E_{k} (x) = (x + k) mod 26, D_{k} (y) = (y - k) mod 26 .

Caesar used $k = 3$ ; Augustus, his nephew, used $k = 1$ . Hebrew scribes had their own variant, Atbash, which reverses the alphabet ( $x \mapsto 25 - x$ ); it appears in the Book of Jeremiah. ROT13, the shift by 13 that hid joke punchlines on Usenet, is its own inverse because $13 + 13 = 26$ .

Caesar's cipher and how to break it. Change the shift: the ciphertext changes. Below, the attacker's view: the ciphertext decrypted with every other key. With only 25 candidates, the one that reads like the language is obvious, and the figure picks it automatically by comparing letter frequencies (the χ² score explained below).

The weakness is the size of the key space: 25 useful keys can be tried by hand in minutes. The lesson, still valid, is the first rule of cipher design.

Principle (exhaustive search)

Any cipher can be attacked by trying every key and recognising the right plaintext. A cipher with $K$ keys is at most as strong as a search of $K$ trials; to be secure, $K$ must be beyond the attacker's means. Today that means at least $2^{128}$ .

Every permutation of the alphabet

The obvious fix is to allow any rearrangement of the alphabet, not just shifts: write the 26 letters in a scrambled order, often derived from a keyword, and replace each letter by the one under it. This monoalphabetic substitution was the workhorse of diplomacy for a millennium.

Proposition (the key space of substitution)

The keys of a monoalphabetic substitution are the permutations of 26 letters, so there are

26! = 403 291 461 126 605 635 584 000 000 \approx 4 \times 10^{26} \approx 2^{88.4}

of them: more than the keys of DES ( $2^{56}$ ), and far too many to try one by one, even today.

And yet substitution ciphers fall in minutes to a person with a pencil. A large key space is necessary but not sufficient: the cipher must also not leak structure. Monoalphabetic substitution leaks the most important structure of all.

Al-Kindi counts letters

In ninth-century Baghdad, at the House of Wisdom, the philosopher Abu Yusuf Yaqub ibn Ishaq al-Kindi wrote A Manuscript on Deciphering Cryptographic Messages, rediscovered in an Istanbul archive in 1987. In it he describes, for the first time, frequency analysis:

One way to solve an encrypted message, if we know its language, is to find a different plaintext of the same language long enough to fill one sheet or so, and then we count the occurrences of each letter. […] Then we look at the cipher text we want to solve and we also classify its symbols.al-Kindi, c. 850

Letters do not occur equally often. In English, E makes up about 12.7% of letters, T 9.1%, A 8.2%, while J, Q, X and Z together barely reach 0.5%; in Spanish, E (13.7%) and A (12.5%) lead. A substitution cipher renames letters but keeps their counts: the most frequent symbol of a long ciphertext is almost surely E. To measure how much a candidate decryption “looks like” the language, compare the observed counts $O_{i}$ with the expected ones $E_{i} = N p_{i}$ :

χ^{2} = \sum_{i = 0}^{25} \frac{(O_{i} - E_{i})^{2}}{E_{i}} .

A small $χ^{2}$ means the text has the letter statistics of the language. This single number breaks any shift cipher automatically: decrypt with all 26 shifts and keep the one with the smallest $χ^{2}$ .

Frequency analysis. The dark bars are the letter frequencies of a ciphertext encrypted with a secret shift; the light bars are those of the language. Slide the shift until the two profiles line up (the χ² score drops sharply): the plaintext appears below. The secret shift is chosen at random each time you load the page.

For a general substitution the attacker matches the most frequent symbols first, then uses pairs (TH, HE, IN in English; DE, EN, EL in Spanish), doubled letters and short words to fix the rest. Edgar Allan Poe made a cult of it in The Gold-Bug (1843), and Arthur Conan Doyle gave Sherlock Holmes a substitution of dancing men to break in 1903. In real life, frequency analysis sent Mary, Queen of Scots, to the scaffold in 1587: Thomas Phelippes broke the nomenclator she used to correspond with the Babington plotters.

The indecipherable cipher

The defence against counting is to make each plaintext letter go to many different ciphertext letters. Leon Battista Alberti, the Renaissance architect, built a cipher disk in 1467 and suggested turning it every few words. Johannes Trithemius tabulated all 26 shifts in his tabula recta (Polygraphia, 1518). In 1553 Giovan Battista Bellaso added the decisive idea: choose the shift of each letter from a keyword that repeats. Blaise de Vigenère described a stronger variant in 1586, and history gave his name to Bellaso's cipher. With a keyword of length $L$ , $k_{0} k_{1} \dots k_{L - 1}$ :

c_{i} = (p_{i} + k_{i mod L}) mod 26, p_{i} = (c_{i} - k_{i mod L}) mod 26 .

With the keyword LEMON, ATTACKATDAWN becomes LXFOPVEFRNHR: the two Ts of ATTACK become X and F; the four As become L, O, E and N. The letter counts are flattened, and the cipher earned the name le chiffre indéchiffrable. It kept it for three hundred years; as late as 1917 Scientific American called it “impossible of translation”. It had been broken sixty years earlier.

Breaking Vigenère: Babbage, Kasiski, Friedman

The weakness is the repetition of the keyword. If we knew its length $L$ , we could split the ciphertext into $L$ columns (letters $0, L, 2 L, \dots$ ; letters $1, L + 1, \dots$ ), and each column would be a simple Caesar cipher, broken by frequency analysis. Charles Babbage found the length around 1854 but never published; the Prussian officer Friedrich Kasiski published the method in 1863:

Method (Kasiski examination)

When the same plaintext fragment falls on the same position of the keyword, it is encrypted identically. So the distances between repeated fragments of the ciphertext tend to be multiples of $L$ , and their greatest common divisor is usually $L$ or a small multiple of it.

In 1922 William Friedman, the founder of American cryptanalysis, replaced the search for repetitions with a statistic that uses every letter of the text.

Definition (index of coincidence)

The index of coincidence of a text of $N$ letters, with $n_{i}$ occurrences of letter $i$ , is the probability that two letters drawn at random from it are equal:

IC = \sum_{i = 0}^{25} \frac{n_{i} (n_{i} - 1)}{N (N - 1)} .

Proposition (Friedman)

If a text's letters have probabilities $p_{i}$ , then $IC \to \sum_{i} p_{i}^{2}$ as $N$ grows. For uniformly random letters this is $26 \cdot (1 / 26)^{2} = 1 / 26 \approx 0.038$ ; for English it is about $0.066$ and for Spanish about $0.072$ . The IC is unchanged by any substitution, because a substitution only renames the letters.

Why the IC does not change under substitution

$\sum_{i} n_{i} (n_{i} - 1)$ depends only on the multiset of counts ${n_{i}}$ , not on which letter has which count. A substitution is a bijection of the alphabet, so it permutes the counts and leaves the sum unchanged. In a Vigenère column built with the right $L$ , every letter was shifted by the same amount: the column is a substitution of plain language, so its IC is the language's. With a wrong $L$ , the column mixes several shifts, its letter distribution is flatter, and its IC drops towards $1 / 26$ .

So the attack is mechanical: for each candidate length $L = 1, 2, 3, \dots$ , cut the ciphertext into $L$ columns and average their IC. The first $L$ whose average jumps to the language's value is the key length. Then each column is a Caesar cipher, and the $χ^{2}$ of the previous section recovers each letter of the keyword.

Breaking Vigenère from the ciphertext alone. Change the text or the keyword. The bars are the average index of coincidence of the columns for each candidate key length: they jump at the true length (and at its multiples). The figure then breaks each column as a Caesar cipher with χ² and prints the key it recovered. Short texts or very long keywords defeat it: each column needs enough letters for its statistics to show.

Playfair and the digraphs

Another way to flatten frequencies is to encrypt pairs of letters: there are $26^{2} = 676$ pairs, and their frequencies are far flatter than those of single letters. Charles Wheatstone invented such a cipher in 1854; his friend Lord Playfair promoted it so well that it carries his name. The key is a 5×5 square holding the letters of a keyword followed by the rest of the alphabet (I and J share a cell). The plaintext is split into pairs, with an X between doubled letters; each pair is replaced by the other two corners of its rectangle in the square, or by the letters to its right (same row) or below (same column). The British army used it in the Boer War and the First World War, for tactical messages that only had to stay secret for a few hours; it is still breakable by hand, using the frequencies of pairs. The desktop app includes it with Wikipedia's classic example.

What the classics teach

The key space must be huge, or exhaustive search wins (Caesar).
A huge key space is not enough: the ciphertext must not leak the statistics of the plaintext (substitution and al-Kindi).
Anything that repeats is a foothold: a repeating key turns one hard cipher into several easy ones (Vigenère and Kasiski).
Statistics beat secrecy: Friedman's IC needs no guess about the plaintext at all.

The next step was mechanical: a key that never repeats in practice, produced by a machine. That machine was Enigma.

§Caesar's shift

§Every permutation of the alphabet

§Al-Kindi counts letters

§The indecipherable cipher

§Breaking Vigenère: Babbage, Kasiski, Friedman

§Playfair and the digraphs

§What the classics teach

§Further reading