首页 > 区块链 > 关键词 > RSA算法最新资讯 > 正文

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

2019-05-08 13:43 · 稿源:区块链大本营公众号

程序员 黑客 代码 漏洞

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

声明:本文来自于微信公众号区块链大本营(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爵士等计算机领军人物捐献的 50 件计算机历史上伟大的藏品

这其中,很可能包括 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 准备将解决方案发送给麻省理工学院计算机科学实验室主任,但他惊讶地发现这个实验室已经不复存在,早在 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

  • 相关推荐
  • 大家在看
  • 支付公司PayPal将推出加密货币直接买卖服务

    【TechWeb】6月23日消息,据国外媒体报道,知情人士透露,支付公司PayPal即将推出一项直接买卖加密货币的服务。知情人士表示,该服务将允许用户直接通过PayPal及旗下移动支付服务Venmo买卖加密货币,它将具有某种内置的钱包功能,用户可以将加密货币存放在那里。外媒报道称,PayPal的这项服务可能会在未来三个月内推出,上线时间可能还会更早。目前尚不清楚该公司将提供多少种加密货币的直接销售服务。一位消息人士表示,Paypal将

  • OKEx早报:PayPal招聘加密货币专家,北京比特大陆新增商标申请

    OKEx早报将在每日早间为您带来最新的行情,以及相关行业动态。帮助投资人在最短的时间内了解夜间的动态消息,更好的握把每日行情。行情速递6月23日讯,昨日晚间BTC出现一轮上涨幅度接近100美元,通过OKEx平台交易数据可以看出,BTC今日开盘报9494.79美元,开盘后直接上涨,至1:00开始横盘整理,4:30左右开始第二轮拉升,至早间最高点9784.38美元,随后再次开始横盘,截止发稿BTC报9623.71美元。图片来源:OKEx平台BTC/USD交易数?

  • 月入两万的程序员背着电脑送外卖:甲方提需求好随时改代码

    每个人对生活都有不同的理解,也有丰富多彩的选择。据国内媒体报道,来自安徽合肥的小张毕业于安徽师范大学计算机专业,95后,毕业后从事PHP程序员工作已经三年,收入2万元左右。不过,与众

  • 27岁程序员转职赏金猎人:一个漏洞10万美元,比工资香多了

    6 月 1 日,有报道称,印度开发者 Bhavuk Jain 向苹果安全团队报告了 Sign in with Apple(通过 Apple 登录)中存在一个零日漏洞,它允许攻击者远程劫持任意用户账户,影响严重。为此苹果向 Jain 支付了十万美元的巨额赏金。

  • 字节跳动程序员期权价值过亿 28岁辞职享受人生引热议 当事人回应

    有人28岁刚刚硕士毕业,有人28岁已经实现财富自由并退休。近日,知乎一篇“如何看待年仅28岁的郭宇宣布从字节跳动退休?”引发网友热议。今年2月,郭宇在个人微博发文称:“

  • 独家专访28岁退休程序员郭宇:1600人加好友,问我“挣了多少钱”

    微信好友的“问候”排满了对话框,点开来都是雷同的标题——“ 28 岁退休的程序员xxxx”。在知乎上,“如何看待年仅 28 岁的郭宇宣布从字节跳动退休?”的问题,有近 1000 万人浏览阅读。

  • 即刻怎么改密码 新版本即刻密码修改教程

    即刻APP经常的会碰到要修改密码的操作,很多人还不清楚在哪可以比较方便的改密码,下面就来为大家详细的介绍一下。

  • 币安区块101对话Multicoin Capital执行董事Mable:加密经济中的3个财富密码

    2020 年 6 月 24 日,币安吴迪对话Multicoin Capital执行董事Mable。Mable认为更符合自己的标签是一个创业者,不管是找投资还是做研究,都需要非常努力以创业者的心态脚踏实地去做。Mable认为Arweave的核心价值在于预付一笔费用之后就可以永久存储数据,从历史来看未来储存的成本会无限压缩趋近于零,所以是可以被假设为免费存储的。Arweave的模型是传统比特币的共识机制,但在上面增加了访问证明(proof-of-access),激励矿工尽?

  • 犯罪大师crimaster赌王密码是多少 赌王银行遗产暗号密码一览

    ​犯罪大师crimaster中有一个赌王的银行遗产,需要你破解其中的密码,很多玩家还不清楚这个暗号密码到底是多少,下面就来为大家分享一下犯罪大师crimaster赌王密码是多少。

  • 别跟瑞幸学上市,要学就学如何开店选址

    今晚,瑞幸将正式退市。这个沸沸扬扬上演了两年多的资本闹剧,似乎终将收场。2019 年 5 月,创立仅 18 个月的瑞幸在美股上市。但在 2020 年 1 月底,做空机构浑水发布报告显示,这家公司疑似存在财务造假。 2 个月后,瑞幸官方承认存在“ 22 亿元财务造假”,公司股价闪崩80%,并在不久后便收到来自于纳斯达克的退市通知。

  • 为兴趣而学,大鹏教育赢得学员青睐

    作为互联网教育企业,大鹏教育依托互联网+科技快速发展成为一家专注于在线兴趣教育的创新型教育公司,为用户提供个性化兴趣教学服务。“学我想学,找到生活的热情“是大鹏教育对广大学员的承诺。自成立以来,大鹏教育以兴趣先行,根据不同年龄段的学员的不同需求,先后推出了设计、美术、国画、书法等学院,赢得了众多学员青睐。大鹏教育以兴趣先行为保障教学质量,提高学员学习体验度,大鹏教育搭建了由专业的讲师、助教、学管师?

  • 苹果照片怎么导入电脑?这个备份你一定要学!

    苹果照片怎么导入电脑?现在使用苹果手机拍照的小伙伴越来越多了,但如果在拍完之后想要将照片备份下来,并导到电脑上应该怎么操作呢?其实也不难,下面小编就给你分享几招,一起来看看吧!方法一:借助云盘随着智能科技的不断发展,云盘对于我们用户而言是一种十分方便的工具,但使用时也需要分为iOS和Android这两大类。iOS用户可以直接利用的就是手机中的iCloud,只需在苹果手机的设置中开启“iCloud云备份”功能,将照片同步至?

  • 以苦难之名,“卖惨”背后的财富密码

    恻隐之心,人皆有之。但一旦被利用了,就总感觉不是滋味。近期B站拥有 20 万粉丝的UP主“虎子的后半生”颇受争议,在这位自称是肺癌晚期患者的自述中,家庭负债累累,母亲又遭遇中风,人生走向绝境。但有网民爆出疑似其大众点评账号两年打卡约 500 个消费场所,花销巨大。

  • 独居青年消费图鉴:陪伴和社交成为“财富密码”?

    当独居人群不断扩大,这个群体也开始被社会认识,他们的生活方式逐渐被主流的舆论场所关注。今年 5 月,腾讯视频上线的《让生活好看》就是一部以年轻艺人的独居生活为切口的观察类综艺。节目邀请了 95 后的费启鸣、 90 后的郑爽、许魏洲、伍嘉成、 80 后的柳岩等,关注了一系列独居年轻人会遇到的生活问题。

  • 用算法寻找肿瘤的分子弱点,代码真的能治愈癌症?

    ruxolitinib试验是哥伦比亚大学系统生物学家Andrea Califano历时十年的追求的产物。通过复杂的计算,他对催化癌细胞的分子网络进行建模,并精确定位到转录因子蛋白作为关键因子,从而控制细胞内许多基因表达。

  • 加密行业的比尔·盖茨——赵长鹏

    得益于币安赵长鹏的正确领导,币安在全球化道路上遥遥领先于coinbase, huobi ,okex,国际化市场份额取得极其亮眼的成绩。而其首创的平台币BNB,也在平台币中处于龙头地位。目前币安又开启“开放式平台”商业模式,引领区块链行业发展进步。为此,很多人都对赵长鹏充满了疑问,这个神一般的人物到底是什么样的?有人称他为加密行业的比尔·盖茨,因为他不仅在推动加密货币行业的发展,而且正在改变根深蒂固的经济和社会文化。他在

  • 健合集团科研团队解锁宝宝睡眠密码

    关爱母婴身心健康,保障婴幼儿心智成长,是健合集团科研团队以来持续不断的坚持。为了让妈妈们更好地关爱襁褓中的婴儿,合生元可贝思近期携手著名心理学家张怡筠、广州白云妇幼保健院主任医师蹇涵等嘉宾为妈妈在关于儿童睡眠等平时容易忽视的问题上答疑解惑。据了解,健合集团科研团队研制的可贝思羊奶粉以卓越品质安抚宝宝睡眠。安抚婴儿睡眠问题一直以来是妈妈们的一大难题,也是健合集团科研人员研究的主要方向。4月12日,合生?

  • 不惧诉讼和天蝎再次做空? 跟谁学股价再涨超20%

    6月16日消息,美股昨日低开高走,热门中概度多数出现上涨,其中,跟谁学股价涨幅尤未突出,盘中一度大涨近30%,创下上市一年来最大盘中涨幅,最终收涨20.82%,报52美元,全天成交量超过三个月日均量的4倍,公司市值也涨超124亿美元。截至发稿,跟谁学股价盘后再涨1.5%。与跟谁学股价大涨状态相反的是,跟谁学目前仍然面临着来自空头的狙击。就在昨天,多家美国律师事务所表示,针对跟谁学的集体诉讼已经开始,包括Levi

  • 重磅!「晓程序观察」独家:支付宝小程序最全运营宝典!

    ​随着 618 战火愈演愈烈, 2020 年即将正式驶过一半航程了。年初疫情足不出户时,你们闭门在家做的目标计划书,不知道已经实现得如何了?

  • 字节跳动推出“学浪计划” 扶持教育创作者

    抖音、今日头条、西瓜视频宣布推出“学浪计划”,将投入百亿流量,扶持平台教育创作者。据悉,该计划将为k12、语言教学、高考、考研、职业教育等严肃教育内容提供流量支持,并为相关创作者提供运营培训、变现指导等服务。字节跳动方面表示,学浪计划将根据不同平台抖音、今日头条、西瓜视频宣布推出“学浪计划”,将投入百亿流量,扶持平台教育创作者。

  • 参与评论
文明上网理性发言,请遵守新闻评论服务协议

热文

  • 3 天
  • 7天