Al-Kindi and the invention of frequency analysis

Over eleven hundred years ago in Baghdad, a philosopher wrote down the first known way to break a cipher without the key. Al-Kindi's idea was simple. In any language some letters turn up far more than others, and a cipher that swaps each letter for one fixed substitute keeps that imbalance visible. Frequency analysis, counting the letters of a ciphertext and matching them to the letters of the language, ended the safe life of every simple substitution cipher and set cryptography's agenda for the next thousand years. We'll tell the story, work the method on a real example, and point you to the tool that does the counting for you.

Who al-Kindi was

Abu Yusuf Ya'qub ibn Ishaq al-Kindi lived from about 801 to about 873. He was born in Kufa and died in Baghdad, capital of the Abbasid caliphate and the center of an age of translation and scholarship. He worked at the House of Wisdom, where, by one account, the caliph al-Ma'mun (reigned 813 to 833) appointed him, and under al-Mu'tasim (833 to 842) he tutored the caliph's son. The bibliographer Ibn al-Nadim called him "the Philosopher of the Arabs". He wrote on philosophy, mathematics, medicine, optics, music and plenty more, and much of his work is lost. In the twentieth century, twenty-four of his lost works turned up in a library in Turkey.

The treatise

One of those works, Risalah fi Istikhraj al-Mu'amma, usually translated as On Deciphering Cryptographic Messages, is the oldest known description of cryptanalysis by frequency analysis. Sources date it to about 850. Its modern rediscovery has two accounts. Simon Singh says it was found in 1987 in the Sulaimaniyyah Ottoman Archive in Istanbul. Another account describes a team from the Arab Academy of Damascus (M. Mrayati, Y. Alam and M. al-Tayyan) who searched from 1979 for lost works on the subject and published their Arabic edition in 1987, so the 1987 date may be the publication. The treatise spends most of its length on statistics, Arabic phonetics and Arabic syntax, and the cryptanalytic method itself fills just two short paragraphs. In modern terms, it goes like this:

1. Take a long sample of plain text in the same language as the secret message and count how often each letter occurs. Rank the letters from most common to least.
2. Count the symbols of the ciphertext the same way and rank them.
3. Write the most common ciphertext symbol over the most common plain letter, the next over the next, and so on.
4. The result won't be right everywhere, because short texts don't follow the average exactly. But enough letters come out right to show words, and the words give away the rest.

The key observation is that this uses only the structure of the language and never touches the key. The cipher might use a scrambled alphabet with billions of possible keys, and the letter counts don't care.

A worked example

Take a famous passage from the Declaration of Independence (public domain), 330 letters, and encrypt it with a simple substitution cipher where every letter always becomes the same other letter (the simple substitution page). With the scrambled alphabet QWERTYUIOPASDFGHJKLZXCVBNM (plain A to Z map to those letters in order), the start of the text becomes:

VITFO FZITE GXKLT GYIXD QFTCT FZLOZ WTEGD TLFTE TLLQK NYGKG
FTHTG HSTZG ROLLG SCTZI THGSO ZOEQS WQFRL VIOEI IQCTE GFFTE
ZTRZI TDVOZ IQFGZ ITKQF RZGQL LXDTQ DGFUZ ITHGV TKLGY ZITTQ

It looks like noise. Now count (the numbers come from scripts/examples/al-kindi-example.mjs). The commonest ciphertext letters are T (50 times, 15.2% of the text), Z (37, 11.2%), then G and I (27 each, 8.2%), Q (26, 7.9%), F (24, 7.3%), L (22, 6.7%) and O (17, 5.2%). In English, E makes up about 12.7% of letters and T about 9.1%, so the guess is that T stands for e and Z for t. That's right: in the key, E became T and T became Z. Now look for words. The spaces were removed, so look for a short group that repeats. ZIT appears many times (in FZITE, ZITHG, ZITKQ and a dozen other places). With Z = t and T = e it reads t?e, and the only common English word of that shape is the, so the cipher letter I is h. That's three letters. The text opens with VITF, now ?he?, and when is the obvious word, so V = w and F = n. The rest of the opening, OF ZIT, becomes ?n the, so O = i. In a few minutes the whole passage falls apart. On a long ciphertext it's quicker still to let a program try the possibilities, which is what the substitution solver does by hill climbing.

You can do the counting yourself. Paste the ciphertext above, or any text of your own, into the tool below. You'll see a bar for each letter, the typical English frequencies as dots, and the index of coincidence, a single number that tells a substitution cipher (about 0.066 for English, and 0.0733 for this example) from a polyalphabetic one (nearer 0.04):

Text to analyze (ciphertext or plain)

Load a Vigenère exampleLoad a plain English example

What this suggests

Nothing you type here leaves your browser.

How many letters do you need?

A short ciphertext doesn't follow the average, and a few letters can be anything. A simple substitution on English has 26! (about 4 × 10²⁶) possible keys, but Shannon's calculation of the unicity distance shows that about 28 letters of ciphertext are enough, in principle, for only one key to produce readable English (Shannon and perfect secrecy). In practice a person wants a hundred or so letters, and a program manages with far less. That's why newspaper cipher puzzles are always sentences and never single words.

The arms race it started

Once frequency analysis was known, simple substitution was finished for serious use, and cryptographers set out to flatten the counts.

• Homophones. Give the common letters several different symbols and spread their use. A homophonic cipher existed at the court of the Duke of Mantua in the early fifteenth century.
• Polygraphic ciphers. Encrypt letters in pairs or larger blocks, so the unit being counted is bigger and the counts get far thinner: Playfair, Hill.
• Polyalphabetic ciphers. Use a different substitution at each position, so one plaintext letter spreads across many ciphertext letters. Leon Battista Alberti gets credit for proposing the idea around 1467, and Bellaso's repeating-key form of 1553 became known as the Vigenère cipher. It held out against frequency counting for about three centuries, until Babbage and Kasiski found how to split it into separate Caesar ciphers.

By the Renaissance, European states used similar methods widely. In 1474 Cicco Simonetta wrote a manual on deciphering Latin and Italian text, and by the 1580s cryptanalysis was good enough to help send Mary, Queen of Scots to the scaffold (the cipher that convicted Mary). The countermeasures had a practical weakness: they added complexity, and complexity led to mistakes. A British foreign secretary is said to have rejected the Playfair cipher because "our attachés could never learn it".

Frequency analysis today

It lives on as the first test applied to any unknown cipher, and as the reason real ciphers are built to make the ciphertext look uniform. Rotor machines such as Enigma were nearly immune to simple frequency analysis, though other attacks broke them. In the Second World War, mechanical letter counting supplemented the manual work. And a modern cipher like AES aims for the strongest defense: its output is indistinguishable from random bytes, so counting anything gives nothing. The ECB picture demo shows the same instinct at work on a modern block cipher. In the wrong mode, blocks repeat, and the picture shows through.

How cipher.ink uses this

The point of al-Kindi's method is the opposite of what cipher.ink does. A message sealed here is encrypted with AES-256 in GCM mode, whose output is statistically indistinguishable from random bytes, with no letter counts, patterns or repeated blocks to find (AES-GCM). Count the characters of a cipher.ink ciphertext in the tool above and you get a flat table. Frequency analysis is a weapon against ciphers that preserve the structure of the message, and a modern cipher is built to preserve none of it.