3 The Caesar Cipher | V'ir Tbg n Frperg This document as PDF | 5 An Unbreakable Cipher |
So far, it seems we've gone in the wrong direction: from the poorsecurity offered by the general substitution cipher to nearly nosecurity offered by a shift cipher. But, taking a step backward willallow us to leap forward.
In the Vigenère Cipher, we choose a word or phrase as our encryptionkey. We then convert it to a sequence of numbers (again usinga=0, b=1, ..., z=25), and apply a differentshift to the plaintext corresponding to the letters in the keyword.When we use up the shifts from the keyword, we repeat itagain.
This is probably best understood via an example. Suppose we choosejasmine as our key, and want to encrypt the phrase weare getting hungry.Translating jasmine to its numerical equivalents gives thesequence of shifts 9, 0, 18, 12, 8, 13, 4. So we work asfollows:
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 ofplaintext could be any one of several ciphertexts. For example, in the example above, e becomes E, M, orI, and the two Es in the ciphertext come from an eor an r.
The Vigenère cipher is significantly harder to break than a Caesarcipher. For about 300 years, it was believed to be unbreakable,although Charles Babbage and Friedrich Kasiski independentlydetermined a method of breaking it in the middle of the nineteenthcentury. The method uses repeated patterns in the text todetermine the length of the key. Once it is known that the key is,say, 8 characters long, frequency analysis can be applied to every 8thletter to determine the plaintext. This method is called Kasiskiexamination (although it was first discovered by Babbage).Despite the fact that the method of breaking the Vigenére cipher hadbeen published 50 years earlier, the cipher was widely held to be unbreakable until the 1920s, being described as ``impossible of translation'' in an articleappearing in Scientific American in 1917.We should remark that one can implement this cipher using a tabula recta, which is a 26 x 26 table listing all theshifts corresponding to each letter of the key. It is really just anaddition 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 themodular addition; this is how people in the sixteenth century used thecipher. However, the underlying mathematical structure is hidden, which isa disadvantage for our purposes.
The Vigenère cipher is named after Blaise de Vigenère, a sixteenthcentury diplomat and cryptographer, although the cipher was invented byGiovan Batista Belaso in 1553. Vigenère actually invented adifferent cipher, which we will now discuss.
The cipher Vigenère invented is a little harder to crack than theone that bears his name. In this cipher, rather than repeating thekey, one begins with a key, and then appends the text itself to getthe shifts to apply. This is a type of autokey cipher, becausethe 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 autokeycipher. 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 bookin order to determine the sequence of shifts. The location of thestart of the passage serves as the key.For example, the key might be given as 123:5, and then cryptographerturns 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 sourcebooks.
While these methods do away with the problem of repeating shifts thathinder the Vigenère cipher, frequency analysis and similartechniques can still be employed. This is because certain letters(specifically e, t, o, etc.) will still occurmore frequently in both the text and the key. Given a long sample ofciphertext, 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.
3 The Caesar Cipher | V'ir Tbg n Frperg This document as PDF | 5 An Unbreakable Cipher |
Scott Sutherland
2005-10-26