The simple math behind public key cryptography

The original version of this story appeared in Quanta Magazine.

For thousands of years, if you wanted to send a secret message, there was basically a way to do it. You can scramble the message using a special rule, known only to you and your intended audience. This rule acted as the key to a lock. If you have the key, you could unscramble the message; otherwise, you need to pick the lock. Some closed they are so effective that they can never be chosen, even with infinite time and resources. But even those schemes suffer from the same Achilles’ heel that plagues all encryption systems of such 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 encryptionit 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, even the person you are communicating with. It is only by using this combination of two keys – one public, one private – that someone can decrypt and unscramble a message.

To understand how it works, it is easier to think of the “keys” not as objects that fit into a lock, but as two complementary ingredients in an invisible ink. The first ingredient makes the messages disappear, and the second makes them reappear. If a spy named Boris wants to send his counterpart Natasha a secret message, he writes a message and then uses the first ingredient to make himself invisible on the page. (This is easy for him to do: Natasha published an easy and well-known formula for the ink to disappear.) When Natasha receives the card in the mail, she applies the second ingredient that makes Boris’s message reappear.

In this scheme, anyone can make the messages invisible, but only Natasha can make them visible again. And because she never shared the formula for the second ingredient with anyone, not even Boris, she can be sure that the message was not deciphered along the way. When Boris wants to receive secret messages, he simply uses the same procedure: he publishes an easy recipe to make the messages disappear (which Natasha or someone else can use), while he keeps another one just for himself that makes them reappear.

In public key encryption, the “public” and “private” keys work as the first and second ingredients in this special invisible ink: One encrypts the messages, the other decrypts them. But instead of using chemicals, public key cryptography uses so-called mathematical puzzles trap functions. These functions are easy to calculate in one direction and extremely difficult to reverse. But they also contain “trapdoors”, pieces of information that, if known, make 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 the inversion – that is, starting with the product and finding each prime factor – is impractical in calculation. To make a public key, start with two large prime numbers. These are your trapdoors. Multiply the two numbers together, then perform some addition mathematical operations. This public key can now encrypt messages. To decrypt them, you need the corresponding private key, which contains the main factors – the necessary trapdoors. With these numbers, it is easy to decrypt the message. Keep these two main factors secret, and the message will remain secret.