Public Key Cryptography: Encryption, Signatures and Certificates

Public Key Cryptography is a technology that forms the basis of a strong form of data encryption, digital signatures, and digital certificates. This post attempts to explain—in broad strokes—how these technologies work.

Key Pairs

The engine that drives Public Key Cryptography is the "key pair". A key pair is basically a set of two numbers, each of which can be used to encrypt data. These keys are used in the same way that passwords are used by the more common type of encryption—secret key encryption.
Key pairs have 2 properties that make them very useful.

• Things encrypted with one key of the pair can only be decrypted by using the other key in the pair.
• It is exceedingly difficult to derive one key from the other. Doing so requires solving a problem known to be difficult in computer science (like for instance factoring large prime numbers).

One naive encryption scenario involves splitting a key pair between two people who want to communicate privately. When Alice wants to send a private message to Bob, she encrypts it with her key, and Bob uses his to decrypt. When Bob wants to reply, he encrypts with his key and Alice uses hers to decrypt.

Figure 1: Naive Encryption Scenario

Public Key Encryption

Public Key Encryption takes this scenario one step further. In Public Key Encryption, the idea is that every participant has their own pair of keys. But rather than treat both keys as secret (as in the naive scenario above), only one of the keys is secret. The other is considered to be Public—its owner disseminates it far and wide. This is safe to do because of the second property of key pairs—just because someone knows your public key does not give them an advantage in guessing what your secret key is.

Figure 2: Key Generation & Exchange

There are special kinds of internet servers that do nothing but serve as open clearinghouses of public keys.

If someone wants to send you a private message, they get your public key (either from a keyserver, or directly from you in an e-mail) and use it to encrypt the message. You then use your secret key to decrypt the message. For a message back to them, you grab their public key and encrypt with that. So all the encrypting is done with the public keys, and all the decrypting is done with the corresponding private keys.

Figure 3: Secure Data Transfer with PKC

There's one major benefit to doing encryption this way—you never need to send anything secret (like a password) over an insecure channel. Your public key goes out to the world—it's not secret and it doesn't need to be. Your private key can stay snug and cozy on your personal computer, where you generated it—it never has to be e-mailed anywhere, or read over the phone, snailed on a floppy, etc.

Compare old-style, Secret Key encryption, where both people communicating need to know the same password—in that case you've got to come up with some way of getting that password to your friend in such a way that it can't be intercepted. That is often problematic.

But wait—there's more. Since things encrypted with one key of a pair can only be decrypted by the other key, the owner of a key pair can also encrypt a message with their private key. Given that in theory at least, everyone in the world has your public key, and that any message encrypted with your private key can be decrypted by your public key, this is not a recipe for private communication—anyone at all can decrypt the message. So why would you do that?

Digital Signatures

You would do that to authenticate the message—to prove that it came from you. Any message decryptable with a given public key is sure to have come from the person holding the corresponding private key. So to the extent you can trust that a given public key really belongs to a particular person, you can be sure that such a message really did come from that person. This is the basis of Digital Signatures.

Typically, since you're not going for privacy when you digitally sign a message, there will be a plain text version of the message, followed immediately by an encrypted version. To verify the signature the encrypted version is decrypted, and that decrypted text is compared to the plain text version. If they match, you can be sure the message is authentic, otherwise the message is probably bogus—it either came from some other person entirely, or it was altered after being signed.

This is a huge benefit. All of a sudden, the formerly anonymous Internet can now support verifiable digital identities—so people and organizations who 'meet' on the internet can have a basis for trusting one another—they at least know who the other party is.

But consider that phrase above "to the extent you can trust that a given public key belongs to a particular person" . That's potentially a big problem for digital signatures. Key pairs are very easy to generate—free software for doing so is available on the internet. Just because a given public key has my name on it does not necessarily mean that I generated it. Furthermore, public keys are usually transmitted over insecure channels—like the internet—which excepting maybe public cell phone yelling is probably the least secure channel known to humankind. Thus, they are subject to hacking.

So how can you be assured that a given public key really truly belongs to Bob Friend, and not Emily Enemy?

There are 2 methods.

1. Give Bob a call and ask him to read his public key to you over the phone. This is tedious and annoying. More importantly, it assumes that you know Bob personally, know his phone number, and will recognize his voice. In many situations (described below) this is unrealistic.
2. If you have a friend in common with Bob (let's call him Tommy Trustworthy), whose public key you have and trust, and Tommy has a copy of Bob's public key, then you could get Tommy to digitally sign his copy of Bob's public key and send the signed copy to you. When it arrives, you verify Tommy's signature, and if it checks out, you're all set. In a sense, Tommy is vouching for Bob's identity.

The Web of Trust

This second method is the basis of something called "the web of trust". The idea amounts to a network of people vouching for each other. If everybody endorses the the public keys of everybody they know personally (by digitally signing those keys & registering their signature with an internet keyserver) then eventually we will build up a web of trust associations, from which I should be able to trust your key. I may not know you directly, but I know Fred, who knows Mary, who knows Chris, who knows you. The more people you can get to sign your key, the larger the group of people who will be able to use this system to verify your public key.
It's sort of like a digital security version of Six Degrees of Kevin Bacon.


Figure 4: Kevin's worked with everyone

This is also tedious, but it's usually less tedious than the first option—especially for people you don't know personally. Technical people understand this, and will go to the trouble. At computer conferences you will find geeks congregating in "key signing parties" where everybody gets together, proves their identities to one another (driver's licenses, passports, etc.) and signs one another’s keys.

But non-technical people generally won't do this. Being able to digitally sign things is just not that important to them. Nobody expects them to be able to do this, and nobody they know has a public key to sign.

Enter the Certificate Authority.

Imagine that, instead of a network of lots of little trusting geeks, we have one, big, super Tommy Trustworthy, who is willing to verify the identities of anyone and everyone, and after doing so, sign their keys for them.

Imagine that this Super Tommy has incredibly rigorous methods of identification. Super Tommy flies out to your location, talks to your friends and associates, and only if everything smells right does he sign your key. It's worse than applying for a mortgage. But Super Tommy and his identification methods are so well known that no matter who you are—if Tommy trusts that you are who you say you are, then the rest of the world will too.

Now, Super Tommy doesn't do all this out of the goodness of his heart—you've got to pay him to go to all this trouble. But it's worth it in order to get the enormous numbers of people who trust Super Tommy to trust you too (and to avoid having to hang out with all those geeks at the key signing party).

Super Tommy is trading on his reputation.

Digital Certificates

The role Super Tommy is playing is called a Certificate Authority—an entity that is in the business of manually authenticating and certifying people's identities, and providing them with the digital credentials to signify it. Your signed public key is now a Certificate—it's a public key that's been endorsed by a Certificate Authority. You can present this certificate to anyone, and they can verify Super Tommy's signature on it, and trust that you are who the cert says you are. "If you're good with Super Tommy, you're good with me."

Why would anyone go to this trouble?

If you are a company wanting to do business on the internet, you can take your company's certificate and install it on a web server, and thereby identify the web server as belonging to you. That way when someone goes to your web site to buy something, they can be sure that the site they are interacting with is actually yours—not some hackers' in Belarus.

That can go a long way toward making people comfortable entering their credit card numbers into your web site. And furthermore, it's a key requirement (pun intended) of the Secure Sockets Layer (SSL) technology. When you visit a website that lives on a server that has a Certificate installed (and that's using secured HTTPS) you get that reassuring little padlock icon at the bottom of your browser screen.

Figure 5: SSL-signifying padlock icon

That padlock tells you 3 things.

1. The site has presented your browser with a certificate.
2. The certificate has been signed by someone (some Certificate Authority) your machine is set up to trust.
3. The internet traffic in between your browser and the web server is being encrypted. (Both to and from the server).

To see the evidence of this, double-click the little padlock icon. You'll see a dialog box that lists the person or entity to whom the certificate was issued. That's who you sue if they do you wrong. The Certificate Authority who issued the cert can tell you where that person or entity can be found.

Figure 6: The Identity established by the Certificate

Figure 7: Certificate Authorities Short-circuit the Web of Trust; VeriSign = Super Tommy.

Notice how one-sided this is. You know that you're really dealing with Amazon.com, but how does Amazon.com know that they are really dealing with you? You don't have one of these fancy certificates to present. They don't! And in fact—they don't care. If you can produce a valid credit card number, expiration date, and that new code from the signature bar on the back of the card, they can bill the account. From there, any identity disputes are between you and Visa.

But what if a site did care about the identity of the people who used it? If you went to the trouble of obtaining a certificate of your own (these are generally referred to as "client-side" certificates) then there is a process for installing that cert on a particular machine, and associating it with a particular user account. If you do that, your browser would present the certificate to the web server on request, and the web site would 'know' who it was dealing with.

For instance, CRN's Secure File Transfer website requires that users have a client-side certificate, that Kaiser Northwest issues, so they can be sure that users aren't just sharing their username/passwords. You can share your username & password with someone else fairly easily, but it is much more difficult to share a certificate.

Conclusion

Public Key Cryptography is an important technology that forms the basis of several other important technologies. The engine that powers PKC is the "key pair"—a mathematically derived pair of numbers, each of which can decrypt messages encrypted with the other. Private communication can be ensured by using public keys to encrypt messages. Messages can also be digitally signed by including a private-key-encrypted version of the message along with the plain text version.

By linking public keys to real-world trust associations we can establish a "web of trust" through which digital messages can be tied to particular legal entities. Because of their good reputations for carefully authenticating PKC users, Certificate Authorities serve as large portions of the web of trust.