The unique model of this story appeared in Quanta Journal.
For hundreds of years, in the event you needed to ship a secret message, there was principally one approach to do it. You’d scramble the message utilizing a particular rule, identified solely to you and your supposed viewers. This rule acted like the important thing to a lock. Should you had the important thing, you may unscramble the message; in any other case, you’d want to choose the lock. Some locks are so efficient they will by no means be picked, even with infinite time and assets. However even these schemes endure from the identical Achilles’ heel that plagues all such encryption methods: How do you get that key into the precise arms whereas maintaining it out of the improper ones?
The counterintuitive resolution, often called public key cryptography, depends not on maintaining a key secret however slightly on making it broadly accessible. The trick is to additionally use a second key that you just by no means share with anybody, even the individual you’re speaking with. It’s solely by utilizing this mix of two keys—one public, one non-public—that somebody can each scramble and unscramble a message.
To know how this works, it’s simpler to think about the “keys” not as objects that match right into a lock, however as two complementary elements in an invisible ink. The primary ingredient makes messages disappear, and the second makes them reappear. If a spy named Boris desires to ship his counterpart Natasha a secret message, he writes a message after which makes use of the primary ingredient to render it invisible on the web page. (That is simple for him to do: Natasha has revealed a simple and well-known formulation for disappearing ink.) When Natasha receives the paper within the mail, she applies the second ingredient that makes Boris’ message reappear.
On this scheme, anybody could make messages invisible, however solely Natasha could make them seen once more. And since she by no means shares the formulation for the second ingredient with anybody—not even Boris—she may be certain the message hasn’t been deciphered alongside the way in which. When Boris desires to obtain secret messages, he merely adopts the identical process: He publishes a simple recipe for making messages disappear (that Natasha or anybody else can use), whereas maintaining one other one only for himself that makes them reappear.
In public key cryptography, the “public” and “non-public” keys work similar to the primary and second elements on this particular invisible ink: One encrypts messages, the opposite decrypts them. However as a substitute of utilizing chemical substances, public key cryptography makes use of mathematical puzzles known as trapdoor capabilities. These capabilities are simple to compute in a single course and intensely tough to reverse. However in addition they comprise “trapdoors,” items of data that, if identified, make the capabilities trivially simple to compute in each instructions.
One frequent trapdoor operate entails multiplying two giant prime numbers, a simple operation to carry out. However reversing it—that’s, beginning with the product and discovering every prime issue—is computationally impractical. To make a public key, begin with two giant prime numbers. These are your trapdoors. Multiply the 2 numbers collectively, then carry out some further mathematical operations. This public key can now encrypt messages. To decrypt them, you’ll want the corresponding non-public key, which comprises the prime components—the required trapdoors. With these numbers, it’s simple to decrypt the message. Preserve these two prime components secret, and the message will keep secret.
