如果今天的密码协议失败，就不可能保护在线连接——发送机密信息、进行安全的金融交易或验证数据。 任何人都可以访问任何东西； 任何人都可以伪装成任何人。 数字经济将崩溃。
当（或 if）功能齐全的量子计算机变得可用，这正是可能发生的事情。 因此，美国政府的国家标准与技术研究院 (NIST) 于 2017 年发起了一项国际竞赛，以寻找实现“后量子”密码学的最佳方法。
上个月，该机构选出了第一批获胜者：四个协议，经过一些修改，将被部署为量子盾牌。 它还宣布了仍在考虑中的另外四名候选人。
然后在 30 月 XNUMX 日，一对研究人员透露，他们已经 破坏了其中一名候选人 在笔记本电脑上一个小时。 （从那时起，其他人使攻击速度更快，在几分钟内就破坏了协议。）“如此戏剧性和强大的攻击......真是令人震惊，”说 史蒂文·加尔布雷思，新西兰奥克兰大学的数学家和计算机科学家。 攻击背后的数学不仅令人惊讶，而且还减少了后量子密码学的（急需的）多样性——消除了与 NIST 竞争中绝大多数方案的工作方式截然不同的加密协议。
“这有点令人沮丧，”说 克里斯托弗·佩克特，密歇根大学的密码学家。
结果让后量子密码学界既震惊又鼓舞。 动摇了，因为这次攻击（以及前一轮比赛的另一次攻击）突然将看起来像数字钢门的东西变成了湿报纸。 “它突然出现，”说 达斯汀穆迪，领导 NIST 标准化工作的数学家之一。 但是，如果密码方案要被破坏，最好在它被广泛使用之前发生。 “有很多情绪通过你，”说 大卫·饶，加拿大滑铁卢大学的数学家，与 IBM 研究员一起 卢卡德费欧，在 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 垮台的原因。
旧数学的新转折
托马斯·德克鲁 并没有打算打破 SIDH。 他试图在此基础上再接再厉——推广增强另一种密码学的方法。 这没有成功，但它引发了一个想法：他的方法可能对攻击 SIDH 有用。 于是他走近 沃特卡斯特里克，他在比利时鲁汶天主教大学的同事和他的一位前博士顾问，两人深入研究了相关文献。
他们偶然发现了数学家发表的一篇论文 恩斯特·卡尼 1997 年。Castryck 说，这是一个“几乎立即适用于 SIDH”的定理。 “我想一旦我们意识到……攻击来得很快，在一两天内。”
最终，为了恢复 Alice 的秘密行走（以及共享密钥），Castryck 和 Decru 检查了两条椭圆曲线的乘积——Alice 的起始曲线和她公开发送给 Bob 的曲线。 这种组合产生了一种称为阿贝尔曲面的曲面。 然后，他们使用了这些阿贝尔曲面、卡尼定理（将阿贝尔曲面与椭圆曲线联系起来）以及爱丽丝给鲍勃的额外信息，以揭示爱丽丝所采取的每一步。
“这几乎就像一个归位信号，可以让你锁定[某些阿贝尔曲面]，”Jao 说。 “那个信号告诉你，这是你应该采取的下一步寻找正确的[秘密步行]的方式。” 这让他们直接找到了 Alice 和 Bob 的共享密钥。
“这是一种非常出人意料的方法，通过更复杂的对象来得出关于更简单对象的结果，”Jao 说。
“我很高兴看到这种技术被使用，”说 克里斯汀劳特，Meta AI Research 的数学家和密码学家，他不仅帮助开发了基于同源的密码学，而且还研究了阿贝尔曲面。 “我很惭愧，因为我没有把它当作打破 [它] 的一种方式。”
Castryck 和 Decru 的攻击在 62 分钟内打破了 SIDH 协议的最低安全版本，并在不到一天的时间内打破了最高安全级别。 然后，不久之后，另一位专家对攻击进行了调整，因此只需 10 分钟就可以破解低安全版本，并用几个小时来破解高安全版本。 更一般的攻击 在过去几周发布 使SIDH不太可能被抢救。
“那是一种特别的感觉，”卡斯特里克说，虽然是苦乐参半。 “我们杀死了我们最喜欢的系统之一。”
分水岭
不可能保证系统是无条件安全的。 相反，密码学家依靠足够的时间流逝和足够多的人试图破解这个问题来感到自信。 “这并不意味着你明天不会醒来发现有人找到了新的算法来做这件事，”说 杰弗里霍夫斯坦，布朗大学的数学家。
因此，为什么像 NIST 这样的比赛如此重要。 在上一轮 NIST 竞赛中，IBM 的密码学家 Ward Beullens 设计了一种攻击 破坏了一个名为彩虹的计划 在一个周末。 像 Castryck 和 Decru 一样，他只有在从不同的角度看待潜在的数学问题后才能发动攻击。 就像对 SIDH 的攻击一样，这次攻击破坏了一个系统，该系统依赖于与大多数提议的后量子协议不同的数学。
“最近的袭击是一个分水岭，”说 托马斯·珀斯特，初创公司 PQShield 的密码学家。 他们强调了后量子密码学的难度，以及研究各种系统的安全性可能需要进行多少分析。 “一个数学对象在一个角度可能没有明显的结构，而在另一个角度有一个可利用的结构，”他说。 “困难的部分是确定正确的新视角。”
