MIT 80万亿次平方运算加密难题,被小哥用家用台式机自学破解

近日,麻省理工学院(MIT)正式宣布一名自学成才的比利时程序员 Bernard Fabrot 成功破解了 RSA 算法发明者 Ron Rivest 20 年前提出的难题。据称,这一行动对于当前流行的加密算法将产生深远影响。

这个名为 LCS35 的难题是由加密算法界元老、RSA 暗码系统发现者之一、MIT 教授 Ron Rivest 在 1999 年 4 月提出的。发起者们曾预测:以 1999 年的芯片计算速度作为起点并考虑到摩尔定律的话,即使用最快的增长模型,破解这一难题所需的算力也要在 35 年之后(也就是今天看来,最快 15 年之后)才能出现。

如果你感兴趣的话,问题在这里:https://people.csail.mit.edu/rivest/lcs35-puzzle-description.txt

然而,Bernard Fabrot 这次只使用了一台 CPU 为英特尔 Core i7 的家用台式机就把问题解决了。

Bernard Fabrot

据 MIT 介绍,Fabrot 花费了三年半的时间解决这一难题,这一题目涉及到长度为 80 万亿次平方运算的起始数字,而且专门被设计为阻止破解者使用并行算法进行加速破解。

1999 年 4 月初,一个时间胶囊(time capsule)被送到著名建筑师 Frank Gehry 手中,并指示他将这个时间胶囊融入到建筑设计中,而这最终建成了麻省理工学院(MIT)的计算机科学暨人工智能实验室(CSAIL)。这个时间胶囊本质上是一个早期计算机历史博物馆,其中收藏有微软创始人比尔·盖茨和万维网之父蒂姆·伯纳·李爵士捐赠的 50 件物品。

这个时间胶囊在 35 年内不会被公开—直到有人可以破解设计中的暗码加密。该暗码加密由 Ron Rivest 设计,其名字中的「R」代表了 RAS 暗码系统中的「R」,该系统是有史以来最重要的加密协议之一。Ron Rivest 称加密的设计并不复杂,但几乎要花费 35 年的时间才能计算出答案。

4 月 15 日,在 Rivest 提出该难题的 20 年之后,一位自学成才的比利时程序员 Bernard Fabrot 解决了这一难题。该难题的原始指令是将解决方案送到计算机科学实验室主任手中,但 Fabrot 意外地发现该实验室不存在了(该实验室在 2003 年与 MIT 的人工智能实验室合并为 CSAIL)。更令 Fabrot 感到惊讶的是,当他告知 CSAIL 主任 Daniela Rus 自己的解决方案时,这位主任竟然不知道该难题的存在。

Rivest 的难题主要是为了得出运行平方运算近 80 万亿次所得到的最终数字。举例而言,当你计算 2 的平方会得到 4,计算 4 的平方会得到 16,以此类推,运行平方运算 80 万亿次。之后,利用最终得到的数字运行一个数学运算,而该运算又将使用最终的平方运算数字以及难题提示给出的一个数字。这样会分解出一个可以被编译成简短祝贺短语的新数字(Rivest 和 Fabrot 均拒绝透露精确短语,该短语会在 5 月 15 日的时间胶囊开启仪式上公布)。

该难题的关键在于其要求序列运算,这意味着你无法通过并行计算而更快地得到答案。你需要在前一个平方运算结果的基础上一步步地运行平方运算,所以使用更多计算机或采用超级计算机对结果无益。根据摩尔定律以及 1999 年运行平方运算需要花费的时间,Rivest 预测计算出该难题的答案应该需要 35 年左右。

Fabrot 是一位独立开发者,他在 2015 年偶然发现了这个难题。尽管 Rivest 最初以 Java 语言发布了该难题的代码,但 Fabrot 意识到如果自己使用 GNU Multiple Precision Arithmetic Library(一款用于「精确计算」的免费软件),则能更快地解决这一难题。因此,Fabrot 专门在其家用台式电脑中安装一个 CPU 内核来全天候、无眠无休地运行平方运算。

Fabrot 说:「这些年,除了很亲密的朋友,没有人知道我在尝试解决这个难题。我觉得自己有可能解决这个难题,如果我告诉别人,那他们可能用更强大的 CPU 来打败我。」

三年半之后,Fabrot 最终完成了大约 80 万亿平方运算,并获得了难题的解决方案。时间刚刚好!虽然 Fabrot 不知道,一组计算机科学家和密码学专家正在研究一个名为 Cryptophage 的项目,该项目使用专门的硬件来解决 MIT 的难题。

英特尔工程师 Simon Peffers 领导的 Cryptophage 小组在研究可验证延迟函数作为区块链(如以太坊)安全机制的可能性。可验证延迟函数是 Rivest 早期关于时间延迟密码学的现代成果,它们的解决方案只能通过序列运算获取。Peffers 表示,研究期间 Cryptophage 小组遇到了 Rivest 的难题,他们认为该难题是验证其研究的不错方式。

3 月中旬,该团队开始运行萨班吉大学研究人员 Erdinc Ozturk 设计的一个算法,该算法被优化用来减少平方运算之间的延迟。它是在 FPGA 芯片上实现的,这款芯片是多用途的,只运行特定算法,因此比通用 CPU 更高效。使用 Ozturk 的算法,FPGA 比运行非优化软件的高端商用 CPU 快了约 10 倍。

基于芯片的计算效率,Cryptophage 小组估计其将在 5 月 10 日晚上得出 MIT 难题的正确解决方案,这离他们开始计算仅两个月而已。当他们联系 MIT 并声称即将有一个解决方案出炉时,Rivest 告诉他们 Fabrot 已经捷足先登,给出答案了。

「在这两拨人几乎同时来找我们并告诉我们说解决了这个问题之前,几乎从没有人来找过我们,这真是一个惊人的巧合。」Rivest 表示。

Rivest 很快承认,自己高估了难题的难度。Rivest 表示,在如此长的时间内对技术的进步进行预测有些困难,他没想到像 FPGA 芯片这样的突破,以前的芯片没这么复杂,用途也没这么广泛。

Ron Rivest,著名密码学家,MIT 教授。

尽管 Cryptophage 小组不是第一个揭开难题的,但 Peffers 表示他们仍将出席 5 月 15 号的时间胶囊开启仪式。只有胶囊的设计者知道里面的全部内容,不过它的确包含蒂姆·伯纳斯-李(万维网的发明者)、罗伯特·梅特卡夫(以太网的发明者)和比尔·盖茨等人的贡献。Fabrot 说,他最兴奋的是看到胶囊里有 Zork(最早的电脑游戏之一)的原件。

参考内容:

  • https://www.csail.mit.edu/news/programmers-solve-mits-20-year-old-cryptographic-puzzle

  • https://people.csail.mit.edu/rivest/pubs/RSW96.pdf

  • https://www.wired.com/story/a-programmer-solved-a-20-year-old-forgotten-crypto-puzzle/

工程程序员加密MIT
相关数据
英特尔机构

英特尔是计算创新领域的全球领先厂商,致力于拓展科技疆界,让最精彩体验成为可能。英特尔创始于1968年,已拥有近半个世纪产品创新和引领市场的经验。英特尔1971年推出了世界上第一个微处理器,后来又促进了计算机和互联网的革命,改变了整个世界的进程。如今,英特尔正转型成为一家数据公司,制定了清晰的数据战略,凭借云和数据中心、物联网、存储、FPGA以及5G构成的增长良性循环,提供独到价值,驱动日益发展的智能互联世界。英特尔专注于技术创新,同时也积极支持中国的自主创新,与产业伙伴携手推动智能互联的发展。基于明确的数据战略和智能互联全栈实力,英特尔瞄准人工智能、无人驾驶、5G、精准医疗、体育等关键领域,与中国深度合作。面向未来,英特尔致力于做中国高价值合作伙伴,在新科技、新经济、新消费三个方面,着力驱动产业协同创新,为实体经济增值,促进消费升级。

https://www.intel.com/content/www/us/en/company-overview/company-overview.html
相关技术
微软机构

微软是美国一家跨国计算机科技公司,以研发、制造、授权和提供广泛的计算机软件服务为主。总部位于美国华盛顿州的雷德蒙德,最为著名和畅销的产品为Microsoft Windows操作系统和Microsoft Office办公室软件,以及Xbox的游戏业务。微软是美国《财富》杂志2015年评选的世界500强企业排行榜中的第95名。

https://www.microsoft.com/en-us/about
区块链技术

区块链是用分布式数据库识别、传播和记载信息的智能化对等网络, 也称为价值互联网。 中本聪在2008年,于《比特币白皮书》中提出“区块链”概念,并在2009年创立了比特币社会网络,开发出第一个区块,即“创世区块”。

人工智能技术

在学术研究领域,人工智能通常指能够感知周围环境并采取行动以实现最优的可能结果的智能体(intelligent agent)

以太坊技术

以太坊(英文Ethereum)是一个开源的有智能合约功能的公共区块链平台,通过其专用加密货币以太币(Ether)提供去中心化的虚拟机(“以太虚拟机” Ethereum Virtual Machine)来处理点对点合约。 以太坊的概念首次在2013至2014年间由程序员Vitalik Buterin受比特币启发后提出,大意为“下一代加密货币与去中心化应用平台”,在2014年通过ICO众筹开始得以发展。

摩尔定律技术

摩尔定律是由英特尔创始人之一戈登·摩尔提出来的。其内容为:积体电路上可容纳的电晶体数目,约每隔两年便会增加一倍;经常被引用的“18个月”,是由英特尔首席执行官大卫·豪斯所说:预计18个月会将芯片的性能提高一倍。

暂无评论
暂无评论~