椭圆曲线密码体制及其应用.pdf

《椭圆曲线密码体制及其应用.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、椭圆曲线密码体制及其应用1985年，Koblitz和Miller相互独立地提出了在密码学中应用椭圆曲线(EllipticalCurve)的思想，使其成为构造公开密钥密码体制一个有力的工具。椭圆曲线密码体制为公钥机制，提供如同ElGamal一样的功能。但是，它的安全性依赖不同的困难问题，也就是椭圆曲线离散对数问题(ECDLP)。一、椭圆曲线概念1、实数域上的椭圆曲线椭圆曲线并非椭圆，之所以称为椭圆曲线是因为它的曲线方程与计算椭圆周长的方程类似。椭圆曲线的方程是的三次方程：y2+axy+by=x3+cx2+dx+e(1)其中a，b，c，d，e是满足某些简单条件实数

2、。椭圆曲线：232Ex={(,)

3、yya++=+++∪xybyxcxdxe}{}∞这里∞为无穷远点.一条椭圆曲线E指的是由韦尔斯特拉斯(Weierstrass)方程：y2+axy+by=x3+cx2+dx+e所确定的平面曲线，它是由方程的全体解(x,y)再加上一个无穷远点∞构成的集合。其中系数a，b，c，d，e是满足一些简单条件的实数。亦即：椭圆曲线232Ex={(,)

4、yya++=+++∪xybyxcxdxe}{}∞上面的方程可经适当的变换化为y2≡x3+ax+b由它确定的椭圆曲线常记为E(a,b)，简记为E。当4a3+27b2≠0时．称E(a,b)是一条非

5、奇异椭圆曲线。2实域上的椭圆曲线（典型的椭圆曲线）2323(a)E:y=x−x；(b)E:y=x+73123.椭圆曲线上的加法运算（几何方法）椭圆曲线上成一直线的三个点，其和为O。∴P+Q+(−R)=OP+Q=R加法運算：P+Q的结果R为“取P,Q两点的直线与椭圆曲线相交之唯一交点的负点”。3.椭圆曲线上的加法运算（几何方法）倍数运算：P+P=2P的结果为“点2P是经过P点的切线与椭圆曲线相交之唯一交点的负点”。依此类推…kP=P+P+…+P(k個P相加)以上定义的加法具有加法运算的一般性质，如交换律、结合律等。3加法法则23例.假定椭圆曲线为:Ey=x+=7

6、3。令P(29)，和，Q(==310)，求RPQR+,2通过PQ和的直线是Lyx=+7解23代入的方程得到：Ex(7+)=+x73因此，椭圆曲线与直线相交于第三点有x=−4。由于yx=+73(，我们有y=。因此，R=−−4，3)。2Ey的方程求导数得到：23dy=xdx，因此2dy3x

7、

8、==−8xx=−44=−dxyy=−332y=−过点的切线方程：Ry=−+−8(x4)323代入的方程得Ex(8(4)3)−+−=+x73有xy=72，=−611。因此，2R=(72611)，。显然(1)PP+∞=。(2)(x，，yxy)(+−=)∞定义.()(−=x，yxy

9、，)−。两个点相减P−QP，也可以简化为相加+−()Q(3)PQG++=∞⇔PQG，，共线。加法运算性质(1)结合律：(PQRPQR++=++)()(2):交换律PQQP+=+(3)椭圆曲线上的点构成阿贝尔群.E∞（记O）是加法单位元。二、有限域上的椭圆曲线密码中普遍采用的是有限域上的椭圆曲线，有限域上的椭圆曲线是指曲线方程定义式中，所有系数都是某一有限域GF(p)中的元素（其中p为一大素数）。其中最为常用的是由方程y2≡x3+ax+b(modp)(a,b∈GF(p),4a3+27b2(modp)≠0)定义的曲线。我们把该椭圆曲线记为E(a,b)，简单记为E.

10、该椭圆p曲线只有有限个点.23例如，若E是F7上椭圆曲线yxx=++24则E(a,b)上的点是7E(2,4){,(0,2),(0,5),(1,0),(2,3),(2,4),(3,3),(3,4),=O7(6,1),(6,6)}一般来说，中的点由以下方式产生：Ep①对每一x(0≤x

11、群的阶（E的点的个数）:pp#(,)Eab=+−≤p1,2ttpp•如果#E是素数，则该群是循环群并且∃PEabEabk∈=pp(,):(,){P:0≤k#E≤}•如果#E有素因子,则存在一个循环子群。例:GF(23)上椭圆曲线p=2323Ey:4=++xx#2E=⇒9该群是一个循环群E上的点由下列点以及Ο组成:P=(0,2)2P=(13,12)3P=(11,9)4P=(1,12)5P=(7,20)6P=(9,11)7P=(15,9)8P=(14,5)9P=(4,7)10P=(22,5)11P=(10,5)12P=(17,9)13P=(8,15)14P=(18

12、,9)15P=(18,14)16P=(