该加密难题由麻省理工学院实验室的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,218
n = 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 对本文撰写提供了帮助

创作场景

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