Tuesday, April 21, 2015

Encryption 101: The Vigenère cipher

The Vigenère cipher (as it is currently known) was created by Blaise de Vigenère in 1585. However, it is worth mentioning that the cipher has undergone many reinventions over time and its original method is actually believed to have been created by Giovan Battista Bellaso, who first mentioned it in his book ‘La cifra del. Sig. Giovan Battista Bellaso’ in 1553.

A solution to frequency analysis

As you might already know, particularly if you’ve read any of the previous entries in the Encryption 101 series, most of the ciphers we’ve looked at up until now were vulnerable to the cryptanalysis method known as ‘letter frequency analysis’.

The Vigenère cipher, however, is a polyalphabetic substitution cipher and offers some defence against letter frequency analysis. In essence, while the functions of this cipher are very similar to that of the monoalphabetic substitution ciphers that we’ve looked at before, rather than using a single alphabet when encrypting information, we make use of multiple alphabets – 26 of them to be precise!

Vigenère square

Creating the square is fairly simple. On the top line, write out the alphabet going from A to Z. On the next line, move every letter one space to the left, wrapping any over flow round to the end of the row. Repeat this for the remaining letters until you have the square shown below.


Encryption

In order to encrypt the message, first of all a key has to be agreed upon. In this example, we’ll be using ‘DRAX’. Next, the key is repeated until it is the same length as the length of the message being encrypted – for example:

Key: DRAX 

Plaintext: Nothing goes over my head. My reflexes are too fast, I would catch it.

Adjusted Key: DRAX DRAXDRAXDRAXDRAXDRAXDRAXDRAXDRAXDRAXDRAXDRAXDRAXDR


Ciphertext: Qfteleg drvs lyvr jb yexg. Dy ohwlbavs xuv tlr wapw, Z wlxcd zdkce lk.

To encrypt, we now take the first letter of the plaintext and pair it up with the first letter of the key string. One is placed along the top row and one is placed in the first column. The letter at the point where they intersect will be the first letter of the ciphertext, in this case: 


Decryption

To decrypt a piece of ciphertext, we follow much the same method used to encrypt the message. We place the first letter of the key in either the top row or the first column. Then, we follow the line along until we hit the first letter of the ciphertext: ‘Q’. The letter at the top of the column or row where the intersection occurs is the first letter of the recovered plaintext.



Weaknesses

By using multiple different alphabets, we’re now slowly gaining some defence against letter frequency analysis since the letter ‘N’ won’t always encrypt to the letter ‘Q’. However, that’s not to say the cipher is bulletproof.

The main weakness of this cipher comes down to the length of the key used. Since we used a four letter key in our example, we had to repeat the key multiple times to ensure it matched the length of our message (54 letters). This use of a repeating key will inevitably result in some patterns occurring in our resultant ciphertext and using these patterns, the likely length of the key can eventually be reasoned.

One such method that can be used when trying to deduce the length of the key is known as the ‘Index of coincidence’. Like letter frequency analysis, it is focused on looking at ‘normal’ patterns that occur in texts and how the ciphertext deviates from these patterns.

Once we know the key length, the ciphertext can be rearranged so that it is written in a series of columns, as shown below. We then know that each column was encrypted using the same key – in other words, a Caesar cipher was used. With this information, our old friend frequency analysis can be used to help reconstruct the key.


Even with this weakness, however, the use of multiple alphabets proved an effectual method at protecting information for over two centuries, earning the cypher the name of ‘Le Chiffre Undechiffrable’ or in English: ‘The Unbreakable Cipher’. It was finally defeated in 1854 by an English cryptographer, Charles Babbage – who required a mix of cunning, intuition and amazing cryptographic genius to finally break the unbreakable cipher.

A glimpse of perfection

The Vigenère cipher also gave us perhaps our first glimpse of ‘perfect’ cryptography – that is to say, the information is ‘theoretically secure’. If we had a 250 character long message with a 250 character long random key, then there would be no clues as to what the ciphertext is or what key was used. Perhaps even more incredible is this 250 character ciphertext can be decrypted into any 250 character plaintext message, using any 250 character key – so how do we know which message was the real message?!

This ‘theoretically secure’ idea will be explored more when we take a look at the one-time pad cipher, which has seen use in World War II and in an early version of the ‘Red Phone’ that connected offices of the President of the United States to the President of the Soviet Union.

No comments:

Post a Comment