西电教授攻破国际密码学难题

2016年3月22日《西安晚报》第五版

        一个原本有望成为国际密码学研究新技术的GGH密码映射方案，最近被西安电子科技大学胡予濮教授攻破，对GGH映射本身以及基于GGH映射的各类高级密码应用进行了颠覆性的否定。胡予濮教授的相关研究成果已经被2016年欧洲密码年会正式接收。5月8日，胡予濮将赴奥地利维也纳，在欧密会上正式向全世界的密码同行报告这一突破性成果。
        世界密码学者试图解决的一个公开问题
        “用最通俗的话来说，GGH密码是和人们的通信安全有关。”西安电子科技大学综合业务网理论及关键技术国家重点实验室的胡予濮教授表示，1976年以前，人们在通信领域的观念是“不事先进行秘密共享是无法进行保密通信”。1976年，斯坦福大学的密码学家惠特菲尔德·迪菲和马丁·赫尔曼首次提出公钥密码体制的思想，给出非交互密钥协商的概念。胡予濮介绍，“提出这个概念后，颠覆了人们传统的观念，使得用户可以在一个完全开放的信道上进行秘密共享，实现保密通信。这一思想上的突破，成为了现今密钥交换系统的基础，被广泛应用于网络通信。”
        “举个通俗的例子，假设有A和B两人在异地， A想告诉B一个秘密，但不想让其他人知道，若直接写信的话，可能会被快递员偷看，现在他把秘密放进一个带锁的盒子里，B收到盒子后再用钥匙打开，但前提是B和A要事先拥有共同的钥匙。而‘事先拥有共同的钥匙’其实就是密钥协商 。”胡予濮教授的博士研究生贾惠文说。
        “迪菲与赫尔曼实现了无需交互就可以在公开信道上共享密钥，但仅限于两方。如何将这一机制扩展至三方乃至多方，一直是现代密码学没有解决的公开问题。在接下来的几十年中，全世界密码学者们都在试图解决这个公开问题，然而研究始终未能取得突破性进展。”胡予濮表示，2013年的欧密会上，时为加州大学洛杉矶分校的博士生萨吉·杰瑞格以及IBM研究员克雷格·金特里和塞·哈勒维，共同提交了一篇论文《基于理想格的候选多线性映射方案》。该论文提出一个分级编码系统概念，并以此在理想格上实现了第一个多线性映射方案（GGH映射，取名于三位作者姓名Garg、Gentry和Halevi的首字母），进而解决了现代密码学遗留的这个公开问题，这篇论文也因此获得当年欧密会的最佳论文奖。
        “GGH多线性映射方案，对密码学界产生了深远的影响，迅速在国际密码学界引发了多线性研究的热潮。”胡予濮介绍，这几个人因为这个里程碑式的密码映射方案，不仅为密码学界遗留下来的公开问题找到了答案，也促使了其他近似多线性映射方案的构造，并有望在未来广泛应用于证据加密、广播加密、属性加密、功能加密、聚合签名等多种场合，从而将现代密码学大大地向前推进一步。但由于多线性映射的特殊性，杰瑞格等人无法直接证明GGH密码方案是安全可行的，所以他们在论文中采取穷举攻击的办法，尝试了所有现存的以及他们自己提出的攻击方法，来间接表明该方案是安全的。胡予濮说，“2014年5月底，我在日本九州大学进行学术访问时，无意间了解到了这个信息，觉得很有意义，就尝试着要对它进行密码分析，也就是破解。”
        沉浸“密码世界”挑战国际顶尖研究
        “粗看上去，杰瑞格等人提出的GGH密码映射方案到处都是漏洞，但你就是无论如何也攻破不了它。”胡予濮回忆他初次接触GGH时说，“GGH提出者均是当今国际上顶尖的密码研究者，他们的方案十分完整，已经列举了各种能够想到的攻击方法，并都进行了尝试。”
        从2014年5月底到2015年2月中旬，胡予濮的脑海里全是GGH密码方案，他完全沉醉在格公钥密码、数论、概率统计等学科的世界里。
        “在攻破GGH密码方案的过程中，最具有纪念意义的一天是2015年3月7日。”胡予濮表示，“我一晚上都没睡觉，突然觉得GGH的结构有些不对，半夜起来开始验算。到了第二天早上还是觉得不对，又躺在床上稍微休息了一会儿，希望等脑子清醒了继续推算。到了中午时候，我再一步一步进行验证，第一次发现了GGH的漏洞确实是存在的！”胡予濮激动地说，即便经过多次推导，已经验证了GGH存在漏洞，但自己还是没有轻易下结论说攻破了这一方案。他将演算思路告诉自己的博士生贾惠文，要求他对该过程进行反复推导和验证。最终，他们得出一致结论，攻击过程正确无误。
        “在此前的大半年时间里，胡老师和我到处碰壁、毫无成果，各种攻击方法尝试了50多种。有一次，我们甚至都已经将文章投递出去了，但大半夜胡老师发现推导过程有漏洞，让我赶紧撤稿。”贾惠文表示。
        2015年3月15日，为了确认已经攻破了GGH密码方案，胡予濮将描述攻击过程的手稿发给了该方案的三位原作者。“该方案的第三作者塞·哈勒维代表三人回函称：‘感谢您发送的手稿，您描述的攻击方式，似乎的确打破了我们在GGH一文中提到的多方密钥协商机制。’”胡予濮告诉记者，找到了GGH的漏洞，原作者也承认了他提出的攻击是有效的，但密码学领域的这场智力较量却刚刚开始。后来，胡予濮和贾惠文将进一步的研究成果发给GGH相关论文的作者，对方一片沉默。
        利用“组合拳”破解“高人”研究成果
        “我们的研究成果，一是攻破了GGH映射的安全性假设，二是攻破了基于GGH映射的非交互多方密钥交换协议，三是攻破了基于GGH映射的第一个证据加密方案（无论编码工具公开还是隐藏），四是给出GGH映射的两个修改方案并对它们进行有效攻击。可以说，这是一套组合拳，是对GGH密码映射方案一次釜底抽薪式的攻击。”胡予濮表示。
      密码学和信息安全有什么关系？密码技术是信息安全的核心技术。胡予濮说，如果把信息安全当作一个有大门、有围墙的院子。要想进院子，办法有多种，可以翻墙进去，也可以推倒墙进去，还可以挖个洞爬进去，但正常合理的办法是把门上的锁打开，然后推开门走进去。密码技术就是大门上的那把锁，锁的质量好不好，虽然决定不了院子是否安全，但却是合法通行的关键。密码技术的不断研究，推动着信息安全技术的发展。
        胡予濮介绍，现代密码学发展，就是密码编码学和密码分析学“相互打架”的过程，也就是设计密码和破解密码两拨人的较量。设计密码的人希望自己的密码体制难以被对手攻破，破解密码的人希望可以破解敌方的所有密码体制。
        “学术研究上，破解的目的是帮助原有密码变得更加完善，推动现代密码学向前发展。GGH可以被看作是一种密码原语，一旦被证明安全可行，就可以在它的基础上构造出许多新的密码体制，将极大地丰富未来密码应用的场景。”胡予濮表示，虽然他们在破解GGH密码方案的过程中已经做了不少工作，但一切才刚刚开始，下一步他们还将对基于GGH映射的不可区分混淆进行分析。 通讯员秦明 记者任娜