I’ve been trying for a couple of weeks to put together a couple of interesting posts on the cryptographic modes of operation for confidentiality and integrity, and I just can’t do it. I’m finding it boring to write about, and if it bores me to write it, I know there’s no way that it’s going to be engaging to readers!
So, I’m going to move on. I’ve explained the basic idea of the message authentication code as an integrity check, and I’ve described one simple way of integrating it into a common mode of operation. If you’re really interested in learning more, I recommend Bruce Schnier’s book on cryptography, which has ton of material on modes of operation and protocols, how they work, and how they can fail.
Meanwhile, I’m going to move on to something that doesn’t bore me to write about, and therefore hopefully won’t bore you to read about: asymmetric cryptography, also commonly referred to (although not entirely accurately) as public key cryptography.
What we’ve looked at so far is symmetric cryptography. The basic idea of it is illustrated to the right. In a symmetric cryptosystem, you’ve got two parties who want to communicate, and they’ve got a shared secret. That shared secret is the key to the cryptosystem. Put in pseudo-mathematical syntax, the symmetric cryptosystem is a pair of functions, En and De, such that given a secret key S:
- Ciphertext = En(S, Plaintext)
- Plaintext = De(S, Ciphertext)
We call it symmetric because both the sender and the receiver need the same information. Both of them can encrypt messages using the key; both can decrypt. There’s no way to distinguish between the two on the basis of what information they have, or how they encrypt their messages.
In an asymmetric system (as illustrated above) that’s no longer true. Asymmetric systems use two keys, S1 and S2 (also called the private key and the public key) such that:
- CiphertextS1 = En(S1, Plaintext)
- Plaintext = De(S2, CiphertextS1)
- CiphertextS2 = En(S2, Plaintext)
- Plaintext = De(S1, CiphertextS2)
In english, suppose you’ve got two people, Ann and Bob who want to communicate. They each have their own key. To send a message to Bob, Ann encrypts the message with her key. When Bob receives the message, he decrypts it not with the same key that Ann used to encrypt it, but with his own key. When he wants to send a message back to Ann, he takes the same key that he used to decrypt the message from Ann, and uses it to encrypt a message to Ann.
This leads to one of the basic terminological confusions. Reading that description: Bob’s key decrypts messages from Ann, and encrypts messages to Ann has an element of symmetry to it. There is a very elegant symmetry to asymmetric encryption! But the terms asymmetric and symmetric in cryptography refer to the information that each of the parties uses in a cryptosystem. In a symmetric system, both parties have exactly the same information. In an asymmetric system, they’ve got different information.
For the most part, the basic requirements of an asymmetric cryptosystem are very similar to the requirements of a symmetric one – you want to be able to compute the ciphertext easily given the encryption key and the plaintext; you want to be able to compute the plaintext easily given the ciphertext and the decryption key; you don’t want to be able to compute the key given the ciphertext and the plaintext, and so on. But there’s one major complication in asymmetric cryptosystems that creates an additional requirement: given the encryption key, it must be computationally infeasible to generate the decryption key.
That last requirement kills the overwhelming majority of potential and proposed asymmetric systems. Having one of the keys in a pair means that you’ve effectively got access to an unlimited chosen plaintext attack: you’ve got the ability to generate the ciphertext of any plaintext, as many times as you want, and to use that to try to find the value of the key that will decrypt that text.
The most common use of asymmetric cryptography is public key cryptography. One of the really fascinating things about it is that instead of trying to keep the keys private, you deliberate make one of the two keys widely available – you give it to everyone.
The idea is that you take one key, which we call your private key, and you lock that away. No one but you should ever have access to your private key. The second key, called your public key, you give to everyone. You post it on public websites, you register it with key libraries, you send it to all of your friends, etc. Anyone who wants to be able to read encrypted messages from you needs to be able to get your public key.
Now, when you want to send someone a message and prove it’s from you, you encrypt it with your private key. Anyone can decrypt it – but only you could have encrypted it in a way that allows your public key to decrypt it.
Similarly, when someone wants to send you an encrypted message, they encrypt it with your public key. Then only you can decrypt it.
To set up a secure cryptographic channel with someone, you need to have their public key. So, suppose that we have Amy and Bill, who want to send secure messages to each other. What are the goals of the cryptosystem here? When Amy wants to send a message to Bill, she wants to make sure that only Bill can read it. When Bill gets a message from Amy, he wants to make sure that only Amy could have sent it.
The way we can provide both of those is by having Amy take her message, and first encrypt it with her private key. Then she encrypts it with Bill’s public key. The message has been encrypted twice: the first encryption pass guarantees that the message is from her (because no one else could have encrypted a message with her private key); the second encryption pass guarantees that no one but Bill can read it (because no one but Bill can decrypt a message with his private key).
Bill does exactly the same thing when he wants to send a message to Amy. First he encrypts it with his private key, to show that it’s really him who sent the message. And then he encrypts it with Amy’s public key, which ensures that only Amy can read it.
Towards the beginning of this message, I said that asymmetric cryptography is sometimes incorrectly called public key cryptography. The reason that I said that is because public key cryptography is really the combination of an asymmetric cryptosystem together with the infrastructure that allows the kind of scenario I described above, for Amy and Bill, to work. For it to work, Amy and Bill need to have a way of getting each other’s public keys – and being sure that they are really getting the correct, valid public keys for each other. There’s a very elegant cryptographic attack called a man in the middle attack, which relies on weaknesses in the public key infrastructure, not in the actual asymmetric cryptographic system used by the public key system, which I’ll describe in a future post.