Al-Kindi and frequency analysis: the first codebreaker

Breaking codes with statistics, part one of six.

For most of history, a secret message was protected by the simplest of tricks: swap every letter for another letter, or for a symbol. Write "q" wherever you mean "a", "x" wherever you mean "b", and so on. Without the list of swaps, the message looks like nonsense. With it, the reader recovers every word.

It feels safe. There are an enormous number of ways to scramble an alphabet, far too many for anyone to try one by one. For centuries that was taken as reason enough to trust it.

In ninth-century Baghdad, a scholar showed why it was not.

The scholar

Abu Yusuf Ya'qub ibn Ishaq al-Kindi lived and worked in Baghdad, then one of the great centres of learning in the world, under the Abbasid caliphs. He wrote on philosophy, mathematics, medicine, astronomy and music, and is often remembered as one of the first great philosophers writing in Arabic.

Among his many works is a treatise on deciphering secret messages. It is the earliest surviving work on breaking ciphers, and it contains the first known description of a technique that would shape codebreaking for the next thousand years.

The insight

Al-Kindi's idea was to stop looking at the scrambled letters as symbols and start counting them.

In any language, letters are not used equally. Some appear constantly, others rarely. Al-Kindi described taking a long text written in the same language as the secret message and counting how often each letter occurs. That gives a ranking, from the most common letter to the least common.

Then you count the symbols in the secret message the same way. Swapping one letter for another changes what each letter looks like, but not how often it turns up. The symbol that appears most in the message most probably stands for the letter that appears most in the language. The second most common symbol probably stands for the second most common letter, and so on down the list.

The counts only give a starting point. From there, the codebreaker tries the likely swaps, looks for words that begin to make sense, and corrects the guesses as the message opens up. Common short words, familiar letter pairs and letters that tend to sit next to each other all help confirm the choices. A message that seemed to hide behind a vast number of possible alphabets gives way to patient counting and a few hours of careful thought.

This is what we now call frequency analysis. Al-Kindi worked with the letters of Arabic, but the method works in any written language, because every language has its favourite letters.

Why it mattered

The insight was that a secret could be undone without ever finding the key. The codebreaker did not need to steal the list of swaps or guess it. The message itself leaked enough to rebuild it.

The method has limits. It works best on longer messages, because a short message may not have enough letters for the counts to settle into their usual pattern. A message of a few words can stubbornly refuse to look like the language it was written in. A long letter almost always gives itself away.

The scale of possible alphabets, which made the simple swap feel safe, turned out to be beside the point. What mattered was what the scrambled text still revealed about the language underneath it.

How the idea travelled

Al-Kindi's treatise was little known in the West for centuries. By the Renaissance, codebreakers in Europe were using frequency analysis too, and governments were employing specialists to open and read the letters of foreign powers. Simple swap ciphers kept being used long after they could be broken, often by people who had no idea how exposed their messages were.

The response, slowly, was to design ciphers that would smooth out the letter counts. That contest, between people hiding patterns and people measuring them, runs through the rest of this series.

What it teaches

The lesson outlived the cipher it broke. Protection that looks strong because the number of possibilities is huge can still fail if what it produces carries a pattern. Any protection worth trusting has to hold up against an adversary who counts and measures everything it can see.

Next in the series: Babbage and Kasiski, and how repeated fragments broke the cipher that had been called "indecipherable".

If your organisation holds data that has to stand up to that kind of counting, join the waitlist for early access.