Limited Entropy Dot Com Not so random thoughts on security featured by Eloi Sanfèlix

Crypto Series: Vigenère Cipher

Today we're gonna go a little further on the study of classical ciphers. We're gonna see an evolution of simple substitution ciphers known as Vigenère cipher, how it works and cryptanalysis methods that we can apply.

Vigènere Cipher

This cipher is named after the Frenchman Blaise de Vigènere, to whom it was wrongly attributed in the 19th century. Actually it's a quite simple cipher combining several Caesar's ciphers according to a secret key. An example will help to understand it.

If the key is abcs, then the first letter is encrypted shifting it 0 times, second letter 1 time, third letter 2 times, fourth letter 3 times, and then we start again with 0 times. So, the key is repeated as many times as needed to encrypt the complete plaintext. This operation can be seen as a two entries subtitution table (tabula recta or Vigenère's table):

Vigènere table

Using this table, the row corresponds to the plaintext letter to encrypt and the column corresponding to the key letter will give us the resulting cryptogram letter. To decrypt, we should place ourselves in the row corresponding to the key letter, move right up to the cryptogram's letter column, and then move upwards to know which plaintext letter corresponds looking at the column header.

Let's take a look at an example.We want to encrypt the word WADALBERTIA with the key ERP, so we write down the letter with the key below, repeated as many times as needed to reach the word's number of characters:

WADALBERTIA

ERPERPERPER

In order to obtain our result using the table, we go to column W and go down till row E. This gives us our first cryptogram letter, A. Then we repeat the operation with column A and row R, which brings us R. We repeat this process with the remaining letters and finally obtain ARSECQIIIMR.

For decryption, we would go to the key's letter, for instance E. Then we would move right through the columns to find an A, and then we would move up to the header to see that this is encrypted labeled as letter W. Continuing until the end, we would get back our input plaintext.

Attacking Vigenère's cipher

Now that we know how it works, we can proceed to see how we could break this cipher. It's clear that the simple method applied to Caesar's cipher is not useful here, since each letter is encrypted independently of the previous one. However, if we have a key of length L, every L letters the sequence is repeated. Thus, we have L different Caesar's ciphers and we could break them as we learnt last time.

To do so, we need to determine L. Therefore, Vigenère's cipher cryptanalisis will focus on methods to find out how long is the key, so that we can analyse later on the different Caesar ciphers. We will study two different methods to obtain it.

Kasiski's method

This method is based on looking for repeated patterns in the cryptogram. Kasiski observed that for a given pair of repeated fragments in the plaintext to be encrypted two times in the same way, the distance between them must be a multiple of the key length. Then, each letter of the repeated string will be encrypted with the same part of the key. Let's see an example taken from Wikipedia:

abcdeabcdeabcdeabcdeabcdeabcdeabc
crypto is short for cryptography.

In this case, we can see that the string crypt would be encrypted both times by abcde. This is due to the fact that the key is 5 characters long (abcde) and the distance between the two appearances of crypto is 20 characters ( 4 times 5). In case the distance was not a multiple of 5, this wouldn't occur.

Therefore, in this case we could sey that the key length should be one of the divisors of 20: 1,2,4,10 and 20. However, if we encounter any other repetition, then we can reduce the search space to the common divisors of both distances. With several repetitions, it could be possible to reduce the number of candidates to one and therefore discover the key length.

Obviously, it might be that some of the repetitions are just coincidence. Thus, it is possible that the different distances have a greatest common divisor of 1, which means that they only have 1 as a common divisor. This would lead us to discard some of the repetitions found; but following this method we would be able to reduce the key length to a very few candidates. Then all what is needed is to analyze the different Caesar's ciphers that form the Vigènere cipher.

Next post

We're gonna stop here for now, cause I've had the post half-way written for two weeks and didn't have time to finish it... Next time we'll revisit Vigenère's cipher with another method to obtain the key length and some examples.

I hope you're enjoying it 🙂