第04章椭圆曲线密码体制ECC.ppt
《第04章椭圆曲线密码体制ECC.ppt》由会员分享,可在线阅读,更多相关《第04章椭圆曲线密码体制ECC.ppt(24页珍藏版)》请在三一文库上搜索。
1、椭圆曲线密码(ECC)体制,一般椭圆曲线 有限域上的椭圆曲线 椭圆曲线密码算法 椭圆曲线密码体制的安全性,ELGamal密码体制能够在任何离散对数难处理的有限群中实现。我们已经使用了乘法群Zp*,但其他群也是合适的候选者,如椭圆曲线群。 椭圆曲线在代数学和几何学上已广泛研究了150多年之久,有丰富而深厚的理论积累。椭圆曲线密码体制(Ellipse Curve Cryptosystem,ECC)在l 985年由Koblitz和Miller提出,不过一直没有像RSA等密码系统一样受到重视。纵观目前的发展趋势,椭圆曲线已经逐渐被采用,很可能是一个重要的发展方向。,椭圆曲线并非椭圆,这么命名是因为它们
2、是由三次方程描述的,而这些三次方程类似于计算椭圆周长的方程。一般的,描述椭圆曲线方程的形式是 y2 + axy + by = x3 + cx2 + dx + e 其中a、b、c、d和e是满足一些简单条件的实数 一般来说,椭圆曲线还包含了一个特殊的点,即称为无穷远点(Point at Infinity)或零点(Zero Point)的O。,4.4.1 一般椭圆曲线,对于椭圆曲线上的点可以定义一种形式的加法:如果一个椭圆曲线上的三个点处于一条直线上,那么它们的和为O。从这个定义可以导出椭圆曲线上点的加法法则。 (1) O是加法的单位元,因而OO;对于椭圆曲线上的任何一点P,有P+OP。 (2) 一
3、条与x轴垂直的线和曲线相交于两个x坐标相同的点P1=(x,y)和P2(x,y),同时它也和曲线相交于无穷远点,因此P1+P2+OO。因而一个点的负值是与其有着相同x坐标和相反的y坐标的点,如图4.1(a)所示。,(3)要对具有不同x坐标的两个点Q与R进行相加,先在它们之间画一条直线并求出第三个交点P1。容易看出这种交点是惟一的。 注意到Q+R+P1O,有Q+RP。 特别地,当Q=R时,相当于对一个点Q加倍,只需画出一条切线并求出另一个交点S,那么Q+Q=2Q=S。 显然,根据定义,此类加法满足交换率和结合率.而一个点的倍乘定义为 nPP+P+P+P,4.4.2 有限域上的椭圆曲线,密码学中关心
4、的是有限域F上的椭园曲线。讨论比较多的是素域Fp上的椭圆曲线,这里P是一个素数。选择两个小于P的非负整数a和b满足 4a3 + 27b2 (mod p) 0 用Ep(a,b)表示如下模p的椭圆群中的点(或如下有限域Fp上的椭圆曲线的点),再加上一个无穷远点O。 设(x,y)是Ep(a,b)中的点,x和y是小于p的非负整数,则有如下椭圆曲线方程: y2 x3 + ax + b (mod p),如取p23,a=b=l,有 4*13 + 27 * 12 (mod 23 ) 8 0, 则y2=x3 + x +1 是椭圆曲线。因此E23(1,1)是一个模23的椭圆群。产生E23 (1,1)是中点的过程如
5、下: (1) 对x=0,1,2,p-1, 计算x3 + x +1 (mod p); (2)对于上一步骤得到的每个结果确定它是否有一个模P的平方根,如果没有,则E23 (1,1)中没有具有与该结果相应的x坐标的点。如果有,就有两个平方根y和py,从而点(x,y)和(x,py)是E23 (1,1)中的点(特别情况下,如果结果是0,只有一个点(x,0)。,椭圆曲线E23(1,1)上的点,Ep(a,b)上的加法规则,P十OP; 如果P(x , y),则P + ( x , y) =O,点(x,y)是P的加法逆元,记为 P; 如果P(x1,y1),Q(x2,y2),并且PQ,则P + Q = (x3,y3
6、)由下列规则确定: x32 x1 x2 ( mod p ) y3 ( x1 x3) y1 (mod p ) 其中: (y2-y1)/(x2x1) 如果PQ = (3x12a)/2y1 如果 P=Q,例子:,考虑P=(3,10) , Q=(9,7) 则: =(710)/(93)=3/6=1/2=11 mod 23 x3=11239=109 17 mod 23 y3=11(3(6)10=89 =20 mod 23 因而P+Q=(17,20). 计算2P: =(3(32)+1)/(2*10)=5/20=1/4=6 mod 23 x3=6233=30=7 mod 23 y3=6(37)10=34= 1
7、2 mod 23 因此 2P=(7,12),椭圆曲线群中的离散对数也属于难解问题。与通常理解的对数概念不同,由于椭圆曲线群中的运算是加法,加法的倍数对应于原来乘法的指数,因而椭圆曲线群中的离散对数问题是指已知群中的Q和R,求解方程: RkQ 中k值的问题。,对基于F23的椭圆群y2x3 + 9x + 17,求R=(4,5)对于Q=(16,5)的离散对数,最直接的方法就是计算Q的倍数,直到找到R。 Q(16,5),2Q=(20,20),3Q(14,14), 4Q=(19,20),5Q(13,10), 6Q(7,3), 7Q(8,7),8Q(12,17),9Q(4,5) 因此k关于Q的离散对数是9
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 04 椭圆 曲线 密码 体制 ECC
链接地址:https://www.31doc.com/p-3417393.html