Additive Ciphers (Vernam One-Time-Pad)

The basic idea of encryption is an additive cipher which adds a keystream (K) to the plaintext (C).

$Z = K+C$
The problem is that if we do this for every bit (or character) we can get a resulting bit (or character) which exceeds the range of representable characters. To fix this we can take the rest of a division by the number of available characters without loss of generality. To represent one bit we use modulo 2 division: This operation is also referred to as XOR (exclusive or).

$Z = K xor C$
The truth table for this operation is

K_i	Ci	Z_i
0	0	0
0	1	1
1	0	1
1	1	0.

We can prove that decryption works in the same way as the encryption by writing out:

$C = Z xor K=X xor C xor K=C xor (K xor K)$
and since

$K xor K = 0$
we get

$C = C xor 0 = C.$
Thus we obtained the original plaintext. Furthermore, this encryption is safe as long as one uses a random keystream and does not reuse the same keystream for different messages.

Possible attacks

Assuming we have two encrypted messages Z₁ and Z₂:

$Z1 = K + C1, Z2 = k + C2$
Adding them both together gives

$Z1 xor Z2 = C1 xor C2$
Thus we got rid of the keystream and trying common patterns in successive positions in C₁ we can obtain parts of the two messages and the keystream. If this keystream is not random a search for patterns or other methods can yield more information about the key and a whole keystream can be reconstructed. That's why the two conditions given above are necessary to ensure that this encryption scheme is successful.

Unfortunately the restraint to a completely random keystream requires the parties of communication to have long copies of the keystream, which must be as long as the transmitted messages. This is highly impractical and a common solution is a pseudo-random generator which is initialized with secret values. These values become the key shared by both parties and are used to set up the key generator to obtain the keystream. These pseudo random generators are mostly broken by finding a non-random pattern and reconstructing the secret initialization values from it. In some cases (like the Lorenz encryption machine) it is even possible to find the structure of the keystream generator.