[Techie] How Does Public Key Encryption Work?

Your bank says all your online transactions are safe. They prove it by showing this little icon in your browser:

So how do they keep the information safe? The answer is something called Public Key Encryption. The details of how it's done can be very complex, but the concept behind it is surprisingly simple.

Imagine I go to the hardware store today and buy a padlock. It's the kind you might buy for your gym locker, but this one is just slightly different. It has two keys instead of one. And the way it's designed, if the padlock is locked with one of the keys, it can only be unlocked by the other, and vice versa. So, let's call the keys A and B. If I lock the padlock with A, I can only unlock it with B. If I lock it with B, I can only unlock it with A. If I lock the padlock with A, I can't even unlock it with A. It only works if both keys are used. This is the mechanism behind Public Key Encryption. The magic is in how it's implemented.

So, what could I do with this crazy lock? Well, one thing I could do is set up a secure mailbox. For example, I could keep key A and give key B to my colleague. Then if I ever wanted to pass a confidential note, I could put it in the mailbox and lock it with A. I'll know that only my colleague can open it, because only he has key B. He could send me a note the same way. One of the problems with this implementation is that I'm going to have to create a key pair for everyone that I want to have secure communication with. Another problem is that I can't ensure the integrity of key B. For all I know, my colleague has created 100 copies of key B and is leaving them in insecure locations all over the place. If someone else gets hold of key B, I have to buy a new lock and key pairs.


Authentication and One-Way Encryption

So how about this: I take key A (or key B, it doesn't really matter), and I put it in my pocket. That is now my private key. No one even gets to look at it except me. Then I make 100 copies of the other key (my public key) and give them out to all my work team. Now I have security in either direction, but not both:

• I can put information in my locker (say, this week's work assignments) and lock it with key A, then anyone on my team (with key B) can get into that locker and get the information. The receiver of the information can be assured that I am the one who put the information in the locker, since I'm the only dude with key A. This is a form of authentication.
  
• Working in the other direction, anyone on my team can put a private message for me in the locker and lock it with key B, knowing that I'm the only person who can unlock the padlock, since I'm the only guy with key A. In information security terms, this serves the same function as encryption, since the information cannot be seen by others from the time it's locked until the time I unlock it.

Two-Way Authentication and Encryption

Now imagine that I modify the locker so that it can be secured with two locks. Each of my colleagues has their own version of the fancy padlock and their own pair of keys. We all have our own private key and we all have copies of each other's public keys. Now, if I want secure, authenticated two-way communication with any of my colleagues, all I have to do is lock the locker with my private key and with their public key. I can be assured that no one can get to the information except the intended recipient, and the recipient can be assured that no one could have sent the information but me. In addition, we can both be assured that no one else was able to get to the information from the time the locker was locked to the time it was opened.

Now the only problem is scalability. What if my team consists of hundreds or thousands of people? Am I going to have to create a new copy of my public key every time I meet someone I want to share information with? How am I going to manage if someone loses their private key and has to re-create their key pair? What about if I lose my private key? Am I going to have to create a thousand new copies of my public key and run around handing them out?

How about this: What if there's a single person that everyone trusts who will take on the job of keeping everyone's public key in a central place?


Now all I have to do is go to the trusted keymaster (or Public Key Server) to get anyone else's public key. My private key is still my own responsibility, but now whenever I create a new one, I just have to give my new public key to the keymaster. A system which involves a number of encryption partners and a Public Key Server is referred to as a Public Key Infrastructure (PKI).

This is Public Key Encryption in a nutshell. Of course the devil is in the implementation details. Web servers use a form of Public Key Encryption called Secure Sockets Layer (SSL). Email encryption uses something called Pretty Good Privacy (PGP), among other things. Network encryption uses something called IPSec. Each of these technologies implements Public Key Encryption in a unique way and uses unique terminology to describe what are essentially the same functions.


Secure Sockets Layer (SSL)

That little lock icon at the bottom of your browser window indicates that you have connected to a server using SSL, that the server has been identified, and that your communications are being encrypted. SSL uses the term "certificate" instead of "key," but the function is pretty much the same. Your browser, when connecting to an SSL server, first connects to a "Certificate Authority" (CA) (the keymaster, or Public Key Server) to verify the server's identity before proceeding with the SSL encryption methods. You can view some of these CAs in Internet Explorer by clicking Tools -> Internet Options -> Content -> Certificates.


After verifying the server's certificate, the client uses that certificate to send an encrypted request to the server to agree how to encrypt the rest of the communication. This is kind of like using the locker in the earlier illustration to pass a secret decoder ring from one person to another. The locker is used as a rudimentary way to pass the information which is used to do the actual encryption.

However, notice that the first step is really a one-way encryption. The client gets a copy of the server's key (certificate), but the server doesn't have a copy of the client's certificate. So the first step is really only to authenticate the identity of the server and provide a brief window of encrypted communication to decide how the real two-way encryption will work. It's a subtle but important distinction.


Pretty Good Privacy (PGP)

PGP works almost exactly like the locker illustration, and was one of the first widely-implemented consumer-grade versions of Public Key Encryption. It was first released in the wild by a guy named Phil Zimmermann in 1991 and was free for anyone to use for a long, long time. It was considered so secure that the U.S. government labelled the technology a "munition" and made it against the law to export the software overseas. Eventually, the software was purchased by some company and now it's not free anymore. But the same technology is still out there for free, going by the name of GNU Privacy Guard (GPG) (get it?).


IPSec

IPSec is an implementation of Public Key Encryption that allows private networks to encrypt data that flies across an untrusted network (such as the Internet). For example, a company that has offices in New York and San Francisco may create an IPSec connection using their existing Internet connections rather than install a very expensive private connection. This technology works similar to the SSL technology in that the partners use their keys to decide how to encrypt their data. In this case, however, the initial communication is encrypted both ways, usually using a Certificate Authority (public or private). IPSec is becoming more widely used, since the Internet is increasingly reliable, ubiquitous, and cheap. IPSec is now built into Microsoft's operating systems for securing communication between hosts.


Links for further reading:
What is public-key encryption?
What is SSL?
How does SSL work?
PGP Corporation
What is IPSec?
IP Security protocol suite