Section 3.1 Vigenère Encryption
A polyalphabetic cipher is a letter for letter substitution but the same letter in the plaintext may get encrypted as a different ciphertext letter depending on its location in the plaintext according to the use of a key. That is, A may get encrypted as K in one location, but get encrypted as W in another location. Our first look at a polyalphabetic cipher will be the Vigenère cipher. This cipher is named after Blase de Vigenère who published an article on polyalphabetic encryption called Traicté des chiffres, ou secrètes manières d'escrire in 1586. Curiously, he was not the first to propose a polyalphabetic system nor did he propose the specific system that bears his name. However, the name has stuck nonetheless.
The idea of a Vigenère cipher is to use a keyword to determine a different monoalphabetic cipher to be used with different parts of the text. In particular, this technique uses a keyword to specify multiple shift ciphers. Frequently this is implemented with the use of a Vigenère square. However, it can also be implemented with a cipher disk (as in the cipher disk used by the Confederacy in Figure 2.1.4) where the setting is changed for each letter of the key. A Vigenère square is a 26 × 26 square which contains all 26 shifts of the alphabet. A message is encrypted by first finding the plaintext letter in the top row of the square. This gives the column for the ciphertext letter. Secondly, the keyword letter is found in the the leftmost column. This gives the row of the ciphertext letter. Thus the ciphertext letter is the letter in the intersection of the column containing the plaintext letter and the row containing the keyword letter.
Example 3.1.3.
To encrypt the plaintext message HELLO using the keyword KEY we write each letter of the keyword under the text to tell us how to encrypt each letter of the plaintext. We first find the plaintext letter in the top row of the square. For the plaintext letter H, this gives us the teal column in Figure 3.1.4. Then we find the keyword letter in the first column of the square. For the keyword letter K, this gives us the pink row in Figure 3.1.4. Then to find the ciphertext letter, we find the letter in the Vigenère square that is in the same column as the plaintext letter and the same row as the keyword letter. For the first letter, H is the 8th column (of the first row) and K is the 11th row (of the first column). The letter that is in the 8th column and the 11th row is is R, so that is the ciphertext letter. That is, the purple R is the letter in the intersection of the teal column and pink row in Figure 3.1.4. We repeat similarly for each letter of the plaintext.
| PT: | H | E | L | L | O |
| K: | K | E | Y | K | E |
| CT: | R | I | J | V | S |
Note that the two Ls in the word HELLO do not get encrypted the same way each time. One L gets encrypted as a J and the second L gets encrypted as a V. This is a major difference between polyalphabetic and monoalphabetic ciphers. This difference means that frequency analysis will not help us to solve Vigenère ciphers.
To decrypt a message we do the process in reverse. First, find the keyword letter in the leftmost column. Then find the ciphertext letter in the same row as the keyword letter. Lastly, determine the plaintext letter by finding the letter in the first row in the column corresponding to the ciphertext letter.
Example 3.1.5.
Decrypt ciphertext OAM with the keyword MAT. In this case we first find the row of the keyword letter. For the first keyword letter M, we have the pink row in Figure 3.1.6. Next we find the column of the ciphertext letter in the row of the keyword letter. For the first ciphertext letter O, we have the teal column in Figure 3.1.6. The plaintext letter will be the letter in the first row that is in the column of the ciphertext letter. We see that we get the purple C in Figure 3.1.6 as the first letter of the plaintext.
| CT: | O | A | M |
| K: | M | A | T |
| PT: | C | A | T |
If we know the plaintext and ciphertext and want to find the key, we use a similar process. However, this time we begin by finding the plaintext letter in the top row of the Vigenère square and the ciphertext letter in the same column as the plaintext letter. Then we find the keyword letter by reading off the letter in the left most column that is in the same row as the ciphertext.
Example 3.1.7.
If the plaintext message, DOG, corresponds with the ciphertext message, JOY, find the keyword that was used. Note that the keyword will not necessarily be a word in English. In this case, we first find the plaintext letter in the first row and identify its column. For plaintext letter D we have the teal column in Figure 3.1.8. Next we find the ciphertext letter in that column and identify its row. For ciphertext letter J we have the pink row in Figure 3.1.8. Lastly, we find the keyword letter in the first column that is in the same row as the ciphertext letter. We get the purple G in Figure 3.1.8 as the first letter of the keyword.
| PT: | D | O | G |
| CT: | J | O | Y |
| K: | G | A | S |
Investigation Time!
Time for you to explore the Vigenère cipher in Investigation: Using the Vigenère Square.
The Vigenère cipher was used extensively in the 1700's and 1800's, and at one time was known as le chiffre indéchiffrable. As is the case with most encryption systems, eventually weaknesses were discovered and it became possible to break messages enciphered in this system. To explore how these weaknesses were discovered, we first turn to a related question. How might we determine if a message is monoalphabetic or polyalphabetic? To do this we will explore a concept called the Index of Coincidence which is the probability that two letters picked at random from the ciphertext are identical. Thus, we will need a small excursion into topics in probability before we can answer either of those questions.