 4 Many Caesars: the |
 V'ir Tbg n Frperg  This document as PDF |
 6 Modern Times |
The idea is similar to the Vigenère cipher, except that instead of using English text as our key, we use a sequence of random numbers. It is critical that the random sequence of numbers be truly random, and that the sequence never be reused. Such a cipher is called a one-time pad, and was proven to be unbreakable by Claude Shannon in 1949.
To use a one-time pad, we have an arbitrarily long list of random numbers. This sequence is our ``one-time pad''. We add each of these in turn to our plaintext, and reduce modulo 26. This gives our ciphertext. To decrypt, we reverse the process, subtracting the same sequence of numbers from the ciphertext. For this to be truly secure, we can never use this sequence of numbers again, hence the phrase ``one-time'' in the name.
The security of the system stems from the fact that any plaintext can encrypt to any ciphertext of the same length. For example, the ciphertext QQQQQQ could correspond to the plaintext attack or gohome. For the first, the key sequence is 16,23,23,16,14,6 and in the second message, the key is 13,2,12,2,4,9. Since the key could be any of these (or any other one), there is no way to break the cipher except to get your hands on the key.
One-time pads were used heavily during the second world war, and during the cold war. Books consisting of long lists of random digits were given to agents. But it was critical that the codebooks not fall into enemy hands, or the ciphers would immediately become useless. Anyone who possessed the codebook could easily decrypt the messages.
It is also very important that the numbers be truly random. A computer program cannot generate truly random numbers without some outside source of randomness. Several successful attacks on early ``secure'' web communications relied on weaknesses in the browser's random number generator. There is a story that during World War II, some of the codebooks were generated by drawing numbered balls out of a bin. However, the person drawing the balls would put the ball back if he drew it twice in a row, thinking a repeated number wasn't random. This slight deviation from true randomness was enough to enable several ``unbreakable'' messages to be broken.