Vigenère Cipher

The Vigenère cipher is a method of encrypting messages by using a series of different Caesar ciphers based on the letters of a particular keyword. The Vigenère cipher is more powerful than a single Caesar cipher and is much harder to crack.

A \(16^\text{th}\)-century French diplomat, Blaise de Vigenère, created a very simple cipher that is moderately difficult for any unintended parties to decipher. There are too many possible keys to brute-force, even if the key is known to come from a particular language. It cannot be broken with the word pattern attack that worked on the simple substitution cipher. It is thought to have remained unbroken until Charles Babbage, considered to be the father of computers, broke it in the \(19^\text{th}\) century.

Vigenère ciphertext is a combination of a Caesar shift combined with a keyword. The length of the keyword determines the number of different encryptions that are applied to the plaintext. For example, if the keyword is 4 characters in length, then the plaintext is divided into 4 subtexts and a separate Caesar shift is applied to each subtext depending on the value of the corresponding letter in the keyword. The cipher is polyalphabetic, which means that a character can be enciphered in different ways—for example, an "A" in one subtext could be encoded as a "T", and in another subtext it could be encoded as a "P". This interferes with frequency analysis, a method of breaking codes by looking at the most common characters and mapping them to the most common characters in the (non-encrypted) language.

\(\qquad\qquad~~\)

Vigenère substitution is based on the above table. The Vigenère cipher uses this table together with a keyword to encrypt a message.

All 26 possible Caesar ciphers are represented in the table (one per row), since each row displays the alphabet shifted by one more letter than the above row. The key letter is shown at the beginning of each row. The rest of the row shows the letters A to Z (in shifted order). Although there are 26 key rows shown, the encoder will only use as many rows (different alphabets) as there are unique letters in the key string.

The letters in the top row of the table represent the letters in a message. To encode the message, find the column headed by the letter to encode, find where it intersects with the row of the keyword letter that maps to the letter in the message. The letter at the intersection point will be the letter that the message letter is encoded as.

Suppose we wish to encrypt the plaintext message THE SUN AND THE MAN IN THE MOON ,
using the keyword KING.

Begin by writing the keyword, repeated as many times as necessary, above the plaintext message. To derive the ciphertext using the table above, for each letter in the plaintext, find 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:    KIN GKI NGK ING KIN GK ING KING
Plaintext:  THE SUN AND THE MAN IN THE MOON
Ciphertext: DPR YEV NTN BUK WIA OX BUK WWBT

To decrypt the text, find the cipher alphabet in the row of the keyword letter, then see the column of the cipher alphabet.

To decrypt the text:

Keyword:    KIN GKI NGK ING KIN GK ING KING
Ciphertext: DPR YEV NTN BUK WIA OX BUK WWBT
Plaintext:  THE SUN AND THE MAN IN THE MOON

Encrypt the following message: CRYPTOGRAPHY IS SUPER COOL ,
using the keyword MATH.

Show Answer

Keyword: MATHMATHMATH MA THMAT HMAT Plaintext: CRYPTOGRAPHY IS SUPER COOL Ciphertext: ORRWFOZYMPAF US LBBEK JAOE

To decrypt the text:

Keyword:    MATHMATHMATH MA THMAT HMAT 
Ciphertext: ORRWFOZYMPAF US LBBEK JAOE
Plaintext:  CRYPTOGRAPHY IS SUPER COOL

Here is an online Vigenère cipher that you can use to generate your own coded messages and check your answers.

The strength of the Vigenère cipher is that it is not susceptible to frequency analysis due to the fact that the cipher rotates through different shifts, so the same plaintext letter will not always be encrypted to the same ciphertext letter. For example, let’s say that “e” is the most common letter in English words. A codebreaker using frequency analysis may think that the most common letter in an encoded message likely corresponds to “e”. However, since a Vigenère cipher encodes the same letter in different ways, depending on the keyword, “e” could be encoded as many different letters, thus breaking the assumptions behind frequency analysis. As such, they were regarded by many as unbreakable for 300 years.

A Vigenère cipher is difficult to crack using brute-force because each letter in a message could be encoded as any of the \(26\) letters. Because the encoding of the message depends on the keyword used, a given message could be encoded in \(26^k\) ways, where \(k\) is the length of the keyword. For example, if we only know that a message is encoded with a word of 7 letters, then it could be encoded in \( 26^7 \approx 8 \) billion ways!^[1]

The primary weakness of the Vigenère cipher is the repeating nature of its key. If a cryptanalyst correctly guesses the length of the key, then the ciphertext can be treated as interwoven Caesar ciphers, which, individually, can be easily broken. For example, in the cryptogram above, the plaintext THE occurs twice in the message, and in both cases, it lines up perfectly with the first two letters of the keyword. Because of this, it produces the same ciphertext BUK.

Repetitions in the ciphertext indicate repetitions in the plaintext, and the space between such repetitions hint at the length of the keyword.

In fact, any message encrypted with a Vigènere cipher will produce many such repeated instances. Although not every repeated instance will be the result of the encryption of the same plaintext, many will be and this provides the basis for breaking the cipher. This method of analysis is called Kasiski examination.

Here is one way to implement a Vigenère cipher in Python.^[2]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

# Creates the base Alphabet which is used for finding preceeding characters from the ciphertext.
baseAlphabet = ('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 
'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z')

plainText = raw_input("Please enter the plain text")
key = raw_input("Please enter the key word")
keyList = []
keyLength = 0
while keyLength < len(plainText):
    # Adds the users entered key into a list character by character. 
    # Also makes the key the same length as plainText
    for char in key:
        if keyLength < len(plainText):
            keyList.append(str(char))
            keyLength = keyLength + 1

# The variable each processed letter is appended to
completeCipherText = [] 
# This is the value used to temporaily store the ciphertext character during the iteration
cipherCharIndexValue = 0
keyIncrement = 0

# Iterates through the plain text
for plainTextChar in plainText:
        # Adds the base alphabets index value of the key and the plain text char
        cipherCharIndexValue = baseAlphabet.index(keyList[keyIncrement]) + baseAlphabet.index(plainTextChar)
        while cipherCharIndexValue > 25:
             # makes the addition value under 26 as to not go out of range of base alphabet tuple
            cipherCharIndexValue = cipherCharIndexValue - 26 
         # appends the ciphertext character to the completeCipherText variable. 
         # The character is the index of the key + index of the       plainTextChar from baseAlphabet
        completeCipherText.append(baseAlphabet[cipherCharIndexValue])
         # Moves onto the next key
        keyIncrement = keyIncrement + 1
print ''.join(completeCipherText) # Makes the result a strings for printing to the console.                                  

1. Sweigart , A. THE VIGENÈRE CIPHER. Retrieved May 22, 2016, from https://inventwithpython.com/hacking/chapter19.html
2. Woolley, J. The Vigenère cipher in Python. Retrieved May 13, 2016, from http://jamesdotcom.com/?p=258