公钥密码发明者荣获 2015 年度 ACM 图灵奖

程京德

ACM 宣布，2015 年度图灵奖授予公钥密码发明者 Whitfield Diffie 和 Martin E. Hellman，比因为发明 RSA 公钥密码的三人获奖(2002年)晚了 13 年。

公钥密码系统是上个世纪（甚至人类社会历史）最伟大的密码发明。到 20 世纪 70 年代中叶，历史上所有的密码系统的（加密和解密）密钥都是对称的，因此也是不能公开的。

1976 年，Diffie 和 Hellman 从计算复杂性观点出发，认识到理论上的计算可能和实际上的计算可能之间有着巨大的差异，这个差异可以用来设计出实践中实用的非对称公钥密码系统，在 1976 年的 AFIPS 会议上发表了他们划时代的想法，提出了非对称公钥密码系统的原理。Diffie 和 Hellman 的原创性先驱性的工作立刻引起密码学界和产业界的巨大兴趣，他们的正式论文也被破例地立刻发表在当年的 IEEE Transactions on Information Theory 上。遗憾的是，他们两位设计的世界上第一个非对称公钥密码系统被发现是有缺陷的，易于被攻破的。

1977 年，MIT 的三个青年计算机科学家 Rivest，Shamir 和 Adlemen 基于 Diffie 和 Hellman 的想法，发明了真正实用并且安全的 RSA 非对称公钥密码，并且因此贡献而荣获 2002 年度 ACM 图灵奖。

下面的内容转载自ACM (http://amturing.acm.org/) :

Cryptography Pioneers Receive 2015 ACM A.M. Turing Award

Whitfield Diffie, former Chief Security Officer of Sun Microsystems and Martin E. Hellman, Professor Emeritus of Electrical Engineering at Stanford University, are the recipients of the 2015 ACM A.M. Turing Award, for critical contributions to modern cryptography. The ability for two parties to communicate privately over a secure channel is fundamental for billions of people around the world. On a daily basis, individuals establish secure online connections with banks, e-commerce sites, email servers and the cloud. Diffie and Hellman’s groundbreaking 1976 paper, “New Directions in Cryptography,” introduced the ideas of public-key cryptography and digital signatures, which are the foundation for most regularly-used security protocols on the Internet today. The Diffie-Hellman Protocol protects daily Internet communications and trillions of dollars in financial transactions.

“Today, the subject of encryption dominates the media, is viewed as a matter of national security, impacts government-private sector relations, and attracts billions of dollars in research and development,” said ACM President Alexander L. Wolf. “In 1976, Diffie and Hellman imagined a future where people would regularly communicate through electronic networks and be vulnerable to having their communications stolen or altered. Now, after nearly 40 years, we see that their forecasts were remarkably prescient.”

“Public-key cryptography is fundamental for our industry,” said Andrei Broder, Google Distinguished Scientist. “The ability to protect private data rests on protocols for confirming an owner's identity and for ensuring the integrity and confidentiality of communications. These widely used protocols were made possible through the ideas and methods pioneered by Diffie and Hellman.”

Cryptography is a practice that facilitates communication between two parties so that the communication will be kept private and authenticated from a third party trying to read or alter what is being communicated. From ancient times, cryptography has been achieved through encryption, the conversion of readable information into gibberish that only a select few can decipher. In its earliest incarnations, encryption might have involved substituting one letter for another or rearranging the order of letters in the message. The development of radio in 1903, followed a decade later by World War I, gave cryptography a central role it never had before. At the same time, the development of electricity and machining allowed the development of machines that could encrypt far more securely than any human could. The post-World War I period saw the development of a number of enciphering machines that matured over the next 20 years and became the backbone of World War II cryptography. After the war, the development of computer technology led to faster and more secure cryptography by purely electronic machines.

In encryption, a “key” is a piece of information used to transform readable plain text into garbled incomprehensible cipher text. Encryption is much like keying a lock to accept a particular key and decryption is like using the key to open the lock. In the past, when two parties were seeking to establish secure communications, they needed to have identical keys. Supplying these keys—key management— was a major limitation of the flexibility of encrypted communications.

Two significant shortcomings of symmetric cryptosystems are the need for a secure means of key transfer and, because both parties have the same key, one could forge a message to oneself, claiming it came from the other. In addition, overuse of a particular key may provide an opponent with sufficient ciphertext to break the cryptosystem (i.e., discover the key). To limit the number of parties sharing the same key, separate keys are often distributed to each pair of communicating parties, posing additional key management challenges.

In “New Directions in Cryptography,” Diffie and Hellman presented an algorithm that showed that asymmetric or public-key cryptography was possible. In Diffie and Hellman's invention, a public key, which is not secret and can be freely distributed, is used for encryption, while a private key, that need never leave the receiving device, is used for decryption. This asymmetric cryptosystem is designed in such a way that the calculation of the private key from the public key is not feasible computationally, even though one uniquely determines the other.

Reversing the process provides a digital signature. The transmitter of a message uses a private key to sign the message, while the receiver uses the transmitter’s public key to authenticate it. Such digital signatures are more secure than written signatures because changing even one word of the message invalidates the signature. In contrast, a person’s written signature looks the same on a $10 check and a $1,000,000 check.

Any user of the World Wide Web is likely to be familiar with the use of public-key cryptography to establish secure connections. A typical secure URL begins with “https,” where the “s” means that the Secure Transport Layer protocol will be used to encrypt the communication. The secure connection is established using a combination of public-key cryptography to transport a key with symmetric cryptography that is used to encrypt subsequent communications.

In addition to laying the foundation for today’s online security industry and establishing cryptography as a leading discipline within computer science, Diffie and Hellman’s work made encryption technologies accessible to individuals and companies.

Press Release

ACM will present the 2015 A.M. Turing Award at its annual Awards Banquet on June 11, 2016 in San Francisco, California.