Perfect encryption

The one-time pad

The one-time pad (often abbreviated OTP) is the only encryption scheme that has been proven unbreakable. Its principle is disarmingly simple: combine each bit of the message with a bit of a perfectly random key.

The XOR operation

Everything rests on a single boolean operation, the exclusive OR, written XOR or ⊕. It takes two bits and returns 1 if — and only if — the two bits are different.

 a | b | a XOR b
---+---+--------
 0 | 0 |   0
 0 | 1 |   1
 1 | 0 |   1
 1 | 1 |   0

Remember it this way: XOR answers the question "are these two bits different?".

Encrypting and decrypting

Let M be the plaintext (a sequence of bits) and K the key, or pad, a sequence of bits of the same length as the message. Encryption is done bitwise:

encrypt : C = M XOR K
decrypt : M = C XOR K

The same key serves in both directions: the one-time pad is a symmetric encryption scheme.

The reversibility of XOR

Why does applying the pad twice give back the message? Because XOR is its own inverse. For any bit x and any key bit k:

(x XOR k) XOR k = x XOR (k XOR k) = x XOR 0 = x

Two properties guarantee this: k XOR k = 0 (a bit always equals itself) and x XOR 0 = x (masking with zeros changes nothing). Applying the pad a second time cancels it out.

An example on one byte

Let's encrypt the letter A, whose ASCII code is 01000001, with a random pad 10110100.

Message  M : 0 1 0 0 0 0 0 1   ("A")
Pad      K : 1 0 1 1 0 1 0 0
             ---------------  bitwise XOR
Cipher   C : 1 1 1 1 0 1 0 1

The ciphertext 11110101 bears no resemblance to the starting letter. Let's decrypt by re-applying the same pad:

Cipher   C : 1 1 1 1 0 1 0 1
Pad      K : 1 0 1 1 0 1 0 0
             ---------------  bitwise XOR
Message  M : 0 1 0 0 0 0 0 1   ("A")   ✔

We recover exactly the initial byte. In each column, we have indeed applied the same pad bit twice, and it cancels out.

In summary