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. Scramble your message using special rules that only you and your target audience know. This rule served as a key. If you have the key, you can unscramble the message. Otherwise, you will need to unlock it. some locks It’s so effective that even if you had infinite time and resources, you wouldn’t be able to choose it. But even these schemes suffer from the same Achilles heel that plagues all such cryptographic systems. It’s all about how to get the key into the right hands without giving it to the wrong person.
This is known as a counterintuitive solution. public key cryptographyrelies on making the key widely available rather than keeping it secret. The trick is to use a second key that you never share, even with the people you communicate with. It is only by using the combination of these two keys (one public and one private) that messages can be both scrambled and unscrambled.
To understand how this works, it’s easy to think of the “key” not as an object that fits into the lock, but as two complementary elements in invisible ink. The first element clears the message and the second element redisplays the message. If a spy named Boris wants to send a secret message to his counterpart Natasha, he will write the message and use the first element to hide it on the page. (This is easy for him; Natasha published a simple and famous formula for erasing ink.) When Natasha receives the paper in the mail, she applies the second ingredient, which reproduces Boris’s message.
In this scheme, anyone can hide messages, but only Natasha can show them again. And since she has never shared the formula for the second ingredient with anyone (not even Boris), we can be sure the message wasn’t deciphered along the way. When Boris wants to receive a secret message, he simply adopts the same procedure. He publishes a simple recipe for making the message disappear (which can be used by Natasha or anyone else), while keeping to himself another recipe for making the message appear again.
In public key cryptography, the “public” and “private” keys act like the first and second elements of this special invisible ink. One encrypts the message and the other decrypts the message. But instead of using chemicals, public key cryptography uses a mathematical puzzle called . Trap door function. These functions are easy to compute in one direction, but very difficult to compute in the opposite direction. But they also contain “trapdoors”, information that, if known, makes it easy to compute functions in both directions.
One common trapdoor function is to multiply two large prime numbers, and it’s easy to do. But reversing it, 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 two numbers and perform additional operations. mathematical operations. This public key now allows you to encrypt messages. To decrypt them, we need the corresponding private key, which contains the main element: the necessary trapdoor. Using these numbers, you can easily decipher the message. If we keep these two prime factors secret, the message will remain secret.
