第九讲-离散对数课件.ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《第九讲-离散对数课件.ppt》由用户(三亚风情)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第九 离散 对数 课件
- 资源描述:
-
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算法(续)。得到离散对数,最后,解同余方程。因此,。用穷举搜索,计算得使。和计算。举搜索,计算得。使用穷和计算。使用穷举搜索,计算得。和计算。计算计算。则。和计算计算。阶的素数分解可按如下计算。则离散对数,考
展开阅读全文