Ever since writing has existed, people have wanted to send secret messages to one another--and others have wanted to intercept and read them. This is the second installment of a blog series taking you through the history of cryptography, its present, and future possibilities of unbreakable codes. Click here to read Part 1: Encryptions Past.
Some of the very first secret codes were substitution ciphers--schemes for transforming the letters in a message to render them unreadable to anybody who didn't know the secret to decoding them. The reader of the message would use a "key," information that revealed how to translate the message back into normal text, that could come in the form of an exact list of letters or numbers, a code word, or another variable. In theory, only people with knowledge of the key could read the encoded messages. In practice, though, the earliest ciphers were simple enough to break by analyzing the frequency of letters or simple trial and error.
The good news for secret-keepers: In World War II, an unbreakable encryption scheme was invented. The bad news: The One-Time Pad, as it was called, never really caught on. And for good reason.
Here's how it worked. Users would need two identical copies of a long book of random numbers--the "One-Time Pad" itself. The first message sent would use the first page of the One-Time Pad, and each subsequent message would use a new page, so that by the 999th message both communicators would have gone through 999 matching pages of random numbers.
Because the numbers in the key didn't repeat, there were no patterns to analyze: hence the unbreakableness. Sure, a spy could guess the exact string of random numbers used and decode the message. But how would he know it was the right message? With a slightly different string of random numbers, the message could decode to say something completely different, and there was no way to verify a correct decoding.
Unbreakable it may have been, but the One-Time Pad was also rather inconvenient. Bulky books of random numbers were impractical to carry and use on the battlefield. There was always the risk that they would be stolen by the enemy. Even the process of generating truly random numbers was much more difficult than you'd expect, and any patterns in the numbers could be exploited to crack the code. The unbreakable One-Time Pad points to the problem with all ciphers invented up to this point--in order to send a secret message, the sender and recipient had to already share a secret: the key, whether it was a list of letters and their counterparts or a book of random numbers. And the system would only be as secure as the method used to share the key. It would be quite some time before anybody overcame that particular hurdle.
German Enigma machine. Via Wikimedia.
So far I've only talked about pen-and-ink ciphers: the kind that are easy to encrypt and transmit by hand. But the push for more complexity meant, that during World War II, armies were always on the lookout for a fast, convenient way to send out orders and information. Pen and paper gave way to simple mechanical devices, which soon blossomed into complex machines whose codes required even more complicated machines to crack. A famous example: Germany's use of the mechanical encryption system called ENIGMA to conceal its plans. ENIGMA was powerful because it was flexible: the machine's settings allowed users to access a huge number of encryption schemes based on keys that were shared among all the operators and changed by the day.
Here is how the process worked: ENIGMA sent each typed letter through three of its many scrambling rotors. At each rotor, ENIGMA switched the letter with another letter. Then, the letter went through a plugboard that could swap several letters with each other--the swap list was changed every day. After every key type, the rotors would increment forward, ensuring that the encryption of the next letter would be different. The message could only be decoded if the machine was set up with the identical rotors in the same position and the same plugboard settings--leaving 159 million million million possible "keys" or settings for a given message's beginning. (See How the Enigma Works for more about ENIGMA's inner workings.)
Because the plugboard and rotor settings were changed by all ENIGMA users on a daily basis (each ENIGMA operator had a thick book of settings to use each month), British scientists were forced to rush and break the code each day to read transmissions before the information became obsolete.
The race to break ENIGMA is a famously dramatic story. Ultimately, the scientists at Britain's Bletchley Park invented a mechanical device the size of several rooms to crack the code. Their machine was built of several pieces called bombes that recreated ENIGMA's internal machinery. These bombes automatically cycled through trying all the possible rotor combinations to break the day's transmissions. The bombes were precursors to the computers we know today; ENIGMA motivated scientific development and showed the world the possibilities of using machines to encode and transmit information.
Today, you can use a computer to create a polyalphabetic substitution code complicated enough that it would take impossibly long for someone to decode without the key. And indeed, many encryption systems available commercially rely on that basic format.
But isn't there a way to get rid of this reliance on secret keys?
Well, yes--as we'll explore next.