Vigenère

The Vigenère cipher is a polyalphabetic substitution. Blaise de Vigenère actually produced a more sophisticated autokey cipher, but through an accident of history his name has become attached to this weaker cipher. The cipher below is not le chiffre indéchiffrable, though it has sometimes been mistakenly called that. This said, the Vigenère cipher is reasonably secure - requiring more work than a simple monoalphabetic substitution. Yet it is still possible to break by pencil and paper methods, and if one knows the techniques it is quite vulnerable. I have heard that a well known scientific magazine said that it was "uncrackable" as late as 1917 - even though it had been broken before then.

Grommit

The Vigenère cipher makes use of a tableau.

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
B C D E F G H I J K L M N O P Q R S T U V W X Y Z A
C D E F G H I J K L M N O P Q R S T U V W X Y Z A B
D E F G H I J K L M N O P Q R S T U V W X Y Z A B C
E F G H I J K L M N O P Q R S T U V W X Y Z A B C D
F G H I J K L M N O P Q R S T U V W X Y Z A B C D E
G H I J K L M N O P Q R S T U V W X Y Z A B C D E F
H I J K L M N O P Q R S T U V W X Y Z A B C D E F G
I J K L M N O P Q R S T U V W X Y Z A B C D E F G H
J K L M N O P Q R S T U V W X Y Z A B C D E F G H I
K L M N O P Q R S T U V W X Y Z A B C D E F G H I J
L M N O P Q R S T U V W X Y Z A B C D E F G H I J K
M N O P Q R S T U V W X Y Z A B C D E F G H I J K L
N O P Q R S T U V W X Y Z A B C D E F G H I J K L M
O P Q R S T U V W X Y Z A B C D E F G H I J K L M N
P Q R S T U V W X Y Z A B C D E F G H I J K L M N O
Q R S T U V W X Y Z A B C D E F G H I J K L M N O P
R S T U V W X Y Z A B C D E F G H I J K L M N O P S
S T U V W X Y Z A B C D E F G H I J K L M N O P Q R
T U V W X Y Z A B C D E F G H I J K L M N O P Q R S
U V W X Y Z A B C D E F G H I J K L M N O P Q R S T
V W X Y Z A B C D E F G H I J K L M N O P Q R S T U
W X Y Z A B C D E F G H I J K L M N O P Q R S T U V
X Y Z A B C D E F G H I J K L M N O P Q R S T U V W
Y Z A B C D E F G H I J K L M N O P Q R S T U V W X
Z A B C D E F G H I J K L M N O P Q R S T U V W X Y

The cipher also requires a key, the ciphertext is formed by first writing the key underneath the plaintext. In the following example I will use the plaintext "electronics for dogs" and the key "grommit".

 Plaintext : electronics for dogs
       Key : GROMMITGROM MIT GROM
Ciphertext :

The question remains: How do I now form the ciphertext?

To do form the ciphertext we need to use the Vigenère tableau, the plaintext is encrypted letter by letter using the correspponding key letter.

Using the tableau, a paper copy is useful, locate the first plaintext letter, "E", along the left hand side of the table, then locate the corresponding letter of the key, "G", along the top of the table.

Reading along from the E and down from the G will give the ciphertext letter, in this case the ciphertext is "K".

Messy Grommit

Continuing this for all of the other letters we can obtain the full ciphertext.

 Plaintext : electronics for dogs
       Key : GROMMITGROM MIT GROM
Ciphertext : KCSOFZHTZQE RWK JFUE

You'll notice that a given letter of the plaintext does not yield the same letter of the ciphertext each time it appear. For instance the word "electronics" with the key "grommit" yields the ciphertext "kcsofzhtzqe" - the plaintext letter "e" yields both the ciphertext letters "k" and "s". This is a feature of any polyalphabetic cipher. Polyalphabetic meaning "many alphabets".

Decoding is easy for anyone with the key. One just needs to find the letter of the key from the side of the table, read along the row to find the ciphertext letter and then move to the top of the column to find the original plaintext letter.

How can it be Broken?

Obviously, a Vigenère cipher is more secure than a straightforward monoalphabetic substitution to a casual analysis. Nevertheless, the cipher is still vulnerable to attack.

The first job is to find the length of the key. This may be done by using the Method of Coincidences. The plaintext is shifted against itself and the number of matches between letters is counted. A random shift will give a low number, a shift which is a multiple of the key length will give a high number. This is because some letters are more frequent in English, and a letter is more likely to match a copy of itself which has been coded with the same keyletter.

Using the ciphertext above, a shift of 3 gives the following...

KCSOF ZHTZQ ERWKJ FUE.. .
   KC SOFZH TZQER WKJFU E

There is one coincidence. The ciphertext would be shifted different amounts in order to select the most likely key length. (Obviously there is not enough ciphertext in this example to produce a statistically significant result, but hopefully you get the idea.)

That bit is quite important, go back and make sure you get it.

So, we have the key length, how does this help?

Let's assume that the key is found to be five letters long. We may then divide the message up into ciphertext which has all been enciphered with the same letter. In other words, letters one, six, eleven etc. were all encrypted with the first letter of the key, letters two, seven, twelve etc. were all encrypted with the second letter and so on.

Each "group" of letters is simply enciphered by a Caesar shift (think what happens if the Vigenere cipher is used with the key GGG). Thus the key letter may simply be found by observing the relative frequencies of letters. Once the key letter has been determined for each group then the message may be reassembled. The cipher is solved.

Edit (17/10/04): A series of posts which show how Beaufort can be analysed are elsewhere on this site. Vigenère can be analysed using identical methods, the only difference is in how the key is applied to the text.