In 1882, a banker in Sacramento, Calif., named Frank Miller developed an absolutely unbreakable encryption method. Nearly 140 years later, cryptographers have yet to come up with something better.
Miller had learned about cryptography while serving as a military investigator during the U.S. Civil War. Sometime later, he grew interested in telegraphy and especially the challenge of preventing fraud by wire—a problem that was frustrating many bankers at the time. As a contemporary, Robert Slater, the secretary of the French Atlantic Telegraph Co., wrote in his 1870 book Telegraphic Code, to Ensure Secresy [sic] in the Transmission of Telegrams, “Nothing then is easier for a dishonest cable operator than the commission of a fraud of gigantic extent.”
In his own book on telegraphic code, published in 1882, Miller proposed encrypting messages by shifting each letter in the message by a random number of places, resulting in a string of gibberish. For example, to encode the word HELP, you might shift the H by 5 so that it became an M, the E by 3 so that it became an H, the L by 2 so that it became an N, and the P by 4 so that it became a T. Even a meddlesome cable operator wouldn’t know what to make of MHNT unless he also had the list of random numbers, 5-3-2-4. For truly unbreakable encryption, each string of random numbers would encode only one message before being discarded.
About 35 years after Miller’s book, Bell Labs engineer Gilbert S. Vernam and U.S. Army Capt. Joseph Mauborgne came out with essentially the same idea, which they called the one-time pad. And ever since, cryptographers have tried to devise a way to generate and distribute the unique and truly random numbers that the technique requires. That, it turns out, is incredibly hard to do.
So instead, we’ve relied on less secure encryption methods, with the consequence that attackers who are sufficiently patient and knowledgeable can now crack into any encrypted data they want. And compared with Miller’s day, today we have more ways of connecting than the telegraph—through Internet of Things devices, wearable tech, and blockchain-dependent services, to name just a few—and they all need strong encryption. According to the 2017 “Cyber Incident & Breach Trends Report” [PDF] by the Online Trust Alliance, more than 150,000 businesses and government institutions were the victims of cybercrime last year. In just one of those attacks, on the consumer credit reporting company Equifax, hackers culled the personal information of nearly 148 million customers. “Surprising no one, 2017 marked another ‘worst year ever’ in personal data breaches and cyber incidents around the world,” the report concluded.
Fortunately, researchers have made good progress in recent years in developing technologies that can generate and distribute truly random numbers. By measuring the unpredictable attributes of subatomic particles, these devices can use the rules of quantum mechanics to encrypt messages. And that means we’re finally getting close to solving one of cryptography’s biggest puzzles and realizing the unbreakable encryption envisioned by Miller so many years ago.
As any cryptographer knows,you need three ingredients to make a hackproof encryption method. First, you need an algorithm that converts your message into a string of meaningless characters. Second, you need a way to produce random numbers. And finally, you need the means to deliver the first two ingredients to the intended recipient without anyone else gaining access.
You cannot protect a message with the first ingredient alone, no matter how good the algorithm is. An encrypted message will be completely exposed to anyone who knows the algorithm used to secure it. That’s why we combine the algorithm with random numbers. Despite its relatively simple algorithm, the one-time pad becomes unbreakable with the addition of random numbers. To recover the original message, you need to know the specific sequence of random numbers the algorithm used to encrypt the message. Those random numbers are a cryptographic key, which unlocks the content of the encrypted message, but it’s useless for deciphering other messages, just as your house key opens your front door but not your neighbor’s. Your encryption system is thus only as strong as your cryptographic key is unpredictable.
Unfortunately, most sources of random numbers aren’t truly random. These pseudorandom-number generators use algorithms to produce sequences of numbers that look random. But again, if you know the underlying algorithm, they become completely predictable.
We can also generate random numbers by measuring physical processes, like flipping a coin or the interference of radio communications on an electric current. One problem with this approach is that if the process is bound by the laws of classical physics, the measurements can be predicted. To be sure, it may take some doing to reverse engineer what’s being measured, but a cryptographer has to assume that somebody will eventually find a way to do so.
Many physical random number sources are also slow. One common method is to record the coordinates of mouse clicks or movements on a computer screen. KeePass, an open-source password manager, uses mouse jiggles to generate a master password. Think how much random clicking or jiggling it would entail just to encrypt every email you wanted to send.
What’s needed, then, is a source of true randomness that is fast enough and that any device can use. That’s where quantum mechanics comes in.
By their nature, subatomic particles like electrons and photons behave in ways that can’t be predicted. If you take two photons emitted by the same atom at different times but under the same conditions, they may exhibit different behaviors, and there’s no way to predict those behaviors ahead of time. That’s not to say any behavior is possible, but of the outcomes that arepossible, we can’t predict which one we’ll get. That unpredictability is crucial for developing a random number generator.
Source: IEEE Spectrum