Babbage, Kasiski and the Vigenère cipher: how it fell

Breaking codes with statistics, part two of six.

Once letter counting was known, a cipher that swapped each letter for one fixed substitute was in trouble. The common letters of the language still showed through, just wearing different clothes. Anyone patient enough to count could read the message.

The answer, worked out by several European writers in the fifteenth and sixteenth centuries, was to stop using a single substitute alphabet. Use many, and switch between them as you write.

The cipher that was called indecipherable

The best-known version carries the name of Blaise de Vigenère, a French diplomat of the sixteenth century, although others described similar schemes before him. It works with a keyword. Write the keyword over the message, repeating it as often as needed. Each letter of the keyword says how far to shift the letter of the message beneath it along the alphabet.

The effect is that the same letter of the message is written differently depending on where it falls. An "e" might become one letter in one place and a quite different letter a few words later. The tidy peaks of letter frequency that undid simpler ciphers are spread out and flattened. Count the letters of the scrambled text and you see something close to a level field.

For a long time this seemed to defeat frequency analysis completely. The cipher became known as "le chiffre indéchiffrable", the indecipherable cipher. It was slow to use by hand, which limited how widely it spread, but its reputation for strength lasted for centuries.

Babbage, in private

Charles Babbage is remembered today for his designs for mechanical calculating engines. He was also a keen codebreaker, and by the mid-1850s he had worked out how to break the Vigenère cipher.

He never published his method. The reasons are unclear, and his work came to light only in the twentieth century, when historians went through his notes. For more than a century the credit went elsewhere.

Kasiski, in print

In 1863 Friedrich Kasiski, a Prussian army officer, published a book on secret writing and the art of deciphering it. In it he set out a general method for breaking ciphers of the Vigenère kind, the same weakness Babbage had found.

The weakness is in the repetition of the keyword. Messages are full of common words and letter groups. Now and then, the same group of letters in the message lines up with the same part of the keyword, and it is written the same way both times. The result is a repeated fragment in the scrambled text.

Kasiski's step was to look for those repeats and measure the distances between them. If a fragment appears twice, the gap between the two appearances is very likely a whole number of keyword lengths. Collect several such gaps and the keyword length usually stands out as the number that divides most of them.

Once you know the keyword length, the cipher falls apart into pieces you already know how to break. Take every letter that was shifted by the first letter of the keyword and you have a simple single-alphabet cipher. Do the same for the second, the third, and so on. Each group can then be attacked with the letter counting that al-Kindi had described a thousand years earlier.

What changed

The defence had been to hide the patterns of language by spreading them out. Kasiski and Babbage showed that the spreading itself left a pattern. A short keyword used over and over is a rhythm, and a rhythm can be measured.

The lesson was taken seriously. Cipher designers began to look for ways to avoid any regular repetition, through longer keys, keys that did not repeat, and, later, machines whose settings changed with every letter. Codebreakers, in turn, began to look for subtler regularities than a repeated fragment. Twenty years later, Kerckhoffs would argue that a cipher must stay safe even when the enemy knows how it works, which, after Kasiski, meant knowing exactly where to look for repeats.

What it teaches

A cipher's reputation is not a measurement. The Vigenère cipher looked strong because the simple counts came out flat. A sharper count, aimed at the structure of the key rather than the letters, found it out. Protection has to hold up against an adversary who counts and measures everything, including things the designer never thought to count.

Next in the series: Friedman, and how counting coincidences turned codebreaking into a science.

If you hold data whose protection has to be measured rather than taken on reputation, join the waitlist for early access.