The Vigenère cipher

In the last lesson the substitution cipher fell to simple letter counting. The commonest letter of the ciphertext is almost certainly E, the next ones T and A, and the rest of the text appears by itself. The weakness is that each letter is always replaced the same way: if E became Q, then every E in the letter is a Q, and together they give themselves away by their frequency. How do you fix that? Make the same letter encrypt differently each time.

European cipher makers took more than a century to get there. Around 1467 the Italian architect and scholar Leon Battista Alberti described a cipher disc of two rings, much like the Caesar disc from the first lesson, but with a twist: every few words you turn the ring, so the cipher changes in the middle of the message. In 1518 the German abbot Johannes Trithemius published his Polygraphia with a table of every shift of the alphabet, the very table we now call the Vigenère square. And in 1553 the Italian Giovan Battista Bellaso worked out how to drive the change of alphabets with an easily remembered word: a key.

The key is a word, not a number

Remember Caesar: the key is one number, the shift. Bellaso's idea was to take a word and treat each of its letters as a separate shift: A is a shift of 0, B is 1, C is 2 and so on up to Z, 25. The key LEMON is five shifts in a row: 11, 4, 12, 14, 13.

You write the key over the plaintext and repeat it until the text runs out. The first letter of the text moves by the first letter of the key, the second by the second, the sixth by the first again:

Look at the word “attack”. Its two Ts became X and F, its two As became L and O. And it works the other way too: the different letters D and N in “dawn” both came out as R. The frequency analysis of the last lesson trips up here: the commonest letter of the ciphertext no longer stands for the commonest letter of the language.

Ciphers like this are called polyalphabetic: instead of a single substitute alphabet, as in Caesar or simple substitution, they use several in turn. The key LEMON has five of them, five Caesar ciphers with different shifts woven together letter by letter.

A square instead of arithmetic

Adding letter numbers in your head is tiring, so cipher clerks used a table. Its first row is the plain alphabet, the second is shifted by one letter, the third by two, all 26 rows of it. In Latin it is the tabula recta, the “straight table”; in English it is usually called the Vigenère square.

To encrypt a letter, find the row of the key letter and the column of the text letter. Where they cross is the cipher letter. To decrypt, go back: find the cipher letter in the key letter's row and look at which column it sits in.

Notice that row A is just the alphabet. A key letter A changes nothing, and a plaintext A turns into the key letter itself, which is exactly what happened to the As in “attack”.

Why Bellaso's cipher carries Vigenère's name

Blaise de Vigenère, a French diplomat, published his Traicté des chiffres (Treatise on ciphers) in 1586. He described the keyword cipher there too, but the invention he was proud of was another one, the autokey: a short key goes only at the start, and after that the plaintext itself is the key. That cipher is noticeably stronger, because its key never repeats.

Two hundred-odd years later the credits got mixed up. Bellaso's cipher was put down to Vigenère, and Vigenère's own invention was forgotten. The name stuck, and it is far too late to change it now. Cryptography is full of this: the Playfair cipher, for one, was invented by Charles Wheatstone, while Lord Playfair only championed it.

The indecipherable cipher

Why did Vigenère hold out for so long? Look at what the key does to the frequencies. Below is one and the same text encrypted with keys of different lengths. The bars show how often each ciphertext letter occurs, from the commonest to the rarest. In grey is the same for ordinary English.

With a long key the profile is almost flat, like a random string of letters. A codebreaker used to looking for the commonest letter has nothing to grab hold of. The French called it le chiffre indéchiffrable, the indecipherable cipher. For about three hundred years after Bellaso it was the model of a safe cipher. Diplomats used it, and so did the Confederate army in the American Civil War, with brass cipher discs and keys such as “Manchester Bluff” and “Complete Victory”. The Union, as it happens, read those dispatches regularly.

Babbage and Kasiski: the key gives itself away

The first to break Vigenère was the Englishman Charles Babbage, the inventor of mechanical calculating engines, around 1854. But he published nothing, and his success only came to light in the twentieth century from his papers. So the credit went to Friedrich Kasiski, a Prussian officer, who published the same method in a book on secret writing in 1863.

Here is the idea. A long message repeats words: “the”, “that”, “which”. Usually a repeat falls under different key letters and encrypts differently. But now and then the key lands on the word exactly as it did before, and the ciphertext shows an identical chunk. That happens when the distance between the repeats is a multiple of the key length.

So you look for identical groups of three or four letters in the ciphertext and measure the distances between them. In the dispatch on the codebreaker's bench below, the group POM turns up 14 letters apart and then another 14, and the group LAP at distances of 147, 154 and 84. Every one of those numbers divides by 7. Most likely the key has seven letters, or 14, or 21. Chance repeats happen too, so you look at what most of the distances divide by.

The index of coincidence: measuring how uneven a text is

In the 1920s the American cryptologist William Friedman came up with a sturdier method. Pick two letters from a text at random. What is the chance they are the same? That number is the index of coincidence.

In ordinary English some letters are common and others rare, so matches happen fairly often: the index is about 0.067. In a random jumble where all 26 letters are equally likely it is lower, 1/26, about 0.038. A Vigenère cipher with a long key turns text into just such a jumble. You could see it on the slider above.

Now the key trick. Suppose the key has L letters. Write the ciphertext out in rows of L letters, so you get columns. If L is right, every letter in a column was encrypted with the same key letter, which makes the column an ordinary Caesar cipher. And Caesar doesn't mix frequencies, it only moves them around, so the column's index of coincidence will be like the language's, about 0.067. If L is wrong, the column mixes different alphabets and the index is low.

All that is left is to try lengths 1, 2, 3… and see where the index jumps.

A high index shows up not only at the right length but also at its multiples, 14 and 21. If the key has seven letters, then at length 14 each column is still encrypted with a single letter: the key has just been “written out” twice. So you take the shortest length with a high index.

Once the length is known, Vigenère falls apart into several independent Caesars. Each one breaks by trying all 26 shifts: the shift at which the column's letter frequencies best match the language's is the right one. The match is measured with the χ² number you met in the first lesson: the smaller it is, the more the column looks like English.

Can Vigenère be fixed?

The whole attack rests on one thing: the key repeats. The longer the key compared with the text, the fewer letters each column gets and the worse the statistics work. What if the key is as long as the message itself? Then every “column” holds a single letter and there is nothing to count.

Even that isn't enough. If the key is meaningful text, say a page from a book, it can be guessed piece by piece: the codebreaker tries common words and checks whether something readable appears in both texts at once. Only one thing is truly safe: a key of random letters, as long as the message, used once. That cipher is called the one-time pad, and it has been proved impossible to break in principle. It gets its own lesson on XOR.

What to take with you

• The Vigenère cipher is several Caesar ciphers taking turns. The letters of the keyword set the shifts, and the key repeats along the whole text.
• The same letter encrypts differently each time, so the ciphertext's frequencies flatten and plain frequency analysis fails.
• A repeating key gives away its length: through repeats in the ciphertext (Kasiski's method) and through the index of coincidence of the columns (Friedman's).
• Once the length is known, every column is an ordinary Caesar, and letter counting breaks it.
• The cipher only becomes unbreakable with a random key as long as the message, and that is already a one-time pad.

So far every cipher has replaced letters. In the next lesson the letters stay the same but change places: transposition ciphers, from the Spartan scytale to the field ciphers of the twentieth century. Next: transposition ciphers →