Introduction

Vigenère’s cipher was invented in the 16^th century and was considered secure until well into the twentieth century despite attacks being developed in the 19^th century by the British mathematician Charles Babbage and the German cryptographer Friedrich Kasiski.

A cipher is an encryption system that maps a character to some other character unlike a code which is a mapping between words. Vigenère’s cipher is an example of a shift cipher wherein each letter of the plaintext is ‘shifted’ by some value to become a different letter via the encryption process. This ultimately yields the ciphertext which can then be sent as a secure message. That is, in a shift cipher, each letter in the plaintext is linearly mapped to some other character for use in the ciphertext.

Encryption

The steps of Vigenère’s cipher are as follows:

1. Choose a keyword or a key length and subsequently a set of characters equal to that length.
2. Convert both the plaintext and key to integers based upon the alphabetic position of the letters (e.g. A = 0, B = 1, …, Z = 25).
3. Repeat the key if necessary so that it is at least as long as the plaintext to be sent.
4. Add the values of the (repeated) key to the values of the plain text and take the modulus of them mod 26.*
5. Convert the numbers back to letters.

* Modulus 26 (often shortened to mod 26) means take the remainder of the value when divided by 26. Values from 0 to 25 remain unchanged but values beyond 25 are reduced to values between 0 and 25. For example 40 (mod 26) ≡ 14 since 40 ÷ 26 = 1 remainder 14.

26 is used because this is the number of letters in the English alphabet and hence its use ensures that we always have a value between 0 and 25 which can then be mapped back to a letter.

Let’s try an example using VECTOR as our key:

Plaintext:  THISISATEST → 19 07 08 20 08 20 00 19 04 20 19
Key:        VECTORVECTO → 21 04 02 19 14 17 21 04 02 19 14
                          ————————————————————————————————
            +             40 11 10 39 22 37 21 23 06 39 33
            (mod 26)      14 11 10 13 22 11 21 23 06 13 07
Ciphertext:               O  L  K  N  W  L  V  X  G  N  H 

This encryption has rendered the original plaintext THISISATEST to the ciphertext OLKNWLVXGNH simply by shifting each letter by its corresponding letter in the key VECTOR.

Decryption

To decrypt ciphertext encrypted using Vigenère’s cipher one must know the key. From here getting back to the original plaintext message is relatively simple. Do the reverse of the encryption algorithm; that is take the value of the corresponding letter of the key from the values of the letters of ciphertext and convert back to the English alphabet.

The decryption algorithm therefore follows the steps below:

1. Convert both the ciphertext and the known key to integers based upon the alphabetic position of the letters (e.g. A = 0, B = 1, …, Z = 25).
2. Repeat the key if necessary so that it is at least as long as the ciphertext received.
3. Subtract the values of the (repeated) key from the corresponding values of the ciphertext and take the modulus of them mod 26.
4. Convert the numbers back to letters and you have the original message.

Let us now consider an example of decryption using our previous encrypted message as an example. If you were to receive the ciphertext from our earlier encryption: OLKNWLVXGNH. You would decrypt it as follows:

Ciphertext:  OLKNWLVXGNH → 14 11 10 13 22 11 21 23 06 13 07
Key:         VECTORVECTO → 21 04 02 19 14 17 21 04 02 19 14
                           ————————————————————————————————
             -             -7 07 08 -6 08 -6 00 19 04 -6 -7
             (mod 26)      19 07 08 20 08 20 00 19 04 20 19
Plaintext:                 T  H  I  S  I  S  A  T  E  S  T 

Shared secret

The successful use of Vigenère’s cipher is dependent on the same key being known by the sender of the encrypted message and the receiver. This is why the key is often known as a shared secret. If outsiders know the key then they will be able to intercept messages and decrypt them rendering the encryption useless.

Attacks on Vigenère’s cipher

The security of this system depends on neither the keyword nor its length being known to outsiders.

There are several types of attacks one often considers in cryptography. Most common are known plaintext attacks, where the attacker can see the plaintext before encryption and receives the ciphertext, chosen plaintext attacks where the attacker is able to choose the plaintext sent to the encryption algorithm and receives the corresponding ciphertext and ciphertext only attacks where only the intercepted ciphertext is known to attackers.

Chosen plaintext attack

In the case of Vigenère’s cipher getting the key under a chosen plaintext attack is simple. One simply chooses plaintext of AAAAAA… and then receives the key repeated. The repetition can be noted and then used to find the key.

Known plaintext attack

The plaintext can be ‘subtracted’ from the ciphertext modulo 26 and again the repeating key will be revealed.

Ciphertext only

Alternatively with enough ciphertext letter frequency attacks can be undertaken. This becomes a brute force attack as each key length must be tried but put simply one takes the ciphertext and calculates letter frequencies for each n^th letter. Knowing the frequency of letters in written English with enough text the value of n for which the frequency values of letters in the ciphertext match the frequency values of letters in English will be the key length. Then the letters of the key can be found my mapping ciphertext letter frequencies for every n^th letter to the English letters whose frequencies are known. This type of attack assumes that the initial language of the plaintext is known.

A more approximate yet faster way of deducing the key length is to write the ciphertext down several times and each time shift the ciphertext by some number of columns as demonstrated below.

O L K N W L V X G N H
  O L K N W L V X G N H
    O L K N W L V X G N H

For each shift number the number of matches should be counted. Where the number of matching values between the initial ciphertext and the shifted ciphertext reaches its maximum this is the most probable value for the key length. In our case there are no matches for the 1 and 2 character shifts shown. This technique is not effective here because our ciphertext sample is very small.

The reason why the ‘shifting’ technique works in finding the key length is a little more involved than is fitting for this overview of Vigenère’s cipher however a full explanation is given in the textbook “Introduction to Cryptography with Coding Theory” by Wade Trappe and Laurence C. Washington widely available online as a free PDF.

Conclusion

In summary, Vigenère’s cipher is a shift cipher based on the use of a key word or phrase for encryption. It works by ‘adding’ the key to the plaintext modulo 26 and thereby returning the encrypted text or ciphertext. This cipher works requires that neither the key nor its length is known to attackers. It is also vulnerable to letter frequency attacks. The most secure implementation would use a long key which is not a known English word to send only short messages. This avoids brute force attacks of common word keys and prevents enough cipher text to be collected for a letter frequency attack to be undertaken.