Frequency Analysis

Secret Writing: A History of Codes, Ciphers and Codebreaking

Course 1 · Chapter 3 · Arab Scholars and Frequency Analysis

Chapter 2 ended with a puzzle: a cipher with so many keys that nobody could try them all. For centuries that looked like safety. Then, in ninth-century Baghdad, a scholar noticed that a message is not just a pile of symbols: it is language, and language has habits. Counting those habits is enough to break the cipher, however many keys it has.

Baghdad and the House of Wisdom

Under the Abbasid caliphs, Baghdad became a centre of translation and study, with scholars gathering Greek, Persian and Indian works and adding their own. Among them was Abu Yusuf Ya'qub ibn Ishaq al-Kindi (died around 873), a philosopher, mathematician and physician. Among his many writings is a treatise on deciphering secret messages, usually titled A Manuscript on Deciphering Cryptographic Messages. It is the earliest surviving description of what we now call frequency analysis.

Key figure Al-Kindi (around 801 to around 873): Baghdad scholar, author of the earliest known account of breaking a cipher by counting letters.
Not Yet Verified The dates for al-Kindi, the exact title of the treatise and the claim that it is the earliest surviving text on frequency analysis are written here from general knowledge and were not checked against a source for this chapter. The same applies to the later Arabic works mentioned below. Treat the names and dates as a pointer for your own search, not as settled citations.

The Big Idea: Letters Are Not Equally Common

Take any long passage of ordinary English and count the letters. They are far from evenly spread. E is by far the most common, followed by T, A, O, I and N. At the other end, Z, Q, X and J are rare. Every language has its own pattern, and a given language's pattern is remarkably stable from one book to another.

RankEnglish letterRoughly how often
1Eabout 1 letter in 8
2Tabout 1 in 11
3Aabout 1 in 12
4 to 6O, I, Neach a little over 1 in 15
LastZ, Q, X, Jeach under 1 in 100

The figures are rounded and vary a little between sources and samples, so use them as a guide to order, not as exact quotas.

Why a Simple Substitution Cipher Falls

A simple substitution cipher replaces each letter by one fixed symbol. The disguise changes the letter, but not the count. If the cipher letter P turns out to be the most common in a long message, it very likely stands for E. That is the whole method:

  1. Count how often each cipher letter occurs.
  2. Rank them, and match the top ones to the common letters of the language.
  3. Guess a few letters and look at the partial words that appear (a three-letter word starting with T and ending in E is probably THE).
  4. Refine: each correct guess reveals more, and the rest falls into place quickly.
Cipher text (a Caesar shift, so the whole alphabet moved by one fixed amount) AOL SLAALY L HWWLHYZ TVYL VMALU AOHU HUF VAOLY Count: L appears most often, so guess L stands for E. E is 7 places before L in the alphabet, so shift everything back by 7. THE LETTER E APPEARS MORE OFTEN THAN ANY OTHER

A Caesar shift is the easiest case, because one correct guess fixes the whole alphabet. A general substitution cipher needs more guesses, but the principle is the same, and a few hundred letters of ciphertext are usually plenty.

Beyond Single Letters

Later cryptanalysts added more handles, all of them extensions of the same idea that language leaves fingerprints:

  • Common pairs and triples: TH, HE, IN and ER are common pairs in English; THE and AND are common triples.
  • Word shapes: a repeated pattern like ABCCDE could be a word such as LETTER. Single-letter words in English are almost always A or I.
  • Vowels and consonants: vowels tend to sit next to many different letters, while consonants cluster.
  • Probable words: if you know a message is a military report, words like ATTACK or DAWN are good guesses. This "probable word" trick returns in Chapter 8.
Not Yet Verified Later Arabic writers, such as the authors of medieval encyclopedias of court administration, are said to have extended the method with tables of Arabic letter frequencies and advice on word patterns. I did not check this, and I have no source for the name of any work or author: look it up before relying on it.

What the Cipher-Makers Did Next

Once frequency analysis existed, simple substitution was no longer safe, and the history of the next several centuries is largely a series of attempts to flatten the counts so that nothing stands out:

DefenceIdeaWhy it helpsWhy it is not enough alone
Keyword alphabetStart the cipher alphabet with an easily remembered word, then the unused lettersEasy to remember; far more keys than CaesarThe counts are unchanged, so frequency analysis still works
NullsInsert meaningless symbolsDisturbs word shapes and pairsThe common letters still stand out
HomophonesGive common letters several symbols (E might have five)Flattens the countsPairs and word patterns still leak; more to memorise
Multiple alphabetsChange the substitution as the message goes onSpreads each plaintext letter across many ciphertext lettersNeeds a clever scheme: Chapters 4 and 5
Keyword alphabet using the keyword ZEBRA (repeated letters removed) 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 : Z E B R A C D F G H I J K L M N O P Q S T U V W X Y
Try it yourself: let the counts decide This message uses a Caesar shift, but you are not told the shift:

TYDAPNETZY ZQ ESP WPEEPCD DSZHD ESP DPNCPE

Count the letters. Which is the most common? Assume it stands for E and work out the shift.
Show the worked answer

The count is P seven times, E six times, D five times. P is the most common, so guess P stands for E. P is 11 places after E in the alphabet, so shift everything back by 11. T to I, Y to N, D to S, A to P, P to E, N to C, E to T, T to I, Z to O, Y to N gives INSPECTION; ZQ gives OF; ESP gives THE. The full message is INSPECTION OF THE LETTERS SHOWS THE SECRET.

Where This Leaves the Secret Writer

The lesson of frequency analysis is bigger than one technique. A cipher is only as strong as the weakest statistical fingerprint it leaves behind. From now on, the story is a contest: designers hide the fingerprints; analysts look for new ones. The next chapter moves to the Renaissance courts of Italy, where the first professional cipher secretaries went to work.

Exercises

Exercise 1

This Caesar message is long enough to count: AOL SLAALY L HWWLHYZ TVYL VMALU AOHU HUF VAOLY PU LUNSPZO ALEA. (a) Which cipher letter is the most common, and how many times does it appear? (b) Assuming it stands for E, what is the shift? (c) Decipher the message.

Exercise 2

This message uses a general substitution cipher (not a shift): ZIT TFTDN QZZQEAL QZ RQVF. It is too short for counting to work well, so use word shapes. (a) Which word looks like the most likely candidate for THE, and why? (b) Use that to guess the other words, given that the message is a short military report. (c) Write down the substitution pairs you found.

Exercise 3

(a) Using the keyword ZEBRA as in the chapter, build the cipher alphabet. (b) Encipher MEET ME AT NOON. (c) Explain why this cipher is much harder to break by trying keys than a Caesar shift, yet still falls to frequency analysis.

Quick Reference

  • Frequency analysis: count the symbols, match the commonest to the commonest letters of the language
  • English order: E, T, A, O, I, N are the most common; Z, Q, X, J the rarest
  • Method: count, rank, guess, refine using word shapes and pairs
  • Lesson: a huge number of keys is no protection if the counts show through
  • Defences: nulls, homophones and (later) multiple alphabets, all aimed at flattening the counts
  • Check: al-Kindi's dates and treatise title, the later Arabic works on frequencies

Next chapter: Renaissance Secretaries, with the cipher offices of Rome and Venice, nomenclators, and Alberti's cipher disk.