Crypto shocker: 'Perfect cipher' dates back to telegraphs
35 years prior to being invented
A computer scientist has unearthed evidence that a theoretically unbreakable form of cryptography was in use by telegraph operators as early as 1882, 35 years before its supposed invention by a duo from Bell Labs and the US Army.
The one-time pad, which is also known as the perfect cipher, uses a random key that is shared by both sender and receiver to encrypt and decode a sensitive message. Assuming the key is used only once and both parties securely dispose of it, the technique is the only known method to perform mathematically unbreakable encryption, according to this post by cryptography historian Dirk Rijmenants. Until now its invention was dated to 1917 and credited to Gilbert Vernam of Bell Labs and Captain Joseph Mauborgne of the Army Signal Corps.
But according to The New York Times, computer scientist Steven Bellovin recently found a description of the one-time pad algorithm in an 1882 telegraphers' codebook titled Telegraphic Code to Insure Privacy and Secrecy in the Transmission of Telegrams. It was written by one Frank Miller, a successful banker from California who went on to become a trustee of Stanford University. He also served in the US Army's inspector general's office, where he worked on a team investigating the assassination of Abraham Lincoln.
"A banker in the West should prepare a list of irregular numbers to be called 'shift numbers,'" Miller wrote. "The difference between such numbers must not be regular. When a shift-number has been applied, or used, it must be erased from the list and not be used again."
The NYT said independent specialists in cryptography have confirmed that Miller's work proves he developed the one-time pad long before its discovery and later patenting by Vernam and Mauborgne.
“Miller probably invented the one-time pad, but without knowing why it was perfectly secure or even that it was,” David Kahn, the author of the 1967 book The Codebreakers, was quoted as saying. “Moreover, unlike Mauborgne’s conscious invention, or the Germans’ conscious adoption of the one-time pad to superencipher their Foreign Office codes, it had no echo, no use in cryptology. It sank without a trace — until Steve found it by accident.”
A PDF of Bellovin's writeup in the July issue of the journal Cryptologia is here. ®
OK - this is how a one time pad works
The one time pad IS inherently and provably unbreakable (properly implemented of course). There is obviously some confusion about this:
A one time pad is pre-shared encryption key that is used for only one message and then discarded. The key is of at least equivalent length to the message. Each letter in the message is shifted by the amount suggested by the corresponding part of the key. The key must be properly randomly generated.
Frequency analysis will not work as every instance of each letter is shifted by a random amount. Because the key length >= the message length there is no repetition of the shifts to attack. In the same way the discarding of the key after one use prevents analysis over several messages.
You could try every key combination - but that would just yield every possible message of equivalent length with no way to distinguish the right message - i.e. for a 17 letter message you would have all of the following decrypts:
WE ATTACK AT DAWN
WE ATTACK AT DUSK
STEVE LOVES KATIE
DINNER IS IN OVEN
To put it in context:
A simple shift cipher (ROT 13) is attacked by trying all the values to shift by
A Caesar cipher can be defeated by frequency analysis
The Spartan cipher rod is a transposition cipher and can be broken by putting the code into various tables
Polyalphabetic ciphers (using a different cipher alphabet for every nth character) are vulnerable to frequency analysis - but each alphabet needs to be broken individually.
Machines like Enigma change the cipher alphabet for every character, but do so in a pre-determined way given a particular set of initial settings.
A one time pad uses a different cipher alphabet for every character but does so in a 100% random way.
Does this also push back the first instance of a technology patent found to have been granted despite the existence of prior art?
And that point is "all the way".
The idea of the one-time pad is that you change the cipher for *each* *letter* of the original message as you go, so every "e" in the plaintext can potentially be encrypted as a *different* letter in the ciphertext.
Putting spaces between words is just a schoolboy error -- either your contact at the far end will be able to work out where the spaces should be, if they have decrypted the message correctly, or you encrypt spaces.