Digital certificates are used in cryptography to certify the identity of a message sender to a message recipient who doesn't know the message sender. An advisor to a state legislature considering cryptography-related legislation recently stated that a dishonest certifier, after certifying a sender, could impersonate the sender by retaining a copy of the sender's private cryptographic key.
The Task Force on the National Information Infrastructure (NII) recently recommended changes to US copyright law, including a proposal to prohibit commerce in devices whose primary use is to defeat copyright-protecting technology. A professor of law recently suggested that if encryption technology is used to protect a document, decryption technology could be outlawed under the NII's proposal.
In public key cryptography, one reads signed messages by decrypting them with the public key corresponding to the message sender's private key. An officer in a large multinational bank that belongs to an electronic commerce consortium recently worried that storage of public keys could present space problems. After all, each public key is on the order of a thousand bits long.
Several consortiums are competing to develop uniform standards for electronic commerce, including encryption. One consortium, which is apparently using DES encryption technology, has openly published the source code for its system software. A competing consortium, which appears to be using RSA encryption technology, has published the standard (compatibility specifications) for its electronic commerce system, but refuses to publish the actual code. Some members of the first consortium have accused the second consortium of promoting a "closed" system to dominate electronic commerce.
With these examples as background, let's begin our quick tour of cryptography.
Unfortunately, DES has the same disadvantages as a physical lock and key system. The biggest is that the same key performs both encryption and decryption, so that both sender and receiver must have the key in order to communicate. This presents a key distribution problem for two people that don't know each other and a source authentication problem because the receiver (or anyone who steals the DES key) can impersonate the sender, i.e., when I receive a message signed by Lisa, how do I know that it really came from Lisa ? Finally, there is also a message integrity problem -- suppose a thief steals Lisa's key and uses it to intercept and modify her messages for his benefit ? For example, when Lisa tells her bank to pay Tom $1000, the thief could substitute his name as the payee!
In the late 70s, a pair of Stanford scientists (Merkle and Hellman) invented a better electronic lock-and- key system -- called public key cryptography-- and a trio of MIT scientists (Rivest, Shamir and Adelman) invented what is today the de facto standard public key algorithm -- RSA public key cryptography. The idea behind public key cryptography is that the single DES key is replaced by a key pair comprising a public key and a private key. Everyone has his own public-private key pair, and freely distributes his public key while keeping his private key secret. A message can be encrypted (locked) with either key, and can only be decrypted (unlocked) by the corresponding member of the pair. Let's be more specific. A message encrypted (locked) with the receiver's public key can only be decrypted (unlocked) with the receiver's private key. Let's call this RSA encryption. What does it mean?
In RSA encryption, a sender encrypts a message (providing confidentiality) with the receiver's public key (no key distribution problem because public keys are distributed publicly) and the receiver uses his private key to decrypt the message (no one else can decrypt the message, because no one else has the private key). This also solves the message integrity problem -- no one can decrypt the message in order to modify it!
Thus, replacing DES encryption with RSA encryption solves both the key distribution and message integrity problems. However, RSA has one disadvantage -- it's much slower than DES. Therefore, in practice, one often combines DES with RSA in the following manner: use RSA to encrypt a DES key and securely transmit it to the receiver, then use the DES key for all future communications. The DES key is called a session key because it's only used for a particular session -- a series of related communications over a finite period of time.
Everything's perfect now, right? Not quite. There's still a source authentication problem -- when I receive a message encrypted with my public key, how do I know who it came from? Sure, the message says it came from Lisa, but how can I be sure? The answer lies in RSA signing. RSA signing is like RSA encryption but it uses the sender's keys and operates in reverse order: a message is encrypted (locked) with the sender's private key and is decrypted (unlocked) with the sender's public key. If I replace DES encryption with RSA signing, anyone who successfully decrypts my messages knows they came from me ! Furthermore, I can also use RSA encryption to encrypt the RSA-signed message with the receiver's public key to make sure only he can read the message. Now I've guaranteed confidentiality, source authentication and there's no key distribution problem.
Sounds great, right? Unfortunately, I now have to perform two slow RSA cryptographic operations on every message I transmit -- an RSA encryption and a separate RSA signing. This is considerably slower than before, when I only had to perform one slow RSA cryptographic operation, and where I only had to perform that operation once -- on a short DES session key -- rather than for every message transmission. I was then able to use the fast DES key to encrypt all my message transmissions during a session.
What I really need is a way to use RSA signing for source authentication without displacing the fast DES session key. To further minimize the cost, I would prefer to RSA sign something small compared to the entire DES-encrypted message. The solution is something called a digital signature, which is also called a keyed hash. The "keyed" part is easy -- it simply means that a sender RSA signs the hash to guarantee source identity. But what is a "hash"? It's a highly compressed representation of a message which has the property that it can only have come from the message. Thus, verifying the hash is equivalent to verifying the message, which is why I need only RSA sign the hash rather than the entire message. By sending the hash along with the message, and allowing the receiver to recompute the hash, he can verify that the message hasn't been changed.
Let's consider an example. Suppose every letter is represented by its numerical occurrence in the alphabet: A=1, B=2, and so on up to Z=26. Further suppose that one hashes a message by adding the squares of all the letters in the message. For example, the message "ABC," which is "123," would hash to 1 + 4 + 9 = 14. If the message were intercepted and changed to "ABD," which hashes to 1 + 4 + 16 = 21, the receiver would know the message had been changed because he was expecting it to hash to 14 but got 21 instead. Finally, as mentioned earlier, the hash is RSA signed (remember RSA signing guarantees source authenticity) to guarantee that the hash itself hasn't been changed along with the message.
We've now constructed a process in which each encryption performs that portion of the overall encryption for which it is best suited: DES for fast message encryption, RSA encryption for DES key security and receiver confidentiality, and digital signaturing (hashing and RSA signing) for message integrity and source authenticity. We now have a quick and secure messaging system, right ? Well, almost. There's one loose end we have to tie up.
Earlier, I implied that RSA encryption solved the key distribution problem. That's not quite true. RSA encryption solves the DES key distribution problem, but how are the RSA public keys distributed ? What prevents an impersonator from generating his own public-private key pair, and impersonating me by passing off his public key as mine ? A recipient who doesn't know me has no way to verify that the public key he's received is indeed mine. The solution is to have someone who knows both me and the receiver certify (vouch for) my public key by RSA signing it with his own (the certifier's) private key. This is called a digital certificate. If the receiver successfully decrypts the digital certificate to yield my public key, he knows that my public key has not been replaced with someone else's (assuming that the impersonator is not in cahoots with my certifier!). If the receiver doesn't have my certifier's public key, because they don't know each other, my certifier can send his public key to the receiver via another digital certificate. Thus, certification cascades upward to whatever level is necessary, perhaps ultimately terminating in a universally trusted root certifier whose public key is known to all. The digital certificate provides the public key distribution mechanism necessary to ensure secure messaging.
Now let's put it all together.
To send a message, I:
1) "Cryptographic Impersonation"
It was suggested that a dishonest certifier, having certified a sender, could impersonate the sender by retaining a copy of the sender's private cryptographic key.
This statement is blatantly wrong. A digital certificate only contains the sender's public key -- it's impossible for a certifier to impersonate a sender by retaining a copy of the sender's private key because the certifier never sees the sender's private key.
2) "Decryption is Bad"
It was suggested that decryption technology is bad because it could be used to defeat copyright protection of a document that had been protected using encryption.
This statement is wrong. To say that encryption is "good" and decryption is "bad" simply miscomprehends the way cryptography works. It's like calling my car key "good" when I use it to lock the door, but "bad" when I use it to open the door I just locked. Encryption and decryption work together to protect messages because without decryption, encrypted messages could never be read. Furthermore, decryption is only able to unlock messages that were locked with the corresponding encryption key -- decryption is not a general purpose encryption-breaking technology. Thus, if anything, decryption must be regarded as a copyright- protecting technology.
3) "Key Storage Problems"
It was suggested that "large" public keys would present storage problems.
This statement is only mildly wrong -- or perhaps merely confused. A 1000-bit long key is 125 bytes, or 1/8 kilobytes long. At that size, my one gigabyte hard disk (retail cost $300) can hold 8 million public keys. I doubt if I'll ever need to communicate with 8 million other people. Surely key storage is not a problem !
4) "Closed Standards"
It was suggested that openly publishing the standard for an electronic commerce system that uses public key cryptography, without publishing the actual source code implementing the standard, constitutes promoting a "closed" system motivated by a desire to dominate electronic commerce.
This statement is not really wrong, but it may be misleading by omission.
The first system uses public- domain DES cryptography, so the code can
be freely published. The second system uses patented RSA cryptography,
so the specification ("this system requires RSA public key cryptography")
can be freely published, but not the code (remember, the code is a working
implementation of the system). This does not mean that the system is exclusionary,
only that one has to pay RSA to participate. Anyone who buys the consortium's
code automatically pays a royalty to RSA. Those who don't want to use the
consortium's code can develop their own version that's fully compatible
with the published standard, but they'll have to arrange for their own
license from RSA. Pay to play ? Yes. Exclusionary ? No. Closed ? You decide.
Odds & Ends
Let me conclude with a short list of Odds & Ends that may be useful to keep in mind when reading the popular press:
Dr. Joseph Yang, Attorney at
Law, Skadden, Arps, Slate, Meagher & Flom, LLP