Vigenère Cipher: Find the Key Length, Then Break It

A key of L letters turns a message into L interleaved Caesar ciphers. Write the ciphertext in rows of k and count coincidences down each column: at the right k, every column is English again. Step through the attack, or choose a bar yourself.

Worked example — Vigenère Cipher: Find the Key Length, Then Break It

Letters in the message, N	600
Index of coincidence of the ciphertext	0.0417
The line: ¾ of the way from 1/26 to English	0.0595
Key length: the smallest k over the line	6
Average IC of the 6 columns	0.0659
Expected at this k for a key of 6 letters	0.0665
Key read back	RABBIT
Letters read back right	600 of 600 (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 — Vigenère Cipher: Find the Key Length, Then Break It

The Vigenère cipher adds a repeating key to the message letter by letter. With A = 0 to Z = 25, cipher letter i is (message letter i + key letter i mod L) mod 26, so each key letter is a Caesar shift applied to every L-th letter. The index of coincidence of N letters, IC = Σ n(n − 1) / (N(N − 1)), is the chance that two letters taken from different places are the same: 1/26 = 0.0385 for random letters, about 0.066 for English. Friedman's test writes the ciphertext in rows of k and counts coincidences down the columns: at the key length, and at its multiples, every column is shifted English and its IC returns to English's. Kasiski's test, published in 1863, factors the spacings between repeated groups of letters.

What each symbol means

L: the number of letters in the key
k: a key length being tried: the number of columns the ciphertext is dealt into
N: the number of letters in the message
n: in the IC formula, how many times one letter occurs

Assumes: Letters only: case, spaces and punctuation are dropped before encrypting, as on Carroll's card. “English” here means Chapter I of Alice's Adventures in Wonderland, 8,606 letters; its letter shares and its IC of 0.0665 are the reference for every test, and the trials that measure success draw their messages from the same chapter, which flatters the attack slightly. The key length is the smallest k whose average column IC is at least three quarters of the way from 1/26 to English. Random keys draw each letter uniformly, so their letters may repeat, and a key whose letters repeat at half its length can lift the bar at half the length over the line.

On average, each bar stands gcd(k, L)/L of the way to English 🖖

Press RABBIT, 600 letters and look at the bars. Dealt into k columns, each column mixes the alphabets of L/gcd(k, L) key letters and, averaged over keys, keeps gcd(k, L)/L of the gap between random letters and English. For the six letters of RABBIT that puts 6, 12 and 18 at the top, 3, 9 and 15 halfway, the other even k a third of the way and the rest a sixth; the bars here land at 98 to 106%, 42 to 52%, 26 to 37% and 9 to 23%. Bar 1 is the whole ciphertext, so a key of ten letters leaves, on average, a tenth of English's unevenness in the letter counts, while every tenth letter is still English. Averaged over 100 random keys of each length from 1 to 12, every one of the twenty bars falls within 3% of the gap of where gcd(k, L)/L puts it. The 1935 printing of Friedman's paper on the index of coincidence gives the two ends: 0.066 for a correct period, 0.038 for a wrong one. This chapter counts 0.0665, and 1/26 is 0.0385. The line sits three quarters of the way up because the bar at L/2 lands, on average, about halfway, and a little under it when the columns are short.

Every key letter is one more Caesar cipher to win 🖖

Press Twelve-letter key. The length is right, and each of the twelve columns is now a Caesar cipher of 18 letters, broken by trying all 26 shifts against the chapter's letter shares. Eleven come out right. Column 5 holds only two Es and three Rs, and the shift that turns each R into an E fits English a little better than the true one. A single column of 30 letters comes out right 98% of the time, but the key needs every column: over 2,000 stretches of this chapter at 30 letters a column, all twelve were right 81% of the time. Each column is the previous rung's Caesar attack run again, so a long key multiplies the chances to miss: counted in steps of five letters, a twelve-letter key first comes out whole 99% of the time at 55 letters a column, 660 in all. That is once the length is found. The bar test itself needs more text for a short key, because it averages over fewer columns: at 60 letters a column the whole attack reads back a one-letter key about 87% of the time and a twelve-letter key more than 99%.

A key as long as the message leaves only E 🖖

Press Key as long as the message and step to the end. Twenty letters under twenty key letters puts one letter in each column. There is no pair to count, so bar 20 is missing, and chi-squared over a single letter can only prefer the shift that turns it into E, the commonest letter in the chapter. Every column reads E, and the read-back is right twice, at the two Es of “Alice was beginning to g”. Over the whole chapter E is 1,078 of 8,606 letters, 12.5%, and at one letter a column the attack scores 12.6% on stretches of it: what it already knew about English, and nothing it learned from the ciphertext. If the twenty key letters are drawn at random and never used again, every twenty-letter message fits these twenty cipher letters equally well. That is the one-time pad.

Problem solved in full

Was Carroll's cipher card right? 4 steps
Lewis Carroll had a card printed explaining this cipher. It is undated; his letters about sending a key-word are from April 1868, five years after Kasiski's book. The card encrypts “meet me on Tuesday evening at seven” under the key-word vigilance and promises that it will be “impossible for any one, ignorant of the key-word, to decipher the message, even with the help of the table.” Press Carroll's card: can the page read his message? Then encrypt the opening of Chapter I under the same key-word. How many letters does the page need to read VIGILANCE back?

Open this problem in the tool
1. Check one letter by hand. m is 12 and v is 21; 12 + 21 = 33, and 33 − 26 = 7, which is h. The page's ciphertext, HMKBXEBPXPMYLLYRXIIQTOLTFGZZV, is Carroll's letter for letter.
  
  $m + v = 12 + 21 = 33 \equiv 7 = h (mod 26)$
2. 29 letters in 9 columns gives two columns of 4 and seven of 3. No three-letter group repeats, so Kasiski has nothing to factor. No bar reaches the line at 0.0595; the tallest is k = 9, at 0.0556, so the length comes out right. Chi-squared over three or four letters is close to a guess, though: the key comes back as HIGXXLNPM, with 3 of its 9 letters right, and 10 of the 29 message letters.
  
  $29 = 9 \times 3 + 2 : columns of 4, 4, 3, 3, 3, 3, 3, 3, 3; \overline{IC}_{9} = 0.0556 < 0.0595$
3. Press VIGILANCE, 189 letters: the chapter's opening under Carroll's key-word, 21 letters a column. Bar 9 is the first over the line, at 0.0794, and 4 of the 5 spacings between repeated groups are multiples of 9 (54, 36, 27 and 72; the fifth is 29). All nine columns come out right, and so do all 189 letters.
  
  $189 = 9 \times 21 : \overline{IC}_{9} = 0.0794 \geq 0.0595; 54, 36, 27, 72 divisible by 9, 29 not$
4. Set the letters to 188. The length is still 9, but column 9 now has 20 letters and fits T better than E: 168 of 188 letters come back. The 189th letter falls in column 9 and tips it to E.
  
  $188 = 8 \times 21 + 20 : column 9 reads T, \frac{168}{188}$
Answer

On the page, Carroll's own message holds and 189 letters of Alice do not. Three or four letters a column is too few to count, and the key comes back as HIGXXLNPM; 21 letters a column are enough to read VIGILANCE back. What protected his message was its length. Whether someone who guessed one of its words, “Tuesday” say, could read the rest, the page cannot test: it only counts letters.

$29 letters: 10 right; 189 letters: VIGILANCE$

Learning path

How codes are broken

References (3)

The two ends of the bar chart in the first insight (.066 for a correct period, .038 for a wrong one), and the method itself: write the ciphertext in lines of the assumed period and count coincidences down the columns, for each assumption in turn: William F. Friedman, "The Index of Coincidence and Its Applications in Cryptanalysis," Technical Paper, War Department, Office of the Chief Signal Officer. Washington: Government Printing Office, 1935. A 1923 revision of the paper of the same title published in 1922 by the Riverbank Laboratories. p. 11.
Kasiski's 1863 book and what his method does (repetitions, their spacings factored, the key length, then letter frequencies), in the lesson's definition: David Kahn, "Kasiski, Friedrich W.," in Neue Deutsche Biographie 11 (1977), pp. 317 f.
Carroll's Alphabet-Cipher card, its example (vigilance, 'meet me on Tuesday evening at seven', the ciphertext the page reproduces) and its promise, in the worked problem; the April 1868 letters about a key-word: Lewis Carroll (C. L. Dodgson), "The Alphabet-Cipher," printed card, undated (c. 1868). Images of both sides and an account of the letters at Lewis Carroll Resources, "Ciphers."

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