The original version from this story appeared in Quanta Magazine.
Basically, if you wanted to send a secret message across millennia, there was a way to do it. They would encrypt the message using a special rule known only to you and your target audience. This rule acted like a key to a lock. If you had the key, you could decrypt the message; otherwise you would have to pick the lock. Some castles are so effective that they can never be selected, even with infinite time and resources. But even these systems suffer from the same Achilles heel that plagues all such encryption systems: How do you get that key into the right hands while keeping it out of the wrong ones?
The counterintuitive solution, known as Public key cryptographyThe aim is not to keep a key secret, but rather to make it generally available. The trick is to also use a second key that you never share with anyone, including the person you are communicating with. Only by using this combination of two keys – one public and one private – can someone both encrypt and decrypt a message.
To understand how this works, it’s easier to think of the “keys” not as objects that fit into a lock, but as two complementary parts of an invisible ink. The first ingredient makes messages disappear, the second makes them reappear. When a spy named Boris wants to send a secret message to his counterpart, Natasha, he writes a message and then uses the first ingredient on the page to make it invisible. (This is easy for him: Natasha has published a simple and well-known formula for making ink disappear.) When Natasha receives the paper in the mail, she uses the second ingredient, which causes Boris’ message to reappear.
In this scheme, anyone can make messages invisible, but only Natasha can make them visible again. And since she doesn’t share the formula for the second ingredient with anyone – not even Boris – she can be sure that the message wasn’t decoded along the way. When Boris wants to receive secret messages, he simply does the same thing: he publishes a simple recipe to make 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 in the same way as 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 so-called mathematical puzzles Trapdoor features. These functions are easy to calculate in one direction and extremely difficult to reverse. But they also contain “trap doors,” information that, if known, makes calculating the functions in both directions trivially easy.
A common trapdoor function is to multiply two large prime numbers, an easy operation to perform. But reversing it – that is, starting with the product and finding each prime factor – is computationally impractical. To create a public key, start with two large prime numbers. These are your trap doors. Multiply the two numbers together and then carry out further steps mathematical operations. This public key can now encrypt messages. To decrypt them, you need the corresponding private key, which contains the prime factors – the necessary trap doors. With these numbers it is easy to decipher the message. Keep these two main factors secret and the message will remain secret.
