MIT 80万亿次平方运算加密难题，被小哥用家用台式机自学破解

近日，麻省理工学院（MIT）正式宣布一名自学成才的比利时程序员 Bernard Fabrot 成功破解了 RSA 算法发明者 Ron Rivest 20 年前提出的难题。据称，这一行动对于当前流行的加密算法将产生深远影响。

这个名为 LCS35 的难题是由加密算法界元老、RSA 暗码系统发现者之一、MIT 教授 Ron Rivest 在 1999 年 4 月提出的。发起者们曾预测：以 1999 年的芯片计算速度作为起点并考虑到 摩尔定律 的话，即使用最快的增长模型，破解这一难题所需的算力也要在 35 年之后（也就是今天看来，最快 15 年之后）才能出现。

如果你感兴趣的话，问题在这里：https://people.csail.mit.edu/rivest/lcs35-puzzle-description.txt

然而，Bernard Fabrot 这次只使用了一台 CPU 为英特尔Core i7 的家用台式机就把问题解决了。

Bernard Fabrot

据 MIT 介绍，Fabrot 花费了三年半的时间解决这一难题，这一题目涉及到长度为 80 万亿次平方运算的起始数字，而且专门被设计为阻止破解者使用并行算法进行加速破解。

1999 年 4 月初，一个时间胶囊（time capsule）被送到著名建筑师 Frank Gehry 手中，并指示他将这个时间胶囊融入到建筑设计中，而这最终建成了麻省理工学院（MIT）的计算机科学暨人工智能实验室（CSAIL）。这个时间胶囊本质上是一个早期计算机历史博物馆，其中收藏有微软创始人比尔·盖茨和万维网之父蒂姆·伯纳·李爵士捐赠的 50 件物品。

这个时间胶囊在 35 年内不会被公开—直到有人可以破解设计中的暗码加密。该暗码加密由 Ron Rivest 设计，其名字中的「R」代表了 RAS 暗码系统中的「R」，该系统是有史以来最重要的加密协议之一。Ron Rivest 称加密的设计并不复杂，但几乎要花费 35 年的时间才能计算出答案。

4 月 15 日，在 Rivest 提出该难题的 20 年之后，一位自学成才的比利时程序员 Bernard Fabrot 解决了这一难题。该难题的原始指令是将解决方案送到计算机科学实验室主任手中，但 Fabrot 意外地发现该实验室不存在了（该实验室在 2003 年与 MIT 的人工智能实验室合并为 CSAIL）。更令 Fabrot 感到惊讶的是，当他告知 CSAIL 主任 Daniela Rus 自己的解决方案时，这位主任竟然不知道该难题的存在。

Rivest 的难题主要是为了得出运行平方运算近 80 万亿次所得到的最终数字。举例而言，当你计算 2 的平方会得到 4，计算 4 的平方会得到 16，以此类推，运行平方运算 80 万亿次。之后，利用最终得到的数字运行一个数学运算，而该运算又将使用最终的平方运算数字以及难题提示给出的一个数字。这样会分解出一个可以被编译成简短祝贺短语的新数字（Rivest 和 Fabrot 均拒绝透露精确短语，该短语会在 5 月 15 日的时间胶囊开启仪式上公布）。

该难题的关键在于其要求序列运算，这意味着你无法通过并行计算而更快地得到答案。你需要在前一个平方运算结果的基础上一步步地运行平方运算，所以使用更多计算机或采用超级计算机对结果无益。根据摩尔定律以及 1999 年运行平方运算需要花费的时间，Rivest 预测计算出该难题的答案应该需要 35 年左右。

Fabrot 是一位独立开发者，他在 2015 年偶然发现了这个难题。尽管 Rivest 最初以 Java 语言发布了该难题的代码，但 Fabrot 意识到如果自己使用 GNU Multiple Precision Arithmetic Library（一款用于「精确计算」的免费软件），则能更快地解决这一难题。因此，Fabrot 专门在其家用台式电脑中安装一个 CPU 内核来全天候、无眠无休地运行平方运算。

Fabrot 说：「这些年，除了很亲密的朋友，没有人知道我在尝试解决这个难题。我觉得自己有可能解决这个难题，如果我告诉别人，那他们可能用更强大的 CPU 来打败我。」

三年半之后，Fabrot 最终完成了大约 80 万亿平方运算，并获得了难题的解决方案。时间刚刚好！虽然 Fabrot 不知道，一组计算机科学家和密码学专家正在研究一个名为 Cryptophage 的项目，该项目使用专门的硬件来解决 MIT 的难题。

前英特尔工程师 Simon Peffers 领导的 Cryptophage 小组在研究可验证延迟函数作为区块链（如以太坊）安全机制的可能性。可验证延迟函数是 Rivest 早期关于时间延迟密码学的现代成果，它们的解决方案只能通过序列运算获取。Peffers 表示，研究期间 Cryptophage 小组遇到了 Rivest 的难题，他们认为该难题是验证其研究的不错方式。

3 月中旬，该团队开始运行萨班吉大学研究人员 Erdinc Ozturk 设计的一个算法，该算法被优化用来减少平方运算之间的延迟。它是在 FPGA 芯片上实现的，这款芯片是多用途的，只运行特定算法，因此比通用 CPU 更高效。使用 Ozturk 的算法，FPGA 比运行非优化软件的高端商用 CPU 快了约 10 倍。

基于芯片的计算效率，Cryptophage 小组估计其将在 5 月 10 日晚上得出 MIT 难题的正确解决方案，这离他们开始计算仅两个月而已。当他们联系 MIT 并声称即将有一个解决方案出炉时，Rivest 告诉他们 Fabrot 已经捷足先登，给出答案了。

「在这两拨人几乎同时来找我们并告诉我们说解决了这个问题之前，几乎从没有人来找过我们，这真是一个惊人的巧合。」Rivest 表示。

Rivest 很快承认，自己高估了难题的难度。Rivest 表示，在如此长的时间内对技术的进步进行预测有些困难，他没想到像 FPGA 芯片这样的突破，以前的芯片没这么复杂，用途也没这么广泛。

Ron Rivest，著名密码学家，MIT 教授。

尽管 Cryptophage 小组不是第一个揭开难题的，但 Peffers 表示他们仍将出席 5 月 15 号的时间胶囊开启仪式。只有胶囊的设计者知道里面的全部内容，不过它的确包含蒂姆·伯纳斯-李（万维网的发明者）、罗伯特·梅特卡夫（以太网的发明者）和比尔·盖茨等人的贡献。Fabrot 说，他最兴奋的是看到胶囊里有 Zork（最早的电脑游戏之一）的原件。

参考内容：

• https://www.csail.mit.edu/news/programmers-solve-mits-20-year-old-cryptographic-puzzle

• https://people.csail.mit.edu/rivest/pubs/RSW96.pdf

• https://www.wired.com/story/a-programmer-solved-a-20-year-old-forgotten-crypto-puzzle/