XOR bitwise operation

The Ultimate Shift Cipher

If you’ve seen the lesson on the one-time pad, you know that it is the ultimate shift cipher. It involves the application of a random list of shifts equal to the length of the message. It’s important to understand exactly how and why the one-time pad is unbreakable, or, perfectly secret.

To understand why, we need to first introduce the AND, OR and XOR bitwise operations. Specifically why XOR must be used when performing the one-time pad on computers. Bitwise simply means that we are dealing with individual bits, or binary numbers. In any modern/computerized encryption scheme we represent our symbols using binary digits. If you forgot why, you can check out this video on Computer Memory

Encrypting Colors

Let’s begin with a visual example by encrypting a color in the Khan Academy logo.

How do we turn a color into a number? Well, right now you are looking at HTML colors which are defined using the RGB color model. This is an additive model based on mixing some amount of red, green and blue light.

We can define exactly how much RED, GREEN and BLUE using a number from 0-255. Black is all off (0,0,0) while white is all on (255,255,255). In between there are 16 million possible colors (256 * 256 * 256). Next let’s sample the green in the Khan Academy leaf in any image editing tool:

color picker

Notice it stores it as  RED=156, GREEN=181 & BLUE=58. If we express these numbers in binary we get:
10011100 + 10110101 + 00111010. Which we can squeeze together as: 100111001011010100111010

Binary RGB representation of the Khan Academy green:

greeg

Application of Random Shifts

Now let’s say you generate a shift sequence using coin flips converted into binary as:

HTHTTHTHHHHTTHTTTTHTTHHH = 010110100001101111011000

Let’s think about how we could apply this shift sequence to our color in order to encrypt it using the one-time pad

100111001011010100111010 + 010110100001101111011000 = ?

To make the one-time pad work we need to choose the correct operation so that the resulting sequence is equally likely to be any color. Let’s go over three different operations:

AND

The AND operator is also known as logical conjunction, and works just like multiplication. 
It outputs a 1 only if all of the inputs are 1. Here is the truth table:

0 AND 0 = 0

0 AND 1 = 0

1 AND 0 = 0

1 AND 1 = 1

Let’s try it: 100111001011010100111010 AND 010110100001101111011000 = 000110000001000100011000

This results in a very dark purple. Notice when we perform the AND operation on any binary number, the resulting sequence cannot be larger. In our color example this eliminates many possible shades as it pushes the color towards black.

OR

The OR operator is also known as logical disjunction. It outputs a 1 whenever one or more of its inputs are 1. Here is the truth table:

0 OR 0 = 0

0 OR 1 = 1

1 OR 0 = 1

1 OR 1 = 1

Let’s try it: 100111001011010100111010 OR 010110100001101111011000 = 110111101011111111111010

This results in a light purple. Notice when we perform the OR operation on any binary sequence, the resulting sequence cannot be smaller. This eliminates many possibilities as it pushes the color towards white.

XOR

The XOR operator outputs a 1 whenever the inputs do not match, which occurs when one of the two inputs is exclusively true. This is the same as addition mod 2. Here is the truth table:

0 XOR 0 = 0

0 XOR 1 = 1

1 XOR 0 = 1

1 XOR 1 = 0

Let's try it: 100111001011010100111010 XOR 010110100001101111011000 = 110001101010111011100010

dark purple

This results in a slightly darker purple as compared to the OR operation. Notice when we perform the XOR operation on a binary sequence, the resulting sequence could be any possible sequence. Given some encrypted color, all we know is the original color is “equally likely to be any color”. We have no information that could improve a blind guess (1/16 million).

Finally, let’s do a visual demonstration so that we can see the one-time pad in action. Then we can earn more energy points!