How does public key encryption work?

Public key encryption is briefly explained in the first post of this series, here, but it is of such importance in SSL/TLS and SSH that a more detailed explanation is necessary.

Public key encryption, or asymmetric encryption, is a special class of algorithms that uses two separate but related keys, the keypair. One key, known as the private key, is kept secret, and the other key, the public key, is made widely available. Typically, the public key is used to encrypt data, and the private key is used to decrypt data, but they can also be used in reverse.

The advantage of a public key encryption system is this: secret messages can be sent to anyone who has published their public key, and only the recipient will be able to decrypt the message. So as long as their public key can be trusted to be theirs (an important caveat!), a secure system for exchanging secret messages can easily be set up. Each party can publish their public key and send secret messages to the other using the other's public key. They use their own private key to decrypt messages that they receive.

But doesn't publishing the public key make encrypted messages more vulnerable to unauthorized decryption? No, it is not practically possible to derive the private key of a keypair from the public key, and without the private key, the ciphertext can not be decrypted. So publishing the public key does not make it easier to decrypt messages encrypted by the public key.

RSA and Diffie–Hellman were the earliest public key algorithms. For a long time it was thought they were invented in 1976/1977, but when secret GCHQ research was declassified in 1997, it turned out they had been independently conceived of a few years earlier. ElGamal and DSS are other well-known public key algorithms.

There are a number of important uses of public key encryption.

Key distribution

Symmetric encryption uses a single secret key that both parties require, and ensuring that this secret key is securely communicated to the other party is difficult. This is known as the key distribution problem.

As our first post noted, public key encryption is ideally suited to solve this problem. The receiving party, who requires the sender's secret symmetric key, generates a keypair and publishes the public key. The sender uses the receiver's public key to encrypt their symmetric key, and sends it to the receiver. Now, both sender and receiver have the same secret symmetric key, and no-one else does as it has never been transmitted as cleartext. This is often known as the key exchange.

An obvious question is to ask why not use public key encryption for everything, and avoid having to send a secret key altogether? It turns out that symmetric encryption is orders of magnitude faster at encryption and decryption. So it is much more efficient to use public key encryption to distribute the symmetric key, and then to use symmetric encryption. Fortunately, it is computationally easy to generate a keypair for this purpose.

Digital signatures

Public key encryption is an important component of digital signatures. A message can be signed (encrypted) with a user's private key, and anyone can use their public key to verify that the user signed the message, and that the message was not tampered with. Digital signatures are explained in more detail in the next post in this series.

Certificate authorities

A critical requirement for a system using public key encryption is providing a way of reliably associating public keys with their owners. There is no value in being able to use someone's public key to encrypt a message intended for them if it can't be determined that it really is their public key. This is what certificate authorities are for, and both they and certificates will be explained in a subsequent post.