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

《群论在计算机安全领域中应用》由会员分享，可在线阅读，更多相关《群论在计算机安全领域中应用（24页珍藏版）》请在装配图网上搜索。

1、群论在计算机安全领域中应用 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望群论在计算机安全领域中的应用群论在计算机安全领域中的应用v1.椭圆曲线密码椭圆曲线密码v2.子群成员问题子群成员问题v3.DES1.椭圆曲线密码椭圆曲线密码椭圆曲线密码介绍椭圆曲线密码介绍l1985年年Miller,Koblitz 独立提出独立提出y2+axy+by=x3+cx2+dx+el曲线上的点连同无穷远点曲线上的点连同无穷远点O的集合的集合l加法加法:若曲线三点在一条直线上若曲线三点

2、在一条直线上,则其和为零则其和为零l倍数倍数:一个点的两倍是它的切线与曲线的另一一个点的两倍是它的切线与曲线的另一个交点个交点问题阐释问题阐释v有限域上的椭圆曲线有限域上的椭圆曲线 设设K表示一个有限域，表示一个有限域，E是域是域K上的椭圆曲线，则上的椭圆曲线，则E是一个点的集合：是一个点的集合：E/K=(x,y)|y2+a1xy+a3y=x3+a2x2+a4x+a6,a1,a3,a2,a4,a6 x,y K O 其中其中O表示无穷远点。表示无穷远点。在在E上定义上定义+运算，运算，P+Q=R，R是过是过P、Q的直线与曲线的另的直线与曲线的另一交点关于一交点关于x轴的对称点，当轴的对称点，当P

3、=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是比因子分解难得多的问题。是比因子分解难得多的问题。椭圆曲线密码示意图椭圆曲线密码示意图椭圆曲线上的加法椭圆曲线

4、上的加法:P+Q=R 椭圆曲线上一点的椭圆曲线上一点的2倍倍:P+P=R.有限域上椭圆曲线有限域上椭圆曲线有限域上椭圆曲线有限域上椭圆曲线y2 x3+ax+b mod p p是奇素数是奇素数,且且4a3+27b2 0 mod py2+xy x3+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),如果如果P Q =(3x12+a)/2y1,如果如果P=QEp(a,b)椭圆曲线上的整数点在上述运算下成

5、为一个交椭圆曲线上的整数点在上述运算下成为一个交换群换群(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)的一个元素的一个元素,使得使得nG=O的最小正的最小正整数整数n称为元素称为元素G的阶的阶.有限域上椭圆曲线有限域上椭圆曲线v有限域上椭圆曲线有限域上椭圆曲线y2 x3+ax+b mod p p是奇素数是奇素数,且且4a3+27b2 0 mod p针对所有的针对所有的0=x p，可以求出有效的，可以求出有效的y，得到曲线

6、，得到曲线上的点上的点(x,y)，其中，其中x,y p。记为。记为Ep(a,b)Ep(a,b)中也包括中也包括Ov加法公式加法公式: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)其中，其中，如果如果P Q，则，则 =(y2-y1)/(x2-x1)如果如果P=Q，则，则 =(3x12+a)/(2y1)椭圆曲线密钥交换椭圆曲线密钥

7、交换双方选择双方选择Ep(a,b)以及以及Ep(a,b)的一个元素的一个元素G,使得使得G的阶的阶n是一个大素数是一个大素数A选择选择Xn,计算计算PA=X G,AB:PAB选择选择Yn,计算计算PB=Y G,BA:PBA计算计算:X(PB)=X Y GB计算计算:Y(PA)=Y X G=X Y G双方获得了一个共享会话密钥双方获得了一个共享会话密钥(X Y G)l不能抵抗不能抵抗replay攻击攻击l对中间人攻击的抵抗力远好于对中间人攻击的抵抗力远好于“Simple secret key distribution(Merkle的建议的建议)”椭圆曲线密钥交换的攻击椭圆曲线密钥交换的攻击双方选

8、择双方选择Ep(a,b)以及以及Ep(a,b)的一个元素的一个元素G,使使得得G的阶的阶n是一个大素数是一个大素数A选择选择Xn,计算计算PA=X G,AB:PAE截获截获PA,选选Z,计算计算PE=Z G,冒充冒充AB:PEB选择选择Yn,计算计算PB=Y G,BA:PBE截获截获PB,冒充冒充BA:PEA计算计算:X ZE=X Z GB计算计算:Y ZE=Y Z GE计算计算:Z PA=Z X G,Z PB=Z Y GvE无法计算出无法计算出X Y GvE永远必须实时截获并冒充转发永远必须实时截获并冒充转发,否则会被发现否则会被发现.椭圆曲线加密解密椭圆曲线加密解密l选择选择Ep(a,b)

9、的元素的元素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加密信息有扩张加密信息有扩张椭圆曲线用于加密椭圆曲线用于加密v找到一个难题：找到一个难题：考虑等式考虑等式Q=kP，其中，其中Q、P属于属于Ep(a,b)，kp已知已知k和和P，计算，计算Q，是容易的，是容易的已知已知Q和和P，计算计算k，是困难的，是困难的v选

10、择选择Ep(a,b)的元素的元素G,使得使得G的阶的阶n是一个大素数是一个大素数G的阶是指满足的阶是指满足nG=O的最小的最小n值值v秘密选择整数秘密选择整数r，计算，计算P=rG，然后，然后公开公开(p,a,b,G,P)，P为公钥为公钥保密保密rv加密加密M：先把消息：先把消息M变换成为变换成为Ep(a,b)中一个点中一个点Pm然后，选择随机数然后，选择随机数k，计算密文，计算密文Cm=kG,Pm+kP)如果如果k使得使得kG或者或者kP为为O，则要重新选择，则要重新选择k.v解密解密Cm:(Pm+kP)-r(kG)=Pm+krG-rkG=Pmv加密信息有扩张加密信息有扩张椭圆曲线密码的安全

11、性椭圆曲线密码的安全性难点难点:从从P和和kP获得获得k对椭圆曲线研究的时间短对椭圆曲线研究的时间短椭圆曲线要求密钥长度短椭圆曲线要求密钥长度短,速度快速度快对比对比:ECC RSAKey sizeMIPS-Yrs1503.8 10102057.1 10182341.6 10285123 1047682 10810243 101112801 101415363 101620483 10202.子群成员问题子群成员问题的例子子群成员问题的例子(1)n,l是自然数是自然数,Zn*,的阶为的阶为l,:=1,2,l-1是是Zn*的的l阶阶子子群群,A要要向向B证证明明.开开始始时时B检检查查n 1,l

12、 1,Zn*,l=1,如如果果不不是是,停停机机;否否则则A,B重重复复执执行行下下列列步骤步骤m次次(m=|n|:n的的二进制长度二进制长度):A随机选择随机选择j Zl*,计算计算=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 nt容易知道容易知道B的所有计算量是的所有计算量是|n|的多项式的多项式.t上述协议也可以上

13、述协议也可以“并行并行”完成完成子群成员问题的例子子群成员问题的例子:完全性完全性完完全全性性:如如果果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随机选择随机选择j Zl*,计算计算=j mod n,把把 发

14、给发给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如如何何生生成成(伪伪造造),A无无法法事事先先知知道道,只只好好靠靠猜猜测测,每每次次A只只能能有有一一半半的的机机会会猜猜中中,m次次后后只只有有2-m机会机会.零知识性零知识性:可以证明该协议是完全零知识的可以证明该协议是完全零知识的.DES多重多重DES的应用的应用

15、uDES是否构成一个闭合群是否构成一个闭合群?任给任给K1,K2,是否存在是否存在K3,使得使得:EK1EK2=EK3uDouble DES uTriple DES DES:Expansion table32|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|01DES:S-box(S1)14 04 13 01 02 15 11 08 03 10 06 12 05 09 00 0700

16、 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 13DES:Permutation16 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参考文献v离散数学离散数学 第第3分册分册 代数结构与组合数学代数结构与组合数学 屈婉屈婉玲编著玲编著 北京北京 北京大学出版社北京大学出版社 1998 v漫话群漫话群 邓应生编邓应生编 出版发行项:北京北京 高等教育高等教育出版社出版社 1989.10vhttp:/ 2002.6.vhttp:/