克里斯蒂娜·阿米蒂奇/广达杂志
如果今天的密码协议失败，就不可能保护在线连接——发送机密信息、进行安全的金融交易或验证数据。任何人都可以访问任何东西；任何人都可以伪装成任何人。数字经济将崩溃。
当（或如果）功能齐全的量子计算机可用时，这正是可能发生的事情。因此，美国政府的国家标准与技术研究院 (NIST) 于 2017 年发起了一场国际竞赛，以寻找实现“后量子”密码学的最佳方法。
上个月，该机构选出了第一批获胜者：四个协议，经过一些修改，将被部署为量子盾牌。它还宣布了仍在考虑中的另外四名候选人。
然后在 7 月 30 日，一对研究人员透露，他们在一小时内用笔记本电脑破解了其中一个候选人。 （从那时起，其他人使攻击速度更快，在几分钟内就破坏了协议。）“如此戏剧性和强大的攻击……令人震惊，”美国大学的数学家和计算机科学家Steven Galbraith说新西兰的奥克兰。攻击背后的数学不仅令人惊讶，而且还减少了后量子密码学的（急需的）多样性——消除了与 NIST 竞赛中的绝大多数方案完全不同的加密协议。
“这有点令人失望，”密歇根大学的密码学家克里斯托弗·佩克特 ( Christopher Peikert ) 说。
结果让后量子密码学界既震惊又鼓舞。动摇了，因为这次攻击（以及前一轮比赛的另一次攻击）突然将看起来像数字钢门的东西变成了湿报纸。 “它出人意料，”领导 NIST 标准化工作的数学家之一达斯汀·穆迪 ( Dustin Moody ) 说。但是，如果密码方案要被破坏，最好在它被广泛使用之前发生。 “你有很多情绪，”加拿大滑铁卢大学的数学家David Jao说，他与 IBM 研究员Luca De Feo在 2011 年提出了该协议。其中当然包括惊喜和失望。 “而且，”Jao 补充道，“至少它现在坏了。”
曲线之间的秘密行走
Jao 和 De Feo 看到了一个加密系统的机会，该系统与众所周知的协议既相似又适当不同。他们的方案称为超奇异同源 Diffie-Hellman 协议 (SIDH)，处理椭圆曲线——与当今部署的最广泛的密码学类型之一中使用的数学对象相同。但它以完全不同的方式使用它们。这也是 NIST 正在考虑的最紧凑的方案（权衡它比许多其他候选方案要慢）。
“在数学上，它真的很优雅，”Jao 说。 “当时，这似乎是个好主意。”
美林谢尔曼/广达杂志
假设两方，爱丽丝和鲍勃，想要秘密交换消息，即使在潜在攻击者的注视下也是如此。它们从一组由称为图的边连接的点开始。每个点代表不同的椭圆曲线。如果您可以以特定方式（通过称为同源图）将一条曲线转换为另一条曲线，请在这对点之间绘制一条边。生成的图表很大，很容易迷失：如果你沿着它的边缘走一段相对较短的路，你最终会到达一个看起来完全随机的地方。
Alice 和 Bob 的图都有相同的点，但边不同——它们是由不同的同源定义的。爱丽丝和鲍勃从同一个点开始，他们每个人都沿着自己图上的随机边跳跃，跟踪他们从一个点到另一个点的路径。然后每个人都会发布他们的结束位置，但对他们的路径保密。
现在他们交换位置：Alice 到 Bob 的最后一点，Bob 到 Alice 的。每个人都重复他们的秘密行走。他们这样做的方式是，他们都将在同一点结束。
这个位置是秘密发现的，所以 Alice 和 Bob 可以使用它作为他们的密钥——允许他们安全地加密和解密彼此的消息的信息。即使攻击者看到 Alice 和 Bob 相互发送的中间点，他们也不知道 Alice 或 Bob 的秘密行走，因此他们无法找出最终端点。
但是为了使 SIDH 工作，Alice 和 Bob 还需要交换一些关于他们步行的额外信息。这些额外的信息是导致 SIDH 垮台的原因。
旧数学的新转折
Thomas Decru并没有打算打破 SIDH。他试图在此基础上再接再厉——推广增强另一种密码学的方法。这没有成功，但它引发了一个想法：他的方法可能对攻击 SIDH 有用。于是他找到了他在比利时鲁汶天主教大学的同事，也是他的一位前博士顾问Wouter Castryck ，两人深入研究了相关文献。
他们偶然发现了数学家恩斯特·卡尼 (Ernst Kani ) 于 1997 年发表的一篇论文。其中有一个“几乎立即适用于 SIDH”的定理，Castryck 说。 “我想一旦我们意识到……攻击来得很快，在一两天内。”
最终，为了恢复 Alice 的秘密行走（以及共享密钥），Castryck 和 Decru 检查了两条椭圆曲线的乘积——Alice 的起始曲线和她公开发送给 Bob 的曲线。这种组合产生了一种称为阿贝尔曲面的曲面。然后，他们使用了这些阿贝尔曲面、卡尼定理（将阿贝尔曲面与椭圆曲线联系起来）以及爱丽丝给鲍勃的额外信息，以揭示爱丽丝所采取的每一步。
“这几乎就像一个归位信号，可以让你锁定[某些阿贝尔曲面]，”Jao 说。 “那个信号告诉你，这是你应该采取的下一步行动，以找到正确的[秘密步行]。”这让他们直接找到了 Alice 和 Bob 的共享密钥。
“这是一种非常出人意料的方法，通过更复杂的对象来得出关于更简单对象的结果，”Jao 说。
Meta AI Research 的数学家和密码学家Kristin Lauter说：“我很高兴看到这种技术被使用，”他不仅帮助开发了基于同源的密码学，而且还研究了阿贝尔曲面。 “我很惭愧，因为我没有把它当作打破 [它] 的一种方式。”
Castryck 和 Decru 的攻击在 62 分钟内打破了 SIDH 协议的最低安全版本，并在不到一天的时间内打破了最高安全级别。然后，不久之后，另一位专家对攻击进行了调整，只需要 10 分钟就可以破解低安全版本，并用几个小时破解高安全版本。过去几周发布的更普遍的攻击使得 SIDH 不太可能被挽救。
“那是一种特别的感觉，”卡斯特里克说，虽然是苦乐参半。 “我们杀死了我们最喜欢的系统之一。”
分水岭时刻
不可能保证系统是无条件安全的。相反，密码学家依靠足够的时间流逝和足够多的人试图破解这个问题来感到自信。布朗大学的数学家Jeffrey Hoffstein说：“这并不意味着你明天不会醒来发现有人找到了一种新算法来做这件事。”
因此，为什么像 NIST 这样的比赛如此重要。在上一轮 NIST 竞赛中，IBM 的密码学家 Ward Beullens 设计了一种攻击，在周末破坏了名为 Rainbow 的计划。与 Castryck 和 Decru 一样，他只有在从不同的角度看待潜在的数学问题后才能发动攻击。就像对 SIDH 的攻击一样，这次攻击破坏了一个系统，该系统依赖于与大多数提议的后量子协议不同的数学。
“最近的攻击是一个分水岭，”初创公司 PQShield 的密码学家Thomas Perst说。他们强调了后量子密码学的难度，以及研究各种系统的安全性可能需要进行多少分析。 “一个数学对象在一个角度可能没有明显的结构，而在另一个角度有一个可利用的结构，”他说。 “困难的部分是确定正确的新视角。”
原文： https://www.quantamagazine.org/post-quantum-cryptography-scheme-is-cracked-on-a-laptop-20220824/