original version Of this story appeared in quanta magazine,
For thousands of years, if you wanted to send a secret message, there was basically only one way to do it. You will scrub the message using a special rule, known only to you and your intended audience. This rule worked like a key to a lock. If you had the key, you could open the message; Otherwise, you will have to open the lock. some locks They are so effective that they can never be selected, even with infinite time and resources. But those schemes also suffer from the same weakness that plagues all such encryption systems: How do you get that key into the right hands while keeping it out of the wrong hands?
The counter-intuitive solution, known as public key cryptographydepends not on keeping a key secret but 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 scrape and open a message.
To understand how this works, it's easiest to think of the “keys” not as objects that fit into a lock, but as two complementary materials in an invisible ink. The first component 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 component to make it invisible on the page. (This is easy for her to do: Natasha has published an easy and well-known formula for making ink disappear.) When Natasha receives the paper in the mail, she applies the second ingredient that causes Boris's message to reappear. Is.
In this scheme, anyone can make messages invisible, but only Natasha can make them visible again. And because she never shares the formula for the second ingredient with anyone – not even with Boris – she can rest assured that the message hasn't been understood along the way. When Boris wants to get secret messages, he simply follows the same procedure: he publishes an easy recipe for making the messages disappear (which Natasha or anyone else can use), while keeping another one only for himself. Due to which they reappear.
In public key cryptography, the “public” and “private” keys work just like the first and second stuff 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 functionThese functions are easy to calculate in one direction and extremely difficult to calculate in the opposite direction. But they also contain “traps”, pieces of information that, if known, make it easier to calculate actions in both directions.
A common trapdoor function involves multiplying two large prime numbers, which is an easy operation to execute. But reversing it – that is, starting with the product and finding every prime factor – is computationally impractical. To create a public key, start with two large prime numbers. These are your traps. Multiply both numbers together, then do some addition mathematical operationsThis public key can now encrypt messages. To decrypt them, you will need the corresponding private key, which contains the prime factor-required trapdoor. With those numbers, it is easy to decrypt the message. Keep those two key factors secret, and the message will remain secret.