Digital Alchemy

Medieval alchemists sought to transmute base metals, such as lead and bronze, into gold. Modern science has taught us the futility of that pursuit. In the digital world, there's a kind of digital alchemy that exists thanks to the lowly Boolean XOR operation. The XOR operation is a cousin to the more widely known OR and AND operations. Here's a table showing how XOR works when computing A XOR B for all possible bitwise values of A and B:

As you can see, it's the same as the Boolean OR except the value of 1 XOR 1 is 0. This minor difference enables some truly unique properties, which are commonly used in the field of cryptography.

Suppose you have a message that you want to encrypt (the plaintext). If you represent the message as a string of bits, and you generate a random sequence of bits of the same length to use as the encryption key, then you can encrypt the message by simply XOR'ing each bit of the key with the corresponding bit of the message. The resulting ciphertext is indecipherable without the key. If you send the ciphertext to someone, they can decrypt it simply by XOR'ing the cyphertext with the key, which gives back the original plaintext.

This can be summed up as follows:

C = P XOR K
P = C XOR K

where P is the plaintext, K is the key, and C is the ciphertext. Clearly, XOR'ing with K is a bidirectional transmutation of the plaintext into the ciphertext and vice versa.

This is called a One-Time Pad, and it's a mathematically perfect encryption system, but it's completely impractical to use, because the key is just as large as the message, and you need to have a way to distribute the key to the recipient securely. Oh, and you can never — ever — reuse a key, or it is trivial to crack the encryption. But this post isn't about using XOR as an encryption tool. Instead, I want to show how to use it to transmute any data into any other data, much like the medieval alchemists sought to transmute base metals into gold. This ability to turn any data into any other data has implications for file sharing.

Suppose I want to share the latest DVD image of Windows 7 with other people. If I take the DVD image of Windows 7 and XOR it with an equally large DVD containing, say, a free Linux distribution, then the resulting string of bits will appear to be garbage. Anyone who downloads that string of garbage bits can transmute it back into a Windows 7 DVD image by downloading the same free Linux distribution and XOR'ing it with the garbage bits. The result of that XOR operation is a Windows 7 DVD image.

Of course, it's probably still copyright infringement to do this, but the main idea of this post is that any string of bits can be transmuted into any other — arbitrary — string of bits by XOR'ing with the appropriate string of (apparent) garbage bits. Convert the CD image of Black Sabbath's first album into Handel's Messiah, the text of Mein Kampf into the New Testament, the source code of vi into Emacs, or a DVD of the worst movie ever made into an Oscar-winning classic. This is the modern world's digital alchemy.