Vigenere

A Polyalphabetic Cipher

One of the main problems with simple substitution ciphers (Caesar's Cipher) is that they are so vulnerable to frequency analysis. Given a sufficiently large ciphertext, it can easily be broken by mapping the frequency of its letters to the know frequencies of, say, English text. Therefore, to make ciphers more secure, cryptographers have long been interested in developing enciphering techniques that are immune to frequency analysis. One of the most common approaches is to suppress the normal frequency data by using more than one alphabet to encrypt the message. A polyalphabetic substitution cipher involves the use of two or more cipher alphabets. Instead of there being a one-to-one relationship between each letter and its substitute, there is a one-to-many relationship between each letter and its substitutes.

Vigenere Cipher

The Vigenere Cipher , proposed by Blaise de Vigenere from the court of Henry III of France in the sixteenth century, is a polyalphabetic substitution based on the following tableau:

Encryption
The Vigenere cipher uses this table together with a keyword to encipher a message. For example, we want to encipher the plaintext message:

TO BE OR NOT TO BE THAT IS THE QUESTION

using the keyword "RELATIONS". We begin by writing the keyword, repeated as many times as necessary, above the plaintext message. To derive the ciphertext using the tableau, for each letter in the plaintext, one finds the intersection of the row given by the corresponding keyword letter and the column given by the plaintext letter itself to pick out the ciphertext letter.

Keyword:	RELAT	IONSR	ELATI	ONSRE	LATIO	NSREL
Plaintext:	TOBEO	RNOTT	OBETH	ATIST	HEQUE	STION
Ciphertext:	KSMEH	ZBBLK	SMEMP	OGAJX	SEJCS	FLZSY

Decryption
Decipherment of an encrypted message is equally straightforward. One writes the keyword repeatedly above the message:

Keyword:	RELAT	IONSR	ELATI	ONSRE	LATIO	NSREL
Ciphertext:	KSMEH	ZBBLK	SMEMP	OGAJX	SEJCS	FLZSY
Plaintext:	TOBEO	RNOTT	OBETH	ATIST	HEQUE	STION

This time one uses the keyword letter to pick a column of the table and then traces down the column to the row containing the ciphertext letter. The index of that row is the plaintext letter.

The strength of the Vigenere cipher against frequency analysis can be seen by examining the above ciphertext. Note that there are 7 "T" in the plaintext message and that they have been encrypted by "H", "L", "K", "M", "G", "X", and "L" respectively. This successfully masks the frequency characteristics of the English "T". One way of looking at this is to notice that each letter of our keyword RELATIONS picks out 1 of the 26 possible substitution alphabets given in the Vigenere tableau. Thus, any message encrypted by a Vigenere cipher is a collection of as many simple substitution ciphers as there are letters in the keyword.

Solving the Vigenere Cipher

Vigenere-like substitution ciphers were regarded by many as practically unbreakable for 300 years.

In 1863, a Prussian major named Kasiski proposed a method for breaking a Vigenere cipher that consisted of finding the length of the keyword and then dividing the message into that many simple substitution cryptograms. Frequency analysis could then be used to solve the resulting simple substitutions. Kasiski's technique for finding the length of the keyword was based on measuring the distance between repeated bigrams in the ciphertext.

A variant of this method, proposed by the French cryptographer Kerckhoff, is based on discovering the keyword itself and then using it to decipher the cryptogram. This modern day version of the Kerckhoff method turns out to be very effective.