muonlab

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)

This produces:

YMJVZNHPGWTBSKTCOZRUJITAJWYMJQFEDITL
THEQUICKBROWNFOXJUMPEDOVERTHELAZYDOG