This chapter is from the book
This chapter is from the book
This chapter is from the book
Secrecy Changes Forever
For four thousand years, cryptography was about making sure Eve could not read Alice's message to Bob if Eve intercepted the message en route. Nothing could be done if the key itself was somehow discovered. Keeping the key secret was therefore of inestimable importance, and was a very uncertain business.
If Alice and Bob worked out the key when they met, how could Bob keep the key secret during the dangers of travel? Protecting keys was a military and diplomatic priority of supreme importance. Pilots and soldiers were instructed that, even in the face of certain death from enemy attack, their first responsibility was to destroy their codebooks. Discovery of the codes could cost thousands of lives. The secrecy of the codes was everything.
And if Alice and Bob never met, then how could they agree on a key without already having a secure method for transmitting the key? That seemed like a fundamental limitation: Secure communication was practical only for people who could arrange to meet beforehand, or who had access to a prior method of secure communication (such as military couriers) for carrying the key between them. If Internet communications had to proceed on this assumption, electronic commerce never could have gotten off the ground. Bit packets racing through the network are completely unprotected from eavesdropping.
And then, in the 1970s, everything changed. Whitfield Diffie was a 32-year-old mathematical free spirit who had been obsessed with cryptography since his years as an MIT undergraduate. 31-year-old Martin Hellman was a hard-nosed graduate of the Bronx High School of Science and an Assistant Professor at Stanford. Diffie had traveled the length of the country in search of collaborators on the mathematics of secret communication. This was not an easy field to enter, since most serious work in this area was being done behind the firmly locked doors of the National Security Agency. Ralph Merkle, a 24-year-old computer science graduate student, was exploring a new approach to secure communication. In the most important discovery in the entire history of cryptography, Diffie and Hellman found a practical realization of Merkle's ideas, which they presented in a paper entitled "New Directions in Cryptography." This is what the paper described:
- A way for Alice and Bob, without any prior arrangement, to agree on a secret key, known only to the two of them, by using messages between them that are not secret at all.
In other words, as long as Alice and Bob can communicate with each other, they can establish a secret key. It does not matter if Eve or anyone else can hear everything they say. Alice and Bob can come to a consensus on a secret key, and there is no way for Eve to use what she overhears to figure out what that secret key is. This is true even if Alice and Bob have never met before and have never made any prior agreements.
The impact of this discovery cannot be overstated. The art of secret communication was a government monopoly, and had been since the dawn of writing—governments had the largest interests in secrets, and the smartest scientists worked for governments. But there was another reason why governments had done all the serious cryptography. Only governments had the wherewithal to assure the production, protection, and distribution of the keys on which secret communication depended. If the secret keys could be produced by public communication, everyone could use cryptography. They just had to know how; they did not need armies or brave couriers to transmit and protect the keys.
Diffie, Hellman, and Merkle dubbed their discovery "public-key cryptography." Although its significance was not recognized at the time, it is the invention that made electronic commerce possible. If Alice is you and Bob is Amazon, there is no possibility of a meeting—how could you physically go to Amazon to procure a key? Does Amazon even have a physical location? If Alice is to send her credit card number to Amazon securely, the encryption has to be worked out on the spot, or rather, on the two separate spots separated by the Internet. Diffie-Hellman-Merkle, and a suite of related methods that followed, made secure Internet transactions possible. If you have ever ordered anything from an online store, you have been a cryptographer without realizing it. Your computer and the store's computer played the roles of Alice and Bob.
It seems wildly counterintuitive that Alice and Bob could agree on a secret key over a public communication channel. It was not so much that the scientific community had tried and failed to do what Diffie, Hellman, and Merkle did. It never occurred to them to try, because it seemed so obvious that Alice had to give Bob the keys somehow.
Even the great Shannon missed this possibility. In his 1949 paper that brought all known cryptographic methods under a unified framework, he did not realize that there might be an alternative. "The key must be transmitted by non-interceptable means from transmitting to receiving points," he wrote.
Not true. Alice and Bob can get the same secret key, even though all their messages are intercepted.
The basic picture of how Alice communicates her secret to Bob remains as shown in Figure 5.6. Alice sends Bob a coded message, and Bob uses a secret key to decrypt it. Eve may intercept the ciphertext en route.
){kind=link}
The goal is for Alice to do the encryption in such a way that it is impossible for Eve to decrypt the message in any way other than a brute-force search through all possible keys. If the decryption problem is "hard" in this sense, then the phenomenon of exponential growth becomes the friend of Alice and Bob. For example, suppose they are using ordinary decimal numerals as keys, and their keys are ten digits long. If they suspect that Eve's computers are getting powerful enough to search through all possible keys, they can switch to 20-digit keys. The amount of time Eve would require goes up by a factor of 1010 = 10,000,000,000. Even if Eve's computers were powerful enough to crack any 10-digit key in a second, it would then take her more than 300 years to crack a 20-digit key!
Exhaustive search is always one way for Eve to discover the key. But if Alice encrypts her message using a substitution or Vigenère cipher, the encrypted message will have patterns that enable Eve to find the key far more quickly. The trick is to find a means of encrypting the message so that the ciphertext reveals no patterns from which the key could be inferred.
The Key Agreement Protocol
The crucial invention was the concept of a one-way computation—a computation with two important properties: It can be done quickly, but it can't be undone quickly. To be more precise, the computation quickly combines two numbers x and y to produce a third number, which we'll call x * y. If you know the value of x * y, there is no quick way to figure out what value of y was used to produce it, even if you also know the value of x. That is, if you know the values of x and the result z, the only way to find a value of y so that z = x * y is trial and error search. Such an exhaustive search would take time that grows exponentially with the number of digits of z—practically impossible, for numbers of a few hundred digits. Diffie and Hellman's one-way computation also has an important third property: (x * y) * z always produces the same result as (x * z) * y.
The key agreement protocol starts from a base of public knowledge: how to do the computation x * y, and also the value of a particular large number g. (See the Endnotes for the details.) All this information is available to the entire world. Knowing it, here is how Alice and Bob proceed.
- Alice and Bob each choose a random number. We'll call Alice's number a and Bob's number b. We'll refer to a and b as Alice and Bob's secret keys. Alice and Bob keep their secret keys secret. No one except Alice knows the value of a, and no one except Bob knows the value of b.
- Alice calculates g * a and Bob calculates g * b. (Not hard to do.) The results are called their public keys A and B, respectively.
- Alice sends Bob the value of A and Bob sends Alice the value of B. It doesn't matter if Eve overhears these communications; A and B are not secret numbers.
- When she has received Bob's public key B, Alice computes B * a, using her secret key a as well as Bob's public key B. Likewise, when Bob receives A from Alice, he computes A * b.
Even though Alice and Bob have done different computations, they have ended up with the same value. Bob computes A * b, that is, (g * a) * b (see Step 2—A is g * a). Alice computes B * a, that is, (g * b) * a. Because of the third property of the one-way computation, that number is (g * a) * b once again—the same value, arrived at in a different way!
This shared value, call it K, is the key Alice and Bob will use for encrypting and decrypting their subsequent messages, using whatever standard method of encryption they choose.
Now here's the crucial point. Suppose Eve has been listening to Alice and Bob's communications. Can she do anything with all the information she has? She has overheard A and B, and she knows g because it is an industry standard. She knows all the algorithms and protocols that Alice and Bob are using; Eve has read Diffie and Hellman's paper too! But to compute the key K, Eve would have to know one of the secret keys, either a or b. She doesn't—only Alice knows a and only Bob knows b. On numbers of a few hundred digits, no one knows how to find a or b from g, A, and B without searching through impossibly many trial values.
Alice and Bob can carry out their computations with personal computers or simple special-purpose hardware. But even the most powerful computers aren't remotely fast enough to let Eve break the system, at least not by any method known.
Exploiting this difference in computational effort was Diffie, Hellman, and Merkle's breakthrough. They showed how to create shared secret keys, without requiring secure channels.
Public Keys for Private Messages
Suppose Alice wants to have a way for anyone in the world to send her encrypted messages that only she can decrypt. She can do this with a small variation of the key-agreement protocol. All the computations are the same as in the key agreement protocol, except they take place in a slightly different order.
Alice picks a secret key a and computes the corresponding public key A. She publishes A in a directory.
If Bob (or anyone) now wants to send Alice an encrypted message, he gets Alice's public key from the directory. Next, he picks his own secret key b and computes B as before. He also uses Alice's public key A from the directory to compute an encryption key K just as with the key-agreement protocol: K = A * b. Bob uses K as a key to encrypt a message to Alice, and he sends Alice the ciphertext, along with B. Because he uses K only once, K is like a one-time pad.
When Alice receives Bob's encrypted message, she takes the B that came with message, together with her secret key a, just as in the key agreement protocol, and computes the same K = B * a. Alice now uses K as the key for decrypting the message. Eve can't decrypt it, because she doesn't know the secret keys.
This might seem like just a simple variant of key agreement, but it results in a major conceptual change in how we think about secure communication. With public-key encryption, anyone can send encrypted mail to anyone over an insecure, publicly exposed communication path. The only thing on which they need to agree is to use the Diffie-Hellman-Merkle method—and knowing that is of no use to an adversary trying to decipher an intercepted message.
Digital Signatures
In addition to secret communication, a second breakthrough achievement of public-key cryptography is preventing forgeries and impersonations in electronic transactions.
Suppose Alice wants to create a public announcement. How can people who see the announcement be sure that it really comes from Alice—that it's not a forgery? What's required is a method for marking Alice's public message in such a way that anyone can easily verify that the mark is Alice's and no one can forge it. Such a mark is called a digital signature.
To build on the drama we have used already, we'll continue to talk about Alice sending a message to Bob, with Eve trying to do something evil while the message is in transit. In this case, however, we are not concerned with the secrecy of Alice's message—only with assuring Bob that what he receives is really what Alice sent. In other words, the message may not be secret—perhaps it is an important public announcement. Bob needs to be confident that the signature he sees on the message is Alice's and that the message could not have been tampered with before he received it.
Digital signature protocols use public keys and secret keys, but in a different way. The protocol consists of two computations: one Alice uses to process her message to create the signature, and one Bob uses to verify the signature. Alice uses her secret key and the message itself to create the signature. Anyone can then use Alice's public key to verify the signature. The point is that everyone can know the public key and thus verify the signature, but only the person who knows the secret key could have produced the signature. This is the reverse of the scenario of the previous section, where anyone can encrypt a message, but only the person with the secret key can decrypt it.
A digital signature scheme requires a computational method that makes signing easy if you have the secret key and verifying easy if you have the public key—and yet makes it computationally infeasible to produce a verifiable signature if you don't know the secret key. Moreover, the signature depends on the message as well as on the secret key of the person signing it. Thus, the digital signature protocol attests to the integrity of the message—that it was not tampered with in transit—as well as to its authenticity—that the person who sent it really is Alice.
In typical real systems, used to sign unencrypted email, for example, Alice doesn't encrypt the message itself. Instead, to speed up the signature computation, she first computes a compressed version of the message, called a message digest, which is much shorter than the message itself. It requires less computation to produce the signature for the digest than for the full message. How message digests are computed is public knowledge. When Bob receives Alice's signed message, he computes the digest of the message and verifies that it is identical to what he gets by decrypting the attached signature using Alice's public key.
The digesting process needs to produce a kind of fingerprint—something small that is nonetheless virtually unique to the original. This compression process must avoid a risk associated with using digests. If Eve could produce a different message with the same digest, then she could attach Alice's signature to Eve's message. Bob would not realize that someone had tampered with the message before he received it. When he went through the verification process, he would compute the digest of Eve's message, compare it to the result of decrypting the signature that Alice attached to Alice's message, and find them identical. This risk is the source of the insecurity of the message digest function MD5 mentioned earlier in this chapter, which is making the cryptographic community wary about the use of message digests.
RSA
Diffie and Hellman introduced the concept of digital signatures in their 1976 paper. They suggested an approach to designing signatures, but they did not present a concrete method. The problem of devising a practical digital signature scheme was left as a challenge to the computer science community.
The challenge was met in 1977 by Ron Rivest, Adi Shamir, and Len Adleman of the MIT Laboratory for Computer Science. Not only was the RSA (Rivest-Shamir-Adleman) algorithm a practical digital signature scheme, but it could also be used for confidential messaging. With RSA, each person generates a pair of keys—a public key and a secret key. We'll again call Alice's public key A and her secret key a. The public and private keys are inverses: If you transform a value with a, then transforming the result with A recovers the original value. If you transform a value with A, then transforming the result with a recovers the original value.
Here's how RSA key pairs are used. People publish their public keys and keep their secret keys to themselves. If Bob wants to send Alice a message, he picks a standard algorithm such as DES and a key K, and transforms K using Alice's public key A. Alice transforms the result using her secret key a to recover K. As with all public-key encryption, only Alice knows her secret key, so only Alice can recover K and decrypt the message.
To produce a digital signature, Alice transforms the message using her secret key a and uses the result as the signature to be sent along with the message. Anyone can then check the signature by transforming it with Alice's public key A to verify that this matches the original message. Because only Alice knows her secret key, only Alice could have produced something that, when transformed with her public key, will reproduce the original message.
It seems to be infeasible in the RSA cryptosystem—as in the Diffie-Hellman-Merkle system—to compute a secret key corresponding to a public key. RSA uses a different one-way computation than the one used by the Diffie-Hellman-Merkle system. RSA is secure only if it takes much longer to factor an n-digit number than to multiply two n/2-digit numbers. RSA's reliance on the difficulty of factoring has engendered enormous interest in finding fast ways to factor numbers. Until the 1970s, this was a mathematical pastime of theoretical interest only. One can multiply numbers in time comparable to the number of digits, while factoring a number requires effort comparable to the value of the number itself, as far as anyone knows. A breakthrough in factoring would render RSA useless and would undermine many of the current standards for Internet security.
Certificates and Certification Authorities
There's a problem with the public-key methods we've described so far. How can Bob know that the "Alice" he's communicating with really is Alice? Anyone could be at the other end of the key-agreement communication pretending to be Alice. Or, for secure messaging, after Alice places her public key in the directory, Eve might tamper with the directory, substituting her own key in place of Alice's. Then, anyone who tries to use the key to create secret messages intended for Alice, will actually be creating messages that Eve, not Alice, can read. If "Bob" is you and "Alice" is the mayor ordering an evacuation of the city, some impostor could be trying to create a panic. If "Bob" is your computer and "Alice" is your bank's, "Eve" could be trying to steal your money!
This is where digital signatures can help. Alice goes to a trusted authority, to which she presents her public key together with proof of her identity. The authority digitally signs Alice's key—producing a signed key called a certificate. Now, instead of just presenting her key when she wants to communicate, Alice presents the certificate. Anyone who wants to use the key to communicate with Alice first checks the authority's signature to see that the key is legitimate.
People check a certificate by checking the trusted authority's signature. How do they know that the signature on the certificate really is the trusted authority's signature, and not some fraud that Eve set up for the purpose of issuing fake certificates? The authority's signature is itself guaranteed by another certificate, signed by another authority, and so on, until we reach an authority whose certificate is well-known. In this way, Alice's public key is vouched for, not only by a certificate and a single signature, but by a chain of certificates, each one with a signature guaranteed by the next certificate.
Organizations that issue certificates are called certification authorities. Certification authorities can be set up for limited use (for example, a corporation might serve as a certification authority that issues certificates for use on its corporate network). There are also companies that make a business of selling certificates for public use. The trust you should put in a certificate depends on two things: your assessment of the reliability of the signature on the certificate and also your assessment of the certification authority's policy in being willing to sign things.