Substitution Ciphers: 26! Keys, Broken by Counting Letters

A stretch of a Sherlock Holmes story has been enciphered under a key you cannot see. With a Caesar shift, try the 25 keys one at a time and watch each one's chi-squared bar. With a full substitution, pair the ciphertext's commonest letters with English's, then fix the pairs by reading the words that come out.

Worked example — Substitution Ciphers: 26! Keys, Broken by Counting Letters

Keys to choose from	25
Letters in the message	120
The attack's answer, the lowest χ²	23.3
Next lowest	445.8
Is it the key?	Yes
Right in 20,000 random messages of 120 letters	100.0%

These are the values the calculator shows when the page opens. Change any input above to recompute them.

Loading interactive simulation...

Lesson

The theory — Substitution Ciphers: 26! Keys, Broken by Counting Letters

A substitution cipher replaces each letter of the message by another letter, the same one every time, according to a key: a rearrangement of the alphabet, so there are 26! ≈ 4.03 × 10²⁶ keys. A Caesar cipher is the special case that moves every letter the same number of places along the alphabet, which leaves 25 keys. Frequency analysis attacks either one by comparing how often each ciphertext letter occurs with how often letters occur in ordinary text.

What each symbol means

χ²: chi-squared: the sum over the 26 letters of (O − E)² / E. The smaller it is, the more the decryption's counts look like English
O: how many times a letter occurs in the decryption being scored
E: how many times it would occur in a text of the same length with the letter shares of The Dancing Men

Assumes: Only the 26 letters are enciphered. Spaces and punctuation stay where they were, which gives away the length of every word; the dancing men did the same with their flags. “English” means the letter counts of one Holmes story, 39,859 letters, and the page's own messages are all cut from another, so none of them is scored against itself. The trials draw a random stretch of The Solitary Cyclist and a random key from a seeded generator, so the same figures come back every time.

Twenty-five keys are quick to try; telling which one worked takes about 30 letters 🖖

A Caesar shift has 25 keys, few enough to try by hand. The work is in deciding which decryption is English, and the page hands that to Pearson's chi-squared, which adds up, letter by letter, how far a decryption's counts are from what The Dancing Men predicts for a text of that length. Over 20,000 random stretches of another Holmes story, the lowest score is the right key 85.0% of the time at 12 letters and 99.1% at 31. Press Caesar, 11 letters for a miss: shift 7 scores lower than the true key and reads dan reoep swo, which any reader would reject and the statistic has no way to.

Counting finds e, and little else 🖖

On a 600-letter message, pairing letters by rank puts e in the right place in 96.5% of 400 random trials. The letters after it are too close together for their order to survive a short text: in The Dancing Men, a, o, i, n, h and s all fall between 6.3% and 8.0%, and a few letters of chance reorder them. Rank every letter and you get, on average, 6.3 of the 23.5 letters present right, a third of the text. Holmes, deciphering the dancing men in that same story, says as much: “The order of the English letters after E is by no means well marked, and any preponderance which may be shown in an average of a printed sheet may be reversed in a single short sentence.” He waited for more messages and read words.

A whole story of ciphertext still leaves five letters wrong 🖖

More ciphertext steadies the counts, but they settle on the counts of the story being read, and two stories by the same author do not agree. Press Substitution, a whole story: all 32,725 letters of The Solitary Cyclist, ranked against The Dancing Men, put 21 letters in the right place and five in the wrong one, h, i, n, f and y, leaving 76.1% of the text right. The Cyclist uses h (6.69%) a shade more than i (6.67%) and n (6.34%); the Dancing Men puts i and n ahead of h. Holmes gives the order as T, A, O, I, N, S, H, R, D, L, and the story he says it in has H ahead of S.

Problem solved in full

Where counting stops and reading starts 4 steps
Press Substitution, 600 letters. How long would a computer trying a billion keys a second take to try them all? Then break the message: what do the counts give you, and what do the commonest words give you?

Open this problem in the tool
1. There are 26! = 403,291,461,126,605,635,584,000,000 keys, about 4.03 × 10²⁶. At 10⁹ a second that is 4.03 × 10¹⁷ seconds, and a year is 3.16 × 10⁷ seconds, so 1.28 × 10¹⁰ years: 12.8 billion.
  
  $26! = 403291461126605635584000000 \approx 4.03 \times 1 0^{26}, \frac{4.03 \times 1 0 ^{26}}{1 0 ^{9} \times 3.16 \times 1 0 ^{7}} = 1.28 \times 1 0^{10} years$
2. The commonest ciphertext letter is I, 80 of the 600, 13.3%. In The Dancing Men e is 12.44%, so I is e. The next three, O, N and X, have 49, 47 and 45, too close to put in order with any confidence, and ranking pairs them with t, a and o, all three wrong. The results table shows the cost: pairing by rank alone gets 3 of the 23 letters right, 14.2% of the text.
  
  $\frac{80}{600} = 13.3% \approx 12.44% : I \to e, 49, 47, 45 for O, N, X$
3. Now the words. The three-letter words OBJ and XDI occur five times each, and XDI ends in I, which is e: the, so X is t and D is h. OBJ is then most likely and: O is a, B is n, J is d. The commonest two-letter word, PK, eight times, fits of, and XP, five times, then reads to, which agrees.
  
  $XDI \to t h e, OBJ \to an d, PK \to o f, XP \to t o$
4. Type those eight letters into the boxes. e, t, h, a, n, d, o and f cover 321 of the 600 letters, 53.5%, and the first line reads f·o· the ·ea·· 1894 to 1901. The counts have nothing more to give. Before a date, f·o· is almost certainly from, which hands you r and m, and from there it is reading.
  
  $\frac{321}{600} = 53.5% of the message from 8 letters$
Answer

12.8 billion years to try every key. Counting gives one letter, e; three common words give seven more, and those eight letters already decipher 53.5% of the message.

$1.28 \times 1 0^{10} years; 8 letters \to 53.5%$

Learning path

How codes are broken

References (1)

Both passages the page counts, and Holmes's words quoted in the second and third insights: Arthur Conan Doyle, "The Adventure of the Dancing Men" and "The Adventure of the Solitary Cyclist," in The Return of Sherlock Holmes. Project Gutenberg eBook #108.

By the 42Math team · Reviewed against published sources. Corrections welcome.