颇有潜力的后量子加密算法仅1小时就被完全破解

近期，两位研究人员在1个小时内使用一台10年“高龄”台式计算机成功破解后量子加密算法。

如果人们使用功能先进的量子计算机系统时，网络将面临着安全危机，因此，2017年美国政府和国家标准与技术研究所(NIST)发起了一项国际比赛，用于寻找实现“后量子加密(post-quantum cryptography)”的最佳方式。

今年7月份，美国政府和国家标准与技术研究所选出了第一批获奖者——四个加密算法，它们经过一系列修正后，将作为量子盾部署的四项加密算法，同时，该机构还宣布了四项正在考虑中的候选算法。

7月30日，两位研究人员披露称，他们在1个小时内使用一台计算机就能破解其中一款加密算法(之后其他研究员也开始破解安全算法，并且破解时间更快，有时仅用几分钟时间)，值得注意的是，该记录并非由某台先进计算机创造的，而是来自一台具有10年“高龄”CPU的台式计算机，而且是单核运行，这次破解加密算法让研究人员意识到后量子密码学在被采用之前需要克服许多障碍。

新西兰奥克兰大学数学家和计算机科学家史蒂文·加尔布雷斯(Steven Galbraith)说:“一次如此戏剧性和强大的攻击……是相当令人震惊的，这不仅是因为破解安全算法所采用的数学原理令人感到惊奇，而且还减少了后量子密码学的多样性，消除了一种与NIST竞赛中绝大多数方案工作方式差异很大的加密算法。”

美国密歇根大学密码学家克里斯托弗·佩科特(Christopher Peikert)说：“这有点令人感到失望，该研究结果让后量子密码学界既感到震惊，又感到振奋，震惊是因为这次破解出乎预料，突然将一个看起来像数字铁门的事物变成了湿报纸。”

美国政府和国家标准与技术研究所标准化工作负责人达斯汀·穆迪(Dustin Moody)说：“研究人员仅用1个小时就破解加密算法，这太难以置信，如果一个密码系统方案要被破解，最好是在它投入广泛应用之前就被破解，否则将面临重大损失。”

“秘密曲线”

加拿大滑铁卢大学数学家戴维·饶(David Jao)和同事开始关注加密系统破解，他们的密码系统既类似于众所周知的常规性算法，又有适当的差异，该算法方案被称为“超奇异同源迪菲-赫尔曼算法(SIDH)”，主要是处理椭圆曲线，同样的数学对象被用于现今最广泛的密码学类型。据悉，SIDH算法最初于2011年提出，设计者从超奇异同源椭圆曲线的角度提出一种抵御量子攻击的密码系统，该密码系统依赖于计算超奇异椭圆曲线之间同源的困难性问题，而且密钥长度明显要比其他后量子密码长度短。

戴维说：“从数学角度上讲，椭圆是非常优雅的曲线，应用椭圆曲线作为定理的加密算法是非常不错的。”

如果有两条椭圆曲线(E1和E2)，我们能够创建一个函数，将E1曲线上的点P映射到E2曲线上的点Q，这个函数被称为同源函数，如果我们能映射这个函数，E1曲线每一个点都可以映射到E2曲线，秘密密钥是同源的，公开密源是椭圆曲线。之后假设两个密钥交换当事人分别为爱丽丝和鲍勃，他们希望秘密交换一条信息，即使是在潜在攻击者的监视之下，对于密钥交换，爱丽丝和鲍勃互相将同源曲线混合，从而生成一条“秘密曲线”。

爱丽丝和鲍勃的密钥交换从一组点开始，这些点由叫做“图表”的边线连接起来，每个点代表一条不同的椭圆曲线，如果你能以一种特定方法将一条曲线转换成另一条曲线(通过同源地图)，在两个点之间画一条边线，由此产生的“图表”非常大且复杂，如果沿着边线前行一段相对较短的路程，将会在一个看似完全随机的地点结束。

爱丽丝和鲍勃的图表都有相同的点，但是边线是不同的，该情况被定义为非同源，爱丽丝和鲍勃的交换密钥从同一个点开始，沿着各自的图表上的随机边线跳跃，跟踪从一个点到另一个点的路径，之后爱丽丝和鲍勃都公布了密钥的结束位置，但对相关路径保密。

现在爱丽丝和鲍勃交换位置：爱丽丝到鲍勃的最终点，鲍勃到爱丽丝的最终点，每次都重复“秘密曲线”，这样他们最终会在同一点结束。这个点位已被破解，所以爱丽丝和鲍勃可以用该点位作为秘密密钥——允许安全地加密和解密彼此的信息，即使网络攻击者看到他们发送给彼此的中间点，也不会知道他们的“秘密步数”，因此网络攻击者无法算出最终端点。

但是为了运行SIDH算法，爱丽丝到鲍勃还需要交换关于“秘密曲线”的额外信息，这些额外信息导致了SIDH算法被破解。

传统数学理论的“新转折”

研究员托马斯·德克鲁(Thomas Decru)并未打算破坏SIDH算法，他试图在此基础上进一步应用该方法增强另一种类型密码学，并未成功，却激发了一个新想法，该方法可能对攻击SIDH算法有效。于是，他找到了比利时鲁汶大学同事沃特·卡斯特里克(Wouter Castryck)，他们开始钻研相关文献资料。

他们偶然发现了数学家恩斯特·卡尼(Ernst Kani)于1997年发表的一篇论文，其中有一个定理“几乎能适用于SIDH算法”，卡斯特里克说：“我们曾认为它破解加密算法非常快，可能需要1-2天时间。”

最终，为了恢复爱丽丝的“秘密步数”，以及共享密钥，卡斯特里克和德克鲁检查了两条椭圆曲线的运地结果——爱丽丝的起始曲线，以及她公开发送给鲍勃的曲线，该组合产生了一种叫做“交换面”的曲面，之后他们使用“交换面”、Kani定理(与“交换面”相关的椭圆曲线定理)以及爱丽丝给鲍勃的额外信息，从而揭晓爱丽丝所走的每一步。

Meta AI Research公司的数学家和密码学家克里斯汀·劳特尔(Kristin Lauter)说：“看到该技术被使用，我感到非常兴奋！它不仅有助于开发基于同活的密码学，还研究了交换面，因此我对自己未将该算法作为破解加密算法的解决方案，而感到羞愧。”

目前，德克鲁和卡斯特里克在62分钟内破解了SIDH算法的最低安全等级的算法，并在不足1天的时间内破解了最高安全等级的算法。随后不久，另一位安全专家对网络攻击进行了调整，仅需10分钟便能破解最低安全等级的算法，几个小时就能破解了最高安全等级的算法。在过去几周的时间里，更多一般性网络攻击使得SIDH算法接近崩溃。

一个分水岭

美国布朗大学数学家杰弗里·霍夫斯坦(Jeffrey Hoffstein)说:“我们不可能保证某个加密系统是无条件安全的，相反，密码学家依靠充足的时间和人力试图破解来产生自信，这意味着当明天早上一觉醒来时，你无法保证不会有人能采用某种新算法破解该加密系统。”

因此，像美国政府和国家标准技术研究所举办此类竞赛是非常重要的，在上一轮比赛中，IBM公司密码学家沃德·伯伦斯(Ward Beullens)设计了一次网络攻击，破坏了彩虹签名算法，与卡斯特里克和德克鲁一样，伯伦斯只有从不同角度分析潜在的数学问题后，才对该加密算法攻击奏效。就像对SIDH算法的攻击一样，此次攻击破坏了一个依赖不同于多数提议后量子算法的数学系统。

初创公司PQShield密码破译专家托马斯·普雷斯特(Thomas Prest)说：“最近发生的加密算法破解是一个分水岭，研究后量子密码学难度很大，同时分析各种算法系统的安全性并非简单的事情，一个数学对象可能在某个角度上没有明显结构，但在另一个角度上则有开发结构，最难的部分就是寻找正确的新视角。”