## 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: comments@mathschallenge.net

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:

BinChrBinChrBinChrBinChr 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.