【文章】7.2 公钥密钥长度 - 分解 量子计算机

7.2 公钥密钥长度

    2.3节中已经讨论了单向函数。例如，两个大素数进行相乘就是一个单向函数，得到相乘的结果很容易，但是由这个结果分解得到两个素数却非常困难（见11.3节）。公钥密码体制就是利用这种思想做成单向陷门函数。实际上，那不过是一个谎言；因子分解被推测是一个难题（见11.4节）。众所周知，它似乎是这样。如果它的确是，也没有人能够证明难题就真的很难。大多数人都假定因子分解是困难的，但它从来没有被数学证明过。

    还有必要再啰嗦一点。不难想象50年后的情形，人门围坐在一起，兴致勃勃地谈论着过去的美好时光：那时候，人们习惯于认为因子分解是难的；密码体制正基于这种难度；而公司实际上依靠这种素材大赚其钱。也可以很容易地设想到，未来在数论方面的发展使因子分解更加容易或者复杂度定理的发展使因子分解变得毫无意义。没有理由相信这会发生——并且大多数懂得很多，而有主见的人也会告诉你这是不可能的——但是也没有什么理由相信它不会发生。

    无论怎么样，今天主要的公钥加密算法都是基于分解一个大数的难度，这个大数一般是两个大素数的乘积。（其它一些算法基于称为离散对数问题的东西，这里我们作相同的讨论。）这些算法也会受到穷举攻击的威胁，只不过方式不同。破译它们的出发点并不是穷举所有的密钥进行测试而是试图分解那个大数（或者在一个非常大的有限域内取离散对数——一个类似的问题）。如果所取的数太小，那么就无安全可言；如果所取的数足够大，那会非常安全：集中世界上所有的计算机力量从现在开始工作直到太阳变成一颗新星为止都不能奈何它——当然是基于目前对数学的理解。11.3节更注重数学细节，讨论了大数因子分解的有关问题，这里我们仅讨论分解不同长度的数需要花费多长时间。

    对大数进行因子分解是困难的。不幸地是，对算法设计者来说它正变得越来越容易。更加糟糕的是，它比数学家们所希望的还快。1976年，Richard Guy写道：“本世纪内如果有人不采用特殊的方式成功地对10⁸⁰大小的数进行因子分解的话那我将非常地惊呀！”[680]。1977年，Ron Rivest说过分解一个125个十进制位的数据需要40*10¹⁵年[599]。可是，一个129位（十进制）的数据在1994年被成功分解。如果有什么教训的话，那就是作出预言将是很愚蠢的。

    表7.3列出了过去十年有关因子分解的记录。其间，最快的分解算法是二次筛选法（参见11.3节）。

    这些数据是触目惊心的。今天已经很不容易看到512比特的数据在操作系统中使用了，因为对这些数据进行因子分解，这势必危及到系统的安全，是非常可能的：Internet上的蠕虫可在一个周末完成。

表7.3 使用二次筛选算法进行因子分解

    计算机的计算能力是以mips-years来衡量的，即每秒一百万条指令的计算机运行一年，大约3*10¹³条指令。根据约定，一台1-mips的计算机就等同于一台DEC VAX 11/780。因此，一mips-year就相当于一台VAX 11/780运行一年，或等同的机器。（一台Pentium 100计算机大约是50mips，而一台1800-node Intel Paragon机器则是50000。）

    1983年对一个有71个十进制位的数字进行因子分解需要0.1mips-years；1994年对一个129位的则需要5000mips-years。计算能力这一令人激动的增长很大程度上归功于分布式计算的引入：利用网络上工作站的空闲时间。这一趋势是由Bob Silverman发起而通过Arjen Lenstra和Mark Manasse大力发展的。1983年的分解在一台单独的Cray X-MP上使用了9.5个小时；1994年的分解却使用了5000个mips-years并耗费了全球范围1600台计算机将近8个月的空闲时间。可见，现代的因子分解从这种分布式应用中大受其益。

    情况变得更糟了。一种新的因子分解算法取代了二次筛选法：一般数域筛选法。1989年数学家们会告诉你一般数域筛选法永远不会行得通；到了1992年他们又说一般数域筛选是可行的，但是它仅仅当被分解的数大于130—150位（十进制）时才比二次筛选法快。可是今天，众所周知，对小于116位的数的一般数域筛选法也快得多[472,635]。同时分解一个512位的数一般数域筛选法要比二次筛选法快10倍。在一台1800-node Intel Paragon机器运行该算法不需要一年的时间。表7.4给出了应用该算法对一系列不同大小的数进行因子分解所需的mips-years数[1190]。

    然而，一般数域分解法的速度仍在加快。数学家们则努力紧跟着这些新技巧、新优化、新技术。现在还没有任何原因认为这种趋势不会继续。与其相关的一个算法：特殊数域筛选法，现在已经能够分解一些特殊形式的数——一般并不用于密码分析——其速度比一般数域筛选法分解同样大小的数还要快。假定一般数域筛选法优化后也能做得这样快是不无道理的，或许NSA已经知道怎样做。表7.5给出了用特殊数域筛选法进行因子分解的mips-years数[1190]。

    1991年在EISS（欧洲系统安全研究所）的一个实验室里，参与者们一致认为一个1024-比特的模数可以足够保密到2002年[150]。然而，他们又警告说：“尽管实验室的参与者在各自的领域中都有很高的资格，但是对这些声明（关于安全的持续性）要提高警惕。”这是个好建议。

    在选择公钥密钥长度时，明智的密码人员应是极端的保守主义者。为了断定你所需要的密钥有多长你必须考虑你想要的安全性和密钥的生命周期，以及了解当前因子分解的发展水平。今天使用1024-比特长的数仅获得80年代初期512-比特的安全性。如果你希望你的密钥能够保持20年的安全，那么1024-比特似乎太短了点。

表7.4  利用一般数域筛选法因子分解

表7.5  利用特殊数域筛选法因子分解

    即使你的特殊安全性并不值得花力气对模数因子分解，但仍然处于危险之中。设想一下用RSA加密的自动银行系统吧。Mallory站在法庭上大声说：“难道你没读报，1994年RSA-129就已经被破译，任何组织只要花上几百万美元等上几个月就能将512-比特的数分解吗？我的银行就是使用512-比特的数进行保密的，顺便说一下，我并没有不断地撤消更换。”即使他在撒慌，法官也会责令银行证实的。

    为什么不用10000-比特的密钥呢？可以用，但你必须为密钥变长所需计算时间付出代价。通常是，你既想密钥足够长又想计算所需的时间足够短。

    在本节的开始时我就说过作出预测是愚蠢的。但是现在我也预测一些。表7.6给出了公钥密钥多长才安全的一些忠告。其中，每年列出了三个密钥长度：分别针对个人，大的公司和大的政府。

    下面是摘自文献[66]的一些假设：

    我们相信能够获得十万台没有超人的，缺乏职业道德能力的机器。也就是说，我们绝对不会释放任何Internet蠕虫或病毒为我们寻求资源。很多组织都有几千台计算机在网上。充分利用这些设备的确需要很有技术性的外交能力，但不是不可能的。假定平均计算能力是5mips，那么一年的时间就能从事一项需要50万mips-years的工程。

    因子分解129-digit的数这样一个工程估计需要整个Internet计算能力的0.03%[1190]，这不会令它感到困难。假定一个非常引人注意的工程需要花一年时间使用全球2%的计算力量并非不可理解。

表7.6  公钥密钥长度的推荐值(比特)

    假设一个专注的密码分析家能得到10,000 mips-years的计算能力，一个大公司能得到10⁷ mips-years，并且一个政府能得到10⁹ mips-years。同时假定计算机的计算能力每5年增长10倍。最后假定数学领域因子分解的进步能够让我们以特殊数域筛选法的速度分解一个一般的数。（然而这是不可能的，但话又说回来，技术突破随时可能发生。）表7.6推荐了不同年份不同的安全密钥长度。

    一定要记住需考虑密钥的价值。公开密钥经常用来加密那些时间长，价值大的东西：银行顾客用于数字化取款系统的密钥；政府用于检验其护照的密钥；以及公证人的公开数字签名密钥。或许并不值得花上几个月的计算机时间对一个私钥进行攻击，如果你能用一个破译了的密钥印制自己的钞票的话那它就非常吸引人了。一个1024-比特的密钥足以作为那些用一个星期，或一个月，甚至几年才验证的东西的签名。但是你并不想拿着一份数字签名的文件从现在开始在法庭上站上20年，并且不断让对手演示如何用相同的签名伪造文件。

    对更远的未来进行预测会更加愚蠢。谁能知道2020年计算机，网络，数学等方面发展成什麽样？然而，如果你看得更远点，你就会发现每个年代我们分解数的长度是上个十年的一倍。这引出了表7.7。

    另一方面，分解技术早在2045年之前或许就达到它的极限值。从现在起的20年里我们可以分解任何的数。尽管如此，我认为未必。

    不是每个人都同意我的推荐的。NSA指令512-比特到1024-比特的密钥作为数字签名标准（参见20.1节）——远远低于我所推荐的长期安全的数值。Pretty Good Privacy（参见24.12节）使用了最大长度的RSA密钥，2047比特。Arjen Lenstra，世界上最成功的因子分解专家，在过去十年里拒绝作出预测[949]。表7.8给出了Ron Rivest对密钥长度的建议值，它们最早是在1990年作出的，但我却认为也太乐观了点[1323]。当他的分析在纸面上看来非常合理时，最新的历史却展示了令人惊奇的事正规则的发生着。这对你在选择密钥后面对未来的“惊奇”重新保持沉默是非常有意义的。

    25000美元的预算，使用二次筛选算法，每年的技术进步为20%假定是较低的估计，25000,000美元的预算，使用一般数域筛选法，每年33%的技术进步为一般的估计，而较高的估计假定是预算为25亿美元，使用一般二次筛选法运行在特殊数域筛选法的速度下，每年有45%的技术进步。

    一直有这样一种可能性存在，那就是因子分解方面的进步同样令我吃惊，但归因于我得计算。但是为什么要相信我呢？我也只是通过预测证明了我的愚蠢。

表7.7 对未来因子分解的预测

表7.8  Rivest 乐观的密钥长度推荐值

    DNA 计算法

    现在的情况正变得不可思议。1994年，Lenard M. Adleman在一个生物化学实验室里竟然演示了NP完全问题的解决方法（NP-Complete Problem）（参见11.2节），他用DNA分子链描述对该问题解的推测[17]。Adleman所解决的问题是引向哈密尔顿问题（Directed Hamiltonian Path Problem）的一个实例：汉密尔顿问题是指，给定一张有关城市的地图，其中这些城市是由单向马路连接，要求在地图上找到一条从城市A到城市Z而恰恰仅一次通过所有城市的路径。在Adleman的演示中，每一个城市由一系列不同的随机的20基点的DNA链表示，用传统的微生物技术，Adleman综合处理了50皮摩尔（相当于3*10¹³个分子）的DNA链。每一条路也是由一个20基点的DNA链表示，但这些DNA链并不是随机选取的，Adleman聪明地选择它们以使表示每条路（如Road PK）的DNA链的开始端连到该路的起始城市（如P）DNA链，而其尾部则连到终止城市（如K）。

    Adleman使用了50皮摩尔的DNA链表示每一条路，再用一条表示所有城市的DNA 链将它们混合在一起，然后加入一种捆绑酵素使所有的DNA分子的尾部相连。酵素利用DNA路和DNA城市之间非常技巧的关系把各个表示路的DNA 链连成了一个正当的模式。也就是，路 PK的“出”端连到了始于城市K的所有路的“入”端，而不是其他路的“出”端或始于别的城市的那些路的“入”端。这些混合物经过一段时间的反应（时间是精心计算的），酵素会生成大量的DNA链，这些DNA链就表示地图上合法的但是随机的多路路径。

    在所有的这些路径中，Adliman可以观察到非常细微的痕迹——甚至单个分子——表示该问题解的DNA链。利用微生物学的一般技术，他丢弃那些表示路径过长或过短的DNA链 。（在所希望得到的路径中，路的数目应该等于城市的个数减一。）接着，他依次丢弃那些不经过城市A，B，….Z的DNA链。如果最后某个DNA链“幸存”，那就检测它以找到它所表示的路的序列：这就是有向汉密尔顿路径问题。

    根据定义，任何NP完全问题（NP-Complete）的一个实例都可以在多项式时间里变换成其他NP完全问题的一个实例，当然也可以转换成有向汉密尔顿问题的一个实例。从20世纪70年代开始，密码学家才试着将NP完全问题用于公钥密码体制中。

    由于Adleman解决的这个实例非常的“朴素”（地图上仅有七个城市，用眼睛观察也不过几分钟就能解决。），这项技术还处于初期，并且在发展上没有太大的障碍，所以，有关基于NP完全问题的密码协议的安全性讨论到目前为止才开始。“假定破译者有一百万个处理器，每一个每秒能测试一百万次”，或许很快就被改成“假定破译者有一千个发酵桶，每一个有20，000升的容量。”

表7.9 能阻止穷举攻击的对称密码和公钥密码的密钥长度

量子计算法

    现在，已经更不可思议了。量子计算法的基本原理就是爱因斯坦的玻粒二象性：光子可以同时存在于许多状态。一个典型的例子就是，当光射到银白色的镜面时，它会有波一样的特性，既可以反射也可以传播，就象波浪撞击一堵带有缺口的防波堤，有的会翻回去，有的却可以穿过去。然而对光子进行测量时它又表现出粒子的特性，有一个唯一的被测量的状态。

    在文献[1143]中，Peter Shor 阐述了一个基于量子力学的因子分解机器设计模型。不象一般的计算机在某一特定时刻可以认为有一个单一、固定的状态，量子计算机有一个内部波动函数，这个函数是所有可能基状态的联合重叠。计算机在单步运算中通过改变整套的状态值来改变波动函数。在这个意义上，量子计算机是基于经典的有限状态机改进而成的：它利用量子特性允许在多项式时间里进行因子分解。理论上可以用来破译基于大数分解或离散对数问题的密码体制。

    舆论一致认为，量子计算机与基本量子力学定理是可和谐共存的。然而，在可预见的未来制造出一台量子因子分解机基本上是不可能的。其最大的障碍是非连贯性问题，因为它容易导致叠加后的波形丢失某些特性，从而使计算失败。不连贯性会使运行在1Kelvin下的计算机仅1纳秒后就死机。另外，制造一台量子因子分解设备需要超大量的逻辑门，这使得制造不太可能。Shor的设计需要一部完整的模取幂计算机。由于没有内部时钟，数以千万甚至上亿的独立门被用于分解密码上非常大的数，如果n个量子门有很小的错误概率p，则每成功运行一次所需实验次数就是（1-/（1-p））ⁿ。量子门的数目可假定按被分解的数的长度（比特）呈多项式增加，那么，实验次数将随该长度呈超级指数增长——这比用试除法进行分解还要糟糕！

    所以，虽然量子因子分解法在学术上非常令人兴奋，但它在不远的将来被用于实践却是不可能的。别说我没有提醒你！