Vigenère Cipher
Previously, I talked about a mono-alphabetic cipher, and showed how it might be broken. How can we improve upon this?
The idea
We can use a poly-alphabetic cipher, where each letter is enciphered differently. This means that even if you have a good guess at part of a message, the rest is encoded differently.
Using the key ‘LEMON’, the phrase ‘MEET AT MIDNIGHT NEAR THE FOUNTAIN’ becomes ‘XIQHN EQURA TKTHA PEDHU PJAIA EEUB’
Notice that MEET becomes XIQH - the two Es are different. At the end, FOUNTAIN becomes JAIAEEUB - so one A represents O and the other N, one E represents T and the other A.
This makes it MUCH harder to work out what is going on.
How does it work?
Essentially, we line up the message with a repeating key, encoding it letter by letter using the repeating key
Vigenère Example - Image credit: me
In order to encode it letter by letter, we can use a lookup table like the one below. Find the message letter along the top, and the key letter along the side. This defines a row and column, and lets the encrypted letter be read off.
Enciphering with Vigenère
To undo this, we reverse the process, start with the key letter, look along until you get the enciphered letter, then go up to the first row to get the message letter.
You could also write some code to do this, here is a spreadsheet example written in numbers - the formula is in the third line. The numbers are about shifting the ascii code for the letter down to the 0 to 25 range, and then back again.
Essentially, in cell A7, we get the ascii code for A5 and A6, add them and subtract 130 (twice 65, the ascii code for A). We them divide by 26 and find the remainder with the mod function. Thus we have a result that must be in the range 0 to 25. Adding 65 puts us back in the ascii range for capital letters, and we then convert back into text with char.
This formula in A7 is copied to the right.
Notes
A key like AAAAAA does nothing to the message, and indeed, any key with just one letter reverts to a Caesar shift.
Short keys are not much better than monoalphabets.
If you encode twice, with keys whose lengths are not co-prime is a waste of time. I.e a key with six letters and a key with twelve letters is just the same as a key with 12 letters.
However, a key with seven letters and a key with eleven letters does not repeat for 77 characters (it is not as strong as a 77 character key though, far from it).
Longer keys are more secure - and if the key is gibberish and as long as the message, you have a one-time-pad. This is totally unbreakable if you have a secure way to agree on a one time pad ahead of time, and you never re-use it.
If the key is shorter than the message, and part of the key is recovered, it might be possible to use the partially decrypted message to allow educated guesses to be made on other parts of the communication, and therefore work out what the key must have been.
Other Posts on this topic
All Cryptography Posts
