Following on from Robert Pickerings F# introduction at Progressive.Net in London last week, I was inspired to try and do something with this powerful functional language.
As an exercise I though’t I’d port some old code I wrote in Haskell several years ago, a simple Caeser Cipher cracker.
A Caeser Cipher works by shifting each letter of the alphabet by n positions. A shift of 3 would encode “ABCD” as “DEFG”. Due to this simple linear transform (y = x + c), the Caeser Cipher is incredibly easy to crack with frequency analysis. By shifting the ciphertext by 1-25 positions and comparing the frequency of each letter in the resulting plaintext candidate to a table of English letter frequencies, it is possible to easily discover the original plain text (assuming there is sufficient data to make the expected freqency distributions).
Here’s the code!
Disclaimer: This is the first F# code I’ve ever written, so don’t count on it being remotely decent. Suggestions for improvements are more than welcome!
#light let alphabet = ['A'..'Z'] let getpos x xs = List.find_index ((=) x) xs let let2nat c = getpos c alphabet let nat2let i = alphabet.[i] let shift i a = nat2let ((let2nat a + i) % 26) let encode i s = new string(Seq.map (fun c -> shift i c) s |> Seq.to_array) let decode i = encode (26 - i) let count c s = Seq.filter ((=) c) s |> Seq.length let percent a b = (float a / float b) * 100. let freqs ws = [for x in alphabet do yield percent (count x ws) (Seq.length ws)] let table = [8.2; 1.5; 2.8; 4.3; 12.7; 2.2; 2.0; 6.1; 7.0; 0.2; 0.8; 4.0; 2.4; 6.7; 7.5; 1.9; 0.1; 6.0; 6.3; 9.1; 2.8; 1.0; 2.4; 0.2; 2.0; 0.1] let chisqr os es = let chied = [for x, y in Seq.zip os es do yield ((x - y) * (x - y)) / y] List.sum chied let crack ws = let wws = [for x in [0..25] do yield chisqr (freqs (decode x ws)) table] let n = getpos (Seq.min wws) wws decode n ws let ciphertext = encode 5 "THEQUICKBROWNFOXJUMPEDOVERTHELAZYDOG" let plaintext = crack ciphertext System.Console.WriteLine(ciphertext) System.Console.WriteLine(plaintext)