Q&A: Finding New Directions in Cryptography

Like many developments we now take for granted in the history of the Internet, public key cryptography—which provides the ability to communicate securely over an insecure channel—followed an indirect path into the world. When ACM A.M. Turing Award recipients Martin Hellman and Whitfield Diffie began their research, colleagues warned against pursuing cryptography, a field then dominated by the U.S. government. Their 1976 paper "New Directions in Cryptography" not only blazed a trail for other academic researchers, but introduced the ideas of public-key distribution and digital signatures.

How did you meet?

DIFFIE: In the summer of 1974, my wife and I traveled to Yorktown Heights (NY) to visit a friend who worked for Alan Konheim at IBM.

You’re talking about the head of the IBM mathematics group and author of Cryptography: A Primer, who subsequently moved to the University of California, Santa Barbara.

DIFFIE: Konheim said he couldn’t tell me very much because of a secrecy order, but he did mention that his friend Marty Hellman had been there a few months ago. He said, "I couldn’t tell him anything either, but you should look him up when you get back to Stanford, because two people can work on a problem better than one."

HELLMAN: So Whit gives me a call. Whit, you were up in Berkeley at the time?

DIFFIE: I was staying with Leslie Lamport.

HELLMAN: I think I set up a half-hour meeting in my office, which went on for probably two hours, and at the end of it, I said, "Look, I’ve got to go home to watch my daughters, but can we continue this there?" Whit came to our house and we invited him and his wife, Mary, to stay for dinner, and as I remember we ended the conversation around 11 o’clock at night.

The two of you worked together for the next four years.

HELLMAN: Whit had been traveling around the country and I tried to figure out ways to keep him at Stanford. I found a small amount of money in a research grant that I could use. A lot of good things came of that.

Among them was a vigorous critique of the Data Encryption Standard (DES), a symmetric-key algorithm developed at IBM.

HELLMAN: DES came full-blown from the brow of Zeus. "Zeus," in this case, was NBS, the National Bureau of Standards, or NSA, the National Security Agency, or IBM, or some combination. They didn’t tell us how they had come up with it; they just announced it in the Federal Register as a proposed standard. We quickly realized the key size was too small and needed to be enlarged.

DIFFIE: I had an estimate roughly of half a billion dollars to break it. We eventually decided it could be done for $20-ish million.

HELLMAN: And because of Moore’s Law, it would only get cheaper.

DIFFIE: If you can make a cryptographic system that’s good, it’s usually not hard to make one that’s effectively unbreakable. So it takes some explaining if you make the key size small enough that somebody might conceivably search through it.

HELLMAN: So in March 1975, NBS announced the DES and solicited comments and criticism. And we were naive enough to think they actually were open to improving the standard. Five months later, it was clear to us the key size problem was intentional and the NSA was behind it. If we wanted to improve DES—and we did—we had a political fight on our hands.

That fight was partly about your work on public key cryptography.

MARTIN: There was a lot that led up to that idea. The DES announcement suggested the value of trap door ciphers. It became clear to us that NSA wanted secure encryption for U.S. communications, but still wanted access to foreign ones. Even better than DES’ small key size would be to build in a trap door that made the system breakable by NSA—which knows the trap door information—but not by other nations. It’s a small step from there to public key cryptography, but it still took us time to see.

---

"If you can make a cryptographic system that’s good, it’s usually not hard to make one that’s effectively unbreakable."

---

Whit, you have also said you were inspired by John McCarthy’s paper about buying and selling through so-called "home information terminals."

DIFFIE: I was concerned with two problems and didn’t realize how closely related they were. First, I had been thinking about secure telephone calls since 1965, when a friend told me—mistakenly, as it turned out—that the NSA encrypted the telephone traffic within its own building. From my countercultural point of view, though, my understanding of a secure telephone call was: I call you, and nobody else in the world can understand what we’re talking about. I began thinking about what we call the key-management problem.

In 1970, about the time I got to Stanford, John McCarthy presented the paper that you note. I began to think about electronic offices and what you would do about a signature, because signatures on paper depend so heavily on the fact that they’re hard to copy, and digital documents can be copied exactly.

So in the spring of 1975, as you were preparing your critique of DES, you came to the solution to both problems.

DIFFIE: I was living at John McCarthy’s house, and I was trying to combine what is called identification, friend or foe (IFF), which is a process by which a Fire Control radar challenges an aircraft and expects a correctly encrypted response, and what is called one-way enciphering, which is used in UNIX to avoid having the password table be secret. One of these protects you from the compromise of the password table, and the other protects you from someone eavesdropping on the transmission of your password.

You came to the concept of what we now call digital signatures, constructions in which somebody can judge the correctness of the signature but cannot have generated it.

DIFFIE: Only one person can generate it, but anybody can judge its correctness. And then a few days later, I realized this could be used to solve the problem I’d been thinking of since 1965. At that point, I realized I really had something. I told Mary about it as I fed her dinner and then went down the hill to explain it to Marty.

HELLMAN So then we had the problem of coming up with a system that would actually implement it practically, and some time later we met Ralph Merkle, who had come up with related but slightly different ideas at Berkeley as a master’s student. The algorithm I came up with was a public key distribution system, a concept developed by Merkle. Whit and I didn’t put names on the algorithm, but I’ve argued it should be called Diffie-Hellman-Merkle, rather than the Diffie-Hellman Key Exchange, as it now is.

The NSA was not happy you intended to publish your results.

HELLMAN: NSA was very upset at our publishing in an area where they thought they had a monopoly and could control what was published.

Marty, you have been at Stanford ever since. Whit, you left Stanford in 1978 to work at Bell Northern Research, and later went to Sun Microsystems. And you now are working on a project to document the history of cryptography.

DIFFIE: There have been some major shifts in cryptographic technology in the latter half of the 20^th century; public key is only one of them. I am trying to write the history of some others before all the people who worked on them die off.

Marty, you’re writing a book about your marriage and nuclear weapons.

HELLMAN: Starting about 35 years ago, my interests shifted from cryptography to the bigger problems in the world, particularly nuclear weapons and how fallible human beings are going to survive having that kind of power. What got me started was wanting to save my marriage, which at that time was in trouble. Dorothie and I not only saved our marriage, but recaptured the deep love we felt when we first met. The changes needed to transform our marriage are the same ones needed to build a more peaceful, sustainable world. But it has kind of come full circle, because as we become more and more wired, cyber insecurity may become an existential threat. The global part of our effort is really about solving the existential threats created by the chasm between the God-like physical power technology has given us and our maturity level as a species, which is at best that of an irresponsible adolescent.

Back to Top