20年无人能破的RSA算法发明人出的密码学难题, 竟被这个无名程序员3年破解！

来源 | WIRED

编译 | Guoxi

责编 | Aholiab

出品 | 区块链大本营（blockchain_camp）

1994 年 4 月，作为麻省理工学院计算机科学实验室成立 35 周年的庆祝活动，时任实验室主任 Michael Dertouzos 设计了一个“创新成果时间胶囊“。

他将一系列计算机领军人物的创新成果收录其中，准备在35年后再取出来，作为实验室成立 70 周年的献礼工程。

不过问题来了，如何能保证刚好在 35 年之后取出来呢？这可难不倒麻省理工学院这些顶级的科学家，他们为时间胶囊设计了一把“密码锁“，也就是一道密码学难题。

同时，他们还非常严谨地考虑了未来计算机算力的提升速度，特意加大难度，使得密码学难题至少需要 35 年时间来破解。

业界一众密码学大牛也都十分清楚，麻省理工学院给出的密码学难题肯定不是闹着玩的，所以就没在上面浪费时间。于是乎，这道密码学难题足足尘封了 20 年之久。

今年 4 月，一名程序员成功地破解了麻省理工学院的密码学难题，更厉害的是，这名程序员并不是用了 20 年，他在2015年才偶然发现了这个密码学难题，也就是说他破解只用了 3 年的时间。

他是怎么做到的？他又有着什么样的诀窍？让我们一起走进这名程序员的传奇。



RSA算法发明人设计了一个尘封35年的密码学难题

故事的主人公是 Bernard Fabrot，一名自学成才的比利时程序员。在讲他如何解迷之前，我们先来从头看看故事的起因。

1999 年的 4 月初，著名建筑师 Frank Gehry 收到了一个时间胶囊（time capsule ），时间胶囊就是即将现代发明的有代表性意义的物品装入容器内，密封后深埋地下，在未来的某一时刻打开。按照指示，这个时间胶囊要放入他主持修建的麻省理工学院「计算机科学和人工智能实验室」（简称：CSAIL ）的大楼中。

这个时间胶囊可以说是一个早期计算机历史的博物馆，它里面包含由微软创始人比尔·盖茨和图灵奖得主、万维网之父Tim Berners-Lee爵士等计算机领军人物捐献的 50 件计算机历史上伟大的藏品。

这其中，很可能包括1975年，微软为麻省理工学院开发的Altair BASIC编辑器，也是微软有史以来第一个产品（比尔·盖茨和保罗·艾伦当时编写的BASIC解释器就是后来的Microsoft Basic，也是MS-DOS的基础，后来演变成了现今的Visual Basic）。

顾名思义，时间胶囊需要有了时间的沉淀才会变得更有意义。于是这个与计算机科学密切相关的时间胶囊采取了计算机科学的方法，设计了一个密码学难题，只有破解了这个难题才能打开时间胶囊，这个密码学难题只能通过一次次按顺序的计算解开。

考虑到计算机算力的发展速度，解开这个难题至少需要计算 35 年。

这个别出心裁的设计出自 Ron Rivest 之手，对于 Rivest 这个人你可能不太熟悉，但说到大名鼎鼎的非对称加密的 RSA 算法你可能会觉得有点熟悉。没错，Rivest 就是 RSA 算法三个发明人中的“ R ”（RSA 算法由三个发明人姓氏的开头字母命名）。

Ronald Linn Rivest，美国密码学家；RSA加密算法发明者之一

同时，Rivest 还写了一本书，就是被称为程序员必修课的《算法导论》。RSA 算法可以说是有史以来最重要的密码学算法之一，今天加密货币的辉煌也离不开其底层 RSA 加密算法的支持。

虽然 Rivest 说这个密码学难题并不复杂，但实际上，计算这个难题的答案至少需要花费 35 年的时间。甚至在今天故事的主人公Fabrot把难题的答案发给麻省理工学院的时候，相关负责人都已经忘了这个问题的存在。

在今年 4 月 15 日，也就是 Rivest 提出这一密码学难题后的 20 年，自学成才的比利时程序员 Bernard Fabrot 解决了这个难题。

按照这个密码学难题官方说明的指示，Fabrot 准备将解决方案发送给麻省理工学院计算机科学实验室主任，但他惊讶地发现这个实验室已经不复存在，早在 2003 年，这个实验室就与麻省理工学院人工智能实验室合并，成立了现在的麻省理工学院计算机科学和人工智能实验室。

更令人震惊的是，这个新成立的实验室也早已忘了这个密码学难题的存在，Fabrot 说，现任麻省理工学院计算机科学和人工智能实验室主任 Daniela Rus 在收到解决方案时一头雾水，因为她根本不知道这个密码学难题是怎么回事。

「简单」的麻省理工学院密码学难题

那么，Rivest设 的这个密码学难题到底是什么呢？

简单来说，这个难题就是要找到运行近 80 万亿次平方操作的结果。比如说，如果你从 2 开始计算，平方后就得到了 4 ，紧接着 4 再进行平方计算就得到了 16 ，这个过程需要重复 80 万亿次。

麻省理工学院密码学难题的形式十分简单

当然了，每次平方计算后还需要对一个很大的数字 n 求模值，也就是求除以 n 之后的余数，最后算得的结果与难题中给定的一个数字进行数学计算，你就会得到一个新的数字，也就是这个密码学难题的答案。

虽然说当前密码学难题已经被破解，但出题人 Rivest 和破题人 Fabrot 都拒绝透露确切的答案。他们准备在 5 月 15 日举行一个开启时间胶囊的仪式，届时将会在仪式上公布答案。

你可能觉得这看起来也不难嘛，用更多的计算机加大算力不就可以了么？事实上没那么简单。这个密码学难题的关键在于它需要顺序操作，也就是说你需要在前一步计算结果的基础上进行这一步的平方计算，这意味着你只能一步步计算来得到结果，而无法通过当下常用的并行化计算来更快地得到答案。

Ron Rivest在当年的说明中，给出的解题思路示例

因此使用更多的计算机或是超级计算机都无济于事。考虑到「摩尔定律」（英特尔创始人戈登·摩尔提出的：微处理器的性能每隔 18 个月提升一倍），以及在 1999 年进行平方操作所需要的时间，Rivest 估计仅靠计算得出密码学难题的答案至少需要 35 年。

而作为一名独立开发者，Fabrot是在 2015 年才偶然发现了这个密码学难题。Rivest 最初使用 Java 语言开发了破解难题的代码。

后来，他便意识到如果借助 GNU 多精度运算程序库（GNU Multiple Precision Arithmetic Library）这个用 C 语言编写的精确运算工具可以加快破解难题的速度。

所以 Fabrot 立即着手去做，他在家里的台式计算机上专门分出一个 CPU 内核用于运行平方计算，在此期间除了他去度假或是家里停电，Fabrot 的电脑一直在全天候运行。

“在这些年里，除了非常亲密的几个朋友之外，我没有向任何人透露过我正在解决这个密码学难题，” Fabrot 说，“我相信自己可以做到，同时我也知道如果我告诉其他人，他们可能会使用更强大的 CPU 来超越我。”

三年半之后， Fabrot 终于完成了大约 80 万亿的平方计算，得到了密码学难题的结果。 

解题者不止Fabrot一个

Fabrot 很幸运，虽然他不知道，但此时一群计算机科学家和密码学专家也正在开展一个名为 Cryptophage （直译为：加密噬菌体）的项目，该项目主攻的目标是硬件，目标是使用专门的硬件来解决麻省理工学院提出的密码学难题，而且在 Fabrot 得到结果时， Cryptophage 团队的解决方案也在出炉的边缘。

在前英特尔工程师 Simon Peffers 的带领下，Cryptophage 团队当时正在研究将可验证的延迟函数作为以太坊等区块链安全机制的可能性。

可验证的延迟函数是对 Rivest 早期延时加密工作的进一步拓展，它们的解决方案都只能通过顺序操作得出。 Peffers 说，在研究的过程中， Cryptophage 团队遇到了 Rivest 提出的密码学难题，这个难题似乎是为他们的研究量身定制的“考试”。

3 月中旬， Cryptophage 团队开始研究由土耳其萨班哲大学研究员 Erdinc Ozturk 设计的算法。这个算法为减少平方操作之间的延迟作了专门的优化，并且该算法可以在现场可编程门阵列（FPGA，Field－Programmable Gate Array）上运行。

现场可编程门阵列这种多用途芯片可以为运行特定算法做出优化，因而它比通用的 CPU 更加高效。通过使用 Ozturk 的算法优化，这个密码学难题在现场可编程门阵列上的破解速度比在没有软件层面优化的高端商用 CPU 上快了约 10 倍。

根据现场可编程门阵列的计算能力，Cryptophage 团队推算出他们将在 5 月 10 日晚上（即他们开始计算的两个月后）得出麻省理工学院密码学难题的正确答案。

然而，当他们联系麻省理工学院准备分享这份难题即将被攻克的喜悦时，迎接他们的是一盆冷水，出题人 Rivest 告诉他们 Fabrot 已经捷足先登了。

“在这二十年里没有任何人来找过我们，直到这两个人几乎在同一天告诉我们：“我们已经解决了你的密码学难题，”出题人 Rivest 说，“这是一个令人惊讶的巧合。”

同时，Rivest 也很快承认自己高估了密码学难题的难度。Rivest 表示预测很长一段时间内的技术进步是一件很困难的事，在当时他并没有预料到现场可编程门阵列取得的计算能力突破，而且在那时芯片并不像现在这么复杂，用途也没有这么广泛。

虽然 Cryptophage 团队并不是第一个解决密码学难题的人，但 Peffers 表示他们仍将参加 5 月 15 日开启时间胶囊的仪式。

时间胶囊中都有些什么只有它的设计师 Michael Dertouzos 知道，不过目前可以确定其中包括图灵奖得主、万维网之父 Tim Berners-Lee 爵士，以太网之父 Bob Metcalfe，微软创始人兼微软首款产品 Altair BASIC 的开发者比尔·盖茨等几位计算机先驱人物捐赠的创新成果。

不过 Fabrot 表示，他对时间胶囊最大的期待，就是里面包含的原始版本的世界上最早的电脑游戏 Zork 。

图片来源：维基百科

麻省理工学院密码学难题的官方说明：

https://people.csail.mit.edu/rivest/lcs35-puzzle-description.txt

免费公开课报名倒计时2天

16岁保送北大、麻省理工博士、

EOS黑客松全球总决赛前三名

5月8日晚，纯干货知识分享邀你一同学习

推荐阅读：

猛戳"阅读原文"有惊喜哟

老铁在看了吗？👇