专克量子计算机的超级密码，被10年前的老爷机干碎了
本文来自微信公众号：差评 （ID：chaping321），撰文：及格，编辑：面线，题图来自：视觉中国
最近美国科研圈估计很头大。就在上个月美国国家标准与技术研究所（NIST）结束了一项为期 6 年的国际竞赛，目的是寻找对抗量子计算机的加密算法。
之所以，有这么个竞赛，实在是加密专业的人的活的太惨，堪比国内的土木专业。
自从量子计算机出现，各个学科都赢麻了，唯独搞密码学的崩溃了。
这源于密码学一向叛逆的定位：别的学科是为了算出一个答案，密码学是防止别人算出一个答案。因此，量子计算机直接对密码学带来了“连根拔起”的威胁。
拿最常见的 RSA-2048 算法举例，这个算法是由 2048 位长的加密信息组成的，即使是最先进超级计算机也需要 3 千万年才能破解。（日本的富岳超级计算机，计算速度?442 Pflop/s）
但是量子计算只需要 8 个小时。（使用穷举法，一个一个的试）
这就导致量子计算机原则上可以快速破解大多数的加密算法。
为了应对这种量子层面威胁，世界各地的密码学家在过去的二十年里一直在设计用来抵抗量子计算机攻击的后量子加密算法，并诞生了相应的算法竞赛。
不过，更戏剧的是，这个竞赛刚宣布结果没多久，8 强选手之一的 SIKE 算法，就被人满血给秒了。
而且，SIKE 算法是被一台十年前的台式机，用单核处理器在 4 分钟内破解了低安全版本，并在一个小时内破解了该算法的最强形态。
这有多麻瓜呢？
和 SIKE 安全级别相同的?RSA3068?算法，用目前最先进的超级计算机破解，需要大约 2 万亿年的时间，比宇宙存在的时间都要长。
然而， SIKE 算法，在一台 10?年前的英特尔单核台式机面前，只坚持了一个小时。
一个对抗量子计算机的超级算法，被台式机给击败了，这离谱程度不亚于哥斯拉，被咱们的二踢脚给炸飞了。
不过，差评君仔细研究了一下发现：这可能只是一个严肃科学界的乌龙事件。
这个名为 SIKE 的算法之所以“一碰就碎”，还得从算法的内核说起。
在这个幺蛾子之前，SIKE 算的上是 21 世纪的算法新星了。
这个算法是一种基于超椭圆曲线的年轻加密算法。在它诞生的 12 年里，一直在加强，从未被超越。
它最大的卖点，在超高的性价比上——安全性很高，而且体积还小。
一个由?335?个数字组成的?SIKE?算法，和由?3068?个数字组成的常用算法（RSA?算法），安全性是同一级别的。这就好像用十进制来表达二进制的数字，不仅方便，而且更加简洁。
在 NIST 收集的 90?多种后量子算法中，SIKE 及其衍生的算法占据了绝对的上风，成为最短后量子密码中的的前 16 强。
也正是因此，SIKE 算法一直有不少的拥护者，想要见证和创造历史。
不过，有趣的是，这个算法的破解者托马斯?·?德克鲁也是其中之一。
托马斯是这么描述他的破解过程的：一天，托马斯在和同事沃特?·?卡斯特里克，在研究 SIKE 算法，试图用来增强其他密码的安全性。
结果在研究相关文献的时候，发现了一篇 1997 年的论文。论文中，有一个“几乎立即适用于 SIKE 算法”的定理，以至于他们在两天之内“反向加强”了 SIKE 算法，并用台式机破解了它。
这就邪门了呀，要知道在此之前这个算法的破解已经 10?年没有进展了，而托马斯只用了两天，甚至还写出了一个没有 bug 的破解程序。不仅是密码学家，就连程序员都得羞愧难当了。
8 月 5 日，他们在一篇论文中记录了这一神奇的破解方法：
虽然椭圆曲线是一维对象，但在数学中，椭圆曲线可以被可视化为二维或任何其他维数的对象。人们可以在这些广义对象之间创建同源。
通过应用一个 25 年前的定理，新的攻击使用 SIKE 公开的额外信息来构建二维的同源。然后这种同源性就可以重建 SIKE 用来加密消息的密钥。
专业以外的人其实很难理解，这一过程的有趣之处。
做一个不是很恰当的比方：
这个?SIKE?算法就像一个平面几何问题（也就是二维问题），专门用来对抗量子计算机的运算能力，因为平面几何的难点在于画辅助线。
让计算机一条一条地试辅助线，不知道得试到什么时候去了。
但是 Thomas 将这个图形三维化了，它变成空间向量坐标系的问题。
这样子，这个问题就可以通过列方程组来解决，这就又回到计算的范畴了。
所以，这一次破解 SIKE 算法的关键，被归功于数学之神的青睐。
对此，有位密码学家对这个算法的破解给予了高度的评价，“我怀疑：世界上只有不到 50?人掌握了破解 SIKE 算法必要的数学和密码学知识。”
当然，我也怀疑这个密码学家是在强行找回面子。
因为这个问题的破解者，只是一个非著名大学“鲁汶大学”的博士后，甚至不是 NIST 密码破解组的成员，而是一个业余爱好者。
也有大佬比较客观地表示：“我们应该做好剩下的 7 个选手都被干掉的准备，毕竟所有的密码在被破解之前，看起来都很可靠。”?
总而言之，自从 1981 年量子计算机的概念被提出以来，算法的加密和破解之间的战斗，比之前的几千年都要剧烈。
在此之前，密码学的圣经是：“想要密码更安全？简单加大计算量就行了”。相较于计算机运算速度的发展，将加密信息从 100?位增加到 1000?位，或者是将一种算法更换成更复杂的算法，就已经够用了。
但是，后量子时代要求密码学家的思维更加开阔。
比如，这次竞赛中的另一个种子选手——格算法（Ring learning with errors）就是一个格局非常打开的存在。
格算法看起来比较简单，像是一个将经典问题放在坐标系里。
但是它这个坐标系有些霸道，为了保证安全性，这个坐标系的维度常年保持在 1000?维以上。这就相当于，大家还在做一元二次方程的年纪，你已经在进行 1000?元二次方程的求解了。
同样是九年义务教育，为啥你这么优秀呢？
当然，这也只是冰山一角。
过去几十年，整个密码学都被量子计算机这一个没有落地的概念给唬住了，然后开始拼了命的逃亡。我们见证了密码学的崩溃、重构，甚至衍生出了一种理论上无敌的量子密码，想要找回场子。
科学，真是太魔幻了。
图片、资料来源：
【 后量子密码 】基于格 ( RLWE ) 问题的密钥交换协议和原理 ? 知乎
十年台式机，单核1小时破解后量子加密算法，密码学家：太突然了 ?机器之心
为什么说量子计算机比超级计算机速度快？?知乎
【?后量子密码 】是什么？为什么RSA"不行了"？有什么用？研究和应用现状如何？?知乎
“ Quantum-Safe ” Crypto Hacked by 10-Year-Old PC
Data Is Vulnerable to Quantum Computers That Don’t Exist Yet
‘ Post-Quantum ’ Cryptography Scheme Is Cracked on a Laptop
What Is the Future of Quantum-Proof Encryption?
本文来自微信公众号：差评 （ID：chaping321），撰文：及格，编辑：面线
