For about nine hundred years, anyone who could not read your secret letter could only guess at it. Then a scholar in Baghdad pointed out something embarrassingly simple: a code can rename every letter, but it cannot change how often each one turns up. Here is an intercepted message. Slide its letter counts until they line up with ordinary English, and read it.
The Roman historian Suetonius tells us that Julius Caesar wrote sensitive letters by swapping each letter for the one three places later in the alphabet: A became D, B became E, and so on. His heir Augustus used an even lazier version, shifting just one place. It sounds flimsy, but in a world where few people could read at all, and nobody had a method for attacking a cipher, it did its job.
Caesar's cipher only has 25 possible keys, so a patient enemy could try them all. The general version, where the alphabet is scrambled in any order, looks far safer. There are 26 × 25 × 24 × … × 1 ways to scramble 26 letters, about 4 × 1026. Check a billion keys a second and you would still be at it billions of years from now. For centuries, that kind of "simple substitution" was considered good enough for diplomats and generals.
The breakthrough came from Abu Yusuf Yaqub al-Kindi, a ninth-century philosopher and scientist working in Baghdad. Among his many books was A Manuscript on Deciphering Cryptographic Messages. It lay forgotten for centuries and turned up again only in 1987, in the Süleymaniye Ottoman archive in Istanbul. It is the earliest known description of what we now call frequency analysis.
His recipe fits in a paragraph. Take a long stretch of ordinary writing in the same language and count how often each letter appears. Then count the symbols in the secret message. The symbol that turns up most is probably the language's most common letter; the second most common is probably the second, and so on. Fill in the obvious ones, and the rest start to fall out of the half-readable words.
A substitution cipher changes every letter's name. It does nothing to hide how often each letter is used.
Letters in a language are wildly unequal. In typical English text, E makes up about 12.7% of all letters, T about 9.1% and A about 8.2%, while J, Q, X and Z each stay well under a quarter of a percent. That lopsided shape is a fingerprint. A substitution cipher just moves the bars around: in Caesar's version they all slide along by the same amount, which is exactly what you undo by dragging the chart above.
The fingerprint only shows up when there is enough text. A long letter follows the English pattern closely. A short note might happen to have no E at all, or four W's, and the counts can point you the wrong way. Codebreakers then lean on extra clues: common pairs such as TH and HE, doubled letters like LL and EE, and short words like "the" and "and" that stand out once a few letters are known.
Frequency analysis reached Europe too, and in 1586 it helped end a life. Mary, Queen of Scots, held prisoner in England, was exchanging enciphered letters with Anthony Babington, who was plotting to kill Elizabeth I and put Mary on the throne. Her cipher was more elaborate than Caesar's, with symbols for whole words as well as for letters. But the letters were being smuggled out through a channel controlled by Elizabeth's spymaster, Francis Walsingham, and his codebreaker Thomas Phelippes read them.
When Mary wrote approving the plot, Phelippes is said to have added a forged postscript asking Babington for the names of his fellow conspirators. The plotters were arrested, and Mary was executed on 8 February 1587, convicted largely on the evidence of her own "secret" letters.
Once code-makers understood the attack, they started to blur the fingerprint. Some added meaningless "null" symbols. Others gave common letters several different symbols, so no single one towered over the rest. The bigger leap was to switch between several alphabets as you write, so the same plaintext E comes out as different letters in different places. The best-known of these, the Vigenère cipher, was nicknamed le chiffre indéchiffrable, "the undecipherable cipher", and held out until the 19th century, when Charles Babbage and Friedrich Kasiski each found ways to break it.
Their trick? Work out how many alphabets are in use, split the message into that many piles, and run al-Kindi's letter count on each pile. More than a thousand years on, the man in Baghdad was still doing the heavy lifting.
English letter frequencies are the widely used figures from counts of newspapers and novels (E 12.7%, T 9.1%, A 8.2%, …). The intercepted messages here are invented for the demo.