Digital Certificates

Cryptography literally means "the art of secret writing". It allows two people, commonly known as Alice and Bob, to communicate with each other securely. This means that an eavesdropper, referred to as Eve, will not be able to listen in on their communication. Cryptography also enables Bob to check that the message sent by Alice was not modified by Eve and that the message he receives was really sent by Alice.

Public key and secret key cryptography

There are two major classes of cryptographic systems. The first is called secret key encryption. These systems use a single key, which Alice and Bob both must know. They must keep it a secret (hence the name) from Eve, otherwise Eve will be able to decrypt any messages encrypted using that key.

The second class is called public key encryption. In these systems Alice and Bob both have a key pair, not just a single key. Every pair consists of a public key and a private key. Alice and Bob can freely tell each other what their public keys are, and Eve is allowed to obtain a copy of their public keys. Using Bob's public key Alice can encrypt messages to Bob. Bob can then only decrypt those messages using his private key.

Secret key cryptography

Secret key cryptography uses a single key which both parties (usually named Alice and Bob) both must know. They must keep this key a secret (hence the name) from an eavesdropper (named Eve), otherwise Eve will be able to decrypt any messages encrypted using that key.

Alice uses a secret key encryption scheme (or cryptographic algorithm) to transform a message into something resembling random noise. The scheme may be publicly known. The security of the system comes from the secret key that Alice uses. The transformation can only be undone by Bob and Alice herself, since only they know the secret key.

Encryption and decryption using a secret key

To secretly communicate with Bob, Alice encrypts her messages before sending them. There are many techniques (cryptographic algorithms) that she can use. All these algorithms have in common that they can transform a message using a key into something that resembles random noise. This is called encrypting the message. Only the persons who know the key can transform the random noise back into the original message, or in other words, decrypt the message. This means that those persons must keep this key a secret, hence the name secret key cryptography.

How to get the key to the recipient

A fundamental problem with secret key encryption is that somehow the secret key has to be delivered to the recipient of the message in a secure way. Once that key has been securely delivered, other keys can be delivered by simply encrypting them with that first key. One way to solve this problem is to have Alice and Bob meet in person so they can agree on a key. They must make sure that Eve is not listening in on them, otherwise Eve also learns the key. This applies especially if Alice and Bob agree on a key via telephone or e-mail. Of course Bob must also be able to distinguish Alice and Eve if they meet for the first time (for Alice it shouldn't be a problem to tell Bob from Eve).

If Alice and Bob can not meet in private to agree on the key, it is very difficult for them to use secret key cryptography. 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. If Alice and Bob had a secure channel that Eve could not tap, they could use that channel to agree on a secret key. However, then they could also use the secure channel to simply transmit their messages.

This problem is solved by using public key cryptography, which is discussed in the next chapter.

How secret key cryptography works

Secret key cryptography transforms (scrambles) a message into something resembling random noise. The precise transformation is determined by the key. Mathematically seen, a cryptographic algorithm is a function that maps a message onto a ciphertext (an encrypted message). By using keys, it is possible to encrypt many different messages using one particular cryptographic algorithm in different ways. And keeping the key a secret is much easier than keeping a complete algorithm a secret.

Some cryptographic algorithms operate on single characters of the message. These are called stream ciphers. Others operate on entire blocks, and therefore are called block ciphers. Stream ciphers are easier to implement in hardware than block ciphers, and they are also generally faster. Block ciphers tend to be harder to crack.

Public key cryptography

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.

What is cryptography used for

Cryptography has many practical applications, in particular for electronic communication on the Internet. Alice and Bob can of course encrypt the e-mail messages they exchange. They can also encrypt live communication sessions such as remote logins or chat sessions. In such applications typically every character or sentence Alice enters is encrypted and transmitted as a separate message over an insecure channel. Cryptography is also often used to protect Web transactions and other e-commerce applications. For example, many e-commerce sites use SSL encryption to protect confidential transmissions (which can be seen from the 'https' URL or the little lock in the browser window).

Another popular application is securely logging into remote systems. Traditional methods, such as Telnet, are not secure. Using an application like Secure Shell (ssh) the connection to a remote host is encrypted, making it impossible for third parties to 'tap' the connection.

The basic principle

Alice needs a copy of Bob's public key to encrypt messages to him using public key cryptography. And Bob needs Alice's public key to verify any digital signatures on Alice's messages. Both must be sure that they have the right public key. This is where digital certificates come in.

Digital certificates are messages that couple an identity to a public key. They are signed by the person or authority that created them. If Bob trusts that authority, he can be sure that certificates issued by that authority are genuine and so he can check that he really has Alice's public key.

An important aspect of public key cryptography is that Alice and Bob must be convinced that they have the right public key of each other. Eve could have substituted her own public key for Bob's, and then Alice would be encrypting messages intended for Bob in a way that Eve could read them. Eve could then encrypt them again with Bob's real public key so that he would not notice Alice has the wrong public key. If Eve does the same the other way around, all communication between Alice and Bob can be read by Eve and neither of them knows it!

Alice and Bob could of course meet in person or call each other over the phone to verify that they have the right public keys. This is often impractical, and Alice and Bob might not even know each other. For example, Alice could own a Web store and use public key encryption so that her customer Bob can securely send her his credit card details. Now if Bob tries to call Alice, how can he possibly know that he's talking to Alice and not to Eve?

The use of digital certificates solves this problem. Next to Alice, Bob and Eve, there is now also a trusted third party, usually called Trent because that name also starts with a T. if Alice wants to have Bob's public key, she will go to Trent to ask for a copy. Trent will then send her a message containing details of Bob's identity and Bob's public key. This message, called the certificate for Bob's public key, is signed by Trent. Alice now verifies that the digital signature is correct using Trent's public key. If this is the case, she knows that she has Bob's real public key and she now also knows that Bob is called Bob.

Eve is now no longer able to impersonate Bob by giving Alice a public key pretending it is Bob's. Since this public key is not signed by Trent, Alice will not accept it. And Alice is sure that Trent checked Bob's passport or driver's license before making the certificate.

Of course Eve might now try to pretend that she is Trent. If she can pull this off, she can listen in on everybody's communication! To prevent this, Alice should make sure that she really has Trent's public key. This should be quite easy. Trent could be a government agency or a notary public, and so she can simply visit Trent and take a copy of this public key home with her. She only has to do this once and then she can securely communicate with everyone else who visited Trent and had him make a certificate.