Substitution and frequency analysis

The Caesar cipher fell because it has only 25 keys: the whole alphabet moves at once, like a ring. What if you don't shift it but shuffle it? Let A become F, B become J, C become W, with no system at all. Now there is no single shift to guess: each letter has to be worked out on its own. This is the simple substitution cipher. “Simple” because a plaintext letter is always replaced by the same cipher letter.

But let's start with the oldest shuffle of all, which isn't random in the least.

Atbash: the alphabet backwards

Ancient Hebrew writers had a trick: replace the first letter of the alphabet, aleph, with the last, tav; the second, bet, with the second to last, shin. Hence the name: a-t-ba-sh. The alphabet folds in half like a sheet of paper, and every letter swaps places with its partner from the other end.

A few words in the Book of Jeremiah are written this way. The puzzling “Sheshach”, for instance, is “Babel”, Babylon, read through Atbash. It was hardly a secret to anyone at the time; more likely a literary game, a way of naming the enemy without naming it.

In the Latin alphabet Atbash pairs A with Z, B with Y, C with X and so on, down to M and N in the middle. With 26 letters every letter has a partner and none stays in place.

Atbash has no key at all. There is exactly one Atbash, and anyone who knows about it reads it at sight. It does have one neat property: encrypting and decrypting are the same operation, just like ROT13 in the last lesson.

Any shuffle of the alphabet

Atbash and Caesar are special cases. In general the key of a substitution cipher is the whole alphabet written out in some arbitrary order. Put the ordinary alphabet on top and the shuffled one underneath. To encrypt a letter, find it in the top row and take the letter below it.

How many such keys are there? A can be given any of the 26 letters. B any of the remaining 25. C any of the 24. And so on to the end: 26 × 25 × 24 × … × 2 × 1. Mathematicians write this product as 26! and say “26 factorial”. It comes to about 4 · 10²⁶, a 27-digit number. For the 33-letter Russian alphabet, 33! is about 8.7 · 10³⁶.

Imagine a computer that checks a trillion keys every second. To try every key of the Latin alphabet it would need about 13 million years. For Russian, about 2.7 · 10¹⁷ years, twenty million times the age of the universe. The brute force that broke Caesar in a minute is helpless here.

Letters don't have to be replaced by letters. In the pigpen cipher, also called the Freemasons' cipher, each letter is a corner of a grid, with or without a dot. It looks mysterious, but it is the same simple substitution: one sign, one letter. See how it works in the pigpen tool.

Al-Kindi and letter counting

Brute force is helpless, but simple substitution has a weakness, and it was described more than a thousand years ago. In ninth-century Baghdad lived the scholar Abu Yusuf Yaqub al-Kindi, known as “the philosopher of the Arabs”. Among his hundreds of works on music, medicine and optics was a treatise on reading encrypted letters. It is the earliest known description of frequency analysis.

Al-Kindi's idea is this. In any language some letters are common and others rare. In English about one letter in eight is an E, while J, Q and Z turn up less than once in five hundred letters. A substitution cipher changes the letters but not how often each one appears. If E became Q, then Q will be the commonest sign in the ciphertext. Here is the method in a paraphrase:

Take another text in the same language, long enough, and count how many times each letter appears. Then do the same with the cipher: find its commonest sign and put the commonest letter in its place, swap the second sign for the second letter, and carry on until the whole letter can be read.

Al-Kindi's method, 9th century, paraphrased

Below is that very paraphrase, encrypted with a simple substitution. The bars show how often each sign of the ciphertext occurs. In grey are the frequencies of letters in ordinary English, lined up in the same order.

Notice that the shape of the “mountain” is almost the same for the cipher and for the language. Substitution moves the bars around but doesn't change their height. That is the trace it cannot wipe out.

Still, the bottom row, the “first guess” from frequencies alone, gets only a few letters right. Frequencies wander in a short text: in a paragraph of four hundred letters T can overtake E by chance, and S can beat R. So frequencies are only the beginning. After that you use the other habits of the language.

Crack a cryptogram by hand

Here is a note that one codebreaker left for another. It is encrypted with one random key out of those 4 · 10²⁶. Your task is to rebuild the key letter by letter. Click a cipher sign (in the frequency strip at the top, or right in the text) and type the letter you think it stands for. Every copy of that sign in the text changes at once.

If you don't know where to begin, here are the tricks codebreakers have used for centuries.

• The commonest sign. In English that is nearly always E, then T, A, O. Start with the one or two tallest bars.
• One-letter words. In English there are only two: A and I.
• Short words. The commonest three-letter word is THE; a three-letter word ending in your E is a strong bet. Two-letter words: OF, TO, IN, IT, IS, BE.
• Endings and doubles. Look for -ING, -ED, -LY at the ends of words. Doubled letters are most often LL, EE, SS, OO, TT.
• Try and check. Every letter you place uncovers bits of other words. If you get an impossible cluster such as “QX”, the guess is wrong: clear it and try another.

It works like a crossword: the more letters in place, the faster the rest come. The last few rare letters usually go in from the sense alone.

When the text is short: a known word

Frequency analysis has a limit: it needs a long text. In a note of sixty letters the frequencies are close to random. Here a different weapon helps, the crib, as the codebreakers of Bletchley Park called it during the Second World War. If you know or can guess even one word of the plaintext, a greeting, a signature, a weather report, then several letters of the key are known at once.

Substitution in fiction

Frequency analysis made two stories famous. In Edgar Allan Poe's “The Gold-Bug” (1843) the hero finds a parchment of figures and signs and explains, step by step, how to read it, starting from the commonest sign, which in English must be E. Sixty years later Arthur Conan Doyle wrote “The Adventure of the Dancing Men”, where Sherlock Holmes breaks a cipher of little stick figures, beginning with the observation that the commonest figure has to be E.

Cipher makers knew about the weakness too and tried to get round it. They added meaningless “null” signs, gave common letters several different symbols, or encrypted letters in pairs, as in the Playfair cipher. That made counting harder but didn't stop it. The real breakthrough came when a cipher started switching its alphabet from letter to letter, which is the next lesson.

What to take with you

• A simple substitution cipher always replaces each letter with the same other letter or sign. Atbash, Caesar and pigpen are special cases.
• Substitution has 26! ≈ 4 · 10²⁶ keys, far too many to try.
• But it keeps the letter frequencies. The commonest sign of the ciphertext is most likely the commonest letter of the language. That is al-Kindi's frequency analysis, from the ninth century.
• Frequencies give a first guess; short words, endings and known words do the rest, as in a crossword.
• A short text can't be cracked by frequencies, but a single guessed word can open half the key.

How do you hide the frequencies? Make the same letter encrypt differently each time. For three hundred years nobody found the flaw in that idea. Next: the Vigenère cipher →