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 third installment of the blog series taking you through the history of cryptography, its present, and future possibilities of unbreakable codes. Follow the links to read the first and second parts of the series.
Last time I talked about complex polyalphabetic ciphers--techniques of encoding information that make it nearly impossible to reveal the message without access to a secret key. Because the encryption processes themselves are so intricate, the main security challenge becomes keeping that key private. In order to tell a secret, you already have to share a secret key, and your encoded message will be useless if an eavesdropper finds a way to get ahold of that key.
But in 1976, Ron Rivest, Adi Shamir, and Leonard Adleman invented a method that eliminated the need to give away the key at all. Their method, public key cryptography, is still used today to make secure transmissions of sensitive data and to prove the identities of people online. Public key cryptography turns traditional cryptography on its head: instead of keeping the key a secret, every receiver creates and broadcasts his own individualized key for everyone to see, and anybody who wants to send him a message will use that key to encode it. Because of the way the key was created, he will be the only one who can decode it.
The trick to creating this kind of public key is to use what mathematicians call a one-way function: a type of math operation that's easy to do in one direction but nearly impossible to undo without additional information. One example of a one-way function is multiplying two super-big prime numbers. The multiplication part is easy, but to undo that multiplication, you need to know what the original prime numbers were. And as mathematicians can attest, factoring a number into primes is a ton of work--pick a number big enough, and it'll take all the computers in the world longer than the age of the universe to find the factors.
The RSA public-key cryptosystem that they invented (named after Rivest, Shamir, and Adleman themselves, of course) is still in use today, and it works along exactly these lines. Each person's public key is a version of a large number built from two primes, and only someone with the knowledge of the number's factors--the private key--can decode something encoded using their public key.
The other popular public key cryptosystems today work similarly. They each use a mathematically "hard problem" to create keys so that anyone can encode messages to specific people but only the intended recipients will have the extra information needed to reverse it.
Now, if people wanted to stop at this level of security it would be perfectly understandable. With the computers we have now, public key cryptography is certainly secure enough--so secure, in fact, that it's prompted governments of several countries to put limits on key size, and even to try and ban the exportation of big prime numbers. After all, governments want to be able to read everybody's mail--it wouldn't do for foreign states to have better encryption systems. Public key cryptography is the system that makes e-commerce possible, and it is a standard for high-importance confidential messages. But there is always a chance that someone will find a way to beat the system and find the extra information from the public key.
Enter the next big step, at least in theory--the quantum computer.
More on that next time.