random .NET and web development musings

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

8 COMMENTS
JaneRadriges
June 14, 2009
ad

I really like your post. Does it copyright protected?

June 14, 2009
ad

You can do what you like with it, its just a quick experiment I threw together. What are you planning on doing with it?

Bill Bartmann
September 2, 2009
ad

Cool site, love the info.

Tony Brown
September 24, 2009
ad

I don’t know If I said it already but …This blog rocks! I gotta say, that I read a lot of blogs on a daily basis and for the most part, people lack substance but, I just wanted to make a quick comment to say I’m glad I found your blog. Thanks, :)

A definite great read..Tony Brown

Tnelson
September 25, 2009
ad

Hey, I found your blog in a new directory of blogs. I dont know how your blog came up, must have been a typo, anyway cool blog, I bookmarked you. :)

Donnieboy
October 12, 2009
ad

Just wanted to drop you a line to say, I enjoy reading your site. I thought about starting a blog myself but don’t have the time.
Oh well maybe one day…. :)

Illeteoffisee
December 12, 2009
ad

Excuse me for being Off-Topic … what WordPress theme do you use? It’s looking awesome!!

December 14, 2009
ad

see the link in the footer

Sorry, the comment form is closed at this time.