椭圆曲线密码算法.ppt

《椭圆曲线密码算法.ppt》由会员分享，可在线阅读，更多相关《椭圆曲线密码算法.ppt（44页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、椭圆曲线密码算法(ECC)n椭圆曲线是由Neil Koblitz(Koblitz,1985)和Victor Miller(Miller,1985)两位学者分别于1985年首先提出n大多数的椭圆曲线密码系统是在模p或F2n下运算。此密码系统仍是存有RSA或ElGamal常见的弱点(e.g.同模数攻击、低指数攻击)。nRSA与ElGamal系统中需要使用长度为 1024位的模数，才能达到足够的安全等 级n而ECC只需使用长度为160位的模数即可，且传送密文或签章所需频宽较少，并已正式列入IEEE 1363标准n椭圆曲线密码系统基于椭圆曲线离散对数问题(Elliptic Curve Discrete

2、 Logarithm Problem,ECDLP)。n即在有限域K之下，给定椭圆曲线E上的两相异点P及Q，其中当点P的秩(order)若够大时(大于160位)，要找出一整数l使得Q=lP是很难的计算难题。n在实数域中，椭圆曲线可定义成所有满足方程式 的点(x,y)所构成的集合。若方程式没有重复的因式或 ，则 能成为群(group)。n例如，椭圆曲线 的图形如图1-1所示。若 ，则此曲线将会形成退化(某些数的逆元素(inverse)将不存在)。n椭圆曲线 的图形如图1-1所示。n椭圆曲线密码系统在模p(或Fp)下定义为椭圆曲线 其中 n模F2n下定义为椭圆曲线 其中 ，此曲线称为nonsuper

3、-singular。n椭圆曲线有一个特殊的点，记为O，它并不在椭圆曲线E上，此点称为无穷远点(the point at infinity)n两个相异的点相加：假设P和Q是椭圆曲线上两个相异的点，而且P不等于-Q。若P+Q=R，则点R是经过P、Q两点的直线与椭圆曲线相交之唯一交点的负点。如图1-2所示。n双倍的点：令P+P=2P，则点2P是经过P的切线与椭圆曲线相交之唯一交点的负点。如图1-3所示。椭圆曲线运算规则椭圆曲线运算规则 n椭圆曲线在模椭圆曲线在模p下的运算规则下的运算规则 加法规则：(i)对所有的点 PE(Fp)，则P+O=O+P，(ii)P+(-P)=O(iii)(ii)令 及 且

4、 ，则 ，其中 (iii)如果 ，则对所有的点 而言，n乘法规则：如果 ，则对所有的点 而言，kP=P+P+P(k个P相加)如果 ，则对所有的点 而 言，n例子例子1：有限域F23之下，点 是椭圆曲线 的生成数。请计算2P和3P的值 P=(0,1)2P=(13,13)3P=(5,5)4P=(3,15)5P=(6,17)6P=(19,2)7P=(17,9)8P=(18,0)9P=(17,14)10P=(19,21)11P=(6,6)12P=(3,8)13P=(5,18)14P=(13,10)15P=(0,22)请在坐标上画出各个点，并观察图像特点n注：其实还要加上一个无穷远点，故E上的点共有16

5、个，点P的秩n=16。n例例2：在有限域F23之下，取椭圆曲线 上的两点 及 若 则 R=?解：n例例3 3：条件同：条件同例2，若 ，则R=?解：椭圆曲线在椭圆曲线在 下的运算规则下的运算规则 n加法规则：(i)对所有的点 则 ，(ii)令 及 ，且 。则 ，其x3,y3分别为：(iii)如果 ，则对所有的点 而言，n例子例子4：在有限域 之下，取椭圆曲线 y2+xy=x3+g8x2+g2 上的两点P=(g3,g9)及Q=(g,g5)，其中 g=(0010)为 的生成数，且不可约多项式为 f(x)=x4+x+1。若 P+Q=R=(x3,y3)则R=?解：n注：g的乘幂如下n例5 条件同例4，

6、若 则R=?解：椭圆曲线密钥生成n令E是FP上的椭圆曲线，P是E(FP)上的点，设P的阶是素数n，则集合 =,P,2P,3P,(n-1)P 是由P生成的椭圆曲线循环子群。n素数p，椭圆曲线方程E，点P和阶n构成公开参数组。n私钥在区间1,n-1内随机选择的正整数d，相应的公钥是Q=dP。n由公开参数组和公钥Q求私钥d的问题是椭圆曲线离散对数问题(ECDLP)密钥对生成 输入：椭圆曲线参数组(p,E,P,n)输出：公钥Q和私钥d1.选择d1，n2.计算Q=dP3.返回(Q,d)基本椭圆曲线加密输入：椭圆曲线参数组(p,E,P,n)，公钥Q，明文m输出：密文(C1,C2)1.将明文m表示为E(FP)上的点M2.选择k1，n3.计算C1=kP4.计算C2=M+kQ5.返回(C1,C2)基本椭圆曲线解密输入：椭圆曲线参数组(p,E,P,n)，私钥d，密文(C1,C2)输出：明文m1.计算M=?，并从点M取出明文m2.返回(m)