The Genius of Public Key Cryptography
AKA why the lock icon in your browser address bar is so important
You’re in a room full of people, and you need to pass a secret message to a stranger you’ve never met before, and neither of you know anything about the other. Any message you send can be seen by every person in the room. Is it possible to encode your secret message to this stranger without anyone else in the room being able to decipher it?
This is exactly the sort of problem your computer needs to overcome when you send sensitive information to a website on the internet. Imagine you’re buying a shirt on Amazon. Your computer sends a message to Amazon’s server with your credit card info, but there’s no guarantee that there aren’t people in the middle that can read the message that’s sent. For instance, anyone on your same WIFI network can watch all the traffic you send, or a hacker who has access to any router on the internet that your traffic passes through can see it as well. Also, how can you even tell the server you’re talking to is really Amazon? A hacker could set up a phony wifi hotspot that not only allows them to see what you’re sending, but even redirect it to entirely different servers! If you can’t find a way to transit this info securely then you might be leaking your credit card info to hackers, compromising your entire account, or worse!
Fortunately, there is a solution to this problem in the form of public key cryptography, and all security on the internet is built on top of these ideas. Public key cryptography is an ingenious solution that makes it possible to send your credit card info to Amazon’s server, while being guaranteed that only Amazon can decipher the message and read your credit card number. Furthermore, it also makes it possible to guarantee that the server you’re talking to is really Amazon, and not an impostor.
The secret sauce
In the past all cryptography depended on being able to pass on some hidden secret to the person you wanted to message in advance, like meeting up with them in a shady alley and giving them an envelope with secret codes on them. If you imagine the German Enigma machines in World War II, this is how the cryptography there worked - you would pass out codebooks in advance containing secret keys that only you and the person you’re message know, and use them to encrypt and decrypt your secret messages. But what if you can’t share a secret code with the person you want to message in advance?
The insight that solves this problem is called public key cryptography, and it works off the idea that there are some mathematical operations that are really easy to do in 1 direction, but doing the inverse is computationally extremely difficult, to the point of being nearly impossible.
An example of this sort of operation that’s commonly used in cryptography is the problem of finding prime factors. You may remember from high school algebra class that you can always decompose any non-prime number into a series of prime numbers that are multiplied together, for example the number 35 can be decomposed into the prime numbers 7 x 5. The interesting property of prime factorization is that while it’s easy for computers to find 2 large prime numbers and multiply them together, it’s extremely slow to do the reverse and find the prime factors of a large number. When we say large numbers, we’re talking about numbers like the following:
32317006071311007300714876688669951960444102669715484032130345427524655138867890893197201411522913463688717960921898019494119559150490921095088152386448283120630877367300996091750197750389652106796057638384067568276792218642619756161838094338476170470581645852036305042887575891541065808607552399123930385521914333389668342420684974786564569494856176035326322058077805659331026192708460314150258592864177116725943603718461857357598351152301645904403697613233287231227125684710820209725157101726931323469678542580656697935045997268352998638215525166389437335543602135433229604645318478604952148193555853611059596230656
Using this idea we create a set of 2 keys, key A and key B, that are inverse of each other based on these prime factors. Anything that’s encrypted with key A can only be decrypted with key B, and vice-versa. (If you’re curious for the details about how this works, check out this amazing video from Computerphile)
One of these keys, say key A, you then publish to the world so everyone can see it, but you keep key B completely secret. Key A is called your public key, since it’s public, and key B is called your private key, since it’s kept hidden. The person you want to communicate with does the same thing.
Sending a message securely requires that nobody can read the message except the intended recipient, and that the recipient can be sure the message really came from you.To accomplish this, we encode the message twice. You can think of this like putting the message inside 2 nested boxes, each of which can only be opened with a specific key that either you or the target recipient know.
For the first box, you encrypt the message with your private key. This means that it can be decrypted with your public key. Everyone knows your public key since you make it public. What’s the point then? If a message can be decrypted with your public key, that means it must have been encrypted with your private key. Since only you know your private key, the message thus is guaranteed to have come from you!
At this point, anyone on the internet can still open the box and read the message, not just the intended recipient. The next step is to now take the message you just encrypted with your private key and then encrypt it again with the recipient’s public key. This is like placing the box into another box that only the intended recipient can open. At this point the message is completely secure, since it can only be decrypted by your target recipient’s private key, which only they have.
When the recipient receives your message, they’ll use their private key to decrypt and open the outer box, then they’ll use your public key to decrypt and open the inner box. You can both be guaranteed that the message can only be viewed by the intended recipient, and that it came from where it was expected to have come from!
That tiny lock icon in your browser
The technique we just described above is implemented in your browser and is what it uses when communicating secure data to websites. On the web, you’ll sometimes see the URL start with `https://` and sometimes it will start with `http://`. The difference is that the `S` at the end of `HTTPS` stands for `secure` and means that your browser is using the encryption technique we talk about to ensure that all the communication between your browser and the server is encrypted and secure. In an ideal world, all websites would implement this, but sadly not all do still. If you don’t see a lock icon in your browser, or if the URL for the website starts with `http://` instead of `https://`, then the communication between your browser and the website is happening in plain text, and can be easily read by anyone on your network, or who is able to watch the communication between your computer and the server!
Why does this matter to me?
If you create a product that communicates over the internet, you need to make sure you have encryption set up for all connections. This is typically referred to as SSL or HTTPS, and involves creating public and private keys for your server to prove who you are and encrypt the connection. Fortunately, most hosting providers today make this extremely easy, and many will even do it for you automatically. However, if you neglect this, you will be putting all communication between your users and your server at risk! Without using encryption, there’s nothing stopping all of the data sent and received by your server from being stolen, or for a hacker to set up another server pretending to be yours that communicates with your users instead of you!
Thankfully, you should never have to code any encryption algorithm yourself. 99.9% of engineers will never have to implement any kind of cryptographic encryption from scratch. This is because this part of an application (secure data transmission) is so important, that we as engineers really can't trust ourselves implementing it and risk making a mistake. So we rely on standard battle-tested libraries that we can be confident will work correctly and securely.