椭圆曲线密码学知识简介ppt课件

《椭圆曲线密码学知识简介ppt课件》由会员分享，可在线阅读，更多相关《椭圆曲线密码学知识简介ppt课件（22页珍藏版）》请在装配图网上搜索。

1、第七章第七章 椭圆曲线密码学椭圆曲线密码学1 有关的根本概念(1)无穷远元素无穷远点，无穷远直线 平面上恣意两相异直线的位置关系有相交和平行两种。引入无穷远点，是两种不同关系一致。ABL1，L2L1，直线AP由AB起绕A点依逆时针方向转动，P为AP与L1的交点。L2L1PBAPQQ=BAP/2 AP L2可想象L1上有一点P，它为L2和L1的交点，称之为无穷远点。直线L1上的无穷远点只能有一个。由于过A点只能有一条平行于L1的直线L2，而两直线的交点只能有一个。结论：1*.平面上一组相互平行的直线，有公共的无穷远点。为与无穷远点相区别，把原来平面上的点叫做平常点2*.平面上任何相交的两直线L1

2、,L2有不同的无穷远点。缘由：假设否，那么L1和L2有公共的无穷远点P，那么过两相异点A和P 有相异两直线，与公理相矛盾。3*.全体无穷远点构成一条无穷远直线。注：欧式平面添加上无穷远点和无穷远直线，自然构成射影平面。(2)齐次坐标 解析几何中引入坐标系，用代数的方法研讨欧氏空间。这样的坐标法也可推行至摄影平面上，建立平面摄影坐标系。平面上两相异直线L1,L2，其方程分别为：L1:a1x+b1y+c1=0 L2:a2x+b2y+c2=0AL1L2P其中a1,b1不同时为0；a2,b2也不同时为0。设 D=a1 b1 Dx=b1 c1 Dy=c1 a1 a2 b2 b2 c2 c2 a2假设D0

3、，那么两直线L1,L2相交于一平常点P(x,y)，其坐标为x=Dx/D，y=Dy/D.这组解可表为：x/Dx=y/Dy=1/D(商定：分母Dx，Dy有为0时，对应的分子也要为0上述表示可笼统为Dx，Dy，D).假设 D=0，那么L1L2，此时L1和L2交于一个无穷远点P。这个点P可用过原点O且平行于L2的一条直线L来指出他的方向，而这条直线L的方程就是：a2x+b2y=0.为把平常点和无穷远点的坐标一致同来，把点的坐标用X，Y，Z)表示，X，Y，Z不能同时为0，且对平常点x，y)来说，有Z0，x=X/Z，y=Y/Z，于是有：i.e.X/Dx=Y/Dy=Z/D，有更好的坐标笼统，X,Y,Z),这

4、样对于无穷远点那么有Z=0，也成立。注：a).假设实数p0，那么(pX,pY,pZ)与X,Y,Z)表示同一个点。本质上用X:Y:Z)表示。3个分量中，只需两个是独立的，具有这种特征的坐标就叫齐次坐标。i.e.DDZYDZXyx1b).设有欧氏直线L，它在平面直角坐标系Oxy上的方程为：ax+by+c=0 那么L上任一平常点(x,y)的齐次坐标为(X,Y,Z)，Z0，代入得：aX+bY+cZ=0 给L添加的无穷远点的坐标(X,Y,Z)应满足aX+bY=0，Z=0;平面上无穷远直线方程自然为：Z=0 !(3)恣意域上的椭圆曲线K为域，K上的摄影平面P2(K)是一些等价类的集合(X:Y:Z)。思索下

5、面的Weierstrass方程(次数为3的齐次方程)：Y2Z+a1XYZ+a3YZ2=X3+a2X2z+a4XZ2+a6Z3(其中系数aiK，或aiK为K的代数闭域Weierstrass方程被称为光滑的或非奇特的是指对一切适宜以下方程的射影点P=(X:Y:Z)P2(K)来说，F(X,Y,Z)=Y2Z+a1XYZ+a3YZ2-X3-a2X2Z-a4XZ2-a6Z3=0在P点的三个偏导数 之中至少有一个不为 0假设否称这个方程为奇特的。椭圆曲线E的定义：椭圆曲线E是一个光滑的Weierstrass方程在P2(K)中的全部解集合。Y2Z+a1XYZ+a3YZ2=X3+a2X2Z+a4XZ2+a6Z3

6、注：a)在椭圆曲线E上恰有一个点，称之为无穷远点。即(0:1:0)用表示。ZFYFXF,b)可用非齐次坐标的方式来表示椭圆曲线的Weierstrass方程:设 x=X/Z，y=Y/Z，于是原方程转化为：y2+a1xy+a3y=x3+a2x2+a4x+a6 (1)此时，椭圆曲线E就是方程1)在射影平面P2(K)上的全部平常点解，外加一个无穷远点组成的集合。c)假设a1,a2,a2,a4,a6K，此时椭圆曲线E被称为定义在K上，用E/K表示。假设E能被限定在K上，那么E的K有理点集合表示为E(K)，它为E中的全体有理坐标点的集合外加无穷远点.(4)实域R上的椭圆曲线 设K=R，此时的椭圆曲线可表为

7、平面上的通常曲线上的点，外加无穷远点。实域R上椭圆曲线的点的加法运算法那么：设L P2(R)为一条直线。由于E的方程是三次的，所以L可与E在P2(R)恰有三个交点，记为P,Q,R留意：假设L与E相切，那么P,Q,R可以不是相异的。按下述方式定义E上运算：设P,Q E，L为联接P,Q的直线假设P=Q，那么L取过P点的切线；设R为L与E的另一个交点；再取衔接R与无穷远点的直线L。那么L与E的另一个交点定义为P Q。PQP=QLLLL(PQ)R=TT=(P=Q=R)PQPQRRT 上页的实践图像为椭圆曲线y2=x3-x的普通化。来自对详细曲线的笼统。对运算更详细一些：设 P=(x1,y1)，Q=(x

8、2,y2)，PQ=(x3,y3),由PQ的定义，设y=x+为经过P,Q两点直线L的方程，可算出：=(y2-y1)/(x2-x1),=y1-x1 易见，直线L上的一个点x,x+)是在椭圆曲线E上，当且仅当(x+)2=x3 x。PQ=(x1,y1)(x2,y2)=(x3,y3)=(x3,-(x3+)其中，x3=2-x1-x2=(y2-y1)/(x2-x1)2-x1-x2；y3=-y1+(y2-y1)/(x2-x1)(x1-x3)当P=Q时：PQ=x3，y3算得：x3=(3x12-1)/2y1)2-2x1;y3=-y1+(3x12-1)/2y1)(x1-x3)注：注：a)假设直线假设直线L与与E相交

9、与三点相交与三点P,Q,R(不一定相异，那么不一定相异，那么(PQ)R=(从图中可见。从图中可见。b)任给任给PE,P =P (此时设此时设Q=，易见，易见L=L)c)任给任给P,QE有：有：P Q=Q Pd)设设PE，那么可以找到，那么可以找到-PE使使P -P=e)任给任给P,Q,RE，有，有(P Q)R=P(Q R)综上所述，知综上所述，知E对对 运算构成一个运算构成一个Abel群。群。f)上述规那么可开辟到恣意域上，特别是有限域上。假上述规那么可开辟到恣意域上，特别是有限域上。假定定 椭圆曲线是定义在有限域椭圆曲线是定义在有限域Fq上上q=pm)，那么，那么 E(Fq)=(x,y)Fq

10、Fq|y2+a1xy+a3y=x3+a2x2+a4x+a6 它对它对“构成一个群，为构成一个群，为Abel群。群。2 有限域上椭圆曲线的有限域上椭圆曲线的运算运算 令Fq表示q个元素的有限域，用E(Fq)表示定义在Fq上的一个椭圆曲线E。定理1.(Hass定理)E(Fq)的点数用#E(Fq)表示，那么|#E(Fq)-q-1|2q1/2(1)Fp素域，p为素数上椭圆曲线 令p3，a,bFp，满足4a3+27b20，由参数a和b定义的Fp上的一个椭圆曲线方程为：y2=x3+ax+b (2)它的一切解(x,y)，(xFp，yFp)，连同一个称为“无穷远点记为的元素组成的集合记为E(Fp)，由Hass

11、定理知：知：p+1-2p1/2#E(Fp)p+1+2p1/2 集合集合E(Fp)对应下面的加法规那么，且对加法对应下面的加法规那么，且对加法构成构成一个一个Abel群：群：(i)=单位元素单位元素(ii)(x,y)=(x,y),任给任给(x,y)E(Fp)(iii)(x,y)(x,-y)=，任给，任给(x,y)E(Fp),即点即点(x,y)的逆元的逆元 为为(x,-y).(iv)令令(x1,y1),(x2,y2)为为E(Fp)中非互逆元，那么中非互逆元，那么 (x1,y1)(x2,y2)=(x3,y3),其中其中 x3=2-2x1，y3=(x1-x3)-y1 且且=(y2-y1)/(x2-x1

12、)3(v)倍点运算规那么倍点运算规那么 设设(x1,y1)E(Fp),y10，那么，那么2(x1,y1)=(x3,y3)，其中，其中 x3=2-2x1,y3=(x1-x3)-y1 这里=(3x12+a)/(2y1)(4)注：假设#E(Fp)=p+1，曲线E(Fp)称为超奇特的，否那么称为 非超奇特的。例子：F23上的一个椭圆曲线 令y2=x3+x+1是F23上的一个方程(a=b=1)，那么该椭圆曲线方程在F23上的解为(y2=x3+x+1的点)：(0,1)，(0,22)，(1,7)，(1,16)，(3,10)，(3,13)，(4,0)，(5,4)，(5,19)，(6,4)，(6,19)，(7,

13、11)，(7,12)，(9,7)，(9,16)，(11,3)，(11,20)，(12,4)，(12,19)，(13,7)，(13,16)，(17,3)，(17,20)，(18,3)，(18,20)，(19,5)，(19,18)；。群E(F23)有28个点包括无穷远点。(2)F2m上的椭圆曲线上的椭圆曲线 F2m上由参数a,bF2m，b0定义的一个非超奇特椭圆曲线E(F2m)是方程 y2+xy=x3+ax2+b (5)的解集合(x,y)，其中x,yF2m，连同。E(F2m)的加法规那么如下：(i)+=(ii)任给(x,y)E(F2m)，那么(x,y)=(x,y)(iii)任给(x,y)E(F2m

14、)，那么(x,y)+(x,x+y)=，即点(x,y)的逆为(x,x+y).(iv)两个相异且不互逆的点的加法规那么：令(x1,y1),(x2,y2)E(F2m)且有x1x2那么 (x1,y1)(x2,y2)=(x3,y3)，其中，其中 x3=2+x1+x2+a；y3=(x1+x3)+x3+y1.其中其中 =(y2+y1)/(x2+x1)(v)倍点规那么倍点规那么令令(x1,y1)E(F2m)，其中，其中x10。那么。那么 2(x1,y1)=(x3,y3)，其中，其中 x3=2+a,y3=x12+(+1)x3,这里这里=(x1+y1/x1)易见，群易见，群E(F2m)为为Abel群。群。例：例：

15、F24上的一个椭圆曲线上的一个椭圆曲线f(x)=x4+x+1为为F2上的一个不可约多项式，易见上的一个不可约多项式，易见 F24=F2x/(f(x)=(k0,k1,k2,k3)|(k0,k1,k2,k3)=k0+k1+k22+k33，为为f(x)的零点，的零点，kiF2假定假定F24上的非超奇特椭圆曲线有下述方程定义：上的非超奇特椭圆曲线有下述方程定义：y2+xy=x3+4x2+1，留意，留意f()=0。方程应表为：方程应表为：(1000)y2+(1000)xy=(1000)x3+(1100)x2+(1000)3 椭圆曲线密码体制椭圆曲线密码体制 1985年，N.Koblitz和V.Mille

16、r分别独立提出了椭圆曲线密码体制(ECC)，其根据就是定义在椭圆曲线点群上的离散对数问题的难解性。1知E(Fq)对点的“运算构成一个Abel群设pE(Fq)，假设p的周期很大，即使 p p p=(共有 t个p相加 成立的最小正整数 t，希望 t 很大。(t=p的周期，表示为(p)=t)。并且对QE(Fq)，定有某个正整数m使 Q=mp=p p (共有t个p相加)定义 m=pQ (m为以p为底Q的对数。椭圆曲线上的点构成的群E(Fq)，相关它的离散对数问题是难处置的。2 建立椭圆曲线密码体制 选取基域Fq，Fq的椭圆曲线详细给定为确定的方式。在E(Fq)中选一个周期很大的点，如选了一个点P=(xp,yp)，它的周期为一个大的素数n，记(P)=n(素数)。留意：在这个密码体制中，详细的曲线及点P和它的n都是公开信息。密码体制的方式采用EIGamal体制，是完全类比过来。v)计算点计算点(x2,y2):=kQ,假设假设x2=0,那么回到第那么回到第iii)步步.)计算C:=mx2)传送加密数据(x1,y1,C)给Bobb)Bob的解密过程Bob收到Alice的密文(x1,y1,C)后，执行 i)运用私钥d，计算点(x2，y2):=d(x1,y1)，再计算Fq中x2-1=?Ii)经过计算m:=Cx2-1，恢复出明文数据m。