第10章--椭圆曲线密码学

第10章椭圆曲线密码学椭圆曲线密码学是由美国学者NeilKoblitz与VictorMiller在1985年各自独立创建起来的。RSA与ElGamal加密体制中,如果使用长度为1024比特的模数才可以达到基本的安全等级，那么对于椭圆曲线(ECC)加密体制来说，按目前公开的密码攻击方法，只要使用长度为160比特的模数，就可以达到这个安全等级。参见：有关的基本概念(1)无穷远元素（无穷远点，无穷远直线）平面上任意两相异直线的位置关系有相交和平行两种。引入无穷远点，是两种不同关系统一。AB⊥L1，L2∥L1，直线AP由AB起绕A点依逆时针方向转动，P为AP与L1的交点。L2L1P∞BAP∠BAP→π/2AP→L2可以设想L1上有一点P∞，它为L2和L1的交点，被称之为无无穷远点穷远点。●注意:直线L1上的无穷远点只能有一个（因为过A点只能有一条平行于L1的直线L2，而两直线的交点只能有一个。）结论：1*.平面上一组相互平行的直线，有公共的无穷远点。（为与无穷远点相区别，把原来平面上的点叫做平常点平常点）2*.平面上相交于点A的两直线L1,L2有不同的无穷远点。原因：若否，则L1和L2有公共的无穷远点P∞，则过两相异点A和P∞有相异两直线，与几何公理相矛盾。3*.全体无穷远点构成一条无穷远直线。注注：欧式平面添加上无穷远点和无穷远直线，自然构成射影平面影平面。(2)齐次坐标解析几何中引入坐标系，用代数的方法研究欧氏空间。这样的坐标法也可推广至射影平面上，建立平面射影坐标系,(齐次坐标系).平面上两相异直线L1,L2，其方程分别为：L1:a1x+b1y+c1=0L2:a2x+b2y+c2=0AL1L2P∞其中a1,b1不同时为0；a2,b2也不同时为0。设D=a1b1Dx=b1c1Dy=c1a1a2b2b2c2c2a2若D≠0，则两直线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，则L1∥L2，此时L1和L2交于一个无穷远点P∞.这个点P∞可用过原点O且平行于L2的一条直线L来指出他的方向，而这条直线L的方程就是：a2x+b2y=0.为把平常点和无穷远点的坐标统一起来，把点的坐标用（X，Y，Z)表示，X，Y，Z不能同时为0，且对平常点（x，y)来说，有Z≠0，x=X/Z，y=Y/Z，于是有：相当于说相当于说X/Dx=Y/Dy=Z/D，有更好的坐标抽象(X,Y,Z);Z=0时它表示无穷远点。注解1：实数c≠0，则(cX,cY,cZ)为一等价类,代表元为（X,Y,Z)。实质上用（X:Y:Z)表示的3个分量中，只有两个是独立的，具有这种特征的坐标就叫齐次坐标齐次坐标。.DDZYDZXyx1==例1：求点（1,2）在新的坐标体系下的坐标。解：∵X/Z=1，Y/Z=2（Z≠0）∴X=Z，Y=2Z∴坐标为（Z:2Z:Z），Z≠0。即（1:2:1）（2:4:2）等形如（ｔ:2t:t），其中t≠0的坐标，都是（1,2）在新的坐标体系下的坐标,用代表元（1:2:1)表示即可.例2：求平行线L1：X+2Y+3Z=0与L2：X+2Y+Z=0相交的无穷远点。解：因为L1∥L2,所以有Z=0，X+2Y=0；所以坐标为（-2Y:Y:0），Y≠0。即（-2:1:0）为这个无穷远点的坐标.注解2.欧氏直线L在平面直角坐标系Oxy上的方程为：ax+by+cax+by+c=0=0则L上任一平常点(x,y)的齐次坐标为(X,Y,Z)，ZZ≠≠00，代入得：aX+bY+cZaX+bY+cZ=0=0L上的无穷远点的坐标(X,Y,Z)应满足aX+bYaX+bY=0=0，，Z=0Z=0;平面上无穷远直线的方程自然为：Z=0Z=0!!(3)任意域上的椭圆曲线K为域，K上的射影平面P2(K)是一些等价类的集合{(X:Y:Z)}。考虑下面的Weierstrass方程(次数为3的齐次方程)：Y2Z+a1XYZ+a3YZ2=X3+a2X2Z+a4XZ2+a6Z3(其中系数ai∈K）Weierstrass方程被称为光滑或非奇异的是指对所有适合以下方程的射影点P=(X:Y:Z)∈P2(K)来说，F(X,Y,Z)=Y2Z+a1XYZ+a3YZ2-X3-a2X2Z-a4XZ2-a6Z3=0在P点的三个偏导数之中至少有一个不为0。若否，则称这个方程为奇异的。●●椭圆曲线椭圆曲线EE的定义：椭圆曲线E是一个光滑的Weierstrass方程在P2(K)中的全部解集合。Y2Z+a1XYZ+a3YZ2=X3+a2X2Z+a4XZ2+a6Z3注：a)在椭圆曲线E上恰有一个无穷远点,即(0:1:0),用θ表示.ZFYFXF∂∂∂∂∂∂,,b)可用非齐次坐标的形式来表示椭圆曲线的Weierstrass方程:设x=X/Z，y=Y/Z，于是原方程转化为：y2+a1xy+a3y=x3+a2x2+a4x+a6(※)椭圆曲线E就是方程（※)在射影平面P2(K)上的全部平常点解，外加一个y轴上的无穷远点θ组成的集合。c)若方程(1)的系数a1,a３,a2,a4,a6∈K，此时椭圆曲线E被称为定义在K上，用E/K表示。如果E能被限定在K上，那么E的K－有理点集合表示为E(K)，它为E中的全体有理坐标点的集合外加无穷远点θ。(4)实域R上的椭圆曲线设K=R，此时的椭圆曲线可表为平面上的通常曲线上的点，外加无穷远点θ。实域R上的椭圆曲线方程其系数满足关系式满足该方程的所有点,外加无穷远点θ一起构成的集合,被视为由该方程决定的椭圆曲线。可以按几何关系定义椭圆曲线上点的加法运算。(,)xy427032ab+≠Eyxaxb:23=++实域R上椭圆曲线点的加法运算法则点对X轴的反射点被称为点的负点(逆元),(x,y)+(x,-y)=θ.两相异点加运算：P、Q为椭圆曲线上相异两点，有，点R是经过P、Q两点的直线与曲线相交之点的唯一负点。倍点运算：点P的倍点2P是经过点P的切线与椭圆曲线相交之点的负点（逆元）。若点P重复加昀小的次数n，就得nP=θ，则称点P的阶（周期）为n。Pxy=(,)(,)Pxy−=−Pxy=(,)PQR+=具体描素为：设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与无穷远点θ(=(0:1:0))的直线L′。则L′与E的另一个交点定义为P+Q。PQP+QP=QLLθP+QL′L′(P+Q)+R=θθT+T=θ(P=Q=R)RRT上面的图像为椭圆曲线y2=x3-x的具体图象。然而，用此图象来说明计算点的加法运算规则，并不失一般性。下面针对一般的方程(※)给出的椭圆曲线上的点P=(x1,y1)、Q=(x2,y2)，来计算P⊕Q=(x3,y3)=？由P⊕Q的定义，设y=αx+β为通过P,Q两点直线L的方程，可算出：当P≠Q时：α=(y2-y1)/(x2-x1),β=y1-αx1易见，直线L上的一个点（x,αx+β)是在椭圆曲线E上，当且仅当(αx+β)2=x3+ax+b;P+Q=(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时：P+Q=（x3，y3）算得：x3=((3x12+a)/2y1)2-2x1;y3=-y1+((3x12+a)/2y1)(x1-x3)。图左表示两相异点相加;右图表两个相同点相加注：a)如果直线L与E相交与三点P,Q,R(不一定相异），那么(P+Q)+R=θ(从图中可见）。b)任给P∈E,P+θ=P(此时设Q=θ，易见L=L′)；c)任给P,Q∈E有：P+Q=Q+P；d)设P∈E，那么可以找到-P∈E使P+（-P）=θ；e)任给P,Q,R∈E，有(P+Q)+R=P+(Q+R)综上所述，知E对+运算形成一个Abel群。f)上述规则可开拓到任意域上，特别是有限域上。假定椭圆曲线是定义在有限域Fq上（q=pm)，那么E(Fq)={(x,y)∈Fq×Fq|y2+a1xy+a3y=x3+a2x2+a4x+a6}∪{θ}不难验证它对“+”运算也形成一个Abel群。2有限域上椭圆曲线的+运算令Fq表示q个元素的有限域，用E(Fq)表示定义在Fq上的一个椭圆曲线E。定理定理1.1.(Hass(Hass定理定理))E(FE(Fqq))的点数用的点数用##E(FE(Fqq))表示，则表示，则||##E(FE(Fqq))--qq--1|1|≤≤2q2q1/21/2(1)Fp（素域，p为素数）上椭圆曲线令p3，a,b∈Fp，满足4a3+27b2≠0，由参数a和b定义的Fp上的一个椭圆曲线方程为：y2=x3+ax+b它的所有解(x,y)，(x∈Fp，y∈Fp)，连同“无穷远点”θ组成的集合记为E(Fp)，由Hass定理知：p+1-2p1/2≤#E(Fp)≤p+1+2p1/2集合E(Fp)有如下加法规则：任给(x,y)∈E(Fp),(i)θ＋θ=θ（单位元素）(ii)(x,y)＋θ=(x,y),(iii)(iii)(x,y)＋(x,-y)=θ，(iv)令(x1,y1),(x2,y2)为E(Fp)中非互逆元并且互不相等，则(x1,y1)＋(x2,y2)=(x3,y3),其中x3=α2-x1-x2，y3=α(x1-x3)-y1,斜率α=(y2-y1)/(x2-x1)(v)（倍点运算规则）设(x1,y1)∈E(Fp),y1≠0，则2(x1,y1)=(x3,y3)，其中x3=α2-2x1,y3=α(x1-x3)-y1;α=(3x12+a)/(2y1)注：若#E(Fp)=p+1，曲线E(Fp)称为超奇异的，否则称为非超奇异的。例子1：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,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：F23,点P=(0,1)是椭圆曲线点的生成元.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),16P=θEyxx:23121=++例子3：F23上的椭圆曲线上的两点P=(18,14)、Q=(5,10).求解P+Q=?解:23:1610Eyxx=++λ=−−=yyxxp2121413modmod23=18xxxp3212181852322=−−=−−=λmodmodyxxyp313118182142321=−−=−−=λ()mod()mod∴+==PQR(,)221(2)F2m上的椭圆曲线F2m上由参数a,b∈F2m，b≠0定义的一个非超奇异椭圆曲线E(F2m)是方程y2+xy=x3+ax2+b的解集合(x,y)，其中x,y∈F2m，连同θ。E(FE(F22mm))的加法规则如下：的加法规则如下：(i)θ+θ=θ(ii)任给(x,y)∈E(F2m)，则(x,y)⊕θ