From Sixteenth-Century Cryptography to the New Millennium — The Last 500 Years - Codes: The Guide to Secrecy from Ancient to Modern Times - page 83

On March 21, 1918, the German offensive began with punishing ferocity,
forcing the retreat of British and French troops. Painvin was under incredible
pressure to find the key. He worked day and night, by his own admission,
losing 10 kilograms (22 pounds), but by the evening of June 2, he had broken
the cryptosystem. Now the French military knew where the Germans would
attack and they did so on June 9. The French held their own and the Germans
suffered heavy casualties. Once American forces arrived, the Germans were on
the defensive, and ultimately by November, they had to admit defeat.
The One-Time Pad
In 1918 another event occurred that would have massive cryptological conse-
quences. Gilbert S. Vernam, a cryptologist working for the American Telegraph
and Telephone Company (AT&T) came to the realization that if the Vigenere
cipher were used with a truly random key, with keylength the size of the plain-
text, called a running key , then the Babbage/Kasiski attack would fail. At this
time, AT&T was working closely with the armed forces, so the company re-
ported this to the Army. It came to the attention of Major Mauborgne, head of
the Signal Corps' research and engineering division. (When Mauborgne was still
just a first lieutenant in 1914, he had published the first solution of the Playfair
cipher, see page 68. Also, see page 79 for his refinement of Hitt's rediscovery.)
He played with Vernam's idea and saw that if the key were reused, then a crypt-
analyst could piece together information and recover the key. Hence, he added
the second component to the Vernam idea. The key must be used once, and
only once, then destroyed. Now, the idea was complete. Use the Vigenere ci-
pher with a truly random running key that is used exactly once, then destroyed.
The system is called the one-time pad , and sometimes, perhaps inappropriately
in view of Mauborgne's contribution, the Vernam cipher . Since the key is as
long as the plaintext, and the key selected is truly random, and used exactly
once, then the ciphertext is completely random as well. Thus, the one-time pad
is unbreakable. In other words, it is impossible to crack by any cryptanalytic
methods.
It would take until 1949 with Shannon's concept of perfect secrecy (which we
will discuss in Chapter 11) that the one-time pad was proved to be unbreakable
(see page 440). In other words, the one-time pad is not only experimentally and
practically unbreakable, but theoretically proven to be so. This was the goal
of cryptography, absolute secrecy. Yet, perfection has a price; there are two
distinct problems it faces. Finding truly random keys is not as easy as it might
seem. Even modern-day computers cannot generate truly random numbers
since they are finite-state devices, meaning that eventually they repeat, and so
are predictable. The best that one can expect from computers is what is called
pseudorandomness , which is a computer's simulation of a random number in the
sense that, at least in appearance, they have the statistical properties of truly
random numbers. This in itself is an entire area of study. (Knuth [138, pages
149-189] spends some 40 pages discussing the very definition of randomness!)
Moreover, to generate random sequences in such a fashion that they must be