The first version of this story appeared in Quanta Magazine.
For thousands of years, if you wanted to send a private message, there was actually only one way to do it. You would deface the message using a special rule, known only to you and your target audience. This rule acted as a key. If you had the key, you could delete the message; otherwise, you will need to pick the lock. Some locks are so efficient that they cannot be picked, even with infinite time and resources. But even those plans suffer from an Achilles’ heel that plagues all encryption systems: How do you get that key into the right hands while keeping it out of the wrong ones?
An opposing solution, known as public-key cryptography, does not rely on keeping the key secret but rather on making it widely available. The trick is to use a second key that no one has, not even your contact person. It is by using this combination of two keys—one public, one private—that someone can decrypt and delete the message.
To understand how this works, it’s easy to think of “keys” not as the equivalent of a lock, but as two complementary ingredients in an invisible ink. The first ingredient makes the messages disappear, and the second makes them reappear. When a spy named Boris wants to send his colleague Natasha a secret message, he writes the message and uses the first ingredient to make it invisible on the page. (This is easy for her to do: Natasha has published a simple and well-known formula for making ink disappear.) When Natasha receives a piece of paper in the mail, she uses a second ingredient that makes Boris’s message reappear.
In this program, anyone can make messages invisible, but only Natasha can make them visible again. And because he never shares the formula for the second ingredient with anyone—not even Boris—he can be sure the message hasn’t been divulged along the way. When Boris wants to find secret messages, he simply takes the same procedure: He publishes a simple recipe to make the messages disappear (Natasha or anyone else can use them), while he keeps another one that makes them reappear.
In public-key cryptography, the “public” and “private” keys act as the first and second ingredients in 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 very difficult to reverse. But it also contains “trapdoors,” pieces of information that, if known, make jobs easier to combine in both directions.
One common trapdoor task involves multiplying two large numbers, an easy task to perform. But scaling back—that is, starting with a product and finding each key feature—is mathematically impossible. To create a public key, start with two large numbers. These are your doors. Multiply two numbers together, then do some additional math operations. This public key can now encrypt messages. To decrypt, you’ll need the corresponding private key, which contains the essentials—the necessary keys. With those numbers, it is easy to decrypt the message. Keep those two key features private, and the message will remain private.