XOR Challenge

Problem

Sorting through your emails, and deleting the abundance of junk mail that seems to arrive on a daily basis, your attention is drawn to one particular mail:

----- Original Message -----
To: mastermind@coolmail.co.uk
Sent: Saturday, March 1, 2003 1:00 AM
Subject: Only the best need try...

Hi mastermind

So you think you're good at code breaking? I'll tell you how I encoded the message and all you need to do is decode it!

I started by using the table below to change the message into a binary string, then XOR"ed it with the alternating string 101010101..., finally I converted it back into readable text. I guess you'll have to research how XOR works. ;)

Here's the table:

 Bin Chr Bin Chr Bin Chr Bin Chr 00000 spc 01000 H 10000 P 11000 X 00001 A 01001 I 10001 Q 11001 Y 00010 B 01010 J 10010 R 11010 Z 00011 C 01011 K 10011 S 11011 . 00100 D 01100 L 10100 T 11100 , 00101 E 01101 M 10101 U 11101 ? 00110 F 01110 N 10110 V 11110 ! 00111 G 01111 O 10111 W 11111 -

Here's the encoded message:

,GEXPYFCCOK

Good luck!
mathschallenge.net

Can you decode the message?

Solution

Let us begin with an example. We start by converting the word, CAT, in to binary: 00011 00001 10100. The XOR function works by comparing corresponding bits (0 or 1) in the original binary string with another binary string, called the encryption key. The table below shows what happens when we do A XOR B to produce C.

 A B C 0 0 0 0 1 1 1 0 1 1 1 0

In other words, if the two bits we are comparing are the same we get 0 otherwise we get 1.

It often helps to write the original binary string above the encryption key:

000110000110100 (Original)
101010101010101 (Encryption Key)
101100101100001 (Encoded)

Breaking this down we get 10110 01011 00001, which gives the encoded word, VKA.

The amazing feature of the XOR function is that it is self-inversing. That is, if we re-apply the encryption key to the encoded message we return to the original message. So using this system on our encoded message we get:

 Text (Encoded) , G E X P Y F C C O K Binary (Encoded) 11100 00111 00101 11000 10000 11001 00110 00011 00011 01111 01011 Encryption Key 10101 01010 10101 01010 10101 01010 10101 01010 10101 01010 10101 Binary (Decoded) 01001 01101 10000 10010 00101 10011 10011 01001 10110 00101 11110 Text (Decoded) I M P R E S S I V E !

Hence the decoded message reads: IMPRESSIVE!

As you can see, the XOR function provides a powerful means of encoding messages. Notice how the alternating binary string we used presents two encoded forms for each character; SS in the original message became YF. A more secure method is to use a phrase as a key. For example, we could use the word CAT in binary (see above) to produce the encryption key 000110000110100, which can be repeated throughout the length of the original message.

Problem ID: 1 (Aug 2000)     Difficulty: 3 Star

Only Show Problem