The Vigenère cipher

The Vigenère cipher is a Caesar cipher whose shift changes from letter to letter. A keyword like LEMON gives the shifts 11, 4, 12, 14, 13, used in turn and then repeated, so the same plaintext letter comes out differently each time. For almost three centuries nobody published a way to break it, and the French called it le chiffre indéchiffrable, "the indecipherable cipher". It fell in the 1850s and 1860s. And Vigenère didn't invent it. (This page is how it works. To crack a ciphertext you've got, use the Vigenère cipher decoder.)

Try it

Nothing you type here leaves your browser.

Letters use up key letters. Spaces and punctuation don't.

LEMON in action

Write the key under the message and repeat it as often as you need. Each key letter says how far to shift the plaintext letter above it: A is 0, B is 1, L is 11. Take the message ATTACKATDAWN and the key LEMON:

First letter: A is 0, L is 11, and 0 + 11 = 11, which is L. Second: T is 19, E is 4, 19 + 4 = 23, so X. Third: T is 19, M is 12, 19 + 12 = 31, which wraps past 26 to 5, so F. The whole thing comes out as LXFOPVEFRNHR.

Look at what that does to the letters. The three Ts in ATTACKATDAWN become X, F and E. The two As in ATTACK become L and O. A plain letter no longer gives away how often it occurs.

Before computers, people did the sums with a table. The tabula recta is a 26 × 26 grid where each row is the alphabet shifted one place further than the row above. Find the key letter's row and the plaintext letter's column, and read the cipher letter where they meet.

A key of k letters gives 26^k keys: about 4.6 × 10⁵ for four letters, 3.1 × 10⁸ for six, 2.1 × 10¹¹ for eight, 9.5 × 10¹⁶ for twelve. Nobody's trying 300 million keys by hand. A computer could, for short ones, but it doesn't have to. There's a much better trick.

Whose cipher is it, anyway?

Blaise de Vigenère (1523–1596) didn't invent the cipher that carries his name. Giovan Battista Bellaso described it in 1553, in La cifra del Sig. Giovan Battista Bellaso, building on Johannes Trithemius's tabula recta and adding a repeating keyword. Vigenère published something different and stronger in 1586, an autokey cipher. In the nineteenth century the two got mixed up, and his name stuck to the repeating-key version.

The reputation outlived the security. In 1917, Scientific American called the cipher "impossible of translation", decades after it had been broken. In the American Civil War, Confederate officers used it with a brass cipher disk and a handful of key phrases, among them "Manchester Bluff", "Complete Victory" and, near the end, "Come Retribution". The Union read the messages regularly.

It was broken twice before most people noticed. Charles Babbage solved a version in 1854 and never published. The Prussian infantry officer Friedrich Kasiski published the first general method in 1863. Sources disagree about Babbage's exact date. In the 1920s William Friedman put the whole idea on a statistical footing with the index of coincidence.

Breaking it: slice the cipher into Caesars

If the key has k letters, then letters 1, k+1, 2k+1 and so on were all shifted by the same key letter. Together they form an ordinary Caesar cipher, and so do positions 2, k+2, and the rest. Each of the k columns falls to the chi-squared test from the Caesar page. The only thing missing is k.

Step 1: find the key length

Kasiski's method hunts for repeated stretches of ciphertext. If the same three plaintext letters sit under the same three key letters twice, they encrypt to the same three letters, and the distance between the two appearances is a multiple of the key length. Take the opening of A Tale of Two Cities (217 letters), encrypted with the key DICKENS (7 letters). The ciphertext has 29 repeated three-letter groups, with gaps of 63, 21 and 91 letters between repeats. Their common factor is 7 (63 = 7 × 9, 21 = 7 × 3, 91 = 7 × 13). Count every factor of every gap and 7 turns up 41 times, 3 turns up 34 times. The key length is 7.

Friedman's index of coincidence (IoC) is the probability that two letters picked at random from a text match. English scores about 0.067, because it's full of Es and Ts. Random letters score 1/26, about 0.038. Guess the right key length and every column is English in disguise, so the score is high. Guess wrong and the shifts get mixed together and you land near random. For the same ciphertext, the average IoC across the columns for each guess:

Seven stands out, and so does fourteen, its multiple. Multiples always score well, so take the shortest high value.

Step 2: solve each column

Take every seventh letter, starting from each of the seven positions, and try all 26 shifts on each column, keeping the most English-looking one. The seven winners spell DICKENS, and the text falls out. The breaker does exactly this and shows its working.

You need enough text, roughly 20 letters per key letter. And if the key is as long as the message and never reused, the method has nothing to grab. That's the one-time pad.

The code

// Vigenere: the key's letters, used over and over, give each letter its own Caesar shift.
function vigenere(text, key, decode) {
  var shifts = key.toUpperCase().replace(/[^A-Z]/g, '').split('').map(function (c) { return c.charCodeAt(0) - 65; });
  var i = 0;                                               // counts letters only, so spaces and punctuation do not use up key letters
  return text.replace(/[a-z]/gi, function (ch) {
    var base = ch <= 'Z' ? 65 : 97, s = shifts[i++ % shifts.length];
    var n = (ch.charCodeAt(0) - base + (decode ? -s : s) + 26) % 26;
    return String.fromCharCode(n + base);
  });
}

The only change from Caesar is that the shift is looked up from the key by position.

Cousins

The Beaufort cipher subtracts instead of adding, which makes it reciprocal. The autokey cipher dodges the repeating key by carrying on with the message itself. And machines like the Enigma are really vastly longer polyalphabetic ciphers: the alphabet changes with every letter and the sequence doesn't repeat for about 17,000 letters.