The simple mathematics behind public key cryptography

The original version to This story Featured in Quanta Magazine.

For thousands of years, if you wanted to send a secret message, there was only one way to do it. You can encrypt the message using a special rule, known only to you and your target audience. This rule was like a key to the lock. If you have the key, you can decrypt the message; Otherwise you will need to unlock. Some locks They are so effective that they can never be chosen, even with unlimited time and resources. But even those schemes suffer from the same weakness as all these encryption systems: How can you get this key into the right hands while keeping it out of the wrong hands?

The unintuitive solution, known as Public key encryptiondepends not on keeping a key secret but on making it widely available. The trick is also to use a second key that you never share with anyone, even the person you’re communicating with. Only using this combination of two keys – one public and one private – can anyone encrypt and decrypt the message.

To understand how this works, it’s easier to think of “keys” not as things that can be put in a lock, but as two components integrated in invisible ink. The first item makes messages disappear, and the second makes them appear again. If a spy named Boris wanted to send his counterpart Natasha a secret message, he would write a message and then use the first component to make it invisible on the page. (It’s easy for him to do: Natasha has published an easy, well-known formula for making the ink disappear.) When Natasha receives the paper in the mail, she applies the second ingredient that makes Boris’s letter appear again.

In this scheme, anyone can make messages invisible, but only Natasha can make them visible again. And because she never shared the formula for the second component with anyone — not even Boris — she can be sure that the message wasn’t deciphered along the way. When Boris wants to receive secret messages, he simply adopts the same procedure: he posts an easy recipe to make the messages disappear (which Natasha or someone else can use), while keeping another recipe just for himself that makes them appear again.

In public key cryptography, the “public” and “private” keys act just like the first and second components of this invisible private 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 they also contain “hidden doors,” bits of information that, if known, make it easier to calculate functions in both directions.

A common trapdoor function involves multiplying two large prime numbers, which is an easy process to perform. But the opposite, starting with the sum and finding each prime factor, is mathematically impractical. To create a public key, start with two large prime numbers. These are your trapdoors. Multiply the two numbers together, then do more Arithmetic operations. This public key can now encrypt messages. To decrypt it, you will need the corresponding private key, which contains the necessary primitives – trapdoors. Using these numbers, it becomes easy to decrypt the message. Keep these two key factors secret, and the message will remain confidential.