|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.
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:
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.