Public key cryptography is one of the fundamental technologies used for exchanging information on the Internet securely. It’s used by Web browsers to create secure connections to Web sites, and by e-mail security gateways and applications to encrypt messages. Its strength lies in the fact that it can be used to exchange encrypted information between two parties that have never communicated together before and have therefore never agreed on a secure way of exchanging messages.
To understand how public key cryptography works, let’s consider secure communications in general. One way to send a confidential message to someone is to agree on an obfuscation system in advance—like substituting each letter in the message with the next one in the alphabet.
A more sophisticated method would be to use encryption software which uses an encryption algorithm, known as a cipher. The message (known as plaintext ) is entered and passed to the algorithm along with a key—a string of characters that you supply—comes out in encrypted form (known as ciphertext.) This unintelligible jumble of characters can only be converted back to the original plaintext by passing the message through the same cipher and supplying the same key. This is known as a symmetric encryption system.
An interesting thing about this system is that its security doesn’t rely on the cipher itself being secret. The only thing that needs to be kept secret is the key. (In fact you could argue that the more widely known and understood a cipher is, the more you can trust it to be effective—proprietary algorithms that aren’t open to public inspection by independent experts could have secret “backdoors” built in that allow anyone in the know to decrypt messages without the key.)
One problem with symmetric systems is that to send someone a message securely you have to be able to give them the secret key first without anyone else seeing it. Why is that a problem? Imagine a situation in which you were traveling abroad and had to e-mail some valuable corporate information back to a colleague without the authorities in the country you are in getting their hands on it. If you hadn’t already agreed on a key before you went traveling then you’d be stuck: you couldn’t send an encrypted message without first supplying a key, and you’d have no way of e-mailing a key securely. Of course you could make a phone call to tell your colleague the key you intend to use, but what if the conversation is overheard or the phone line is tapped?
How Public Key Cryptography Works
The solution is to use an ingenious cryptographic system called public key cryptography (PKC). The fundamental part of PKC is that the encryption key is split into two separate keys—let’s call them key A and key B. If you encrypt some plaintext with key A, you can’t decrypt the resulting ciphertext with key A to get back to your original plaintext. To decrypt ciphertext produced using key A, you need to use key B. In fact—and this turns out to be very useful—the reverse is also true: if you encrypt some plaintext with key B, you can’t decrypt it again with that key. You can only decrypt it with key A. If you encrypt a message with one key in the key pair, you can only decrypt it with the other one.
So if you want to be able to receive encrypted messages from anyone who wants to contact you, you first need to generate a key pair (using suitable PKC software.) One of these you designate your private key, which you keep secret. But here’s the clever bit: the other key you designate as your public key, and this doesn’t have to be kept secret. In fact the reverse is true: it should be distributed as widely as possible so that anyone who wants it can easily get it.
To send that message to a colleague now, all you need is their public key. There are a number of ways that you might get might get hold it, which we will look at in a future article. The important thing is that this public key doesn’t have to be kept secret, so even of you called your colleague and the phone line was being tapped it wouldn’t matter. Anyone overhearing the conversation and writing down the public key couldn’t use it to decrypt the message that you encrypt with it.
Now remember how we mentioned earlier that your private key can also be used to encrypt a message that can only be decrypted using your public key. You may well ask what would be the point of encrypting a message if the key needed to decrypt it is publicly available.
The answer is quite surprising. Let’s imagine you receive a message from your colleague, and you believe that it is encrypted with his private key. If you use their public key to decrypt the message successfully then that means that the message must indeed have been encrypted using your colleague’s private key (which only your colleague has access to.) No other key could have been used to encrypt the message. So encrypting a message with a private key acts as a digital signature: If you can decrypt a message with John’s public key, it must have been encrypted using John’s private key, so it must have been written by John.
Using double encryption, it’s possible to send an encrypted, digitally signed message to anyone who has made their public key available. Here’s how:
Imagine you want to send a message to your colleague Bob at head office. First you write your message (the plaintext) and encrypt it with your private key to produce the ciphertext—a message which is effectively digitally signed as coming from you and no-one else. You then encrypt this ciphertext a second time using Bob’s public key. Finally, you e-mail the resulting gobbledegook to Bob.
When Bob receives this message he decrypts it using his private key to get the ciphertext message that you encrypted with your private key. Bob then decrypts this using your public key. If he gets a message (rather than gobbledegook) he knows that the message definitely came from you (because otherwise he couldn’t have decrypted it with your public key) and he knows that no one else could have read the message, because no one else has his private key.
PKE Has Its Limits
Are there any limitations to the PKE approach? The answer to this question is yes.
Firstly, any encrypted message is only as strong as the cipher that is used to encrypt it. If a weakness is discovered in the cipher such that you no longer need a key to decrypt the message or it becomes possible to work out the key (directly or indirectly) from the contents of the ciphertext then clearly the system is not secure.
Another caveat is that any key-based encryption system is susceptible to a bruteforce attack—methodically trying every possible key until the correct one is found. Modern encryption techniques rely on the fact that if there is a sufficiently large keyspace (meaning there are a sufficiently large number of possible keys,) it is likely to take hundreds of millions of years to find a key by brute force using the computers that are currently available. But as computers become more powerful, the length of the keys typically used may need to be increased to ensure that the chances of successfully brute forcing a key remain tiny.
It’s important to remember that any encrypted message is never completely safe from a bruteforce attack: someone might guess the correct key with their very first guess. It’s just that with a strong cipher and a long key the probability of that happening—or that they hit upon the correct key within a thousand years—is vanishingly small.
The final problem that’s worth mentioning is the problem of key management: how do you get hold of someone’s public keys, and how can you be sure that it is the public key belonging to the person you think it belongs to? If you send a message to Bob using the public key which you think belongs to Bob but actually belongs to Carol, then Bob won’t be able to read it. More worryingly, if Carol manages to get her hands on the message she will be able to read it, even though you intended it for Bob’s eyes only.
But despite these potential problems, it’s fair to say that PKE has revolutionized the way that secure communications are carried out. In the next piece in this series, we’ll be looking at key management and how PKE is used in the real world to provide commercial and open-source secure e-mail systems.