群论在计算机安全领域中的应用

群论在计算机安全领域中的应用搜集整理:01047牛先芳信息管理系E-mail:[e-mail]群论在计算机安全领域中的应用1.椭圆曲线密码2.子群成员问题3.DES1.椭圆曲线密码椭圆曲线密码介绍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,a6x,yK}{O}其中O表示无穷远点。在E上定义‘+’运算，P+Q=R，R是过P、Q的直线与曲线的另一交点关于x轴的对称点，当P=Q时R是P点的切线与曲线的另一交点关于x轴的对称点。这样，(E,+)构成可换群(Abel群)，O是加法单位元(零元)。椭圆曲线离散对数问题ECDLP定义如下：给定定义在K上的椭圆曲线E，一个n阶的点PE/K，和点QE/K，如果存在l，确定整数l,0ln-1,Q=lP。前面已经提到，ECDLP是比因子分解难得多的问题。椭圆曲线密码示意图椭圆曲线上的加法:P+Q=R椭圆曲线上一点的2倍:P+P=R.有限域上椭圆曲线有限域上椭圆曲线y2x3+ax+bmodpp是奇素数,且4a3+27b20modpy2+xyx3+ax2+bmod2m加法公式: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),如果PQ=(3x12+a)/2y1,如果P=QEp(a,b)椭圆曲线上的整数点在上述运算下成为一个交换群(Abelian群),记作Ep(a,b).关于|Ep(a,b)|,有如下不等式:p+1-2p1/2|Ep(a,b)|p+1+2p1/2该不等式表明:|Ep(a,b)|~pG是Ep(a,b)的一个元素,使得nG=O的最小正整数n称为元素G的阶.有限域上椭圆曲线有限域上椭圆曲线y2x3+ax+bmodpp是奇素数,且4a3+27b20modp针对所有的0=xp，可以求出有效的y，得到曲线上的点(x,y)，其中x,yp。记为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(modp)y3=(x1-x3)-y1(modp)其中，如果PQ，则=(y2-y1)/(x2-x1)如果P=Q，则=(3x12+a)/(2y1)椭圆曲线密钥交换双方选择Ep(a,b)以及Ep(a,b)的一个元素G,使得G的阶n是一个大素数A选择Xn,计算PA=XG,AB:PAB选择Yn,计算PB=YG,BA:PBA计算:X(PB)=XYGB计算:Y(PA)=YXG=XYG双方获得了一个共享会话密钥(XYG)不能抵抗replay攻击对中间人攻击的抵抗力远好于“Simplesecretkeydistribution(Merkle的建议)”椭圆曲线密钥交换的攻击双方选择Ep(a,b)以及Ep(a,b)的一个元素G,使得G的阶n是一个大素数A选择Xn,计算PA=XG,AB:PAE截获PA,选Z,计算PE=ZG,冒充AB:PEB选择Yn,计算PB=YG,BA:PBE截获PB,冒充BA:PEA计算:XZE=XZGB计算:YZE=YZGE计算:ZPA=ZXG,ZPB=ZYGE无法计算出XYGE永远必须实时截获并冒充转发,否则会被发现.椭圆曲线加密解密选择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=kP，其中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对椭圆曲线研究的时间短椭圆曲线要求密钥长度短,速度快对比:ECCRSAKeysizeMIPS-Yrs1503.810102057.110182341.61028512310476821081024310111280110141536310162048310202.子群成员问题子群成员问题的例子(1)n,l是自然数,,Zn*,,的阶为l,:={1,,2,…,l-1}是Zn*的l阶子群,A要向B证明.开始时B检查n1,l1,,Zn*,,l=1,如果不是,停机;否则A,B重复执行下列步骤m次(m=|n|:n的二进制长度):A随机选择jZl*,计算=jmodn,把发给BB读出并检查是否Zn*,若不是,否定A的证明,停机;若是,从随机带读出一位i(0或1),把i发给A;A计算h=(j+ik)modn,k=logmodn;把h发给BB读出h,验证是否himodn容易知道B的所有计算量是|n|的多项式.上述协议也可以“并行”完成子群成员问题的例子:完全性完全性:如果A遵守协议且,B是否以很大的概率接收A的证明结论?由于,因此hmodn=j+ikmodn(∵h=(j+ik)modn)=jikmodn=imodn(∵=jmodn,=kmodn)所以B以概率1接收A的证明.子群成员问题的例子:合理性合理性:如果,B是否以很小的概率接收A的证明?A随机选择jZl*,计算=jmodn,把发给BB读出,随机选择i(0或1)发给A;A计算h=(j+ik)modn,k=logmodn;把h发给BB读出h,验证是否himodn假如,由于Zn*,和最多只有一个属于,i为0或1决定B要验证哪一个(或),也决定A如何生成(伪造),A无法事先知道,只好靠猜测,每次A只能有一半的机会猜中,m次后只有2-m机会.零知识性:可以证明该协议是完全零知识的.DES多重DES的应用DES是否构成一个闭合群?任给K1,K2,是否存在K3,使得:EK1•EK2=EK3DoubleDESTripleDESDES:Expansiontable32|01020304|0504|05060708|0908|09101112|1312|13141516|1716|17181920|2120|21222324|2524|25262728|2928|29303132|01DES:S-box(S1)14041301021511080310061205090007001507041402130110061211090503080401140813060211151209070310050015120802040901070511031410000613DES:Permutation1607202129122817011523260518311002082414322703091913300622110425参考文献离散数学第3分册代数结构与组合数学屈婉玲编著北京北京大学出版社1998漫话群邓应生编出版发行项:北京高等教育出版社1989.10