国际密码学领域的顶级较量

　　在大众眼里，密码学似乎是一个很神秘的“存在”。就在近日，该领域的一则重磅消息在我国传出西安电子科技大学综合业务网理论及关键技术国家重点实验室的胡予濮教授与他的博士研究生贾惠文，对GGH映射本身以及基于GGH映射的各类高级密码应用进行了颠覆性的否定。

胡予濮教授和他的博士研究生贾慧文

　　这个被攻破的GGH，原本是一个有望成为国际密码学研究新技术的密码映射方案。这一突破的重大意义，可以这样打个比方：GGH方案的提出者，就像是建筑行业里的地基团队。他们设计并挖掘了看起来非常安全保险，足够深的地基，人们翘首期盼施工团队在他们挖下的地基上盖出摩天大厦来。但胡予濮教授从事的密码分析学就类似于监理团队，发现了地基设计图纸的大问题，并指出了挖好的地基存在隐患和问题，无法在上面建造大楼。如果强行建造，必然是楼毁人亡。

　　日前，经密码学专家严格评审，这一研究成果《GGH映射的密码分析》已被2016年欧洲密码年会正式接受。2016年5月8日，胡予濮将赴奥地利维也纳，在欧洲密码年会上正式向全世界的密码同行报告这一突破性成果。

　　现代密码学遗留的公开问题

　　“GGH密码和人们的通信安全有关。”胡予濮说。

　　1976年以前，人们在通信领域的观念是“不事先进行秘密共享就无法进行保密通信”。1976年，美国斯坦福大学的密码学家惠特菲尔德·迪菲和马丁·赫尔曼首次提出公钥密码体制的思想，给出非交互密钥协商的概念。

　　“举个通俗的例子，假设有A和B两人在异地，A想告诉B一个秘密，但不想让其他人知道，若直接写信的话，可能会被快递员偷看，现在他把秘密放进一个带锁的盒子里，B收到盒子后再用钥匙打开，但前提是B和A要事先拥有共同的钥匙。而‘事先拥有共同的钥匙’其实就是密钥协商。”贾惠文说。

　　此举引发了密码学史上的革命，颠覆了人们的传统观念，使得用户可以在一个完全开放的信道上，进行秘密共享，实现保密通信。这一思想上的突破，成为现今密钥交换系统的基础，被广泛应用于网络通信。1976年，也被业界定为现代密码学元年。

　　然而，迪菲与赫尔曼的工作只是第一步，他们实现了无需交互就可以在公开信道上共享密钥，但仅限于两方。如何将这一机制扩展至三方乃至多方，一直是现代密码学遗留下来有待解决的公开问题。

　　接下来的几十年中，全世界的密码学者们都在试图解决这个难题。然而，研究始终未能取得突破性进展。直到2013年，3位密码天才提出GGH方案，才让解决这个问题出现了一道曙光。

　　当年的欧洲密码年会上，时为美国加州大学洛杉矶分校的博士生萨吉·杰瑞格，以及美国IBM公司研究员克雷格·金特里和塞·哈勒维，共同提交了一篇论文，提出一个分级编码系统概念，并以此在理想格上实现了第一个多线性映射方案（GGH映射，取名于3位作者姓名首字母），进而解决了现代密码学遗留的这个公开问题，这篇论文也因此获得当年欧密会的最佳论文奖。

GGH映射的三位作者：Sanjam Garg、Craig Gentry 和 Shai Halevi

　　沉浸“密码世界”挑战顶尖研究

　　GGH多线性映射方案对密码学界产生了重大影响，迅速在国际密码学界引发了多线性研究的热潮。

　　“然而，由于多线性映射的特殊性，杰瑞格等人无法直接证明GGH密码方案是安全可行的，所以他们在论文中采取穷举攻击的办法，来间接表明该方案是安全的。”胡予濮说，2014年5月底，他无意间了解到这个信息，觉得很有意义，“就尝试着要对它进行密码分析，也就是破解。”

　　“粗看上去，杰瑞格等人提出的GGH密码映射方案到处都是漏洞，但你就是无论如何也攻破不了它。”胡予濮说，GGH提出者均是当今国际上顶尖的密码研究者，他们的方案十分完整，已经列举了当时能够想到的各种攻击方法，并都进行了尝试。

　　从2014年5月底到2015年2月中旬，胡予濮的脑海里全是GGH密码方案，他完全沉浸在密码、数论、概率统计等学科的世界里。

　　2015年3月7日，被胡予濮认为是攻破GGH密码方案的过程中最具有纪念意义的一天。“当晚，我一夜未眠，突然觉得GGH的结构有些不对，半夜起来开始验算。”一直到推算、验证到第二天中午，胡予濮第一次发现：GGH的漏洞确实是存在的。

　　即便经过多次推导，已经验证了GGH存在漏洞，但胡予濮还是没有轻易下结论说攻破了这一方案。他将演算思路告诉自己的博士生贾惠文，要求他对该过程进行反复推导和验证。最终，他们得出一致结论，攻击过程正确无误。

　　“此前的大半年的时间里，胡老师和我到处碰壁、毫无成果，各种攻击方法尝试了有50多种。有一次，我们甚至都已经将文章投递出去了，但大半夜胡老师发现推导过程有漏洞，让我赶紧撤稿。”贾惠文说。

　　2015年3月15日，为了最后确认已经攻破了GGH密码方案，胡予濮将描述了攻击过程的手稿，发给了提出该方案的3位原作者。4天后，该方案第三作者塞·哈勒维代表3人回函称：“感谢您发送的手稿，您描述的攻击方式，似乎的确打破了我们在GGH一文中提到的多方密钥协商机制。”

　　找到了GGH的漏洞，原作者也承认了胡予濮提出的攻击是有效的，但密码学领域的这场智力较量却才刚刚开始。

　　2015年4月，胡予濮和贾惠文提出组合精确覆盖问题的概念，对精确覆盖这一NP完备问题进行弱化，同时利用改进的编码/零测试工具，又将基于GGH的证据加密方案攻破了。

　　“方案的作者提醒说，我们只是在编码工具公开的情况下才攻破的，这一方案还可以在编码工具隐藏时进行。”胡予濮回忆说，“我们进一步深入研究，把编码工具隐藏的那种方案也给出了有效的密码分析，真正做到了无论在什么情况下，基于GGH的证据加密都不安全。”

　　胡予濮将修改后的论文再次给原作者发过去，对方长时间沉默。

　　推动现代密码学不断向前发展

　　“我们的研究成果，是对GGH密码映射方案的一次釜底抽薪式的攻击。”胡予濮表示，几乎可以断言，在编码工具公开的情况下，任何基于GGH映射的密码应用都是不安全的；在编码工具隐藏的情况下，至少有一个基于GGH映射的密码应用是不安全的；GGH映射很难进行简单修改来避开我们的攻击。

　　密码技术是信息安全的核心技术。胡予濮打了个比方，如果把信息安全当作一个有大门、有围墙的院子。要想进院子，办法有多种，可以翻墙进去，也可以推倒墙进去，还可以挖个洞爬进去，但正常合理的办法是把门上的锁打开，然后推开门走进去。密码技术就是大门上的那把锁，锁的质量好不好，虽然决定不了院子是否安全，但却是合法通行的关键。密码技术的不断研究，推动着信息安全技术的发展。

　　“现代密码学的发展，就是密码编码学和密码分析学‘相互打架’的过程，也就是设计密码和破解密码两拨人的较量。”设计密码的人，希望自己的密码体制难以被对手攻破；破解密码的人，希望自己可以破解对手的所有密码体制。

　　“学术研究上，破解的目的是帮助原有密码变得更加完善，推动现代密码学向前发展。”GGH方案的提出，似乎让人们看到的解决多方密钥交换的曙光。但胡予濮教授的研究成果，证明其存在严重的漏洞，以致其后续无法成为多方密钥交换的标准。有学界关注者认为，“这也意味着，多方密钥交换协议可能又要向后推迟不可预测的时长，才可以出现新的方案。”

　　但同时，这一发现也意味着人们可以不再继续花费时间和精力，去建造基于GGH方案这一密码原语级别的协议，去构建加密标准、拓展出更多的密钥交换使用场景、设定各种流程及业务逻辑，甚至将其运用于商业、金融、军事等一系列领域。“如果这些成本被投放下去、此方案的漏洞才被发现，社会的损失会非常巨大。”

　　“如果真的可以将无需交互就可以在公开信道上共享密钥的机制扩展至三方乃至多方这个公开问题，能用到什么场景中，也许我们绞尽脑汁也想不到、想不全。”胡予濮表示，虽然他们在破解GGH密码方案的过程中已经做了不少工作，但一切才刚刚开始。下一步，他们还将对基于GGH映射的不可区分混淆进行分析。

荐稿人：wfl 2016-3-26  执行编辑：zjy 2016-03-26  责任编辑：tmy 2016-03-30