One Time Pads

One Time Pads are the only provable totally secure classical cryptographic system. A one time pad is essentially a random, non repeating key, with no redundancy.

Imagine that we were using a Vigenère cipher. Instead of the key being 'freddie' or some such word, imagine that the key was 'ajsfdqwkljhasgqwqwibvcrytmnmzx...' an entirely random sequence of letters which did not repeat for the entire length of the message.

Each letter would effectively be encoded randomly - and one could not decode at all without knowing the precise letter in the key, there are no patterns which emerge.

Consider the word 'attack', if we encode this with the key: fsjdlk then the ciphertext is 'flcdnu'.

Imagine that we tried to decode this by exhaustive search. If we choose the key 'rucqhq' it will decode to 'orange', and the key 'uhqpac' decodes to 'lemons'!

Indeed, we can 'decode' this message to any six letter word we like by 'choosing' the correct key. Of course, this is not analysing the message.

The 'One time pad' will be secure if the key is truly random, and if the key is only used once. If it is used more than once this will introduce redundancy which can be used to analyse the messages (a vigenère is effectively 'redundant' with itself!)

Of course, this provides one major difficulty.

The key, which must be arranged between the two parties, must be kept secure - and it must be as big as the message.

During the cold war, this was a big problem for the Russians who used one time pad for all their messages. They would print blocks of random characters on to pads. The pads would be gummed at the edges (to detect tampering), and the pads would either be sent in the diplomatic pouch for later use, or concealed with an agent. When used, the key would be destroyed, never to be used again.

Vigenère is not often used in a one time pad, quite often the logical operation 'XOR' is used. In this digital age, all text, pictures, soundfiles etc, can be reduced to a string of numbers. Zeros and Ones. The XOR operation works on these numbers.

Imagine we have two 'bits', A and B. A and B can either be 0 or 1. When these are XORed, the output is '1' if A and B are different.

A B | Q
----+--
0 0 | 0
0 1 | 1
1 0 | 1
1 1 | 0

Now imagine that we have a plaintext character, which might be represented as %10001010 (the %indicates that the following number is binary, and is not ten million and a bit. It actually represents the number 138). The random key to encode this 'byte' is %10101101

P: %10001010
K: %10101101
C: %00100111

The lovely thing about XOR is that to get back to the original, we need only apply the key again.

C: %00100111
K: %10101101
P: %10001010

Of course, a 'brute force' search would not work, as if we apply all possibilities for 'K' we will get all possibilities for 'P'.

Another simply candidate for a one time pad is simply addition, this would have worked very well to encode numbers by hand.

Encode: C=P+K (where K is random, and different for each character in P)

Decode: P=C-K

P can only be obtained from C if K is known. One might use modular arithmetic here to prevent C being too large (i.e. count up to a limit, then start from zero - this in no way affects the method - indeed, with modular arithmetic we effectively have a Vigenère-a-like!).

All of this detail is rather superfluous, the essential ingredient of a one time pad is just a truly random key, which is used once, and only once (note this is not using one small key once per message but repeatedly over the message!).

If this condition is met, then we have an unbreakable cipher.