When people think of encryption they usually think of what is known as
symmetric or private key encryption.
The simplest example of this is probably the Caesar
cipher, in which each letter is replaced by one a fixed number of
places away from it in the alphabet.
For example:
| Clear text | A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z |
| Cipher text | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z | A | B | C |
In this example, each letter is replaced by one three letters further along - HELLO WORLD becomes KHOOR ZRUOG. The key, which must be known by both ends, is 3. While the Caesar cipher is trivially reversible without the key, more complicated symmetric key algorithms are much more difficult to reverse. In many cases, no method that is substantially better than a brute force attack of trying all the possible keys is known.
The problem with private key encryption is that both ends must know the key before communication can take place. This implies that there is a secure channel to pass the key between the two ends. If a secure channel existed there would be no need for encryption in the first place.
In public key encryption there are two keys, a public key and a private key. A message encrypted with one of these keys cannot be decrypted with the same key - only the other key of the pair can decrypt it. A person's public key is, as the name implies, made public so that anyone can find out what it is. To send someone a message you encrypt it with their public key. Only the intended recipient, who knows the corresponding private key, can decrypt it. Senders don't need to know the recipient's private key, so there is no need for a secure channel to pass it to them.
Public key encryption also allows some measure of message authentication. If a person encrypts a message with their private key, then recipients can check that it came from the claimed sender by decrypting it with the sender's public key. If the message decrypts successfully then it must have been created by someone who knows the sender's private key - hopefully only the sender. See the sections on message digests and digital signatures for more details.
There are several methods, but the most commonly used one is known as RSA after the initials of its inventors. To generate a pair of keys the procedure is:
To encode a message we convert it into a numeric form and break it into groups of numbers. We then calculate the cipher text C for each group of numbers M as C = Mp mod N To decrypt the message we calculate M = Cs mod N Thus the keys are the integer pairs (N,p) and (N,s).
The security of a public key system depends on the fact that it is difficult to calculate the private key from the public key. In the system described above, it is necessary to factorise N to find x and y.
Factorising is believed to be difficult. For example, it is easy to calculate 101*113=11413, but far more difficult to find x and y such that x*y=11377. In 1995 a 116 digit number was factorised in about 400 MIPS years - i.e. a 400 MIPS computer running for one year, a 200 MIPS computer running for two years etc. Estimates of the time required for different sized keys are
| 512 bits | 30,000 MIPS years |
| 768 bits | 200,000,000 MIPS years |
| 1024 bits | 300,000,000,000 MIPS years |
| 2048 bits | 300,000,000,000,000,000,000 MIPS years |
A message digest is a value calculated from a message. For example, MD5, a popular digest function, calculates a 128 bit value based on the message contents. If you know what the message digest for a message should be, then it is possible to tell if the message has been tampered with - you compute the digest for the message you receive and if it doesn't match what the digest is supposed to be then the message has been altered. For this to work the digest function must have particular properties; most importantly it must be computationally infeasible to find a message which produces a particular digest. If this was not the case, it would be possible to substitute a message for the intended one without detection. It should also be difficult or impossible to find the message from the message digest.
A digital signature is a message digest encrypted with the author's private key, attached to the message. To authenticate a message, you compute a digest for it and compare it with the result of decrypting the attached signature with the purported author's public key. If they match, the reciever knows that the message came from the person it claims to have done - only the sender knows the private key which could produce a digest that decrypts with the public key - and that it hasn't been altered.
If you know a person's public key you can authenticate the person on the other end of a network connection. One way of doing this would be to generate a random string and pass it to the person on the other end. They encrypt it with their private key and send it back to you. If you decrypt the reply with the public key of the person you believe you are talking to and get back your original string, then the person on the other end of the connection must know the private key. The other end of the connection can authenticate you in a similar way.
The main difficulty with public key encryption is getting the public key of the person you want to communicate with. On a small scale, users can simply give their public keys to each other in person, but this is impractical on an internet-wide basis. One possible solution is for users to register their public keys in directories which can be queried. This approach has its own set of problems though. How do you know which directory the person you want to communicate is registered with? If there are only a few central directories they will rapidly become overloaded. If the directory service is down or unreachable you can't send a message, even though there may be nothing wrong with the network between you and the person you want to talk to.
The ideal solution would seem to be for the user to send you their public key as part of the communication, but this has a chicken and egg problem: you can't be sure that you're talking to the real user until you have their public key to perform some sort of authentication, but you can't trust that they're who they claim to be and are giving you the right public key until you can authenticate them. Suppose A is trying to communicate with B, but it's really C on the other end of A's connection. C could claim to be B but send C's public key. The challenge-response protocol would work exactly as above, but A would be talking to C instead of B.
The solution to this problem is to use certificates and certifying authorities.
A certificate is a message containing your public key, digitally signed by a trusted third party - the certificate issuer. To obtain a certificate you visit a certificate issuer with whatever form of identification they require. They produce a message which contains something like
| Name: | fred@foo.bar.edu |
| Public key: | AF43D921CB812FA7 |
and digitally sign it with their public key. When someone wants to communicate with you, you send them this certificate and, as long as they know the certifying authority's public key, they can check the signature on the certificate and extract your public key. It is not necessary to know the public key of every certifier, because certifiers can create certificates for other certifiers. For example, the departmental computing staff could get a certificate for their public key and then issue certificates to users signed with the department's key. The user would send a certificate chain to authenticate themselves - i.e. they would send the department's certificate, signed by the certifying authority, to tell the person on the other end what the department's key was, and their certificate, signed by the department, to tell the other end what their public key was.
Although the above sounds complicated, most of it can be handled automatically behind the scenes. Web browsers, for example, come with the public keys of the major certifying authorities compiled into them. If they receive a certificate signed by an authority they don't know about then, as long as that certificate is accompanied by another certificate signed by an authority they do know about that authenticates it, they can add the new public key to their list and authenticate users whose certificates have been signed by the new authority from then on.
Public key encrpytion is generally too slow to be used for extended exchanges, so once the ends of a connection have authenticated themselves to each other, a random symmetric key is generated and sent via public key encryption. This key is then used to encrypt the connection with a faster, symmetric cipher.
The E&EE IMAP servers provide authenticated, encrypted connections with certificates signed by the department. To use these certificates you must first accept the department as a Certificate Authority. Browse to http://www.see.ed.ac.uk/it/seecert.cacert and follow the instructions your browser provides. This certificate is self-signed - i.e. it is a certificate for the department signed by the department. This means that the certificate must simply be trusted - no one has signed it to confirm that the certificate is real. Most browsers will show you a certificate fingerprint, which you can check with us if you want to be sure. Once you have installed our CA certificate, your mail client will automatically trust certificates signed by the department.
Your mail client should be set up to use IMAP over SSL; otherwise it's just a normal mail server.
SSH also uses public key encryption but doesn't use certificates - the server sends its public key to the client when the connection is opened. This is vulnerable to spoofing as described above. To alleviate the problem clients can be given a list of public keys indexed by host. If the remote host isn't in the list the client will ask the user if they want to accept the key the server has sent.