One-time Pad History Rewritten

Does the discovery in an old telegraph codebook rewrites the history of cryptography? Until now, Gilbert Vernam was generally accepted as the inventor of the unbreakable one-time encryption. His teletype system was later improved by Joseph Mauborgne and paper versions of the systems later became widely used for diplomatic and military communications.

Recently, Steven Bellovin, professor of computer science at the Columbia University School of Engineering, discovered a 1882 telegraph codebook in the Washington Library of Congress. This codebook, compiled by a Frank Miller, describes a superencipherment of telegraph codes by random "shift-numbers" that should not be repeated. Did Bellovin discover the proof that one-time pad was invented 35 years earlier? Should the history of cryptography regarding one-time pads be rewritten?

Let us first explain what was actually discovered. Telegraph codebooks were used extensively in the 19th century to reduce costs of telegrams by compressing words and phrases into codewords or into a combination of letters or digits. Codebooks did not provide any cryptographic security. Therefore, the codes were sometimes superenciphered (an additional layer of encipherment over the code) with a short key to improve its security. Miller's codebook contains 14,000 words or phrases (some are blanks) with their corresponding codewords and a serial number. So far, nothing special.

The codebook also provides instructions for a superencipherment. These instructions are what makes his work extraordinary. In his preface, Miller writes: "the sender and receiver must each cancel "shift-numbers" as soon as they are used". He further states that "if the senders finds that the addition of the key (to the serial-number) produces a sum greater than the highest serial number (14,000) in this book, he must deduct said last serial number (14,000) from said sum." If the receiver finds that the enciphered word "is less than the key which is to unlock it, he must temporarily add to said serial-number the highest number in this book (14,000) and deduct the key from the sum".

Now, let us recapitulate this: to calculate the ciphertext, the sender adds a key (the shift-numbers) to the plaincode numbers (serial numbers). When the total is more than 14,000, he subtracts 14,000. To decipher, the receiver subtracts the key from the ciphertext. However, if the ciphertext is smaller than the key, he first adds 14,000 to the ciphertext and than subtracts the key. This is essentially a modulo 14,000 additive cipher.

Further down, Miller describes the shift-numbers as "a list of irregular numbers" and "the difference between such numbers must not be regular". He also explains that when a shift-number has been used, it should be erased from the list and not used again. Next, some examples are given where words are replaced by their serial-number (plaincode) and a shift-number (key) is added.

This is clearly the essence of one-time pad encryption. Text is converted into numbers, a random key is added by modular arithmetic and the key should not be used again. Moreover, Miller explains that each correspondent should wirte his own shift-numbers list in black ink in a book and the correspondent's list in red ink upon the opposite page. He clearly distinguishes the black (encipher) and red (decipher) shift-numbers. By doing so, he avoids simultaneous use of the same shift-numbers, something that could occur when both correspondents use one single list of shift-numbers.

Unfortunately, Miller falls short in explaining that each shift-number should have a value between 0 and 14,000. He neither addresses the issue of generating truly random values. This could affect the security of the cipher as the user could be seduce into selecting smaller shift-values that don't require the cumbersome modulo 14,000 calculations. The complicated modulo 14,000 might well be the reason why his system never received the attention and success it deserved. Taking the individual digits of the serial numbers as independent, and applying a modulo 10 (add without carry, subtract without borrowing) would have been much easier and faster. We can only speculate about the reason why Frank Miller's one-time encryption never became publicly know.

Steven Bellovin speculates whether Miller's work might somehow, indirectly through Parker Hitt and Joseph Mauborgne, have reached Gilbert Vernam. However, Vernam, as an electrical engineer, approached the one-time encryption from an entirely different angle and discovered a completely different solution of teletype five-bit punched paper tapes using modulo 2 on each of its five bits. Fact is that Frank Miller's work disappeared in oblivion.

It is indisputable that Frank Miller was the first to invent the one-time pad encryption, albeit less practical than in its current form. 35 years later, Gilbert Vernam invented a completely different electromechanical cipher system that incidentally had the same mathematical properties as Miller's pencil-and-paper cipher. Finally, it were the German cryptologists Werner Kunze, Rudolf Schauffler and Erich Langlotz who developed a one-time pad system for use with pencil and paper, thus re-inventing Frank Miller's encryption scheme.

We may conclude that both Miller and Vernam independently invented one-time pad, and both deserve credit for the same achievement, although in a completely different form. But ultimately, we must acknowledge Frank Miller as the first to have invented the one-time pad concept. Sadly, as far as we know, his invention did not influence the history of cryptography. Nevertheless, history rewritten! And finally, not to be forgotten, Steven Bellovin can be credited for discovering the inventor of one-time pad. Congratulations, Steven!

More details about Miller's 1882 telegraphic codebook are found in Steven Bellovin's paper on Frank Miller (direct link to pdf). The history and use of one-time pads is found on my website. More on various old telegraphic codebooks is found on my post about the Nick Gessler collection.