如何评价 Diffie 和 Hellman 获 2016 年图灵奖？

谢不邀…

多图预警，长答案预警，转载请注明出处。

这个答案阅读起来可能需要一点点耐心，嗯…

这道题竟然没有收到邀请，也是有点莫名其妙… 不过，这道题我要尽可能答的完全，答的精彩，因为这是一个需要满怀敬畏之心来回答的题目。

本回答会穿插一些离散数学的知识，不过我将尽可能淡化这些数学知识，尽量以讲故事的方式来回答这个问题。同时，欢迎知友们随时对我的答案提出意见和建议，我会尽可能完善此答案，让这个答案尽可能完美。

本题目将按照下述主线回答：

1. Bailey W. Diffie和Martin E. Hellman的贡献
2. 黑历史：本来应该还有第三个人
3. 现在将图灵奖颁发给Diffie和Hellman的原因

其中，第3部分的内容是我自己的思考，属于主观想法，并没有严谨的考证，仅供参考。

===========================

1. Bailey W. Diffie和Martin E. Hellman的贡献

介绍之前，首先给出两位学者的帅照！左边那位就是Hellman，而右边那位就是Diffie。

实际上，ACM、Stanford News已经表述的很清楚了（原文参见：

），在此我引用微信公众号“新智元”（微信号Al_era）推荐的，王嘉俊、王婉婷、李宏菲、曾天宇、张大少对此篇报道的部分翻译（原文参见：

）。

美国计算机协会（ACM）今天宣布，授予前Sun Microsystems 公司首席安全官 Whitfield Diffie 和斯坦福大学电气工程系名誉教授 Martin Hellman 2015 年的 ACM 图灵奖，由于他们在现代密码学领域的重要贡献。ACM将于6月11日在加利福尼亚州旧金山市举办年度颁奖典礼并授予2015年图灵奖。
建立双方在互联网上私下沟通的安全通道，是数十亿人使用互联网的根本。每一天，个人和银行、电子商务网站、邮件服务器和云平台都在建立着联系。Diffie和Hellman在1976年的开创性论文New Directions in Cryptography（密码学的新方向），介绍了公钥和电子签名的方法，这是今天大多数互联网安全协议的基础。Diffie-Hellman协议保护保护着每天互联网的沟通，以及万亿美元的金融交易。
......
在《密码学新方向》一文中，Diffie和Hellman展示了一种算法，表明非对称加密或是公共密钥加密是可行的。这个算法中，一个公钥——不是秘密的、可以被自由分享——被用来进行加密，而一个永远不需要离开接收装置的私钥被用来进行解密。虽然公钥决定了私钥，但是这种不对称加密系统在设计时使得从公钥中计算私钥变成一件不可行的事。

那么，这篇开创性的论文New Directions in Cryptography[1]到底介绍了些什么呢？这篇论文不仅提出了公钥密码学的概念，它实际上是一个预测性论文，以公钥密码学为核心，预测了密码学未来的发展方向，主要包括：

• 公钥密码学（论文第三章：Public Key Cryptography）
• 单向认证，也就是后来的数字签名（论文第四章：One-Way Authentication）
• 陷门单向函数（论文第五章：Problem Interrelations and Trapdoors）
• 计算复杂性问题（论文第六章：Computational Complexity）

可以说，Diffie和Hellman在这篇论文中指出了密码学的未来发展方向，并且论证了它们之间的关系：利用计算复杂性问题可以构造陷门单向函数，进一步可以构造公钥密码学，而公钥密码学可以实现加密和认证功能。后续的研究一步步地实现了这些功能。

Diffie和Hellman凭这篇论文开创了密码学的一个新领域，而这个新领域随着互联网的发展而得到了广泛的研究与应用。

可以说，Diffie和Hellman的获奖，实至名归。

然而，在ACM的评论中我们可以注意到这样一句话：

Diffie和Hellman展示了一种算法，表明非对称加密或是公共密钥加密是可行的。

之所以这样说，是因为在这篇论文中，Diffie和Hellman并没有提出其中任何一种具体的公钥加密算法，而是只给出了一个在公开信道中双方可以交换一个密钥的协议，这个协议被称作Diffie-Hellman密钥交换协议（Diffie-Hellman Key Exchange）。这个密钥交换协议虽然不是加密算法，但确实体现了公钥加密的思想。实际上，Taher ElGamal在1985年提出的ElGamal公钥加密算法，从原理上可以看作是Diffle-Hellman密钥交换协议的变形[2]。

在1977年，Ron Rivest，Adi Shamir和Leonard Adleman这三个人真正提出了一个公钥加密/数字签名算法，也就是我们都知道的RSA算法[3]。RSA算法的提出，标志着公钥密码学在实际中确实是可以实现的。计算机领域是一个理论与应用结合的领域，只有真正实现了的算法才能被广泛认可。早在2002年，Rivest、Shamir和Adleman就因共同提出了RSA算法而得到图灵奖。Diffie和Hellman得到图灵奖的时间反而晚了14年。

我们要明确的是，RSA算法实际上涵盖了Diffle和Hellman所提出的所有概念：

• RSA算法可以用来对数据进行加密，是公钥密码学的一个典型实例
• RSA算法可以用来实现数字签名，是单向认证的一个典型实例
• RSA算法的本质是RSA陷门单向函数。而且，RSA安全性所基于的大整数分解问题，至今为止都被认为是唯一可以用来构造陷门单向置换（Trapdoor One-Way Permutation）的方法。
• RSA算法的安全性可以规约为一个计算复杂性问题：RSA问题。

因此，RSA算法和Diffie-Hellman所做的贡献本质上属于同一个概念。按照图灵奖的传统，一般不会因为同一个概念而颁发两个图灵奖，那为什么今年又把图灵奖颁发给了Diffie和Hellman呢？更奇怪的是，在“新智元”推荐的文章中，第一张图里面是三个人：

这第三个人又是谁？他和Diffie、Hellman又是什么关系？

===========================

2. 黑历史：本来应该还有第三个人

如果你阅读了New Directions in Cryptography这篇论文的话，你会发现在第三章：Public Key Cryptography中有这样一句话：

Merkle has independently studied the problem of distributing keys over an insecure channel. His approach is different from that of the public key cryptosystems suggested above, and will be termed a public key distribution system.

而引用的标注是：R. Merkle. Secure Communication over an Insecure Channel. Submitted to Communications of the ACM。或者你在维基百科上阅读了Diffie-Hellman密钥交换协议这个词条的话（

），你会发现维基百科是如此描述的：

Diffie-Hellman key exchange is a specific method of securely exchanging cryptographic keys over a public channel and was one of the first public-key protocols as originally conceptualized by Ralph Merkle and named after Whitfield Diffie and Martin Hellman.

如果你再深挖一下的话，你会发现更神奇的事情。Diffle-Hellman密钥交换协议是有专利的（

）。这个专利于1977年9月6日申请，1980年4月29日获批。而这个专利的作者有三个人，正是Hellman，Diffie，以及Merkle。

我靠，你们是不是在逗我？原来密钥交换协议这个概念也不是Diffie和Hellman提的，而是一个叫做Ralph C. Merkle提的，是他最先研究的。实际上，上面图中的第三个人就是Merkle。那么为什么New Directions on Cryptography这篇论文里面没有Merkle的名字，但是专利上面有呢？又是为什么图灵奖没有同时给Merkle呢？Merkle和Diffie、Hellman究竟是什么关系？

先来个Merkle的帅照！嗯… 我觉得还是很帅的。

我们来看看Ralph Merkle的维基百科（

），上面有这样一段描述：

Merkle graduated from Livermore High School in 1970 and proceeded to study computer science at the University of California, Berkeley, obtaining his B.A. in 1974, and his M.S. in 1977. In 1979 he received his Ph.D. in electrical engineering at Stanford University, with a thesis entitled Secrecy, authentication and public key systems; his advisor was Martin Hellman.

其中一个疑问可以解决了，原来Hellman是Merkle的博士生导师，怪不得！不过另一个奇怪的事情是，这哥们在Berkeley研究计算机科学，怎么Ph.D.是在Stanford拿的？实际上，Merkle在Berkeley一直在研究公开信道的密钥交换问题，论文做出来以后，他在Berkeley的导师认为他的论文胡写一通，答辩不通过，不能拿到博士学位。万般无奈之下，Merkle找到了在Stanford的Hellman，并且在Stanford拿到了博士学位… 所以呢？论文答辩不通过也不要灰心，没准研究的是个图灵奖苗子的问题呢？Merkle也没通过嘛！

Merkle最先研究的密钥交换，但是为何New Directions on Cryptography这篇论文里面没有Merkle的名字呢？我们来看看New Directions on Cryptography这篇原始论文的第一页：

一个大大的“Invited Paper”出卖了大家… 这篇论文原来是一篇邀请论文，邀请的正是Diffie和Hellman。作为最先研究密钥交换协议的Merkle由于当时还是个博士生，自然没有收到IEEE Transactions on Information Theory这一大名鼎鼎期刊的邀稿。所以这篇文章的作者中没有出现Merkle的名字。但是，Diffie和Hellman更愿意认为这篇论文，以及它们在论文中给出的密钥交换协议有Merkle的功劳。实际上，Merkle已经因为这一贡献，分别获得了代表密码学最高奖励的RSA奖等等一系列奖。然而，由于这些机缘巧合，Merkle最终没有拿到图灵奖，不得不说是一种遗憾。

不过也还好啦，其实如果你学习过密码学的话，应该听说过一个叫做Merkle Tree的东西。这个就是Merkle提出的。这个密码学数据结构在比特币的区块链（Block Chain）构造中有着非常重要的应用哦！

===========================

3. 现在将图灵奖颁发给Diffie和Hellman的原因

回到正题，为什么这时候将图灵奖颁发给Diffie和Hellman呢？

我个人的理解是：如果不给Diffie和Hellman，后面为密码学做出贡献的各个学者们就都别拿图灵奖了…

到现在为止，公钥密码学的构造主要有三个方向：

1. 基于大整数分解问题。典型的就是RSA问题，以及二次剩余问题等。
2. 基于离散对数问题。典型的就是Diffie-Hellman密钥交换协议，ElGamal加密/签名算法。大家众所周知的比特币（Bitcoin）中所使用的数字签名算法，也是基于离散对数问题，只不过是使用椭圆曲线进行构造的。
3. 基于格困难问题。典型的就是NTRU加密算法，以及现在火的一塌糊涂的全同态加密。

大整数分解问题的代表是RSA，他们开创了这一领域，得到了图灵奖无可厚非。

然而，事物是以螺旋上升发展的。由于RSA算法所依赖的代数结构性质不太好，并且加密/签名算法的密钥长度和密文长度太长，自1985年ElGamal推出基于离散对数问题的公钥加密/签名算法后，RSA就逐渐推出了历史舞台，取代而之的就是基于离散对数问题的公钥加密/签名算法。2001年，随着Boneh和Franklin基于双线性映射构造基于身份的加密算法以后[4]，基于离散对数问题的各种算法火的一塌糊涂。按照延续性的话，任何基于离散对数问题所构造的密码学方案未来有拿奖潜力的话，那么首先就要给Diffie-Hellman颁奖，因为是他们首次提出可以基于离散对数问题构造公钥密码学方案。

有高潮就有低潮，随着2009年，Craig Gentry构造出了第一个全同态加密方案后[5]，基于格困难问题的公钥加密/签名算法逐渐走进了历史舞台。Gentry的贡献可以认为是图灵奖的备选。不过，根据著名密码学家Vadim Lyubashevsky在Winter School on Cryptography 2012: Lattice-Based Cryptography的演讲中所提到的：

那么，子集和问题是谁提出并使用的呢？

嗯，很遗憾… 是Merkle和Hellman提的。所以，如果溯源的话，Diffie和Hellman从这个角度也要拿图灵奖啊有木有！这帮天才，我给你们跪了！

不过，我们可以安慰一下自己，因为天才也有被拒稿的时候！来看看当时RSA论文的其中一个审稿意见吧！（原始链接：

）

A Method for Obtaining Digital Signatures and Public-Key Cryptosystems.” According to the (very short) introduction, this paper purports to present a practical implementation of Diffie and Hellman’s public-key cryptosystem for applications in the electronic mail realm. If this is indeed the premise, the paper should be rejected both for a failure to live up to it and for its irrelevance.
...
I doubt that a system such as this one will ever be practical. The paper does a poor job of convincing the reader that practicality is attainable.
...
The introduction is only two paragraphs long, the relevant literature is not presented or cited, and there is virtually no comparison with the relevant work in the area. In summary, it looks as if this paper is a mathematical exercise with little originality (the authors claim that most of their ideas come from other papers), too far from practical applicability, running against the established standards, and with a declared application area of dubious feasibility. Not the kind of material our readers like to see in the journal. Reject.

我们，一直很欣慰…

以上。

===========================

参考文献

[1] Whitfield Diffie, Martin E. Hellman. New Directions in Cryptography. IEEE Transactions on Information Theory, 1976, 22(6): 644-654.

[2] Taher ElGamal. A Public-Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms. IEEE Transactions on Information Theory, 1985, 31(4): 469-472.

[3] Ron Rivest, Adi Shamir, Leonard Adleman. Method for Obtaining Digital Signatures and Public-Key Cryptosystems. Communications of the ACM, 1977, 21(2): 120-126.

[4] Dan Boneh, Matthew K. Franklin. Identity-Based Encryption from the Weil Pairing. CRYPTO 2001, 213-229.

[5] Craig Gentry. Fully Homomorphic Encryption Using Ideal Lattices. STOC 2009, 169-178.

下图是我在RSAC 2016会议中拍的，中间那位甘道夫（D)和戴眼镜（H）的就是主角。获奖消息是RSAC的cryptographers' panel经典环节前获知的，现场6个嘉宾除去主持人和捧场的，还有2012年获图灵奖的RSA发明者中的Rivest和Shamir，以及DH密钥交换的Diffie和Hellman，只要学过密码学，大家都应该知道这四个人是谁吧？

从往年两个图灵奖获得者变成了四个，无论他们是参加这个panel，还是打麻将，应该都是图灵奖密度最高的组合了吧，当时现场报以热烈掌声，现场没有参加的同学，可以翻墙看一下这个视频（

），如果不会翻墙的话，也可以看看这个

。

为何获奖，ACM主席Wolf在颁奖词中已经说了，Diffie和Hellman的贡献在于现代的密码体系，其1966年论文介绍了公钥密码和数字签名，已经成为了互联网传输的安全协议基础。

关于DH密钥交换，我觉得在一个不可信的环境中，基于离散对数问题，能设计出一个有效密钥交换体系，就是很大贡献了。大家觉得这个公式很简单很优美有木有。。。

今年很热的话题是Apple和FBI撕逼，关于这点Hellman提到很有意思的事情：1970年代NSA主管Bobby差点因为这篇著名的论文将Hellman扔进监狱（感谢他没这么做）。现在Bobby和Hellman却是好朋友，所以这些密码学家在提出广为工业界采用的加密算法和体系的同时，也在与监管机构协商、合作，这种积极入世的态度也许是我们很多国内科研工作者要学习的。