mathschallenge.net logo

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 -----
From: less thancomments@mathschallenge.netgreater than
To: less thanmastermind@coolmail.co.ukgreater than
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
less thanspcgreater than
 
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.

ABC
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