提前 15 年！比利时程序员攻克麻省著名加密难题

该加密难题由麻省理工学院实验室的 Ron Rivest 教授，也就是著名的 RSA 公钥加密算法负责人提出，并预计需要 35 年时间才能得到答案，而比利时的一名程序员近日攻克了该难题，比预计时间提前了 15 年。

对于比利时人来说，2019 年 4 月是个好月份。相比于专业的比利时自行车手 Victor Campanaerts 打破一小时世界记录，独自跑出 55 公里（实际是 55,089 米）的好成绩之外，专业的比利时程序员 Bernard Fabrot 攻克了更具挑战性的难关，破解了一道 1999 年设置的计算难题，该题由麻省理工的 Ron Rivest 教授，也就是著名的 RSA 公钥加密算法负责人，并预计需要 35 年的运算时间才能得到答案，没想到 Bernard Fabrot 提前 15 年就破解了该难题，并且仅用了 3.5 年的运算时间，超出 Rivest 预期的速度 10 倍。

原题概述

1994 年 4 月，在麻省理工学院计算机科学实验室成立 35 周年的庆祝活动上，时任实验室主任的 Michael Dertouzos 设计了一个“创新成果时间胶囊“，这其中囊括了一系列计算机领军人物的创新成果，准备在 35 年后再取出作为实验室成立 70 周年的献礼。

为了保证刚好在 35 年之后取出，Ron Rivest 教授为时间胶囊设计了一把“密码锁“，也就是一道密码学难题。考虑到未来计算机算力的提升速度，还特意加大了难度，使得该难题至少需要 35 年时间才能破解。

该难题是著名的“时锁问题”，即一个耗时的计算，只能通过调整算法或构建更快的计算机硬件来实现加速。时锁问题很有趣也很重要，因为其不能简单的把问题分解成小块，让更多的计算机来同时运行。

并且，时锁难题存在固有时序，要求在实现算法的大量循环中，循环的每次迭代输入只能读取前一次迭代的输出来得到。这种想法让每个人处于同一境地：即使是世界上最大、最富有、最有能力的云计算公司，其所有的服务器、CPU 及 CPU 核也无法让你一定走向成功。

业内其他密码学专家清楚麻省理工学院的技术能力，因此也没有在此上浪费太多时间，因此这道难题尘封了足足 20 年之久。

难点一：可平行化

大部分问题可以分成小的部分，至少其中有些部分可以有所重叠。比如，如果要求数清非洲的大象数量，你可以飞到好望角，然后曲折往北直到埃及的亚历山大，沿途注意所有的大象。

但这是一个可以平行的任务，因为可以忽略一些复杂情况，比如已经数过的大象穿越了国界线，比如赞比亚的大象数可能和其邻居安哥拉的大象数同时进行统计。

简单讲，每个国家可以分配一个人员来统计数目，不用担心各自开始的顺序——在最大的国家中，可以把任务再次细分，比如每个省指派一个人，以此类推。

难点二：长而曲折的关键路径

Ron Rivest 在 1999 设置的难题没法像数大象那样把任务进行分解。本质上来说，这个难题最初设计是通过一个需要运行长达 35 年迭代的紧凑循环来实现，它取决于计算能力在这个周期内能怎样改进。

Rivest 甚至做了一个年度更新方案，假定解题者能每年某个时刻可以暂停计算，来把计算机更新到当前市面上最大最快的计算机。

2015 年，Bernard Fabrot 才开始启动运行该项目，从启动到结束共花费 3.5 年时间，从而提前 15 年结束了该项工作。

解题思路

以下是 Rivest 设置的难题：

该问题是针对特定的 t 和 n，计算 2^(2^t) (模 n)。n 是两个大质数的乘积，t 的选择可以用来设置难题希望的难度级别。

简单解释下， 2^t  是 Ron Rivest 用以表达 2 的 t 次方的文本标识，即 2t,  mod n 表示取余, 即模运算，也就是除以 n 剩余的部分。

比如，6 是 3 的 2 倍, 因此 6 / 3 = 2 余 0 ；但是如果用 7 除以 3，则得 2 余 1，因此 7 / 3 = 2 余 1。

Rivest 设置 t 为正好小于 80 万亿的一个数，n 为一个 2048 位的二进制数（512 位的 16 进制数或 256 字节），如：

t = 79,685,186,856,218n = 0x32052C40E056ED2C9141FC76C060FA685F60C45095EB69930CBE4B2C81B19C33      55FA9149150D7082284CC3903C12B98DACC7E2FC7C16907F8E946AEFB5FD1240      77E05D944B6738334E71A9BD37E1C08F2DF3D119EB95182B0F3E87B341A217BB      433F2114FEAE1555CFB974DA3D56D4AD7C1D83FD789F34143CDD3D502C104639      EE68DDC8D56D5BC6EAAC7ED16C1F5FF02159B5D52AF94979A18A60EFCABE109E      E2E90C14B6FC1225B754644D989FC1B9F87552B255997CEE22429CF49E3599DA      4B3F6D5535B83072A1D4357AE1ABFF8455B80C438EC33A5C7C6CB1ACE22C62FE      67B3040029B3C37E5EC682363A77D42FB223E194878E146D06739EC4E598A9A1

其思路就是这里没有计算最终结果的捷径，除非能知道两个大质数，根据其乘积得到 n 。

Ron Rivest 和现在的 Bernard Fabrot，知道 n 的两个质数，我们称其为 p 和 q 具体是多少 ，但其他人都不知道。

注：Rivest 设计了一个方法，这样可以提前计算出答案，用以确定挑战者是否真正解决了该难题。

因此在不知道 p 和 q 的情况下，要解决这道难题，需要一直不停的进行乘积，直到最后得到计算结果。

每个循环里的乘积都需要用到上次的输出作为本次的输入，所以无法在多台电脑，多 CPU 或 CPU 核间进行计算工作的划分。

代码实现

Bernard Fabrot 尝试使用 Python 来处理该问题。在 Python 中， 操作符 ** 是使数字自乘为指数的幂，即幂运算，% 是找到倍除后的余数，即取模，并假设函数 seq(n) 从数字 1，2，3，一直循环到 n。

   exp = 2 ** 79685186856218   val = 2 ** exp   val = val % 0x32052...98A9A1

除了第一行的 exp 是个接近 20 万亿位的 10 进制数字，其余都比较简单可控。因此需要 10 兆字节来存储这个值，然后在代码第二行，我们要得到 2 的幂次方，而指数就是这个已经大的惊人的数。

如果要用重复乘积来实现幂运算  ，2n 需要 n 次循环，做连续乘以 2 的操作 n 次。从下面可以看出这种计算方法的麻烦之处：

   exp = 1   for i in seq(796851868562180): exp = exp * 2   val = 1   for i in seq(exp): val = val * 2   val = val % 0x32052...98A9A1

第一个 for 循环中，循环次数为 80 万亿。这还只是为了得到这个超级大的指数，用以在第二个 for 循环中进行真正的计算！

平方后求幂

幸好，有个巧办法来做这个计算。

在循环表达式 val = val * 2 中 ， 循环变量的步进是 1，从而每次循环依次得到 2^1, 2^2, 2^3, 2^4, 2^5 等。

但如果不做倍乘而做平方计算，如下所示：

   val = val * val

这种方式可以让指数每次翻倍，而不只是加 1，则依次循环得到 2^1, 2^2, 2^4, 2^8, 2^16 等。

这样就可以用 t 次循环得到 2^(2^t) ，而不像之前需要 2^t 次循环，如下所示：

   val =  2   for i in seq(796851868562180-1): val = val * val   # Now find the remainder   val = val % 0x32052...98A9A1

数值太大

即使现在总共有 80 万亿次循环，而不是更大的 2^80,000,000，这段代码仍不够好，因为该处理过程中数值 val 太大了。

即使在第二行做一部分循环，也可以看到每次的迭代中的每一步所耗费的时间几乎会成倍增加，因为每次循环要乘的数都比前一次多一倍：

   millisecs | value computed           0 | 2^(2^ 1)           0 | 2^(2^ 2)           0 | 2^(2^ 3)           . . . . . . .           0 | 2^(2^16)           1 | 2^(2^17)           2 | 2^(2^18)           5 | 2^(2^19)          11 | 2^(2^20)          25 | 2^(2^21)          49 | 2^(2^22)          97 | 2^(2^23)         195 | 2^(2^24)         406 | 2^(2^25)         833 | 2^(2^26)        1690 | 2^(2^27)        3513 | 2^(2^28)        7182 | 2^(2^29)       14832 | 2^(2^30)

庆幸的是，在模块计算中可以如上最后取余或每步重复取余，因为只有每次循环最后返回的余数需要在下一次乘积中使用到。

因此，可以把计算符 % 放在 for 循环里（在 Python 中，缩进显示了当前循环所在的层级数）：

   val =  2   for i in seq(796851868562180-1):      val = val * val      # Calculate the remainder each time round      # inside the loop, not once at the end      val = val % 0x32052...98A9A1

余数是固定长度的，在这里，余数不能大于 n-1，假设 n 为 2048 比特，就意味着每次步骤里，都需要 2048 比特的数乘以 2048 比特的数，并对乘积做取余处理，该余数也是 2048 比特。

每次迭代后的累计结果 val 是一个 2048 比特的数字，因此下一个迭代输入也是 2048 比特的数字。循环里的每个操作都要增加相同的时间：

   millisecs | value computed           0 | 2^(2^ 1)           0 | 2^(2^ 2)           0 | 2^(2^ 3)           0 | 2^(2^ 4)           0 | 2^(2^ 5)           0 | 2^(2^ 6)           . . . . . . .           0 | 2^(2^27)           0 | 2^(2^28)           0 | 2^(2^29)           0 | 2^(2^30)

在我的 Mac 上，做 1,000,000 次迭代只需要 16 秒，也就是每秒可以做 62,500 次迭代。

按这种速度，需要花费 80,000,000,000,000 / 62,500 秒，也就是 15,000 天或 40 年来完成这个难题。

即便是顶级的 Mac，也许能让 CPU 速度翻倍，计算效率有 4 倍的整体提升，但仍需要 10 年来完成这项工作。

Fabrot 只用了 3.5 年的时间，而且他开始运行时的硬件环境并不如现在，他使用的只是一般商用硬件，这真的是一个了不起的胜利。

根据 Fabrot 的申明，有个做加密货币的新兴公司公开宣称已经用两个月时间使用特殊的现场可编程门阵列（FPGA）解决了该难题。

但尽管其网站上得意地宣称该组织“两个月内解决了该问题”，但这个链接是空的，没有指向任何地方，其可能关联代码的 Github 账号上仍显示“即将提供代码”。

相较而言，Fabrot 默默完成了所有工作。加密专家们表示，攻击只会越来越快，这就是一个重要提醒。

回顾整个过程，算法本身很容易实现。在完成过程中，困难的是需要随时跟踪了解当前进度。与一般程序不一样，该算法没有任何“窍门”，没有精确的计算状态备份供计算机崩溃或开始出现错误时进行恢复，也没有管理良好的备份机制，任何小的故障或断电都会使整个计算过程归于原点。

当然，这里也有挑战，那就是一直不失去信心，继续前行。

感谢 Sophos 研究室的 Alex Bakewell of SophosLabs 对本文撰写提供了帮助