Breaking Vigenère

A Vigenère cipher hides a message by using not one shifted alphabet but several. Pick a short keyword, write it again and again beneath the message, and move each letter of the message forward in the alphabet by the number the letter below it stands for. With the keyword LEMON, the first letter moves by L, the second by E, the third by M, and so on, and when the keyword runs out it simply starts over. The same plain letter can now become many different cipher letters, so the most common letter in the message no longer shows up as the most common letter in the cipher text. That was the whole point, and for a very long time it worked well enough that the cipher earned the name le chiffre indéchiffrable, the indecipherable cipher.

The name is a small injustice. As far as I remember, the scheme of a repeating keyword was described in 1553 by Giovan Battista Bellaso, and Blaise de Vigenère, who published a related but different idea in 1586, only gained the credit later. I am writing these names and dates from memory and have not checked them against a book, so treat them as the usual account rather than as something this page has proved.

What broke it was repetition. If the same piece of the message meets the same part of the keyword twice, the same cipher letters appear twice, and the gap between the two appearances must be a whole number of keyword lengths. Friedrich Kasiski published this observation in 1863, though Charles Babbage seems to have reached it earlier without publishing it. Collect the gaps between repeated groups of letters, ask which key lengths divide them, and the real length stands out. This is the first test the page runs, and it can only work if the text is long enough to contain repeats that are not accidents.

The second test came later. William Friedman, in the 1920s, described the index of coincidence: the chance that two letters picked at random from a text are the same. English is lumpy, with a few letters used far more than the rest, so two letters drawn from it match more often than two drawn from uniformly random letters. Split a Vigenère message into columns by a guessed key length. If the guess is right, each column is just English shifted by one fixed amount, and it keeps its lumpiness. If the guess is wrong, the columns mix several shifts together and look flat.

Once the length is known, the problem falls apart into several simple ones. Each column is a Caesar cipher, which has only possible shifts. For each shift, the page asks how well the shifted column matches the usual letter frequencies of English, and keeps the best. The usual frequencies are not typed in here. They are counted from the letters of this very essay, and a table of published frequencies is shown beside them as a second opinion, although I typed that table from memory too, so it is a different source but not a verified one.

All of this depends on having enough letters. Every key letter needs its own column, and a column of just a few letters is too small to show any pattern: a lucky run of rare letters can point at the wrong shift. A longer key therefore needs a longer message, and a very short message cannot be broken this way at all, however clever the method. That is the claim the grid above puts to the test, by switching its cause off: very short texts with long keys, and a model of English with its letters scrambled, should both fail.