《群论在计算机安全领域中应用.ppt》由会员分享，可在线阅读，更多相关《群论在计算机安全领域中应用.ppt（24页珍藏版）》请在三一办公上搜索。
1、群论在计算机安全领域中的应用,搜集整理:01047 牛先芳 信息管理系E-mail:,群论在计算机安全领域中的应用,1.椭圆曲线密码2.子群成员问题3.DES,1.椭圆曲线密码,椭圆曲线密码介绍,1985年Miller,Koblitz 独立提出y2+axy+by=x3+cx2+dx+e曲线上的点连同无穷远点O的集合加法:若曲线三点在一条直线上,则其和为零倍数:一个点的两倍是它的切线与曲线的另一个交点,问题阐释,有限域上的椭圆曲线 设K表示一个有限域，E是域K上的椭圆曲线，则E是一个点的集合：E/K=(x,y)|y2+a1xy+a3y=x3+a2x2+a4x+a6,a1,a3,a2,a4,a6
2、x,y K O 其中O表示无穷远点。在E上定义+运算，P+Q=R，R是过P、Q的直线与曲线的另一交点关于x轴的对称点，当P=Q时R是P点的切线与曲线的另一交点关于x轴的对称点。这样，(E,+)构成可换群(Abel群)，O是加法单位元(零元)。椭圆曲线离散对数问题ECDLP定义如下：给定定义在K上的椭圆曲线E，一个n阶的点P E/K，和点Q E/K，如果存在l，确定整数l,0 l n-1,Q=lP。前面已经提到，ECDLP是比因子分解难得多的问题。,椭圆曲线密码示意图,椭圆曲线上的加法:P+Q=R 椭圆曲线上一点的2倍:P+P=R.,有限域上椭圆曲线,有限域上椭圆曲线y2x3+ax+b mod
3、p p是奇素数,且4a3+27b20 mod py2+xyx3+ax2+b mod 2m加法公式:P=(x1,y1),Q=(x2,y2)若x1=x2且y1=-y2,则P+Q=O,否则 P+Q=(x3,y3)x3=2-x1-x2y3=(x1-x3)-y1其中,=(y2-y1)/(x2-x1),如果PQ=(3x12+a)/2y1,如果P=Q,Ep(a,b),椭圆曲线上的整数点在上述运算下成为一个交换群(Abelian群),记作Ep(a,b).关于|Ep(a,b)|,有如下不等式:p+1-2p1/2|Ep(a,b)|p+1+2p1/2该不等式表明:|Ep(a,b)|pG是Ep(a,b)的一个元素,使
4、得nG=O的最小正整数n称为元素G的阶.,有限域上椭圆曲线,有限域上椭圆曲线y2x3+ax+b mod p p是奇素数,且4a3+27b20 mod p针对所有的0=x p，可以求出有效的y，得到曲线上的点(x,y)，其中x,y p。记为Ep(a,b)Ep(a,b)中也包括O加法公式:P+O=P如果P=(x,y)，则P+(x,-y)=O，(x,-y)点是P的负点，记为-P。而且(x,-y)也在Ep(a,b)中如果P=(x1,y1)，Q=(x2,y2)，则 P+Q=(x3,y3)为x3=2-x1-x2(mod p)y3=(x1-x3)-y1(mod p)其中，如果PQ，则=(y2-y1)/(x2
5、-x1)如果P=Q，则=(3x12+a)/(2y1),椭圆曲线密钥交换,双方选择Ep(a,b)以及Ep(a,b)的一个元素G,使得G的阶n是一个大素数A选择Xn,计算PA=XG,AB:PAB选择Yn,计算PB=YG,BA:PBA计算:X(PB)=XYGB计算:Y(PA)=YXG=XYG双方获得了一个共享会话密钥(XYG)不能抵抗replay攻击对中间人攻击的抵抗力远好于“Simple secret key distribution(Merkle的建议)”,椭圆曲线密钥交换的攻击,双方选择Ep(a,b)以及Ep(a,b)的一个元素G,使得G的阶n是一个大素数A选择Xn,计算PA=XG,AB:PA
6、E截获PA,选Z,计算PE=ZG,冒充AB:PEB选择Yn,计算PB=YG,BA:PBE截获PB,冒充BA:PEA计算:XZE=XZGB计算:YZE=YZGE计算:ZPA=ZXG,ZPB=ZYGE无法计算出XYGE永远必须实时截获并冒充转发,否则会被发现.,椭圆曲线加密解密,选择Ep(a,b)的元素G,使得G的阶n是一个大素数,秘密选择整数r.计算P=rG,公开(p,a,b,G,P),保密r.加密M:选择随机数k,C=kG,M+kP)如果k使得kG或者kP为O,则要重新选择k.解密C:(M+kP)-r(kG)=M+krG-rkG=M加密信息有扩张,椭圆曲线用于加密,找到一个难题：考虑等式Q=k
7、P，其中Q、P属于Ep(a,b)，kp已知k和P，计算Q，是容易的已知Q和P，计算k，是困难的选择Ep(a,b)的元素G,使得G的阶n是一个大素数G的阶是指满足nG=O的最小n值秘密选择整数r，计算P=rG，然后公开(p,a,b,G,P)，P为公钥保密r加密M：先把消息M变换成为Ep(a,b)中一个点Pm然后，选择随机数k，计算密文Cm=kG,Pm+kP)如果k使得kG或者kP为O，则要重新选择k.解密Cm:(Pm+kP)-r(kG)=Pm+krG-rkG=Pm加密信息有扩张,椭圆曲线密码的安全性,难点:从P和kP获得k对椭圆曲线研究的时间短椭圆曲线要求密钥长度短,速度快对比:ECC RSA,
8、2.子群成员问题,子群成员问题的例子(1),n,l是自然数,Zn*,的阶为l,:=1,2,l-1是Zn*的l阶子群,A要向B证明.开始时B检查n1,l1,Zn*,l=1,如果不是,停机;否则A,B重复执行下列步骤m次(m=|n|:n的二进制长度):A随机选择jZl*,计算=j mod n,把发给BB读出并检查是否Zn*,若不是,否定A的证明,停机;若是,从随机带读出一位i(0或1),把i发给A;A计算h=(j+ik)mod n,k=log mod n;把h发给BB读出h,验证是否 h i mod n容易知道B的所有计算量是|n|的多项式.上述协议也可以“并行”完成,子群成员问题的例子:完全性,
9、完全性:如果A遵守协议且,B是否以很大的概率接收A的证明结论?由于,因此h mod n=j+ik mod n(h=(j+ik)mod n)=jik mod n=i mod n(=j mod n,=k mod n)所以B以概率1接收A的证明.,子群成员问题的例子:合理性,合理性:如果,B是否以很小的概率接收A的证明?A随机选择jZl*,计算=j mod n,把发给BB读出,随机选择i(0或1)发给A;A计算h=(j+ik)mod n,k=log mod n;把h发给BB读出h,验证是否 h i mod n假如,由于Zn*,和最多只有一个属于,i为0或1决定B要验证哪一个(或),也决定A如何生成(
10、伪造),A无法事先知道,只好靠猜测,每次A只能有一半的机会猜中,m次后只有2-m机会.零知识性:可以证明该协议是完全零知识的.,DES,多重DES的应用,DES是否构成一个闭合群?任给K1,K2,是否存在K3,使得:EK1EK2=EK3Double DES Triple DES,DES:Expansion table,32|01 02 03 04|0504|05 06 07 08|0908|09 10 11 12|1312|13 14 15 16|1716|17 18 19 20|2120|21 22 23 24|2524|25 26 27 28|2928|29 30 31 32|01,DES
11、:S-box(S1),14 04 13 01 02 15 11 08 03 10 06 12 05 09 00 0700 15 07 04 14 02 13 01 10 06 12 11 09 05 03 0804 01 14 08 13 06 02 11 15 12 09 07 03 10 05 0015 12 08 02 04 09 01 07 05 11 03 14 10 00 06 13,DES:Permutation,16 07 20 21 29 12 28 1701 15 23 26 05 18 31 1002 08 24 14 32 27 03 0919 13 30 06 22 11 04 25,参考文献,离散数学 第3分册 代数结构与组合数学 屈婉玲编著 北京 北京大学出版社 1998 漫话群 邓应生编 出版发行项:北京 高等教育出版社 1989.10http:/2002.6.http:/2002.6,
