Project Euler – XOR decryption

Welcome to Project Euler’s Problem 59, a decryption challenge.

This is a sample of the encrypted text:

Hard to imagine that I have spent two and a half years with a data encryption company not having any idea on how to crack it?

Even more embarrassing, I posted the problem on my Instagram story and received a screenshot of the correct answer roughly two hours later by a friend who is still working professionally in the field of data security and endpoint protection.

So, how did I solve it? First on reading up on the basics of XOR decryption. Which I didn’t need at all in the end. But at least I did learn something new.

Let’s have a look at a very simple XOR encryption, as given in the problem’s description.

65 XOR 42 = 107. How comes?

ASCII 65 is a capital “A” or 1000001 in binary. 42 is an “*”. In binary it is represented by 0101010.
So…

1000001
0101010
XOR
1101011

The XOR-table (exclusive OR) is simple.
0 and 0 become 0.
0 and 1 become 1.
1 and 0 become 1.
1 and 1 become 0.

That’s all there is to know.

Therefore, 1000001 XOR 0101010 = 1101011 (107, “k”).

The good thing about modern programming languages like Java is that XOR is a built-in operator, ^.
For example 65 ^ 42 = 107. There is absolutely no need to shift any bits around.

Next, I did look up some decryption strategies online. Usually the key length is not known, and one has to figure it out first. Luckily, this is not the case for Problem 59. The key length of 3 is given. Also, the information that it consists of lower case characters only.

Once I understood what is meant by “the key is repeated cyclically throughout the message”, I divided the encrypted text into three blocks. Block one: blue. Block 2: red. Block 3: green.

Behause that’s how the text is encrypted, assuming that the key is “abc”:

For each block I found out which ASCII number occurs most often.

Next, I assumed that this number represents the most common letter in the English language, which is “e”.
A faulty assumption by the way. By reading a bit more about the problem, it occurred to me that the most common character in the text is not an “e” but actually a “SPACE”.

The rest was easy. I XORed each of the three numbers with a SPACE, which gave me three lower case characters.

Next, I pasted the encrypted text into an online tool and provided a guess of the key based on those three characters. The decryption process returned an English text instantaneously.

All that was left was to convert the resulting text back to ASCII codes and calculate their sum. Done!

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 )

Google photo

You are commenting using your Google 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 )

Connecting to %s