previous 3 The Caesar Cipher up V'ir Tbg n Frperg    This document as PDF next 5 An Unbreakable Cipher


4 Many Caesars: the Vigenère Cipher

So far, it seems we've gone in the wrong direction: from the poor security offered by the general substitution cipher to nearly no security offered by a shift cipher. But, taking a step backward will allow us to leap forward.

In the Vigenère Cipher, we choose a word or phrase as our encryption key. We then convert it to a sequence of numbers (again using a=0, b=1, ..., z=25), and apply a different shift to the plaintext corresponding to the letters in the keyword. When we use up the shifts from the keyword, we repeat it again.

This is probably best understood via an example. Suppose we choose jasmine as our key, and want to encrypt the phrase we are getting hungry. Translating jasmine to its numerical equivalents gives the sequence of shifts 9, 0, 18, 12, 8, 13, 4. So we work as follows:

  w e a r e g e t t i n g h u n g r y  
  22 4 0 17 4 6 4 19 19 8 13 6 7 20 13 6 17 24  
+ 9 0 18 12 8 13 4 9 0 18 12 8 13 8 4 9 0 18  
= 5 4 18 3 12 19 8 2 19 0 25 14 20 2 17 15 17 16  
  F E A D M T I C T A Z O U C R P R Q  

Depending on where it falls in the message, each character of plaintext could be any one of several ciphertexts. For example, in the example above, e becomes E, M, or I, and the two Es in the ciphertext come from an e or an r.

The Vigenère cipher is significantly harder to break than a Caesar cipher. For about 300 years, it was believed to be unbreakable, although Charles Babbage and Friedrich Kasiski independently determined a method of breaking it in the middle of the nineteenth century. The method uses repeated patterns in the text to determine the length of the key. Once it is known that the key is, say, 8 characters long, frequency analysis can be applied to every 8th letter to determine the plaintext. This method is called Kasiski examination (although it was first discovered by Babbage). Despite the fact that the method of breaking the Vigenére cipher had been published 50 years earlier, the cipher was widely held to be unbreakable until the 1920s, being described as ``impossible of translation'' in an article appearing in Scientific American in 1917.


Table 2: A tabula recta
\begin{floatingtable}{\ttfamily\tiny
\begin{tabular*}{42em}
{@{\extracolsep{-.8e...
...&F&G&H&I&J&K&L&M&N&O&P&Q&R&S&T&U&V&W&X&Y\\
\end{tabular*}}\end{floatingtable}


We should remark that one can implement this cipher using a tabula recta, which is a 26 x 26 table listing all the shifts corresponding to each letter of the key. It is really just an addition table for letters. To use the tabula recta, the plaintext letter gives the row, and the key letter gives the column. The letter of ciphertext is then found where the two intersect. Using such a table, one doesn't need to do the numerical conversion and the modular addition; this is how people in the sixteenth century used the cipher. However, the underlying mathematical structure is hidden, which is a disadvantage for our purposes.


The Vigenère cipher is named after Blaise de Vigenère, a sixteenth century diplomat and cryptographer, although the cipher was invented by Giovan Batista Belaso in 1553. Vigenère actually invented a different cipher, which we will now discuss.

The cipher Vigenère invented is a little harder to crack than the one that bears his name. In this cipher, rather than repeating the key, one begins with a key, and then appends the text itself to get the shifts to apply. This is a type of autokey cipher, because the key is (semi-)automatically generated by the message itself.

As an example, we will use the same plaintext ( we are getting hungry) and initial key ( jasmine), and apply Vigenère's autokey cipher. The autokey will then be jasminewearegettin, giving us the encryption below.8

  w e a r e g e t t i n g h u n g r y  
  22 4 0 17 4 6 4 19 19 8 13 6 7 20 13 6 17 24  
+ 9 0 18 12 8 13 4 22 4 0 17 4 6 4 19 19 8 13  
= 5 4 18 3 12 19 8 15 23 8 4 10 13 24 6 25 25 11  
  F E A D M T I P X I E K N Y G Z Z L  

Another variation on these same ideas is to use a passage from a book in order to determine the sequence of shifts. The location of the start of the passage serves as the key. For example, the key might be given as 123:5, and then cryptographer turns to page 123 and begins with the 5th word to extract the key. The Bible and the works of Shakespeare were both popular to use as source books.

While these methods do away with the problem of repeating shifts that hinder the Vigenère cipher, frequency analysis and similar techniques can still be employed. This is because certain letters (specifically e, t, o, etc.) will still occur more frequently in both the text and the key. Given a long sample of ciphertext, a competent cryptographer can break both of these codes.



Footnotes

... below.8
Some accounts append the ciphertext to the initial key rather than the plaintext as we do here. In both cases, there is a serious drawback to this cipher: if an error is made in enciphering even one letter, it will propagate throughout the remainder of the text.
previous 3 The Caesar Cipher up V'ir Tbg n Frperg    This document as PDF next 5 An Unbreakable Cipher
Scott Sutherland
2005-10-26