Project Euler Problem #59

November 7, 2009

Read the details of the problem here

Summary

Using a brute force attack, can you decrypt the cipher using XOR encryption?

Solution

I actually got lucky with this one. The clue was that it contained English text, so the most common character was likely to be SPACE (ASCII 32). I tried for a simple frequency analysis first on that basis to find candidate key characters and it gave the right answer. It ran in 0.62 seconds.

If this approach hadn’t worked my next approach would have been to restrict the key characters as per the question and compare each decoded sequence against a valid character set e..g a-z, A-Z, comma, parentheses, full-stops, etc. looking for least exceptions and rating the key against that.

For something like this, where the plaintext type and key length was known it didn’t really warrant coding up a sliding XOR attack.

def seqs = [ [], [], [] ]

new File("euler_p59_cipher1.txt").text.split(",")
        .eachWithIndex { val, idx –>
            seqs[idx % seqs.size()] << val.toInteger()
        }

def answer = 0
def ASCII_SPACE = 32

seqs.each { vals ->

    def freqs = new int[256]
    vals.each { freqs[it]++ }

    def ( pkey, max ) = [ 0, 0 ]
    freqs.eachWithIndex { freq, chr ->
        if (freq > max) ( pkey, max ) = [ chr ^ ASCII_SPACE, freq ]
    }

    answer += vals.sum { it ^ pkey }
}

I went on to decode the passage and the result was truly Biblical. Not sure that I would have used that particular text in such a website but, as this solution proves, you don’t actually need to read it to get the answer. As to the key itself, well, I’d have stayed clear of that too. It’s one of those passwords you just NEVER use!

Conclusion

Groovy was a very nice language to use for this. It made it very easy to read the file and split it into sequences for each character in the keyword. In fact, that could have been a one-liner. The construction of the frequency table and the extraction of a potential key character was also very straightforward.

As there was no heavy maths processing performance was fine, it was quick to write and the code intent is clear.

It also helped that I’ve had an interest in cryptography since young. I thoroughly recommend Simon Singh’s Code Book as a gentle introduction into the topic.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: