Math Detours · Grade 6 · Around the corner · 16

Secret codes and how to break them

Julius Caesar hid his messages by shifting every letter. It worked for centuries. Tonight you learn why it is just clock arithmetic, and how to crack it in five minutes with a pencil.

Name ____________________Date ____________

Tonight's idea

Number the letters: A = 0, B = 1, up to Z = 25.

ABCDEFGHIJKLM
0123456789101112
NOPQRSTUVWXYZ
13141516171819202122232425

A Caesar cipher with key 3 adds 3 to every letter: A becomes D, B becomes E. What about X, which is 23? \(23 + 3 = 26\), and there is no letter 26, so wrap around to 0: X becomes A. That wrap-around is exactly the clock arithmetic you have met: the new letter is \((\text{old} + \text{key}) \bmod 26\). Decoding is subtracting the key, mod 26.

The weakness is obvious once you say it. There are only 25 useful keys (key 0 changes nothing, key 26 is the same as key 0). An enemy can simply try all 25 and see which one produces English. That takes a few minutes by hand and no time at all for a computer.

There is a faster way than trying every key. In ordinary English, the letter E is the most common, about one letter in eight. Then T, A, O, I, N. So count the letters in the secret message. Whichever letter appears most is probably E in disguise, and the gap between that letter and E gives the key. Probably, not certainly: it is a guess that assumes the message is ordinary English, and you test it by decoding and reading. This is called frequency analysis, and it was invented by the Arab scholar al-Kindi in the 800s. It breaks not just Caesar shifts but any cipher that always swaps the same letter for the same letter.

Watch one

Encode MEET ME AT THE OAK TREE AT NOON with key 3. M = 12, plus 3 is 15 = P. E = 4 becomes 7 = H. T = 19 becomes 22 = W. Continue: PHHW PH DW WKH RDN WUHH DW QRRQ.

Break this one without being told the key: WKLV LV HDVB. Count the letters: V appears 3 times, so guess V = E. V = 21 and E = 4, so the key would be 17. Decode the first word with key 17: W − 17 = F, K − 17 wraps to T, then U and E: FTUE. Not English, so the guess is wrong; short messages fool the count. Use word shapes instead: LV is a two-letter word and WKLV ends in the same two letters. THIS IS fits, and gives key 3. Decode the rest with key 3: THIS IS EASY. It reads, and that is the real test. Long messages almost never need the second guess.

Your turn

  1. Encode your first name with key 5. Then decode PDWK LV IXQ, which uses key 3.
  2. Encoding with key 10 and then encoding the result again with key 16 gives back the original message. Why? What single key is the same as key 10 followed by key 7?
  3. Here is a message encoded with an unknown key. Tally the letters in the strip below, find the most common one, work out the key, and decode it.

    OFOBI COMBOD WOCCKQO VOKFOC K DBKSV LOMKECO DRO VODDOB O BOPECOC DY RSNO

    ABCDEFGHIJKLMNOPQRSTUVWXYZ
                              
  4. In your decoded message from question 3, how many E's were there out of the 60 letters? Compare that with the "one in eight" claim.
  5. A friend suggests a stronger cipher: instead of shifting, scramble the whole alphabet (A becomes Q, B becomes M, and so on, in any order). How many keys are there now? (Count: 26 choices for what A becomes, then 25 for B, and so on.) Does frequency analysis still work against it? Explain.
  6. Imagine BANANA written 100 times in a row (600 letters) and encoded with key 3. Predict which letter gets the tallest bar in the tally, then check. A code-breaker who assumes that bar is E in disguise tries which key? How do they find out they were wrong?

Try keys instantly at mathdetours.com/demos/cipher.html, which also draws the letter counts for you. For the stretch, demos/vigenere.html tries keywords: predict the bars for AAAAA and ABCABC before you look.

Stretch: beating the letter count

In the 1500s Blaise de Vigenère's cipher used a keyword. To encode with keyword CAT, shift the first letter by C (2), the second by A (0), the third by T (19), then C, A, T again, and so on. Encode ATTACK AT DAWN with keyword CAT.

Now explain why frequency analysis in its simple form fails: what happens to the letter E when it appears in different positions of the message? For three hundred years this was called le chiffre indéchiffrable, the unbreakable cipher. Then Charles Babbage, and separately a Prussian officer called Kasiski, noticed that if you could guess the keyword's length, you could split the message into three Caesar ciphers and count each one separately. How would you guess the length?

Answers

  1. Names vary. PDWK LV IXQ decodes to MATH IS FUN.
  2. \(10 + 16 = 26\), and shifting by 26 is shifting by 0, so the second encoding undoes the first. Key 10 then key 7 is the same as key 17, because shifts add: \((x + 10) + 7 = x + 17\).
  3. O appears 17 times out of 60, far ahead of anything else. O = 14 and E = 4, so the key is 10. Subtract 10 from everything: EVERY SECRET MESSAGE LEAVES A TRAIL BECAUSE THE LETTER E REFUSES TO HIDE.
  4. 17 out of 60, which is more than one in four. This sentence was chosen to be E-heavy; normal English runs nearer one in eight, but E is still almost always on top.
  5. \(26 \times 25 \times 24 \times \ldots \times 1 = 26!\), which is about \(4 \times 10^{26}\) keys. Far too many to try. But frequency analysis still works perfectly, because each letter is still always replaced by the same letter, so the most common cipher letter is still probably E, the next ones T, A, O, and common short words like THE and AND give the rest away. The number of keys was never the problem.
  6. A appears 300 times, N 200 and B 100. Key 3 turns them into D (300), Q (200) and E (100), so the tallest bar is D. “D is E in disguise” means D = 3 and E = 4, a shift of −1, which is key 25. Decoding EDQDQD with key 25 gives FERERE, not a word, so the guess fails. The count assumed English-like text; reading the result is what catches it.

Stretch. ATTACK AT DAWN with CAT: A+2 = C, T+0 = T, T+19 = M, A+2 = C, C+0 = C, K+19 = D, A+2 = C, T+0 = T, D+19 = W, A+2 = C, W+0 = W, N+19 = G: CTMCCD CT WCWG. Notice the four A's became C, C, C, C by luck of position, but T became T twice and M once. The same letter encodes differently depending on where it falls, so a single count mixes three different shifts together and flattens the peaks. Kasiski's trick: repeated chunks of the real message (the plaintext), like THE, that happen to land in the same keyword position come out identical in the coded message (the ciphertext), and the distance between such repeats is a multiple of the keyword’s period. Measure a few gaps and list their common factors. That list is a clue, not an answer: some repeats are accidents. The true period divides every genuine gap, but so do its factors, and sometimes larger multiples of it. Pick a candidate, split the message into that many Caesar ciphers, break each by counting, and read the result; if it is not English, try the next candidate. One more catch: what matters is the shortest repeating block of the key, so CATCAT behaves exactly like CAT, and AAA is no cipher at all.

← PreviousNext: The detective's method for sequences →