The original version From this story appeared in Quanta Magazine.
For thousands of years, if you wanted to send a secret message, there was basically one way to do it. You would encode the message using a special rule, known only to you and your intended audience. This rule worked like a key to a lock. If you had the key, you could decode the message; otherwise, you would have to pick the lock. Some locks are so good that they can never be picked, even with infinite time and resources. But these schemes also suffer from the same Achilles’ heel that afflicts all these encryption systems: how do you ensure that the key ends up in the right hands while keeping it out of the wrong ones?
The counterintuitive solution, known as public-key cryptography, relies not on keeping a key secret but rather on making it widely available. The trick is to also use a second key that you never share with anyone, not even the person you are communicating with. It is only by using this combination of two keys, one public and one private, that someone can both encode and decode a message.
To understand how this works, it’s easier to think of “keys” not as objects that fit into a lock, but as two complementary ingredients of an invisible ink. The first ingredient makes the messages disappear, the second makes them reappear. If a spy named Boris wants to send a secret message to his counterpart Natasha, he writes a message and then uses the first ingredient to make him invisible on the page. (This is easy for him: Natasha has published a simple, well-known formula for making the ink disappear.) When Natasha receives the paper in the mail, she applies the second ingredient which makes Boris’s message reappear.
In this scheme anyone can make messages invisible, but only Natasha can make them visible again. And since she never shares the formula for the second ingredient with anyone, not even Boris, she can be sure that the message hasn’t been deciphered along the way. When Boris wants to receive secret messages, he simply follows the same procedure: he publishes a simple recipe for making the messages disappear (which Natasha or anyone else can use), while keeping another one just for himself that makes them reappear.
In public key cryptography, the “public” and “private” keys work just like the first and second ingredients of this special invisible ink: one encrypts messages, the other decrypts them. But instead of using chemicals, public key cryptography uses mathematical puzzles called trapdoor functions. These functions are easy to calculate in one direction and extremely difficult to reverse. But they also contain “trapdoors”, information that, if known, makes the functions trivially easy to calculate in both directions.
A common trapdoor function involves multiplying two large prime numbers, an easy operation to perform. But reversing it, i.e. starting from the product and finding each prime factor, is computationally impractical. To create a public key, start with two large prime numbers. These are your trapdoors. Multiply the two numbers together, then perform some additional math. This public key can now encrypt messages. To decrypt them, you will need the corresponding private key, which contains the prime factors – the necessary traps. With those numbers it is easy to decipher the message. Keep these two prime factors secret and the message will remain secret.