资源描述:
《群论在计算机安全领域中的应用》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、群论在计算机安全领域中的应用搜集整理:01047牛先芳信息管理系E-mail:rosalie@ccermail.net群论在计算机安全领域中的应用1.椭圆曲线密码2.子群成员问题3.DES1.椭圆曲线密码椭圆曲线密码介绍1985年Miller,Koblitz独立提出y2+axy+by=x3+cx2+dx+e曲线上的点连同无穷远点O的集合加法:若曲线三点在一条直线上,则其和为零倍数:一个点的两倍是它的切线与曲线的另一个交点问题阐释有限域上的椭圆曲线 设K表示一个有限域,E是域K上的椭圆曲线,则E是一个点的集合:E/K={(x,y)
2、y2+a1x
3、y+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是比因子分解难得多的问题。椭圆曲线密码示意图椭圆曲线上的加
4、法:P+Q=R椭圆曲线上一点的2倍:P+P=R.有限域上椭圆曲线有限域上椭圆曲线y2x3+ax+bmodpp是奇素数,且4a3+27b20modpy2+xyx3+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),如果PQ=(3x12+a)/2y1,如果P=QEp(a,b)椭圆曲线上的整数点在上述运算下成为一个交换群(Abelian群),记作Ep(a,b).关于
5、
6、Ep(a,b)
7、,有如下不等式:p+1-2p1/2
8、Ep(a,b)
9、p+1+2p1/2该不等式表明:
10、Ep(a,b)
11、~pG是Ep(a,b)的一个元素,使得nG=O的最小正整数n称为元素G的阶.有限域上椭圆曲线有限域上椭圆曲线y2x3+ax+bmodpp是奇素数,且4a3+27b20modp针对所有的0<=x
12、a,b)中如果P=(x1,y1),Q=(x2,y2),则P+Q=(x3,y3)为x3=2-x1-x2(modp)y3=(x1-x3)-y1(modp)其中,如果PQ,则=(y2-y1)/(x2-x1)如果P=Q,则=(3x12+a)/(2y1)椭圆曲线密钥交换双方选择Ep(a,b)以及Ep(a,b)的一个元素G,使得G的阶n是一个大素数A选择X13、YG)不能抵抗replay攻击对中间人攻击的抵抗力远好于“Simplesecretkeydistribution(Merkle的建议)”椭圆曲线密钥交换的攻击双方选择Ep(a,b)以及Ep(a,b)的一个元素G,使得G的阶n是一个大素数A选择X14、永远必须实时截获并冒充转发,否则会被发现.椭圆曲线加密解密选择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),k
15、小n值秘密选择整数r,计算P=rG,然后公开(p,a,b,G,P),P为公钥保密r加密M:先把消息M变换成为Ep(a,b)