Encrypting with XOR: A Graphic Example
June 9th 2007 09:24 am
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.
If Alice wants to send a secret message to her friend Bob, she 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.
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. The 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
Below we have the handwritten message “Send Cash” embedded in a 128 by 128-bit image. 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:
|
|
⊕ |
|
Message “Send Cash” |
XOR |
Encryption Key |
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:
 |
 |
In this particular example, the upper left corner of the bitmaps are mirror images. This is because the xor operation is combining the key bits with blank (zero) bits from the upper left corner of the “Send Cash” image. In any case, the blocks may look identically gray, but the actual bits don’t match. Properly encrypted data is supposed to look like random noise. A random field of 0 and 1 bits should produce a gray appearance when shown as a bit mapped image.
To decrypt the message, we simply take the encrypted message and compute xor with the encryption key, bit-by-bit. This yields the original plaintext “Send Money” 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.
Download these images:
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 k be 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.
