第九讲-离散对数

在RSA密码算法中，我们看到如何利用分解的困难性产生有用的密码系统。另一个数论问题，称为离散对数问题，也有相似的应用。Diffie认为离散对数问题来源于Gill的提示。离散对数问题是公钥密码学的又一个重要公开困难问题。本讲提要离散对数计算离散对数ElGamal公钥加密算法比特承诺1离散对数。当然，。上，在有限乘法群由于上的一个生成元。是有限乘法群。令。和为一个整数。有令。，上一个生成元，是有限乘法群令。，写为，满足，数，找到整和一个元上一个生成元有限乘法群，数定义如下：给定一个素离散对数问题11)(mod92226=9log11)(mod922=11=1)(mod)(log)(log1)(mod)log+(log)(log)(log)(mod20(DLP)26166211611**s*p*px*p*pZZppspsZZxppxxZβZp例子1事实1定义1的离散对数。意其它底数法同样可以用来计算任为底数的离散对数算以这意味着任何可以计算。，，这里和，结果是。则，，和，。令上的两个生成元，令有限乘法群为和令。的困难性与生成元无关1)1(log)1mod()(log)(loglog)1(mod)(=log=log=log=DLP1pppyzxzyxZZyzyx*p*p事实2难于解决。更常比的生成元。这一问题通是也没有要求是循环群，表述下，没有要求这里假定存在。在这种，满足，找到整数，和元个有限群一形式可以表述为：给定一个更一般的。，满足，，找到整数及元，以，和其上的生成元的有限循环群何一个阶为定义如下：给定任一般离散对数问题GDLP=GDLP=10(GDLP)GGxGGnxxGGnxx评述.定义22计算离散对数2.1穷举搜索。码关注的情形这恰好是密有效方法足够大的值时，这不是取的阶，因此，当是次乘法，这里。这一方法需要，直到得到，，，的方法是连续计算最为简单的求解)(11)O(...DLP210ppp2.2小步大步算法的方法。如下计算这就给出。，这意味着。因此，，，这里我们可以写，则事实。如果平衡，它的基础是以下在效率和存储之间的算法是对穷举搜索方法的阶。小步大步是，这里令xmjim+jx=ippm=jimjmixx)(0=112.2小步大步算法(续)。设置。则，如果。项是否为表中某个第检查。和设置计算项对表排序。的第。以条目中这里的表，，为建立一个条目。设置。离散对数输出：。和元的阶输入：生成元小步大步法mjmjm+jx=imimjjpmx=p·(4.3))(return(4.2)2(4.1):followingthedo1to0fromFor(4)(3)20)((2)1(1)log1算法12.2小步大步算法(续)次乘法。需要也就是小步大步算法运行时间的明确结论，需要的可以得出需要的时间，那么我们次比较间多于假定一次乘法需要的时次查表完成算法。次乘法和需要表以后，步骤比较来排序。建立这个次次乘法来建立和个群元。表需要需要存储)1O(1lg)1O()1O((4))1lg1O()1O()1O(pppppppp算法1算法1评述.2.2小步大步算法(续)。，因此，离散对数为，最后，由于过程如下：行的某个元相等。这一值与表中第直到有一个，连续计算，，，对于。，接着计算计算项排列表：第，以条目的这里，，建立一个表，条目是。设置的过程如下。计算离散对数。的生成元。考虑是阶为。令100=57log332392655112371002957113)(mod58·5798765432102113)(mod=...210=(4)58113)(mod3838)113(mod3(3)81635140272117971113)(mod3410673952802110))(mod((2)11=112(1)57log57=112=13=1133100111113imiimmjjiijjpαjmpp=31例子22.3Pollard的Rho算法，和，有因此，。，这里，满足，，，，和，，，两个整数序列群元序列按顺序定义了。这一这里，如果，如果，如果序列和，，，。定义如下群元例如，定加以关注，确定。需要对集合的确且元落在哪个集合容易，，和，个规模基本相等的集合的群可以被分成模000......0)(...1=1300210210322112102321baixbbbaaaiSxxSxxSxxxfxxxxSSSSpiibaiiiiiiiii+2.3Pollard的Rho算法(续)。对数定离散方程通常可以有效的确，假定。为底的对数得到对最后式子两边取以。，因此，，就有满足和个群元。我们可以看到要是两这里，，如果，如果，如果和，如果如果，，如果log)1mod()1(mod)(≡log·)(0211222222321132112222pbbpaabbxxxxiSxbSxbSxbbSxaSxaSxaaiiiiiiaabbbabaiiiiiiiiiii+iiiiiii+iiiiiiii2.3Pollard的Rho算法(续)。并否则，计算，则算法以失败告终；如果。设定则做如下步骤：，如果。，，，和，，计算利用前面提到的方程来，，，，和，，使用以前计算了的值，，。，，设置。离散对数输出：。和元的生成元阶为输入：算法的)return(1)()mod(01)mod((2.2)(2.1):followingthedo...21For(2)001(1)log1rhoPollard2122222222222111000xpaarxrpbbrxxbaxbaxbaxbaxibaxx=piiiiiiiiiiiiiiiiii算法22.3Pollard的Rho算法(续)为起点。并以和区间随机选择整数，以在，此外，计算过程也可很少情况会以失败结束法存储需求可以忽略。步算相当，但是相对小步大算法均运行时间与小步大步平算法是一个随机算法，的的计算离散对数00=]2[1(2)rhoPollard(1)000baxbap算法2评述.2.3Pollard的Rho算法(续)。。因此，和，，计算。最后，注意的值。，和，，，，步每一次迭代过程第。我们可以计算出则，；如果，则；如果则，：如果上的元的分类依据规则。对的子群。假定阶为是乘法群元110228log110)(mod191)(136=(mod191)125125(mod191))(144==23)(mod23)(mod03)(mod1228191=22142811128142814222321383383aarrbbrxxbaxbaxSxxSxxSxxZnZiiiii**算法2例子32.3Pollard的Rho算法(续)1041038121451512119612131209830481612112119972569337211118961483304101544872821529152482357225683812144622871861216114683304512055722564118446114409234118420279220279102281222144144iiiiiibaxbaxi2.4Pohlig-Hellman算法。必为偶数。事实上，我们可以判定，由于。假定我们试图解是奇数。否则，是偶数；则，如果。因此，。因此，我们有的最小指数，被假定为产生。然而，，因此注意的最后一比特。我们可以很容易得到。，的生成元，并假定为有限乘法群令6)11(mod19)11(mod921)(mod)1()(mod111)(mod1)(mod1)(1051)/2(1)/2(2/)1(1)/2(1)/2(1)/2(1)(21)/2(xxxxpppppxpxZpxpxpxpppppx*p例子4事实32.4Pohlig-Hellman算法(续)。。这里，，满足，整数使用中国剩余定理计算。设定。计算。和计算计算。计算。和设定。和设定简化符号，这里计算。，这里找到素数分解。离散对数输出：。和一个元的生成元输入：一个阶为算法)Return((4)1)(mod20(3)(2.5)log)(mod)()(mod:followingthedo1to0fromFor)((2.4)(2.3)01(2.2))((2.1)))mod((:followingthedoto1fromFor(2)1=1(1)log=1Hellman-Pohlig1110)1(1)1(111021111121xripxxpxxq+lq++llxlppejlleepqpxxplp+l=lxrieppppxpij+jjiiireiieeij/qpqlj/qpiieiieieiiieree算法32.4Pohlig-Hellman算法(续)。应该等于小定理。因此，最后等式成立的原因是。因此，。步，次迭代的第。接下来，在第的阶为步法的第最终决定。可以看到算，，，系数，的，这里进制表示通过决定。每一个整数整数国剩余定理就可以计算再使用中，这里上述方法先计算出同余则，对数是为素数分解。如果离散令jlqlq+ll/qpqlq+lql/qp/qpqlq+llx/qpqlq+lleijeieiiiieiiereelpjqlllplplp+l=lxpxpxripxxxppppjjeejjieejjjjj+j+jjj+jjiiiirlogFermat)()()()()()(mod(2.4)(2.3)10)1mod(,1)mod(log=1111111111111101111021)1()1()1()()1(11101110212.4Pohlig-Hellman算法(续)1(3)Hellman-Pohlig35037713503772247371047292133937277139650864112766422747515977189798311455964532692850524967592910215852314518195086781039742270882319=107Hellman-Pohlig(1)(2)))+)1((lg(Hellman-Pohlig1(1)4884*1就变得无效。不是一个平滑整数，如果变得相对简单。算法计算离散对数问题，这就使得用因子仅为最大的素数。由于素数分解。位十进制素数：是，这里常有效。考虑乘法群相对比较小时非算法仅当每个素数因子说明次乘法。算法需要的时间是的素数分解，则运行给定算法3评述.pppppZpppeOppiriii2.4Pohlig-Hellman算法(续)。得到离散对数，最后，解同余方程。因此，。用穷举搜索，计算得使。和计算。举搜索，计算得。使用穷和计算。使用穷举搜索，计算得。和计算。计算计算。则。和计算计算。阶的素数分解可按如下计算。则离散对数，考虑是一个生成元。元。令197210log125)(mod72)2mod(1(3)72=52+54+2=2149l