第页共NUMPAGES6页时间存储折衷分析(martinhellman)1、思想简介时间存储折衷攻击是一种选择明文攻击方法。MartinHellman这篇开山之作主要是针对分组密码算法进行分析的，其弱点在于仅仅使用一个明密文对，无法使用更多的明密文对，从而导致其分析结果并不是最优。目前如何使用更多的明密文对从而减少攻击时间是个非常困难的问题。尽管如此，其分析方法比密钥穷举攻击的时间复杂度小，比查表攻击的空间复杂度要小。实际上，密钥穷举攻击和查表攻击分别是在时间和空间上的两个极端做法，而该篇阐述的方法是上述两种方式的一种折衷。该方法的总体思路：由于分组密码算法fk(x0)=y，将k作为输入，y作为输出，其函数称作Sx0(.)。在已知y和分组密码算法是安全的情况下，求取k是困难的，因此Sx0(k)=R(y)是单向函数，仿照【1】R.C.MerkleandM.E.Hellman,Hidinginformationandsignaturesintrapdoorknapsacks,IEEEInformTheory1978.和【2】S.C.PohligandM.E.Hellman,AnimprovedalgorithmforcomputinglogarithmsoverGF(p)anditscryptographicsignificance,IEEEInformTheory1978.的思路将Sx0(.)作为离散对数函数（即：单向函数）对待来建立概率模型。即：当攻击者从线路上得到一个明密文对(P0,C0)后（即：fuk(x0)=y），攻击者开始随机选择m个密钥k1,0,…,km,0,然后将Sp0(k1,0)反复迭代产生一个链条(上面有t+1个元素，仅用前t个元素)，以此类推--共得到m个这样的链条，最终形成m*t（仅仅计算所使用的点的数目）个元素的矩阵。如下图所示：图1假设刚开始m个路径是不相交的，但接下来的一个路径却与前面的路径之一有公共点。由于每条路径最多有t个元素，因此为了保证第m+1路径的每个元素和前m个路径没有交集，就必须满足t*(mt)N，否则mt个元素的集合和t个元素的集合相交的概率（1-P(n,t,mt,0)）大于0.5（其中P是泊松分布的密度函数）。这样只要m*t2N，这两个集合就很可能不相交，这样我们就选择满足关系m*t2=N的m和t，我们称之为矩阵中止规则。如果我们仅仅使用上述一个矩阵点进行攻击，其攻击成功概率是多少呢？上述一个矩阵所覆盖的点仅仅有mt=N/t个。因此，如果t较大时，根据生日攻击可知：寻找uk成功概率很低。一个矩阵最多也就m行，不可能再大了。如何解决这个问题呢？MartinHellman的伟大之处在于他发现可以使用fi(x)=h(f(x))所定义的原始f的变形fi，其中hi是其简单输出的变体（即：将f(x)的比特重新排序）。这些修改的f变形具有下面三个性质：1．对于i≠j，fi和fj矩阵中的点是根本无关的，因为这两个不同矩阵中存在一个共同点并不意味着两条路径中的后续点一定相等。因此，t个矩阵的并集（每个包含mt个点）很可能含有固定的一部分空间。2．在修正后的点yi＝fi(x)＝hi(f(x))上反转任意修正函数fi，可以解决已知的y＝f(x)计算x的问题。3．即使我们不知道x的值也可以将hi应用于已知的y＝f(x)来计算yi＝fi(x)的值。通过w个修改的fi，产生w个矩阵（每个矩阵有m*t个点）,因此总共覆盖的点有w*m*t个点，根据生日攻击,要以较大概率(1-e-1)寻找到c0和上述w个矩阵碰撞的点（即：成功寻找到UK,其中Sp0(k)=c0，fuk(p0)=c0），就必须满足：w*m*tN。我们选择w*m*t=N，因此w等于t。攻击预处理时间是N，攻击所需要的存储量是w*m=m*t，需要的时间复杂度是w*t=t2。设mi=t，则m*t2=N等价于m*m2i=N,推出m=N1/(2i+1)。因此对应攻击过程需要的时间复杂度是N2i/(2i+1)，攻击过程需要的空间复杂度是N(i+1)/(2i+1)。因此随着i趋于0，时间复杂度在减少，而空间复杂度在增加,再逼近N；当i趋于无穷大时，时间复杂度在增加，逼近N，而空间复杂度在减少,逼近N1/2；时间复杂度和空间复杂度相等时，充分必要条件是i=1。因此m=t=N1/3，攻击过程需要的时间复杂度是t2=N2/3，空间复杂度是m*t=N2/3。注意，在这个折衷公式中，时间复杂度T可以为（1,N)中的任何值，空间复杂度M被严格限定在(N1/2,N)中。2、下面介绍时间存储折衷攻击的预处理和攻击过程：第1部分预处理过程如下：输入：明文p0,密文c0和约减函数R。参数：w个表，m个随机起始点，每个链条有t