The exclusive or operation – a logical function applied to binary bits, like AND, OR, and NOT – is a fundamental encryption technique. It is often used in stream ciphers, which are widely used in web browsers when connecting to secure web servers.

When used properly, this technique provides strong protection. In fact, it is the basis for the one-time pad, the only provably uncrackable encryption. However, this protection is easily eroded if the cipher is not used correctly.

Xor is a trivial operation for computer logic to perform (click here for the details). The operation often appears as a built-in machine instruction so that software can perform it in a single machine operation.

Alice wants to exchange secret messages to her friend Bob. To send the message safely, Alice takes the sequence of bits in the message (the plain text) and a sequence of bits known only by her and Bob – the key. To encrypt, she combines the plain text and the key, bit by bit, using xor.

To create their shared secret key, Bob and Alice produce some secret, random data and share it between themselves. To send a message as a single 128×128-bit image, they have shared the following block of bits to use as their shared, secret key:

Alice now needs to send a message to Bob. She writes out the message in the image below:

In a one-time pad, Alice and Bob must use a different set of secret, randomly generated bits for every message they exchange.

In a stream cipher, Alice and Bob share a much smaller number of secret bits and use them to generate a long, hard-to-guess sequence of bits. A stream cipher relies on a cryptographic algorithm to generate that long sequence from a small, shared secret. This generated sequence is then combined with the message using xor.

A Graphic Example

Alice sends the handwritten message “Send Cash” embedded in a 128 by 128-bit image. Black indicates no color, so the black text in the image contains zero bits, and the white space contains 1 bits. For a key, we have collected a 128 by 128 matrix of random bits. In fact, the bits come from a web site, random.org, that uses radio noise to generate random data for experiments like this. We will combine the two matrices using xor:

When we apply xor bit-by-bit to the two matrices, we get the following 128 by 128 matrix of encrypted bits:

Encrypted “Send Cash”

Yes, this looks like nothing more than a mottled gray block, and it doesn’t look a lot different from the gray-block image of the encryption key. If we look closely, the actual bits are different. Here is a closeup of the upper-left corner of the key bits and the encrypted bits. Most of the bits are identical in the two closeups. The bits in the lower-right closeup are different.

  

In the closeup, most of the image is the same in both the key and the ciphertext. The plaintext “Send Cash” message consists of white space (one bits) except where the black letters (zero bits) appear. The xor operation combines black bits in the key with white bits in the message to yield black bits in the encrypted message.

The closeup’s lower right corner captures part of the letter “S” in the message. The black plaintext combines with black key bits to yield white. White key bits are also reversed by the black plaintext.

Even though the key image and the encrypted message look similarly gray, they contain different bits. That difference hides the encrypted message.

Try it yourself

These example images are 128 by 128 bit maps in GIF format. If you have a program that can read GIF files, save them as bit maps, and apply the xor operation bit-by-bit, then you can easily repeat this operation. The examples here were processed by Matlab, a commercial package, but there are numerous other packages that can reproduce the example.

Use your browser to download the individual GIF images for the Send Cash message and the encryption key.

If you apply the xor operation to the first two bit maps, you produce the third. If you combine the key with the encrypted message (k ⊕ e), you will reproduce original “Send Cash” message.

Exclusive-Or – ⊕ – xor

The following table shows how the xor operation transforms individual bits. Let m be a bit from the plain text message, and kbe a bit from the key. The ⊕ column shows the resulting bit.

m	k	⊕
0	0	0
0	1	1
1	0	1
1	1	0

We can also describe the xor operation in terms of traditional logic operations AND, OR, and NOT. Here we use “C” programming language notation: NOT = !, AND = &, OR = |.

(!m & k) | (m & !k)

To decrypt a message, Bob takes his own copy of the key bits, and applies the same xor transformation to the message, bit by bit.