Thirty-five years ago, Martin Hellman, Whitfield Diffie, and Ralph Merkle developed an easy method for sending secure messages over insecure channels. With the advent of the Internet, their technology -- public key cryptography based on what is commonly referred to as Diffie-Hellman key exchange -- is now used continuously everywhere in the world.
"When a lock icon appears at the bottom of your browser, it's using public key cryptography. Your computer and the merchant's computer can talk back and forth across an insecure channel and exchange credit card information in a way that someone listening in cannot get it," said Hellman, Stanford University professor emeritus of electrical engineering.
The Institute of Electrical and Electronics Engineers (IEEE) has named Hellman, Diffie, and Merkle the 2010 Richard W. Hamming Medalists.
Hellman said he was especially happy that the award recognizes the contribution of Merkle, whose early work on public key encryption didn't get the acknowledgement it deserved."Ralph really deserves equal credit with us. I am really glad to see him being recognized on this award," Hellman said.
The IEEE Richard W. Hamming Medal was established by the Board of Directors in 1986 for exceptional contributions to information sciences, systems and technology. The award is named in honor of Dr. Richard W. Hamming, who has had a central role in the development of computer and computing science, and whose many significant contributions in the area of information science include his error-correcting codes.
Public key cryptography is a system for easily encrypting or scrambling information sent between computers. People may access a code called a public key from a server and use it to encrypt a message sent to another person anywhere in the world. The recipient reads the message using a private key. Public key cryptography is used in exchanges such as Internet credit card transactions.
Each of the three medalists became interested in cryptography before they met. Hellman was drawn to coding despite discouragement from almost all of his Stanford colleagues. "They told me I was crazy," Hellman said. "Their arguments were valid: How could I hope to discover anything that the National Security Agency, which is the primary American code-making, code-breaking agency, didn't already know? And they classified everything so highly that if we came up with anything good, they'd classify it."
Hellman decided to pursue cryptography anyway because he could foresee the day when even buying a loaf of bread would involve an electronic funds transfer, he said. "I didn't care what the NSA knew because I could see a need for commercial encryption that could not be met by the classified literature. Also, it didn't matter if everything I developed was already known to them. It is well established that the one to publish first gets credit, not the first to discover and keep it secret," he said.
Merkle also encountered opposition to his work in cryptography as an undergraduate at the University of California-Berkeley. He realized the possibilities of key encryption one night while coming up with a project for his computer security class.
"I stayed up late one night and started thinking. In the process of trying to prove that it was impossible to reestablish keys, I realized that it would in fact be possible. I had the basic outline within a few hours," Merkle said.
His initial thought was, "This is a neat quarter project," unaware of where it would lead. His professor also failed to see its potential. Merkle still has the typewritten proposal on which the professor wrote in blue ink: Your project "is muddled terribly." When Merkle couldn't convince his professor of the possibilities, he saw no point in the class and dropped it to pursue his newfound interest.
Hellman and Diffie were the first to meet. Diffie completed a bachelor's degree in mathematics at the Massachusetts Institute of Technology in 1965, and in the early 1970s began traveling the country to talk to anyone who was working in cryptography. Researchers at IBM connected him to Hellman, who had visited a few months prior.
"In the fall of 1974 Whit shows up on my doorstop. I'll never forget that day," Hellman said. The 30-minute appointment turned into half a day. Diffie stayed for dinner and left at 11 p.m. "Working in a vacuum had been taxing in a way, and finding a kindred spirit was really something," Hellman said.
Meanwhile, Merkle was completing his master's degree in computer science at Berkeley and sitting on his theory. He learned about the Stanford duo when a peer told him, "You know, there are some guys at Stanford who talk just like you."
Merkle joined the team at Stanford for a summer in 1976 and became a doctoral candidate under Hellman the next fall. In November 1976, the IEEE published Diffie and Hellman's first paper on cryptography. The article credited Merkle for his independent work at Berkeley, but the method nonetheless became known as the Diffie-Hellman key exchange.
Merkle had been the first to submit his work to a scientific publication (Journal of the ACM), but not the first to have his paper published, and hence lost the race.
The team expected to see public key cryptography implemented within 10 years, but it only really got going in the mid-1990s. Resistance came from the National Security Agency, which classified encryption as an implement of war.
"If it's available for you and me to use to protect our banking transactions, it's also available to al-Qaida and the Mafia to use to protect their communications. So NSA tried to hold back the advancement of public encryption with export controls," Hellman said.
A software company, for example, could sell a secure program to domestic buyers but not to customers overseas. Because companies feared competitors would tell foreign buyers they were getting a poor version, they often opted to sell weak encryption to both, Hellman said.
As the team began publishing papers in IEEE journals, an IEEE member " who worked for the NSA " sent a letter to the organization, citing Hellman's papers, with concerns about national security laws. Hellman took up the issue with Stanford legal counsel John Schwartz, who explained that the university could defend Hellman in court if it came to that. Penalties could extend to 10 years in prison and a $50,000 fine.
"Schwartz told me that the university could pay all my legal expenses, but if I was judged a criminal and all the appeals were exhausted, they could not aid and abet criminal conduct by paying my fine. And they obviously couldn't go to jail for me," Hellman said.
Hellman had a symposium to attend at Cornell University, at which two of his doctoral students, Merkle and Steve Pohlig, were to present their latest papers. He decided to throw caution to the wind, though some colleagues thought even his life, along with his career, might be in danger. To give proper credit to his students and yet protect them, Hellman presented the paper while they stood silently on stage next to him. He was never arrested.
The NSA's outlook eventually changed, thanks partly to a 1995 National Research Council committee that Hellman joined. The group worked through concerns of both sides of the argument and found that using weak encryption to protect American business and citizens was a greater national threat than allowing both Americans and foreigners to acquire secure encryption.
The rise of the Internet also helped cryptography go commercial. RSA Data Security, a company formed by three faculty members at the Massachusetts Institute of Technology who had invented a new public key algorithm, was the first to apply encryption to electronic commerce. They took Diffie, Hellman and Merkle's public key concept and came up with a better algorithm for use in programs like Netscape's web browser, Hellman said.
Hellman is now professor emeritus of electrical engineering at Stanford, Merkle is a senior research fellow at the Institute for Molecular Manufacturing, and Diffie is a visiting professor at Royal Holloway, University of London.
The IEEE will present the Hamming Medals on June 26 in Montreal, Canada. The prize consists of a gold medal, bronze replica, certificate and $20,000.
— Christine Blackman is a science-writing intern at the Stanford News Service.