资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2013/1/30,#,内 容,欧拉函数与循环群,RSA,原理,RSA,实现的问题,大数因式分解问题,RABIN,公钥密码系统,公钥思想,Diffie and Hellman,1976.,公钥算法,Rivest,Shamir,and Adleman,1977,欧拉函数,自变量为正整数,n,的函数 称为欧拉函数,(n),，,(n),表示小于,n,且与,n,互素的正整数的个数。,当,n,为素数时，,(n)=n-1.,欧拉函数的计算,欧拉函数与循环群,欧拉,(Euler),定理,已知,a,、,n,为整数，如果,gcd(a,n)=1,，则有,a,(n),=1(mod n),费马,(Fermat),小定理,已知,a,、,n,为整数，如果,gcd(a,n)=1,，则有,a,n-1,=1(mod n),封闭,a,b,G(,双向运算),结合律,a,(b c)=(,a,b)c,幺元,a e=e a=a,逆元,a,a,-1,=,a,-1,a,=,e,如果仅满足,(1),和,(2),则称,G,是一个半群,(Semigroup),如果仅满足,(1),、,(2),和,(3),则称,G,是一个含么半群,(Monoid),阿贝尔群,：,a,b=b a (,交换律,),群,：,实数加,e,=0,a,-1,=-a,非零实数乘 e,=1,a,-1,=a,-1,.,e,a,b,c,e,e,a,b,c,a,a,e,c,b,b,b,c,e,a,c,c,b,a,e,实例,(Klein,群,),无限群、有限群、群的阶,设,(G,*),是群，,G,的元素个数是无限时，,G,称为无限群,G,的元素个数是有限时，,G,称为有限群,G,的元素个数称为群,G,的阶。,元素的阶,满足,a,n,=e,的最小正整数,n,，称为元素,a,的阶，记作,O(a),如果等式永不成立，则称,a,的阶为无穷大。,子群,设,S,是群,G,的一个非空子集，如果,S,对,G,的运算也构成群，则称,S,是,G,的子群,(Subgroup),，记作：,SG.,循环子群、生成元,设,G,是群，,a,G,，令,H=a,k,|k,Z,，则,H,称为循环子群,(,Cyclic,Subgroup,),a,为生成元,循环群,一个群,(G,*),称为循环群，如果存在一个元素,a,G,，使得,G,=a,k,|k,Z,：,(,Z,+),是由,1,生成的循环群,如果,p,是素数，那么,(Zp,+),是循环群,b,1,2,3,4,5,2,b,mod11,2,4,8,5,10,6,7,8,9,10,11,9,7,3,6,1,2,如果,p,是素数，那么,(Zp*,*),是循环群,生成元为,2,，,p,=11,时的循环群,RSA,1978,年，,Rivest,，,Shamir,和,Adleman,“,A Method for Obtaining Digital Signatures and Public-Key Cryptosystems,”,RFC2313,与,RFC3447,RFC2537,：,RSA/MD5 KEYs and SIGs in the Domain Name System(DNS).,RFC2792,：,DSA and RSA Key and Signature Encoding for the KeyNote Trust Management System.,RFC3110,：,RSA/SHA-1 SIGs and RSA KEYs in the Domain Name System(DNS).,实例,p=101,q=113,b=6597,a=3533,n=11413,=11200,x=6218,y=9324,NP,完全问题,用非确定性算法可以在多项式时间内求解的问题称为非确定性多项式时间可解类，或简称,NP,完全问题或,NP,问题,n,=,pq,的大数因式分解问题,求,(n),和大数因式分解是等价的,循环攻击,p=23,，,q=31,n=2331=713,a=569,，,b=29,(n)=(23-1)(31-1)=660,x,=25,y,=25,29,mod713=36,y,(0)=25,29,mod713=36,y,(1)=36,29,mod713=676,y,(2)=676,29,mod713=625,y,(3)=625,29,mod713=583,y,(4)=583,29,mod713=656,y,(5)=656,29,mod713=614,y,(6)=614,29,mod713=501,y,(7)=501,29,mod713=397,y,(8)=397,29,mod713=532,y,(9)=532,29,mod713=,25,y,(10)=25,29,mod713=36,同模攻击,p=89,，,q=137,n=89*137=12193,a,1,=10429,，,b,1,=661,a,2,=4468,，,b,2,=1181,x,=2005,y,1,=2005,661,mod12193=3429,y,2,=2005,1181,mod12193=11196,c,1,=661,-1,mod1181=1047,c,2,=(1047,661-1)/1181mod12193=586,RSA,实现的问题,如何找到足够大的素数？,一类是通过数学理论构造出一个大的素数,另一类是随机给定一个足够大的数，然后去证明它是素数。,如何高效地实现模指数运算？,素性检测,验证一个数是不是素数叫素性检测,Wilson,定理,p,是素数,22,！,=1124000727777607680000=-1 mod 23,运算量非常大，并不实用,拟素数,设,n,是一个奇合数，若整数,b,与,n,互素，成立,则,n,称作对于基,b,的拟素数。,随机选取与,n,互素的整数,b,，若,b,n-1,=1(mod n),成立，则,n,为拟素数的概率,50%,，,n,为素数的概率,50%,该性质可以用来构造素性检测算法，算法如下：,1.,给定奇整数,n3,和检测轮数,t,，令,k,1,。,2.,随机选取整数,b,，,2bn,2,。,3.,计算,d,(b,n),。,4.,若,d,1,，则,n,是合数，输出“,Fail”,，结束；否则转,4,。,5.,计算,r=b,(n-1)/2,(mod n),。,6.,若,r1(mod n),，则,n,是合数，输出“,Fail”,，结束；否则，表明,n,通过了一轮素性检测，转到下一步。,7.k,k,1,。若,kt,，转到,(1),；否则表明,n,通过了,t,轮检测，输出“,Success”,，结束。,经过,t,轮检测并输出“,Success,”的拟素数确定为素数的概率是,将接受卡密歇尔数的挑战,卡密歇尔,(Carmichael),数,合数,n,称为卡密歇尔数，如果对所有与,n,互素的正整数,b,，都满足：,b,n-1,=1(mod n).,561,3,11,17,是一个卡密歇尔数,1105=5,13,17,也是一个卡密歇尔数,如果卡密歇尔数是有限的，那么前面的概率素性检测算法还是可用的，只需在每次算法运行前先查询“卡密歇尔数表”即可。,但遗憾的是存在无穷多个卡密歇尔数。,当,n,足够大时，区间,2,，,n,内至少有,n,2/7,个卡密歇尔数。,欧拉拟素数,已知,n,是奇素数，如果对任意正整数,a,，成立,那么称,n,是对于基,a,的欧拉拟素数。,设,n,是奇素数,a=0(mod n),，,a0(mod b),，若方程,x,2,=a(mod n),有解,则称,a,是模,n,的,平方剩余,。,欧拉准则,:,设,n,是奇素数，,a,是整数，那么,a,是一个模,n,的二次剩余当且仅当,a,(n-1)/2,=1(mod n),勒让德,(Legendre),符号,当,n,是素数时，雅可比符号与勒让德符号是一样的,雅可比,(Jacobi),符号定义为,设,m,是正奇数,雅可比符号的四个性质,欧拉拟素数是素数的概率,50%,反例,Solovay,Stassen,概率素性检测算法,1.,随机选取整数,a,，,2an,2.,2.,计算,d,gcd(a,n).,3.,判断：若,d,1,，则,n,是合数，输出“,Fail”,，结束；否则转到,(4),。,4.,计算,r=a,(n-1)/2(mod,n),5.,判断：若,r1(mod n),，则,n,是合数，输出“,Fail”,，结束；否则转,(6),。,6.,计算勒让德符号,s,(a|n).,7.,判断：若,rs,，则,n,是合数，输出“,fail”,，结束；否则转,(8),。,8.n,通过一轮素性检测，,k,k,1.,9.,若,kt,，转,(1),，否则,n,通过,t,轮检测，输出“,Success”,，结束。,通过,t,次,Solovay,Stassen,素性检测的整数,n,为素数的概率,素数定理,从,1,到,N,的整数中抽到素数的概率,任选一个,512,位的随机正整数,它是素数的概率大约为,模指数算法,二进制法,二进制,NAF,算法,滑动窗口算法,s=1,for i=l to 0 do,s=ss mod n,if(ei=1)then s=sg mod n,return s,实例,大数因式分解问题,p-1,法,Dixon,算法,a=2,for i=2 to b,a=ai mod n,d=gcd(a1,n),if(1dn)then,d,是,n,的素因子,else,寻找,n,的素因子失败,设,n=29389613454601,，取,b=600,，运用,p-1,算法进行因式分解：,在循环结束时，得到：,a=22058222139834,于是：,d=gcd(22058222139833,29389613454601)=6210433,进一步检测：,29389613454601=62104334732297,说明因式分解成功。,RABIN,公钥密码系统,中国剩余定理,设 是,n2,个两两互素的大于,1,的整数，令,则同余方程组的解为：,其中,b,i,(1in),是满足同余方程,的一个特解。,x,=5(mod 7)=3(mod 11)=10(mod 13),x,=?,实例,Rabin,密码系统,
展开阅读全文