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 one way to do it. You would encode the message using a special rule, which only you and your target audience know. This rule acted like a key to a lock. If you had the key, you could decrypt the message; Otherwise, you will have to pick the lock. some locks They are so effective that they can never be selected, even with infinite time and resources. But even those schemes suffer from the same Achilles’ heel that plagues all encryption systems: How do you get that key into the right hands while keeping it out of the wrong hands?

The counterintuitive solution, known as public key cryptographyIt is not based on keeping a key secret but on making it widely available. The trick is to also use a second password 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 encrypt and decrypt a message.

To understand how this works, it is easiest to think of “keys” not as objects that fit in 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 a secret message to his counterpart Natasha, he writes a message and then uses the first ingredient to make it invisible on the page. (This is easy for him: Natasha has published an easy and well-known formula to make the ink disappear.) When Natasha receives the paper in the mail, she applies the second ingredient that makes Boris’s message reappear.

In this scheme, anyone can make messages invisible, but only Natasha can make them visible again. And since she never shares the formula for the second ingredient with anyone (not even Boris), she can be sure that the message hasn’t been 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 anyone else can use), while saving another just for himself that makes them reappear.

In public key cryptography, the “public” and “private” keys function the same as the first and second ingredients of this special invisible ink: one encrypts the messages and the other decrypts them. But instead of using chemicals, public key cryptography uses mathematical puzzles called hatch functions. These functions are easy to compute in one direction and extremely difficult to reverse. But they also contain “trap doors,” bits of information that, if known, make functions trivially easy to compute in both directions.

A common trapdoor function involves multiplying two large prime numbers, an easy operation to perform. But reversing it (i.e. 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 trapdoors. Multiply the two numbers and then do some additional operations. mathematical operations. This public key can now encrypt messages. To decrypt them, you will need the corresponding private key, which contains the prime factors – the necessary trapdoors. With those numbers, it is easy to decipher the message. Keep those two prime factors secret and the message remains secret.