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

栗子 发自 凹非寺 量子位 报道 | 公众号 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写的,但博纳认为用GNU多精度运算库 (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。

而大赢家博纳最期待的,还是世界上最早的PC游戏:Zork (魔域) 的原始版本。

谜题本题: http://people.csail.mit.edu/rivest/lcs35-puzzle-description.txt

原文发布于微信公众号 - 量子位(QbitAI)

原文发表时间:2019-04-30

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券