20年未解的MIT密码难题，被自学成才的程序员破解了，比预计早15年

本文经AI新媒体量子位（公众号ID:QbitAI）授权转载，转载请联系出处。

诞生在 1999 年的 MIT 密码难题，被一个自学成才的程序员破解了。

当年，出题人按照摩尔定律估计，完成计算要35 年。

结局的到来，足足提前了 15 年。

而交卷的人类只用了 i7 电脑的一个 CPU 核。

这个密码，还将解锁一个 20 年前的秘密。

怎样的一个谜？

回到 1999 年 4 月，MIT 计算机科学实验室 (LCS) 就要满 35 岁了。

它收到了一份富有仪式感的生日礼物，是个时间囊 (Time Capsule) ：有人把重要的东西藏在里面，设定一个时间，留给未来的人类打开。

与众不同的是，这个时间囊有一个“密码锁”，是由密码学家 Ron Rivest 设计的。著名的RSA 加密算法便是以他的名字命名。

Rivest 设了一个平方密码，初始值是2。2^2=4，4^2=16，16^2=256……

平方之后还要取模 (mod) ，就是余数。如 16 ≡ 1 mod 3， 16 除以 3 余1。

当然，这里不是模三，是模一个很大的数：

△ 这是两个大质数的乘积，RSA 算法的根基

那么，平方运算要做多少次？

80 万亿次。

就像开头提到的那样，用摩尔定律推算，破解这个密码大概需要35 年。这正是实验室当时的年纪。

那如果一直没有人解出答案，或者大家干脆已经忘记了这一道谜题呢？

设计者就把 35 年定为最终期限。即便人类没有交出答卷，时间囊依然会在2033 年、实验室 70 周年的庆典上开启。

当然，1999 年的科学家们不会想到，四年之后 LCS 实验室就和 AI 实验室合体进化，成为了后来大名鼎鼎的CSAIL。

他们大概也不会想到，20 年后会有人提前交卷。

并且，第一个交卷的程序员，只用了三年半来解题而已。

三年半破解谜题

2015 年，谜题发射的 16 年后，自学成才的比利时程序员Bernard Fabrot (简称“博纳”) 和它偶遇了。

谜题代码是用 Java 写的，但博纳认为用 GNP 多精度运算库 (GMP) 的话，解起来会更快。

这个开源库是用C语言写成的，也为 Python、R、C++、PHP 等各种语言做了包装。

博纳把家里台式机的其中一个 CPU 核，变成了解题专用，7 天 24 小时不停地跑。除非家里停电，或者要出远门。

除了最亲密的朋友之外，博纳不敢把自己的秘密行动告诉任何人。

“我知道我是有机会赢的，可如果告诉了别人，他们用上更强的设备就可能超过我了。”

三年有余，博纳完成了那80 万亿次平方运算。

最后一步，是用平方运算得到的结果、和题中给出的一个数，按题目要求做运算；算出的一串数字，可以翻译成一句祝贺。

博纳收到了温暖的贺词，便鸡冻地向 MIT 宣布自己解开了谜题。

像前文说起的那样，20 年了，计算机科学实验室不复存在，与 AI 实验室合体而成的CSAIL 实验室也已赫赫有名。

而 CSAIL 负责人 Daniela Rus 听到这个消息的时候，甚至不知道题目的存在。不过，稍微回溯一下历史，双方便对上了暗号。

博纳现在还不能透露这句话是什么。一切等到5 月 15 日，答案会和时间囊一同昭告天下。

他会带着荣光参加这场仪式。

事实也证明，不让太多人知道自己的想法，是非常机智的：

对手也快完成了

虽然，CSAIL 负责人并不记得当年的故事，但企图解开这个谜团的，并不止博纳一人。

还有一个根正苗红的项目组，名叫Cryptophage，由前英特尔工程师 Simon Peffers 带领，只为破解 MIT 密码而生。

他们用的方法和博纳不一样。那是一个新的平方算法，跑在可编程的加速器FPGA上，大约比 CPU 快 10 倍。

团队说只需要两个月，预计 5 月 11 日就能跑出答案了。

结局总是出人意料。团队满怀欣喜地联系 MIT，预告即将诞生的成果，却被告知已有人捷足先登。

虽败犹荣，他们依然受到了邀请，参加 5 月 15 日时间囊开启的盛会。

One More Thing

在打开之前，除了设计师没有人知道，时间囊里究竟藏了多少秘密。

但现在已经有些剧透了。有的礼物来自比尔·盖茨，有的礼物来自万维网的发明者 Tim Berners-Lee。

（编辑：核心网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!