CP3404 Decrypting the Vigenère Cipher: A Cryptanalysis Report and Educational Tutorial, Singapore

Background

Cryptanalysis of an information system is the study of mathematical techniques for attempting to defeat information security services. A cryptographic system is said to be breakable if a third party (i.e., cryptanalyst), without prior knowledge of the key, can systematically recover plaintext from corresponding ciphertext within an appropriate timeframe.

Julius Caessar used a cipher which moved each letter of the alphabet to the letter three to the left in the predetermined order of the letters of the alphabet. Figure 1 shows the original English alphabet and the corresponding cryptogram alphabet in Caesar cipher:

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
d e f g h i j k l m n o p q r s t u v w x y z a b c
Figure 1: English alphabet letter and their corresponding cryptograms in the Caesar cipher.

To use mathematical notations, lets convert the letters of the alphabet to integers. The most natural conversion is to assign to each letter an integer which indicates the position of the letter in the alphabet. That is, assign 0, 1, …, 24, 25 to a, b, …, y, z, respectively. Using this conversion, Caesar cipher can be expressed as:

C = E_k(M) = M + 3 (mod 26)

where ‘C’ is the cryptogram, ‘E’ is the encryption algorithm, ‘k’ is the key, ‘M’ is the message/plaintext (one may replace integer 3 by letter ‘d’).

Caesar cipher is from the family of shift ciphers, in which the cryptogram is a shifted version of the original alphabet. Cryptanalysis of the Caesar (and all shift ciphers) is easy, because there are only 26 possible keys/shifts.

Vigenére Cipher

In Vigenére cipher the key is more than one letter. That is, Vigenére cipher can be considered as a combination of n shift ciphers, where n is the key-length (i.e., the number of letters in the keyword).

Consider an example where the message/plaintext is ‘individual character’ and the keyword is ‘host’. Vigenére cipher encrypts the message as follows:

Plaintext i n d i v i d u a l c h a r a c t e r
Keyword h o s t h o s t h o s t h o s t h o s
Cryptogram p b v b c w v n h z u a h f s v a s j

That is, the first four letters of the cryptogram are computed as:
‘i’ + ‘h’ = 8 + 7 = 15 (mod 26) i.e., p
‘n’ + ‘o’ = 13 + 14 = 1 (mod 26) i.e., b
‘d’ + ‘s’ = 3 + 18 = 21 (mod 26) i.e., v
‘i’ + ‘t’ = 8 + 19 = 1 (mod 26) i.e., b

Since the plaintext is longer than the keyword, keyword is repeated until all letters of the plaintext are encrypted. As it can be seen, a particular letter of the plaintext may be encrypted with different letters from the keyword. For example, the first occurrence of letter ‘i’ from the plaintext is encrypted with ‘h’, where its second and third occurrences are encrypted with the letters ‘t’ and ‘o’ respectively. That is, Vigenére cipher is a polyalphabetic substitution cipher.

To break a polyalphabetic substitution cipher, the cryptanalyst must first determine the key-length of the cipher. This can be done using Kassiski method. The Kassiski method uses repetitions of patterns in the ciphertext to make a good guess about the key-length. For example, suppose the plaintext ‘to be or not to be’ has been enciphered using the key ‘now’, producing the ciphertext below:

Plaintext t o b e o r n o t t o b e
Keyword n o w n o w n o w n o w n
Cryptogram g c x r c n a c p g c x r

In this cryptogram, a repeated pattern is g c x r (i.e., g c x r c n a c p g c x r), where the distance between these repetitions (i.e., the number of characters form the first letter of the pattern in its first occurrence to the first letter of its second occurrence) is 9. This could be the sign in which the same letters from plaintext is encrypted with the same letters from the keyword. Since in Vigenére cipher the keyword is repeated, the key-length is probably 9 or a divisor of 9 (i.e., 3, because 9 has no other divisor). Note that for longer cryptograms, we can look for multiple repeating patterns of different characters and calculate the distances between these repeating patterns. The greatest common divisor of those distances may give an indication of the possible key-length.

Once we have the key length (k), we split the cryptogram into k cryptograms. For the current example, assuming that the key length is 3, we split the cryptogram into three cryptograms. That is, the 1^st, 4^th, 7^th, … characters of the cryptogram are the result of encrypting the 1^st, 4^th, 7^th, … characters of the plaintext with the first letter of the keyword (in other words, they are shifted with the same number, as in the Caesar cipher). Similarly, the 2^nd, 5^th, 8^th, … characters are the result of encrypting the corresponding letters in the plaintext with the second letter of the key, and the same for the third. That is, this Vigenére cipher is a combination of 3 Caesar ciphers, where the cryptogram of each Caesar cipher is given as below:

Cryptogram 1: g r a g r
Cryptogram 2: c c c c
Cryptogram 3: x n p r

To break each of these Caesar ciphers, we can use the letter frequency in the English text. As shown in Figure 2, ‘e’ is the most common letter used in English texts. That is:

In Cryptogram 1, we can guess that ‘g’ or ‘r’ could be the corresponding letter to ‘e’ in the plaintext.
If ‘g’ corresponds to ‘e’, then the first letter of the key should be ‘g’ – ‘e’ = 6 – 4 = 2, which is ‘c’.
If ‘r’ corresponds to ‘e’, then the first letter of the key should be ‘r’ – ‘e’ = 17 – 4 = 13, which is ‘n’.

In Cryptogram 2, we can guess that ‘c’ is the corresponding letter to ‘e’ in the plaintext.
If ‘c’ corresponds to ‘e’, then the second letter of the key could be ‘c’ – ‘e’ = 2 – 4 = -2 = 24 (calculate mod 26), which is ‘y’.

In Cryptogram 3, each character appears only once, and thus letter frequency does not work.

Remark: This example is simply to show the mechanism of the Kassiski attack. The attack is very effective for large cryptograms (e.g., the size of the cryptograms given in this assignment). You should always consider other potential letters based on letter frequency to determine the correct letter in the keyword (i.e., the most repeated letters won’t always be ‘e’).

Figure 2: Letter frequencies in English texts.

Appendix 2: Ciphertexts

The following are 10 cryptograms that are created by the Vigenere cipher, where the plaintext is complete English text, and the keyword is a meaningful English word. You are required to decipher the cryptogram that matches with your Student ID.

Cryptogram for whom their Student-ID is XXXXXXX7