The flaw: the repetition of the key

The Vigenère cipher resists conventional frequency analysis. However, it has a structural weakness: the key repeats.

Kasiski’s idea

Published in 1863 by Friedrich Kasiski, it is based on a simple observation.

If the same group of letters from the plaintext falls at the same position in the key cycle, it produces exactly the same ciphertext group. These repetitions are visible to the naked eye:

... W Z X ......... W Z X ......... W Z X ...
    |<--- 12 --->|<--- 12 --->|

Here, the repetitions are spaced 12 characters apart. However, this is no coincidence: the spacing is a multiple of the key length.

By identifying several repetitions and taking the GCD of their spacings, we can very likely determine the key length. Here, 12 suggests a key length of 1, 2, 3, 4, 6 or 12.

What next?

Once the length n is known, the whole thing falls apart. We split the message into n groups:

• letters no. 1, n+1, 2n+1 … have all been encrypted using the same key letter;
• the same applies to letters n°, n+2, 2n+2 …;
• and so on.

Each group is therefore a simple Caesar cipher. And a Caesar cipher can be broken by frequency analysis, as we have seen.

Vigenère is not an unbreakable cipher: it consists of interleaved n Caesar ciphers. One simply needs to find n to separate them.

The moral of the story

The weakness lay not in the encryption method, but in the reuse of the key. This is a theme that runs through all of modern cryptography: reusing a key, or a random element, is to offer an attacker a foothold.