Crash course on cryptography: Public key cryptography

In order to decrypt a message, Bob (the recipient) has to know the key. However, it may be difficult for Alice (the sender) to tell Bob what the key is. If they simply agree on a key by e-mail for example, Eve could be listening in on their e-mail conversation and thus also learn what the key is. Public key cryptography was invented to solve this problem.

The basic principle

Public keys and private keys

When using public key cryptography, Alice and Bob both have their own key pairs. A key pair consists of a public key and a private key. If the public key is used to encrypt something, then it can be decrypted only using the private key. And similarly, if the private key is used to encrypt something, then it can be decrypted only using the public key. It is not possible to figure out what the private key is given only the public key, or vice versa.

This makes it possible for Alice and Bob to simply send their public keys to one another, even if the channel they are using to do so is insecure. It is no problem that Eve now gets a copy of the public keys. If Alice wants to send a secret message to Bob, she encrypts the message using Bob's public key. Bob then takes his private key to decrypt the message. Since Eve does not have a copy of Bob's private key, she cannot decrypt the message. Of course this means that Bob has to carefully guard his private key. With public key cryptography it is thus possible for two people who have never met to securely exchange messages.

Combining public key and secret key cryptography

A problem with public key cryptography is that it is very slow. Encrypting a message that is several megabytes long takes a very long time, much longer than when using secret key cryptography. For this reason few people use only public key cryptography. What Alice usually does is encrypt the message using a secret key encryption algorithm and a key she made up on the spot. She then encrypts this key (called the session key) using Bob's public key. Bob can then obtain the session key by decrypting it using his private key. And with the session key he can decrypt the message. This way a long message is encrypted very quickly and Alice can still send it to Bob without needing a secure way of agreeing on the key.

How public key cryptography works

Public key cryptography systems are usually based on the assumption that a particular mathematical operation is easy to do, but difficult to undo unless you know some particular secret. This particular secret that serves as the private key. The two most famous public key cryptography systems are Diffie-Hellman and the RSA system, named after its inventors Rivest, Shamir and Adleman. More recently public key cryptography based on so-called elliptic curves has gotten a lot of attention.

Using public key cryptography it is possible to easily encrypt a message for multiple recipients. It is even possible to later authorize recipients to read the message. The message is simply encrypted with a session key. The session key is encrypted multiple times, once for every recipient using his public key. If later another recipient needs to be added, the session key is simply then also encrypted using his public key. Every recipient can now decrypt the session key independently from every other recipient.

Applications of public key cryptography

Secure Web communication

One important application of public key cryptography is encrypted communication with a Web server. This enables Alice to securely place an order and to transmit her credit card details. Alice's Web browser generates a random number which will be used to encrypt all communication with the server using secret key cryptography. The browser obtains a copy of the public key of the server and uses this public key to encrypt this random number (called the session key). The result is sent to the server. After that, browser and server can encrypt all information so that Eve cannot read it.

Alternatively, it is the server that generates the session key. This requires that the browser sends its own public key to the server so that the session key can be transmitted securely. This makes it easier to upgrade the hardware or software that generates the session key.

Secure content distribution

Content such as music or video can be distributed in encrypted form. To be able to play it back, the recipient needs the decryption key. To avoid having to encrypt the entire movie or song again for every recipient, the content is encrypted with a session key. Every recipient receives the encrypted content together with the session key. The session key is of course encrypted using the recipient's public key. This way only a very small amount of data needs to be encrypted again for every recipient.

It is even possible to distribute the encrypted content in advance. If the recipient wants to play back the content, he can at any time contact the distributor and obtain (purchase) a copy of the session key encrypted using his public key. This is sometimes called 'superdistribution'.

All parts