第九讲-离散对数课件.ppt

1、 在RSA密码算法中，我们看到如何利用分解的困难性产生有用的密码系统。另一个数论问题，称为离散对数问题，也有相似的应用。Diffie认为离散对数问题来源于Gill的提示。离散对数问题是公钥密码学的又一个重要公开困难问题。本讲提要q 离散对数q 计算离散对数q ElGamal公钥加密算法q 比特承诺1 离散对数。当然，。上，在有限乘法群由于上的一个生成元。是有限乘法群。令。和为一个整数。有令。，上一个生成元，是有限乘法群令。，写为，满足，数，找到整和一个元上一个生成元有限乘法群，数定义如下：给定一个素离散对数问题11) (mod 922 2 6 = 9 log 11) (mod 9 2 2 =

2、11 = 1)( mod )(log )(log 1)( mod )log + (log )(log )(log) (mod 2 0 (DLP) 26166211611*s*p*px*p*pZZppspsZZxp pxxZZp例子1例子1事实1事实1定义1定义1的离散对数。意其它底数法同样可以用来计算任为底数的离散对数算以这意味着任何可以计算。，这里和，结果是。则，和，。令上的两个生成元，令有限乘法群为和令。的困难性与生成元无关1) 1 (log) 1mod() (log ) (log log ) 1( mod )( = log = log = log = DLP 1pppyzxzyxZZyz

3、yx*p*p事实2事实2难于解决。更常比的生成元。这一问题通是也没有要求是循环群，表述下，没有要求这里假定存在。在这种，满足，找到整数，和元个有限群一形式可以表述为：给定一个更一般的。，满足，找到整数及元，以，和其上的生成元的有限循环群何一个阶为定义如下：给定任一般离散对数问题GDLP= GDLP = 1 0 (GDLP) GGxGGnxxGGnxx 评述.评述.定义2定义22 计算离散对数2.1 穷举搜索。码关注的情形这恰好是密有效方法足够大的值时，这不是取的阶，因此，当是次乘法，这里。这一方法需要，直到得到，的方法是连续计算最为简单的求解)(1 1)O( . . . DLP210ppp2.

4、2 小步大步算法的方法。如下计算这就给出。，这意味着。因此，这里我们可以写，则事实。如果平衡，它的基础是以下在效率和存储之间的算法是对穷举搜索方法的阶。小步大步是，这里令xmjim+jx=ippm=jimjmixx )( 0 = 112.2 小步大步算法(续)。设置。则，如果。项是否为表中某个第检查。和设置计算项对表排序。的第。以条目中这里的表，为建立一个条目。设置。离散对数输出：。和元的阶输入：生成元小步大步法mjmjm + jx = i mimjjpmx=p (4.3)(return (4.2) 2 (4.1):following thedo1 to0 from For (4) (3)2

5、0 )( (2)1 (1)log 1 算法1算法12.2 小步大步算法(续)次乘法。需要也就是小步大步算法运行时间的明确结论，需要的可以得出需要的时间，那么我们次比较间多于假定一次乘法需要的时次查表完成算法。次乘法和需要表以后，步骤比较来排序。建立这个次次乘法来建立和个群元。表需要需要存储 )1O(1 lg )1O()1O(4)1 lg 1O()1O( )1O( pppppppp算法1算法1算法1算法1评述.评述. 2.2 小步大步算法(续)。，因此，离散对数为，最后，由于过程如下：行的某个元相等。这一值与表中第直到有一个，连续计算，对于。，接着计算计算项排列表：第，以条目的这里，建立一个表，

6、条目是。设置的过程如下。计算离散对数。的生成元。考虑是阶为。令100 = 57log 3 32 392655112371002957113) (mod58 579876543210 2 113) (mod= . . . 2 10= (4)58 113) (mod 38 38 ) 113 (mod 3 (3) 81635140 272117971113) (mod 341067395 280 2 11 0 ) (mod ( (2)11=112 (1)57 log57 = 112 =1 3 = 113 31001 11113imi immjji ijjpjmpp=3 31例子2例子22.3 Pol

7、lard的Rho算法，和，有因此，。，这里，满足，和，两个整数序列群元序列按顺序定义了。这一这里，如果，如果，如果序列和，。定义如下群元例如，定加以关注，确定。需要对集合的确且元落在哪个集合容易，和，个规模基本相等的集合的群可以被分成模0 0 0 . . . . . . 0 )( . . . 1 = 1300210210322112102321baixbbbaaaiSxxSxxSxxxfxxxxSSSSpiibaiiiiiiiii+2.3 Pollard的Rho算法 (续)。对数定离散方程通常可以有效的确，假定。为底的对数得到对最后式子两边取以。，因此，就有满足和个群元。我们可以看到要是两这里

8、，如果，如果，如果和，如果如果，如果log ) 1 mod( ) 1( mod )( log )( 02 1 1 2 22222321132112222 pbbpaabbx xxxiSxbSxbSxbbSxaSxaSxaaiiiiiiaabbbabaiiiiiiiiiii+iiiiiii+iiiiiiii2.3 Pollard的Rho算法(续)。并否则，计算，则算法以失败告终；如果。设定则做如下步骤：，如果。，和，计算利用前面提到的方程来，和，使用以前计算了的值，。，设置。离散对数输出：。和元的生成元阶为输入：算法的)return( 1)( )mod( 0 1)mod( (2.2) (2.1)

9、:following thedo . . . 2 1 For (2)0 01 (1)log 1 rhoPollard 2122222222222111000 xpaarxrpbbrxxbaxbaxbaxbaxibaxx=piiiiiiiiiiiiiiiiii算法2算法22.3 Pollard的Rho算法(续)为起点。并以和区间随机选择整数，以在，此外，计算过程也可很少情况会以失败结束法存储需求可以忽略。步算相当，但是相对小步大算法均运行时间与小步大步平算法是一个随机算法，的的计算离散对数00= 21 (2) rhoPollard (1)000baxbap算法2算法2评述.评述. 2.3 Pol

10、lard的Rho算法(续)。因此，和，计算。最后，注意的值。，和，步每一次迭代过程第。我们可以计算出则，；如果，则；如果则，：如果上的元的分类依据规则。对的子群。假定阶为是乘法群元110 228log 110 )(mod191) ( 136= (mod191)125 125(mod191) )( 144 = = 2 3) (mod 2 3) (mod 0 3) (mod 1 228 191 = 2 2142811128142814222321383383aarrbbrxxbaxbaxSxxSxxSxxZnZiiiii*算法2算法2 例子3例子32.3 Pollard的Rho算法(续) 1041

11、038121451512119612131209830481 6 12112 119972569337211118961483304101544872821529152482357225683812144622871861216114683304512055722564118446114 409234 1 18420279220279102281222144144iiiiiibaxbaxi2.4 Pohlig-Hellman算法。必为偶数。事实上，我们可以判定，由于。假定我们试图解是奇数。否则，是偶数；则，如果。因此，。因此，我们有的最小指数，被假定为产生。然而，因此注意的最后一比特。我们可以

12、很容易得到。，的生成元，并假定为有限乘法群令6 )11(mod19 )11(mod92 1) (mod) 1( ) (mod1 11 ) (mod1) (mod1)( 10 51)/2(1)/2(2/ )1(1)/2(1)/2(1)/2(1)(21)/2( xxxxpppppxpxZpxpxpxpppppx*p例子4例子4事实3事实32.4 Pohlig-Hellman算法(续)。这里，满足，整数使用中国剩余定理计算。设定。计算。和计算计算。计算。和设定。和设定简化符号，这里计算。，这里找到素数分解。离散对数输出：。和一个元的生成元输入：一个阶为算法)Return( (4)1 )(mod 20

13、 (3) (2.5)log )(mod)( )(mod :following thedo 1 to0 from For ) ( (2.4) (2.3)0 1 (2.2) )( (2.1) ) mod( ( :following thedo to1 from For (2)1 =1 (1)log = 1Hellman-Pohlig 1110)1(1)1(111021111121xri pxxpxxq+ lq +llxlp pejlle epqpx xplp + l = lxr ieppppxpij+jjiiireiieeij/qpqlj/qpiieiieieiiieree算法3算法32.4 Po

14、hlig-Hellman算法(续)。应该等于小定理。因此，最后等式成立的原因是。因此，。步，次迭代的第。接下来，在第的阶为步法的第最终决定。可以看到算，系数，的，这里进制表示通过决定。每一个整数整数国剩余定理就可以计算再使用中，这里上述方法先计算出同余则，对数是为素数分解。如果离散令jlqlq + ll/qpqlq + lql/qp/qpqlq + llx/qpqlq + lleijeieiiiieiiereelpjqll lplplp + l = lxpxpxripx xxppppjjeejjieejjjjj+j+jjj+jjiiiir logFermat )( )( )( )()( ) (

15、mod(2.4)(2.3) 10 ) 1mod( ,1) mod( log =1111111111111101111021)1()1()1()()1(11101110212.4 Pohlig-Hellman算法(续) 1 (3)Hellman-Pohlig3503771350377224737 104729213393727713965086411276642274751597718979831145596453269 2850524967592910215852314518195086781039742270882319=107 Hellman-Pohlig(1) (2) )+ ) 1(lg

16、(Hellman-Pohlig1 (1)4884 *1就变得无效。不是一个平滑整数，如果变得相对简单。算法计算离散对数问题，这就使得用因子仅为最大的素数。由于素数分解。位十进制素数：是，这里常有效。考虑乘法群相对比较小时非算法仅当每个素数因子说明次乘法。算法需要的时间是的素数分解，则运行给定算法3算法3评述.评述. pppppZppp eOppiriii2.4 Pohlig-Hellman算法(续)。得到离散对数，最后，解同余方程。因此，。用穷举搜索，计算得使。和计算。举搜索，计算得。使用穷和计算。使用穷举搜索，计算得。和计算。计算计算。则。和计算计算。阶的素数分解可按如下计算。则离散对数，考

17、虑是一个生成元。元。令197210log 125) (mod 72 )2mod(1 (3)72 = 5 2 + 54+2 = 2149log 149 ) (mod )( 115 ) (mod (2.2.4)4 = 113 log 113 )(mod)( 21) (mod (2.2.3)2149log 149 )(mod)( 1 = (2.2.2)20 )(mod (2.2.1)55 )5(mod ( (2.2)1 = 250log= 250)(mod 250 )(mod ) )2(mod ( (2.1) (2)5 2 = 2501 (1)210log 210 = 71 = 251 712220

18、212515420125122005152210322501221371xx xxlpp lpp lpp + l + llx xxppxxpnx=p n/n/n/n/n/n/ 例子5例子52.5 指数积分算法 上元的乘积。合的元可以有效表示为集中大方法中，称之为分解基。这种集合中的元一个相对较小在指数积分算法需要选择。乘法群分算法可以应用于有限积指数时间复杂度。指数旦可以使用，算法为亚一应用于所有群，但是，方法。这项技术并不能数知最有力的计算离散对指数积分算法是目前已SZSZZppp* 2.5 指数积分算法(续)。唯一组解这是为了满足方程组有是一个小正整数，个关系直到得到和重复步骤。性关系两边

19、取对数得到一个线如果成功，对以上方程。，中元的乘积形式：为尝试写。计算，选择一个随机整数上对数元的线性关系收集关于的元的乘积形式。为来自上的元可以有效的表示相当多的在，满足，上选择一个集合在选择一个分解基。离散对数输出：。和元的生成元乘法群输入：指数积分算法) ( (2.2)(2.1) (2.3) 1(modlog 0 )mod( (2.2) , 10 (2.1) )( (2) = )( (1)log = 11*21*ct + cp pc k c ppSnkkSSZpppSZSxZtiiiiticikkkptppi算法4算法42.5 指数积分算法(续)。得到对数步。否则，方程两边取第如果尝试不

20、成功，重复。，中元的乘积形式：写为尝试将。并计算，选择一个随机整数计算。，值得到所有个线性方程的线性系统步中收集到的解在第意义下在模上元的离散对数找出续指数积分算法)Return( ) 1)mod(log(= log 4.1 0 )mod( : (4.2) 1 0 (4.1)( (4)1 log 2 ,1 )( (3)( 11xxpkpd d ppSnkkxti pt + cpSitiiitidikkkii算法4算法42.5 指数积分算法(续) (3) (2) (1)个素数。可以选择前，分解基对于有限乘法群方法也没有被定义。第二，有效的产生关系的技术没有明确定义；择分解基选完全充分描述。第一，

21、因为以下两个原因而未复使用。群计算离散对数可以反定生成元的中，之后对于同一个特对数存储于一个数据库中的所有元的离散算将在集合通常情况下，先进行计tSZ SS*p算法4算法4 评述.评述.2.5 指数积分算法(续)。：的尝试未写出不成功系个与分解基元相关的关我们可以得到以下。，个素数：分解基选择前可按如下步骤。算离散对数则使用指数积分算法计，。考虑生成元有限乘法群。令7 5 3 2 210) 229 (mod6 11 3 2198 229) (mod6 11 7 2 154 229) (mod 6 115 3 165 229) (mod6 112 176 ) 229 (mod 6 5 32 18

22、0229) (mod6 ) ( 6 (2)11 7 5 3 2 5 (1)13log 13 6 = 229 20621436212418221006SZp=*p 例子6例子62.5 指数积分算法(续)。，这样我们有由于。假定选择了整数。和，得到解离散对数个未知参数个方程解用。如下：数方程个关于分解基的离散对这些关系可以产生续117 = 228) (mod 77) 7 log2 + 3 (log13log 7 3 147 229) (mod 6 13 77 = (4)162 = 11 log 107 = 7log 98 = 5log 208=3log21 = 2log )log(56 (3)22

23、8) (mod 7log + 5log + 3log+2log206 228) (mod 11log+3log2 + 2log 143 228) (mod 11log + 7log + 2log 62 228) (mod 11 log+5log + 3log 12 228) (mod 11log+ 2log4 18 228) (mod 5log+3log2+2log 2 100 6 )( 666277666666666666666666666666kiik p =x例子6例子63 ElGamal公钥加密算法 ElGamal公钥加密方案依赖于离散对数问题和Diffie-Hellman问题的困难性

24、。基本的ElGamal公钥加密方案是ElGamal于1985年提出。3.1 算法描述。的秘密密钥就是；，的公开密钥就是。并计算，选择一个随机整数。上的生成元和有限乘法群产生一个大的随机素数做如下步骤：每个实体秘密密钥。自己的公开密钥和对应摘要：每一个实体产生公钥加密的密钥产生aApAppaaZpAaa*p) ( (3) (mod 21 (2) (1)ElGamal 算法5算法53.1 算法描述(续)。得到明文消息通过计算。注意：计算利用秘密密钥应该做如下步骤：，中恢复出明文消息为了从密文消息。给，发送密文消息。和计算。，选择一个随机整数。上的整数，间将具体消息表示为在区。，的真实公开密钥得到做

25、如下步骤：解密之。，给实体加密一条消息摘要：实体公钥加密m p paAmcA c pm ppkkmppABAAmBakaaapapkaka)(mod (2) ( )(mod (1) ) ( = (5)(mod)( )(mod (4)21 (3) 10 (2) ( (1) ElGamal 11解密.解密. 加密.加密.算法6算法63.1 算法描述(续)大的数值。通常需要选择更的一个不利之处在于和通用参数系统内开密钥的尺寸。而使用密钥。这将可以缩减公体的公开可以不再被看作每个实和，这种情况下和生成元用相同的素数所有的实体可以考虑使。的明文消息，这是因为出原始的解密过程将可以恢复pppppmmaka

26、ka ) (mod 评述.评述.算法6算法6. . 解密正确性证明解密正确性证明3.2 例子。息并通过计算恢复明文消，计算为了解密，。给和发送。和并计算选择一个随机整数实体，为了加密明文消息。，的公开密钥为。并计算选择秘密密钥。生成元上的和一个在有限乘法群选择素数实体2035 2357) 697(mod 872 872)2357(mod1430 697 =1430697 2357) (mod1185 2035 1430 2357) (mod 2 1520 = 2035 1185) 2 2357 ( 11852357) (mod2 ) (mod1751 = 2 Z2357 = 605115201

27、5201751*2357m AA BkB mpApaA pAapaa解密.解密. 加密.加密.密钥产生.密钥产生.例子7例子73.3 ElGamal加密算法效率倍。长度为对应明文消息的。也就是，密文消息的因子为于明文消息的扩展加密的一个不利之处在数的搜索攻击。通过小步大步算法对指抵抗，指数也必须足够大以来提高处理速度。但是重量，如低的过程中附加适当性质指数通过在随机选择。这两个模幂计算可以和计算，也就是加密过程需要两次模幂22ElGamal (2)Hamming)(mod)()(mod (1)k p pkak3.4 ElGamal加密算法安全证明。然没有两个问题的等价上的离散对数问题，虽限乘法

28、群，常常被认为是基于有，恢复，和，是，给定参数加密方案的问题，也就破译将很容易被恢复出来。已知，则如果，。由于，和，产生密文消息对和用于加密两条消息为指数。假定同一个的随机整数择不同息进行加密时，必须选注意在对不同的明文消*paZm pmmmmmmkk ElGamal (2) / /) () ( (1)2121212211213.4 ElGamal加密算法安全(续)产生的秘密密钥。将可以威胁所有使用模计算的离散对数数据特定模以提高速度。对于一个数可算系统中具体的离散对复使用，因此，对于计生重散对数数据可以一次产整个系统，分解基的离对于上的离散对数问题时，用指数积分算法计算在使大密钥尺寸。这是因

29、为的系统，还需要适当加使用通用参数比特或更大的模。对于需要使用，上离散对数计算的进展根据目前有限乘法群ppZZ*p*p1024 (3)4 比特承诺 4.1 背景 (1) Alice声称发现了一种方法可以成功预测球赛的结果。她想把这种方法买给Bob。Bob要求她把周末的球赛结果预测一下以证明方法有效。Alice说 “没门，你可能利用我的预测结果去买彩票牟利，并且不与我分成。为什么不让我给你预测上周比赛的结果呢？” 4.2 比特承诺的要求 Alice能发送一个比特b给Bob，这个比特可以是0或1。并需要满足 (1) Bob在没有Alice的帮助下不能决定这一个比特的取值。 (2) Alice一旦发

30、送了这个比特，就不能改变取值情况。这样，对每场球赛，Alice可以发送b=1，表示她预测的队获胜；发送 b=0，表示她预测的队失败。在比赛结束以后，Alice向Bob揭示这一比特的取值，证明自己的预测。4.3 计算模4的离散对数并不同余。，它们模和个值散对数，我们就得到两是离。如果我们也允许我们定义了离散对数是。如，之间的整数才成立。例到为了离散对数可解也仅是在我们规定数。事实上，这一问题生了一个含糊的分数指为指数的值。这实际产算计算法了，这是由于需要我们不再能使用时的情况如何呢的取值。但当离散对数模算法可以很容易计算出时，当4 166 16 69log)11(mod9222 0 )/41(H

31、ellman-Pohlig?)4(mod34 Hellman-Pohlig)4(mod12166pppp4.3 计算模4的离散对数(续)。则。整数，满足的非是两个模和假定为整数。并令为素数，令令)(mod)( ).(mod )(mod 0 2 )4(mod3 1212122122)1(4/ )1(24/ )1(2 p p ppyrpyypyyppypyrrrrrr证明.证明.性质1性质14.3 计算模4的离散对数(续)的取值。，到所有处理过程，我们可以得的取值。反复这一得到上面方程中为算法的输入，我们将以我们发现次，使用。令。，这里，了值。假定我们已经确定的取和一算法，我们可以确定的二进制表示

32、。利用这为并且令位取值。现在假定二进制表示的第数的供新信息仅仅是离散对。因此，算法给我们提易计算出容。事实上，我们可以很时可以输出法在给定一个输入们有一个算为一个生成元。假定我并且令固定一个素数离散对数。的效计算出模们就可以用这一算法有的离散对数，那么，我出模情况下，有效计算以在素数如果我们有一个算法可nrprxxprxxxxrrnnxxxxxpr rxxxxxxxxxxpppprrrrrrrrr10)4/ )1()2(2)4/ )1()2(2)2(11010101111110 ). (mod 1 2 22 )(mod22) (modlog4) (modlog )4 (mod314)4 (mod3 性质1性质1事实4事实44.4 比特承诺方案。诺来确定比特承以及查看通过核实发送给他。将整个的时候，想知道值当。值不能够确定所指出的，。正如我们在给并发送计算。诺安排承比特，它的第选择一个随机数。和一个生成元协商一个大素数和bxpxbxbpbxpxpxx4) (mod )(mod? Bob Alice Bob (3) BobBob )(mod Alice (2) 21Alice (1) )4 (mod3BobAlice11事事实实4 4精品课件精品课件！精品课件精品课件！谢谢!