Crypto 101

5 – Exclusive or

5.1 Description

Exclusive or, often called “XOR”, is a Boolean binary operator that is true when either the first input or the second input, but not both, are true.

Another way to think of XOR is as something called a “programmable inverter”: one input bit decides whether to invert the other input bit, or to just pass it through unchanged. “Inverting” bits is colloquially called “flipping” bits, a term weʼll use often throughout the book.

In mathematics and cryptography papers, exclusive or is generally represented by a cross in a circle: ⊕. Weʼll use the same notation in this book:

The inputs and output here are named as if weʼre using XOR as an encryption operation. On the left, we have the plaintext bit Pi. The i is just an index, since weʼll usually deal with more than one such bit. On top, we have the key bit ki, that decides whether or not to invert Pi. On the right, we have the ciphertext bit, Ci, which is the result of the XOR operation.

5.2 A few properties of XOR

Since weʼll be dealing with XOR extensively during this book, weʼll take a closer look at some of its properties. If youʼre already familiar with how XOR works, feel free to skip this section.

We saw that the output of XOR is 1 when one input or the other (but not both) is 1:

There are a few useful arithmetic tricks we can derive from that.

1. You can apply XOR in any order: a⊕(b⊕c) = (a⊕b)⊕c
2. You can flip the operands around: a⊕ b = b⊕ a
3. Any bit XOR itself is 0: a ⊕ a = 0. If a is 0, then it s̓ 0⊕ 0 = 0; if a is 1, then it s̓ 1⊕ 1 = 0.
4. Any bit XOR 0 is that bit again: a⊕ 0 = a. If a is 0, then it s̓ 0⊕ 0 = 0; if a is 1, then it s̓ 1⊕ 0 = 1.

These rules also imply a⊕ b⊕ a = b:

Weʼll use this property often when using XOR for encryption; you can think of that first XOR with a as encrypting, and the second one as decrypting.