Programming the Vigenère cipher is my go-to problem when learning a new language. It’s only ever a few lines of code, but it’s a pleasant way of getting to grips with some of the basics of syntax. For the past few weeks I’ve been wrestling with Haskell, and I’ve now got to the stage where a Vigenère program is in fact pretty easy.
As you know, the Vigenère cipher works using a plaintext and a keyword, which is repeated as often as need be:
K E Y K E Y K E Y K E Y K E Y K E Y
The corresponding letters are added modulo 26 (using the values A=0, B=1, C=2, and on up to Z=25), then converted back to letters again. So for the example above, we have these corresponding values:
10 4 24 10 4 24 10 4 24 10 4 24 10 4 24 10 4 24
Adding modulo 26 and converting back to letters:
D L G C M Q D L C Z P Y S R R
gives us the ciphertext.
The Vigenère cipher is historically important as it is one of the first cryptosystems where a single letter may be encrypted to different characters in the ciphertext. For example, the two “S”s are encrypted to “C” and “Q”; the first and last “T”s are encrypted to “D” and “R”. For this reason the cipher was considered unbreakable – as indeed it was for a long time – and was known to the French as le chiffre indéchiffrable – the unbreakable cipher. It was broken in 1863. See the Wikipedia page for more history.
Suppose the length of the keyword is . Then the -th character of the plaintext will correspond to the character of the keyword (assuming a zero-based indexing). Thus the encryption can be defined as
However, encryption can also be done without knowing the length of the keyword, but by shifting the keyword each time – first letter to the end – and simply taking the left-most letter. Like this:
K E Y
so “T”+”K” (modulo 26) is the first encryption. Then we shift the keyword:
E Y K
and “H”+”E” (modulo 26) is the second encrypted letter. Shift again:
Y K E
for “I”+”Y”; shift again:
K E Y
for “S”+”K”. And so on.
This is almost trivial in Haskell. We need two extra functions from the module Data.Char: chr which gives the character corresponding to the ascii value, and ord which gives the ascii value of a character:
λ> chr 88
So here’s what might go into a little file called vigenere.hs:
vige :: [Char] -> [Char] -> [Char]
vige  k = 
vige p  = 
vige (p:ps) (k:ks) = (encode p k):(vige ps (ks++[k]))
encode a b = chr $ 65 + mod (ord a + ord b) 26
vigd :: [Char] -> [Char] -> [Char]
vigd  k = 
vigd p  = 
vigd (p:ps) (k:ks) = (decode p k):(vigd ps (ks++[k]))
decode a b = chr $ 65 + mod (ord a - ord b) 26
And a couple of tests: the example from above, and the one on the Wikipedia page:
λ> vige "ATTACKATDAWN" "LEMON"