Old ciphers, and breaking them

For most of history, keeping a message secret meant scrambling its letters by hand, following a rule that only the sender and the receiver knew. This page builds three of those ciphers, each a little stronger than the last, and breaks every one of them. Each break teaches something that modern ciphers are designed to stop.

A few words first. The plaintext is the message as written; the ciphertext is what’s sent; encrypting (or enciphering) turns one into the other, and decrypting turns it back. The key is the small secret that says exactly how: the rule itself can be known to everyone.

The simplest cipher moves every letter a fixed number of places along the alphabet. With a shift of 3, A becomes D, B becomes E, and so on, with X, Y and Z going round to A, B and C. The Roman historian Suetonius wrote that Julius Caesar used exactly this, with a shift of 3, so it’s called the Caesar cipher. To decrypt, shift back.

A shift of 13 is special. The alphabet has 26 letters, so shifting by 13 twice goes all the way round: encrypting twice gives back the original, and the same operation both encrypts and decrypts. (Try it: Shift 13, then Encrypt it again.) Under the name ROT13, “rotate by 13”, it turned up on Usenet, the internet’s discussion forums, by the early 1980s: in the net.jokes group, a joke’s punchline went out in ROT13, so readers saw it only if they chose to. It’s been used since to hide spoilers and puzzle answers, and as a joke about encryption itself: everyone knows the key, so it hides nothing from anyone who wants to look.

The key is the shift, and there are only 25 that change anything. So an attacker doesn’t need to be clever: try every one, and see which gives English. A person can spot English at a glance, but a program needs a number, a score for how English some text looks. Here’s a simple one:

1. Count each letter in the text.
2. Work out how many of each English would have in that many letters. E makes up about one letter in eight of English, so 60 letters of English should have about 7 E’s.
3. For each letter, take the difference between the two, square it (so too many and too few both count), and divide by the number expected (so being 3 out matters more for a rare letter than for E).
4. Add these up over all 26 letters.

English scores low; gibberish, with its letters in all the wrong amounts, scores high. Statisticians call it the chi-squared score (χ², after the Greek letter).

The cipher’s flaw is that its key is so small: anything with 25 keys can be broken by trying them all. That’s the brute-force attack, and the first rule it teaches is that the number of keys must be far too large to try.

So use more keys. Instead of sliding the alphabet, shuffle it: write the 26 letters in any order you like, and let A become the first, B the second, and so on. That’s a substitution cipher, and its key is the shuffled alphabet.

plain    A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
cipher   Q W E R T Y U I O P A S D F G H J K L Z X C V B N M

How many keys is that? A can become any of 26 letters, then B any of the 25 left, C any of the 24 left after that, and so on down to Z, with one left. That’s 26 × 25 × 24 × … × 1, written 26! (“26 factorial”):

26! = 403,291,461,126,605,635,584,000,000, about 4 × 10²⁶.

Trying a billion keys every second, it would take about 12.8 billion years to try them all. Brute force is hopeless. And yet substitution ciphers were broken routinely for centuries, by hand.

The flaw is that each plain letter always becomes the same cipher letter. If E is the commonest letter of the message, then whatever E became is the commonest letter of the ciphertext. The cipher changes the letters’ names, but not how often each one turns up.

In this chapter, E is the commonest letter (12.1% of all letters), then T (10.4%). The first known description of breaking a cipher this way, by counting, is by the Arab scholar al-Kindi, in the ninth century.

Counting gives a start, not an answer: the commonest cipher letter is very likely E, but by the time you’re down to letters that are each about 6% of the text, the order is down to chance. The rest comes from what English words look like: a single letter on its own is A or I; a common three-letter word is often THE or AND; a letter that follows THE’s E might be N. Try it:

Counting alone gets only 4 of this message’s 23 cipher letters right. The words did the rest. Real ciphers often removed the spaces (and wrote the letters in groups of five) to hide the words’ lengths, which makes it harder by hand, but a program can do without them.

A program can’t see words, but it can use a better score than single letters: how often each letter follows the two before it. In English, THE is common and QXZ never happens. Score a candidate decryption by how likely each of its letters is after the two before (counted, again, only in the first part of the chapter), and then hill-climb:

1. Start from the counting guess.
2. Swap two letters of the key at random. If the decryption scores better, keep the swap; if not, swap them back.
3. Repeat until no swap has helped for a while. That’s the top of a hill: maybe the right key, maybe only a key no single swap can improve. So start again from a slightly scrambled guess, a few times, and keep the best.

On 40 messages of 250 letters each, it got every one with at most 6 letters wrong, in a fraction of a second. What’s left wrong is rare letters seen once or twice, which a person fixes by eye. With 100 letters it failed (more than 10 letters wrong) on 20 of the 40, half of them: too few letters for the counts to mean much. Length is the codebreaker’s friend.

So a huge number of keys isn’t enough. A cipher must also hide the patterns of its message, which simple substitution leaves in plain view.

The fix that lasted three centuries was to use several alphabets in turn. Choose a keyword, say LEMON. Shift the first letter of the message by L (A is 0, B is 1, …, so L is 11), the second by E (4), the third by M (12), the fourth by O, the fifth by N, then start the keyword again from L. Now E becomes different letters in different places, and the counts are smeared together.

It was described by Giovan Battista Bellaso in 1553, but named after Blaise de Vigenère, and earned the name le chiffre indéchiffrable: the indecipherable cipher. Counting letters doesn’t work any more, at least not on the whole message.

The weakness is that the keyword repeats. With a 10-letter key, letters 1, 11, 21, … are all shifted by the key’s first letter: on their own, they’re a Caesar cipher, and section 1 breaks those. So everything comes down to finding the key’s length.

For that, a different count. Pick two letters from a text at random: what’s the chance they’re the same letter? English is lumpy (lots of E’s and T’s, hardly any Z’s), so the chance is quite high: about 0.066 for this chapter. If every letter were equally common, it would be 1/26, about 0.038. That chance is the index of coincidence, and a shift doesn’t change it, since shifting renames the letters without changing how lumpy they are.

So guess a key length L, split the ciphertext into L columns (every L-th letter), and measure each column’s index of coincidence. If L is right, each column is one Caesar shift of English, and looks lumpy like English. If not, each column mixes several shifts, and looks flat.

With WONDERLAND as the key and 2,100 letters of message, lengths 10 and 20 stand out (20 is two turns of the key, so it works too), and every column gives its letter: the key comes out exactly. At 300 letters the length is still clear, but each column is only 30 letters, and some come out wrong.

This is the attack William Friedman published in 1922. Friedrich Kasiski had published another in 1863, from repeated pieces of ciphertext, and Charles Babbage seems to have broken it earlier still without publishing.

Each of these ciphers was broken by something modern ciphers are designed against:

• Too few keys (Caesar): any cipher whose keys can all be tried is broken by trying them.
• Patterns that survive (substitution): the ciphertext mustn’t keep the message’s statistics, however many keys there are.
• A repeating key (Vigenère): anything that repeats gives the attacker something to line up.

A modern cipher is, in effect, a substitution on huge blocks of bits instead of single letters, so there are no letter counts to make; its output shows no pattern an attacker can find; and it has so many keys that trying them all is out of the question.

• Caesar shifts every letter; with 25 keys, trying them all and scoring each for English breaks it.
• Substitution shuffles the alphabet: 26! ≈ 4 × 10²⁶ keys, but each letter keeps its frequency, so counting, then words (or a hill-climber scoring triples of letters), breaks it.
• Vigenère uses a keyword of several shifts in turn, flattening the counts; the index of coincidence finds the key’s length, and each column is then a Caesar cipher.
• Longer messages are easier to break: every attack here works by counting.

• David Kahn, The Codebreakers (1967): the history of codes and their breaking, in depth.
• Simon Singh, The Code Book (1999): the same story, shorter and very readable, from Caesar to modern cryptography.
• William F. Friedman, The Index of Coincidence and Its Applications in Cryptography (1922): the counting attack in section 6.