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

《群论在计算机安全领域中的应用》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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.有限域上椭圆曲线有限域上椭圆曲线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).关于

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的阶.有限域上椭圆曲线有限域上椭圆曲线y2x3+ax+bmodpp是奇素数,且4a3+27b20modp针对所有的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)其中，如果PQ，则=(y2-y1)/(x2-x1)如果P=Q，则=(3x12+a)/(2y1)椭圆曲线密钥交换双方选择Ep(a,b)以及Ep(a,b)的一个元素G,使得G的阶n是一个大素数A选择X

13、YG)不能抵抗replay攻击对中间人攻击的抵抗力远好于“Simplesecretkeydistribution(Merkle的建议)”椭圆曲线密钥交换的攻击双方选择Ep(a,b)以及Ep(a,b)的一个元素G,使得G的阶n是一个大素数A选择X

14、永远必须实时截获并冒充转发,否则会被发现.椭圆曲线加密解密选择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)