One-Time Pad

In cryptography, a one-time pad (OTP) is a type of encryption which has been proven to be impossible to crack if used correctly. Each bit or character from the plaintext is encrypted by a modular addition with a bit or character from a secret random key (or pad) of the same length as the plaintext, resulting in a ciphertext. If the key is truly random, as large as or greater than the plaintext, never reused in whole or part, and kept secret, the ciphertext will be impossible to decrypt or break without knowing the key. It has also been proven that any cipher with the perfect secrecy property must use keys with effectively the same requirements as OTP keys. However, practical problems have prevented one-time pads from being widely used.

Creating a Pad

With 10-sided Dice

Although time consuming - You could use five ten-sided dice. With each throw, you have a new five-digit group. Such dice are available in toy stores or on line).

With 6-sided Dice

Never simply use normal six-sided dice, then add the values of two dice. This method is statistically unable to produce values from 0 to 9 and there for insecure (the total of 7 will occur about 6 times more often that the values 2 or 12).

Instead, you may use one black and one white die and assign a value to each of the 36 combinations, taking in account the order/colour of the dice (see table below). This way, each combination has a .0277 probability (1 on 36). We can produce three series of values between 0 and 9. The remaining 6 combinations (with a black 6) are simply disregarded, which doesn't affect the probability of the other combinations.

 TRUE RANDOM 0 TO 9 WITH BLACK AND WHITE DICE
 
 BW        BW        BW       BW       BW       
 11 = 0    21 = 6    31 = 2   41 = 8   51 = 4 
 12 = 1    22 = 7    32 = 3   42 = 9   52 = 5 
 13 = 2    23 = 8    33 = 4   43 = 0   53 = 6 
 14 = 3    24 = 9    34 = 5   44 = 1   54 = 7 
 15 = 4    25 = 0    35 = 6   45 = 2   55 = 8 
 16 = 5    26 = 1    36 = 7   46 = 3   56 = 9 
 
      THROWS WITH BLACK 6 ARE DISCARDED

Practical uses for a One-time Pad

Password Splitting

Using methodological taken from the one-time pad schema it is possible to store a password with multiple individuals or parts. All parts or shares of the encrypted password must be combined before the final password may be reviled. This method allows for a password to be split into 2 or as many shares as an admin wishes.

Why Are One-Time Pads Perfectly Secure?

First, I describe how an xor-based one-time pad (OTP) cipher works. Then, I show why xor-based OTPs are perfectly secure against ciphertext-only cryptanalysis. What is a One-Time Pad?

A one-time pad is a very simple yet completely unbreakable symmetric cipher. "Symmetric" means it uses the same key for encryption as for decryption. As with all symmetric ciphers, the sender must transmit the key to the recipient via some secure and tamperproof channel, otherwise the recipient won't be able to decrypt the ciphertext. The key for a one-time pad cipher is a string of random bits, usually generated by a cryptographically strong pseudo-random number generator (CSPRNG). For more information, see David Deley's Computer Generated Random Numbers. It is better to generate the key using the natural randomness of quantum mechanical events (such as those detected by a Geiger counter), since quantum events are believed by many to be the only source of truly random information in the universe. One-time pads that use CSPRNGs are open to attacks which attempt to compute part or all of the key.

With a one-time pad, there are as many bits in the key as in the plaintext. This is the primary drawback of a one-time pad, but it is also the source of its perfect security (see below). It is essential that no portion of the key ever be reused for another encryption (hence the name "one-time pad"), otherwise cryptanalysis can break the cipher.

The cipher itself is exceedlingly simple. To encrypt plaintext, P, with a key, K, producing ciphertext, C, simply compute the bitwise exclusive-or of the key and the plaintext:

$C=K^{P}$

To decrypt ciphertext, C, the recipient computes

$P=K^{C}$

It's that simple, and it's perfectly secure, as long as the key is random and is not compromised.

Why Are One-Time Pads Perfectly Secure?

If the key is truly random, an xor-based one-time pad is perfectly secure against ciphertext-only cryptanalysis. This means an attacker can't compute the plaintext from the ciphertext without knowlege of the key, even via a brute force search of the space of all keys! Trying all possible keys doesn't help you at all, because all possible plaintexts are equally likely decryptions of the ciphertext. This result is true regardless of how few bits the key has or how much you know about the structure of the plaintext. To see this, suppose you intercept a very small, 8-bit, ciphertext. You know it is either the ASCII character 'S' or the ASCII character 'A' encrypted with a one-time pad. You also know that if it's 'S', the enemy will attack by sea, and if it's 'A', the enemy will attack by air. That's a lot to know. All you are missing is the key, a silly little 8-bit one-time pad.

You assign your crack staff of cryptanalysts to try all 256 8-bit one-time pads. This is a brute force search of the keyspace.

The results of the brute force search of the keyspace is that your staff finds one 8-bit key that decrypts the ciphertext to 'S' and one that decrypts it to 'A'. And you still don't know which one is the actual plaintext.

This argument is easilly generalized to keys (and plaintexts) of arbitrary length.