第15次课ECC

2020/5/3,1,椭圆曲线密码编码学ECC,EllipticCurveCryptography,2020/5/3,2,6.5EllipticCurveCryptography,椭圆曲线密码编码学ECC大多数公开密钥密码系统如RSA,D-H都使用具有非常大数目的整数或多项式，计算量大，密钥和报文存储量也极大。因此，可以使用椭圆曲线密码系统ECC，达到同样安全但位数要小得多。椭圆曲线椭圆曲线并非椭圆，它指的是由Weierstrass方程所确定的平面曲线：y2+axy+by=x3+cx2+dx+e满足上述方程的数偶(x,y)称为椭圆曲线E上的点。同时定义无穷点(pointatinfinity)或零点(zeropoint)的O。,椭圆曲线的形状，并不是椭圆的。只是因为椭圆曲线的描述方程，类似于计算一个椭圆周长的方程，故得名。,2020/5/3,3,椭圆曲线的一般形式,一般形式具有不同根的条件例子,y2+axy+by=x3+cx2+dx+e,2020/5/3,4,y2=x3-x,2020/5/3,5,y2=x3+x+1,2020/5/3,6,椭圆曲线加法,椭圆曲线上的点集及其上的加法操作构成一个群。点集：椭圆曲线上的所有点和无穷远点操作：点加法R=P+Q（或R=P*Q）,运算法则：任意取椭圆曲线上两点P、Q（若P、Q两点重合，则做P点的切线）做直线交于椭圆曲线的另一点R，过R做y轴的平行线交于R。我们规定P+Q=R,这里的“+”不是实数中普通的加法，而是从普通加法中抽象出来的加法，他具备普通加法的一些性质，但具体的运算法则显然与普通加法不同。,2020/5/3,7,椭圆曲线上的形式加法如果椭圆曲线上的三个点处于一条直线上，那么它们的和为O。加法规则：O是加法的单位元(additiveidentity)，O=O；对于椭圆曲线上的任一点P，有P+O=P。一条垂直线与曲线相交于P1=(x,y)和P2=(x,y)，也相交于无穷点O，有P1+P2+O=O和P1=P2。对具有不同的x坐标的Q和R相加，先在它们之间画一条直线求出第三个交点P1，这种交点是唯一的。因为Q+R+P1=O,因此Q+R=P1。对点Q加倍，画一切线求出另一交点S，则Q+Q=2Q=S。一条椭圆曲线上的一点P被一个正整数k相乘的乘法被定义为k个P的相加。,2020/5/3,8,单位元和逆元,逆元P(x,-y)=P(x,y)关于X轴对称点。P+P=O单位元P+O=P,2020/5/3,9,点的累加,二倍过点P(x,y)的切线R=P+P,2020/5/3,10,反复累加,kP=P+P或写为：,2020/5/3,11,数学描述,直线g:y=sx+y0其中：与曲线相交：(sx+y0)2=x3+ax+bR点坐标：,2020/5/3,12,切线g：y=sx+y0与曲线相交：(sx+y0)2=x3+ax+bR点坐标：,2020/5/3,13,提醒大家注意一点，以前提供的图像可能会给大家产生一种错觉，即椭圆曲线是关于x轴对称的。事实上，椭圆曲线并不一定关于x轴对称。,2020/5/3,14,我们现在基本上对椭圆曲线有了初步的认识，但请注意，前面学到的椭圆曲线是连续的，并不适合用于加密；所以，我们必须把椭圆曲线变成离散的点。让我们想一想，为什么椭圆曲线为什么连续？是因为椭圆曲线上点的坐标，是实数的（也就是说前面讲到的椭圆曲线是定义在实数域上的），实数是连续的，导致了曲线的连续。因此，我们要把椭圆曲线定义在有限域上（顾名思义，有限域是一种只有由有限个元素组成的域）。域的概念是从我们的有理数，实数的运算中抽象出来的，严格的定义请参考近世代数方面的数。简单的说，域中的元素同有理数一样，有自己得加法、乘法、除法、单位元(1)，零元(0),并满足交换率、分配率。,2020/5/3,15,下面，我们给出一个有限域Fp，这个域只有有限个元素。Fp中只有p（p为素数）个元素0,1,2p-2,p-1；Fp的加法（a+b）法则是a+bc(modp)；即，(a+c)p的余数和cp的余数相同。Fp的乘法(ab)法则是abc(modp)；Fp的除法(ab)法则是a/bc(modp)；即ab-1c(modp)；（b-1也是一个0到p-1之间的整数，但满足bb-11(modp)；）。Fp的单位元是1，零元是0。,2020/5/3,16,同时，并不是所有的椭圆曲线都适合加密。y2=x3+ax+b是一类可以用来加密的椭圆曲线，也是最为简单的一类。下面我们就把y2=x3+ax+b这条曲线定义在Fp上：选择两个满足下列条件的小于p(p为素数)的非负整数a、b4a3+27b20(modp)则满足下列方程的所有点(x,y)，再加上无穷远点O，构成一条椭圆曲线。y2=x3+ax+b(modp)其中x,y属于0到p-1间的整数，并将这条椭圆曲线记为Ep(a,b)。,2020/5/3,17,有限域上的椭圆曲线EllipticcurvecryptographyusescurveswhosevariablesEp(-1,188),equalstoy2=x3-x+188,G=(0,376)AsendsamessagetoB,Pm=(562,201)Aselectsk=386randomlyandPA=(201,5)ThuskG=386(0,376)=(676,558)Pm+kPA=(562,201)+386(201,5)=(385,328)Therefore,theciphertextisCm=kG,Pm+kPA=(676,558)，(385,328),公钥（G，PA）,2020/5/3,32,ReliesonellipticcurvelogarithmproblemFastestmethodis“Pollardrhomethod”Comparedtofactoring,canusemuchsmallerkeysizesthanwithRSAetcForequivalentkeylengthscomputatio