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
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
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
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
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.