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

栏目: IT资讯 · 发布时间: 5年前

内容简介:诞生在1999年的MIT密码难题,被一个自学成才的程序员破解了。当年,出题人按照摩尔定律估计,完成计算要

栗子 发自 凹非寺

量子位 报道 | 公众号 QbitAI

20年未解的MIT密码难题,被自学成才的 <a href='https://www.codercto.com'>程序员</a> 破解了,比预计早15年

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

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

结局的到来,足足 提前了15年

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

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

怎样的一个谜?

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

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

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

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

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

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

当然,这里不是模三,是模一个很大的数:

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

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

那么,平方运算要做多少次?

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

80万亿次。

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

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

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

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

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

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

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

三年半破解谜题

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

对手也快完成了

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

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

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

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

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

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

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

One More Thing

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

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

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

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

谜题本题:

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

— 完 —

小程序|get更多AI资讯与资源

加入社群

量子位AI社群开始招募啦,量子位社群分:AI讨论群、AI+行业群、AI技术群;

欢迎对AI感兴趣的同学,在量子位公众号(QbitAI)对话界面回复关键字“微信群”,获取入群方式。(技术群与AI+行业群需经过审核,审核较严,敬请谅解)

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

量子位  QbitAI · 头条号签约作者

վ'ᴗ' ի 追踪AI技术和产品新动态

喜欢就点「在看」吧 !


以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

Twenty Lectures on Algorithmic Game Theory

Twenty Lectures on Algorithmic Game Theory

Tim Roughgarden / Cambridge University Press / 2016-8-31 / USD 34.99

Computer science and economics have engaged in a lively interaction over the past fifteen years, resulting in the new field of algorithmic game theory. Many problems that are central to modern compute......一起来看看 《Twenty Lectures on Algorithmic Game Theory》 这本书的介绍吧!

Base64 编码/解码
Base64 编码/解码

Base64 编码/解码

SHA 加密
SHA 加密

SHA 加密工具