Original version With 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 encrypt the message using a special rule known only to you and your target audience. This principle acted like a key to a lock. If you had the key, you could decrypt the message; otherwise you would have to choose a lock. Some locks they are so effective that they will never be harvested, even with infinite time and resources. But even these systems have the same Achilles heel that plagues all encryption systems: how to get the key into the right hands while keeping it out of the wrong hands?
A counter-intuitive solution, the so-called public key cryptographyit is not about keeping a key secret, but rather about making it widely available. The trick is to utilize a second key that you never share with anyone, not even the person you are communicating with. Only by using this combination of two keys – one public and one private – can someone simultaneously encrypt and decrypt 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 components of undetectable ink. The first component causes messages to disappear, and the second component causes them to reappear. If a spy named Boris wants to send his counterpart Natasha a secret message, he writes it and then uses the first ingredient to make it undetectable on the page. (This is straightforward for him: Natasha has published an straightforward and well-known recipe for disappearing ink.) When Natasha receives the newspaper in the mail, she uses a second ingredient that makes Boris’ message reappear.
In this scheme, anyone can make messages undetectable, but only Natasha can make them apparent again. And since she never shared the recipe for the second ingredient with anyone – not even Boris – she can be sure that the message was not decrypted along the way. When Boris wants to receive secret messages, he simply adopts the same procedure: he publishes an straightforward recipe for making messages disappear (which Natasha or anyone else can utilize), keeping for himself another one that makes them reappear.
In public-key cryptography, the “public” and “private” keys work just like the first and second components of that special undetectable ink: one encrypts messages, the other decrypts them. But instead of using chemicals, public key cryptography uses mathematical puzzles called flap functions. These functions are straightforward to compute in one direction and extremely hard to reverse. But they also contain a “trapdoor” – information that, if known, makes calculating the function in both directions trivially straightforward.
One common trapdoor function is to multiply two vast prime numbers, which is an straightforward operation to perform. However, inverting this – that is, starting with the product and finding each prime factor – is computationally impractical. To create a public key, start with two vast prime numbers. These are your trapdoors. Multiply these two numbers together and then do the additional steps mathematical operations. This public key can now encrypt messages. To decrypt them, you will need the appropriate private key, which contains prime factors – the necessary trapdoors. These numbers make it straightforward to decode the message. Keep these two primes secret and the message will remain secret.