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

  • 时间:
  • 浏览:1

图片来源图虫:已授站长之家使用

声明:本文来自于微信公众号区块链大本营(ID:blockchain_camp ),原文:WIRED,编译:Guoxi,授权站长之家转载发布。

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爵士等计算机领军人物捐献的 150 件计算机历史上伟大的藏品

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

顾名思义,时间胶囊时要有了时间的沉淀才会变得更有意义。于是什儿 与计算机科学密切相关的时间胶囊采取了计算机科学的土土办法,设计了一三个小密码学疑问,必须破解了什儿 疑问不需要 打开时间胶囊,什儿 密码学疑问必须通过一次次按顺序的计算解开。

考虑到计算机算力的发展速率单位,解开什儿 疑问大慨时要计算 35 年。

什儿 别出心裁的设计出自 Ron Rivest 之手,对于 Rivest 什儿 人你可能粘壳悉,但说到大名鼎鼎的非对称加密的 RSA 算法你可能会觉得有点儿熟悉。没错,Rivest 然后 RSA 算法一三个小发明的故事人中的“ R ”(RSA 算法由一三个小发明的故事人姓氏的开头字母命名)。

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

觉得 Rivest 说什儿 密码学疑问之然后复杂,但实际上,计算什儿 疑问的答案大慨需大慨 35 年的时间。甚至在今天故事的主人公Fabrot把疑问的答案发给麻省理工学院的然后,相关负责人都可能忘了什儿 疑问的占据 。

在今年 4 月 15 日,也然后 Rivest 提出什儿 密码学疑问后的 20 年,医学会 成才的比利时多线程 员 Bernard Fabrot 解决了什儿 疑问。

按照什儿 密码学疑问官方说明的指示,Fabrot 准备将解决方案发送给麻省理工学院计算机科学实验室主任,但他惊讶地发现什儿 实验室可能不复占据 ,早在 1503 年,什儿 实验室就与麻省理工学院人工智能实验室合并,成立了现在的麻省理工学院计算机科学和人工智能实验室。

更令人震惊的是,什儿 新成立的实验室也早已忘了什儿 密码学疑问的占据 ,Fabrot 说,现任麻省理工学院计算机科学和人工智能实验室主任 Daniela Rus 在收到解决方案时一头雾水,可能她根本真不知道什儿 密码学疑问是为社 回事。

「简单」的麻省理工学院密码学疑问

这么,Rivest设 的什儿 密码学疑问到底是什么呢?

简单来说,什儿 疑问然后要找到运行近 150 万亿次平方操作的结果。比如说,可能你从 2 开始 计算,平方后就得到了 4 ,紧接着 4 再进行平方计算就得到了 16 ,什儿 过程时要重复 150 万亿次。

麻省理工学院密码学疑问的形式十分简单

当然了,每次平方计算后还时要对一三个小很大的数字 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 终于完成了大慨 150 万亿的平方计算,得到了密码学疑问的结果。 

解题者不止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