第15次课ECC.ppt

《第15次课ECC.ppt》由会员分享，可在线阅读，更多相关《第15次课ECC.ppt（33页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、椭圆曲线密码编码学ECCElliptic Curve CryptographyElliptic Curve Cryptography12/29/202216.5EllipticCurveCryptography椭圆曲线密码编码学椭圆曲线密码编码学ECC大多数公开密钥密码系统如大多数公开密钥密码系统如RSA,D-H都使用具有非常都使用具有非常大数目的整数或多项式，计算量大，密钥和报文存储量大数目的整数或多项式，计算量大，密钥和报文存储量也极大。因此，可以使用椭圆曲线密码系统也极大。因此，可以使用椭圆曲线密码系统ECC，达到，达到同样安全但位数要小得多。同样安全但位数要小得多。椭圆曲线椭圆曲线椭圆

2、曲线并非椭圆，它指的是由椭圆曲线并非椭圆，它指的是由Weierstrass方程所确方程所确定的平面曲线：定的平面曲线：y2+axy+by=x3+cx2+dx+e满足上述方程的数偶满足上述方程的数偶(x,y)称为椭圆曲线称为椭圆曲线E上的点。上的点。同时定义无穷点同时定义无穷点(pointatinfinity)或零点或零点(zeropoint)的的O。椭圆曲线的形状，并不是椭圆椭圆曲线的形状，并不是椭圆的。只是因为椭圆曲线的描述的。只是因为椭圆曲线的描述方程，类似于计算一个椭圆周方程，类似于计算一个椭圆周长的方程，故得名。长的方程，故得名。12/29/20222椭圆曲线的一般形式一般形式一般形式

3、具有不同根的条件具有不同根的条件例子例子y2+axy+by=x3+cx2+dx+e12/29/20223y2=x3-x12/29/20224y2=x3+x+112/29/20225椭圆曲线加法椭圆曲线上的点集及其上的加法操作构成椭圆曲线上的点集及其上的加法操作构成一个群。一个群。点集：点集：椭圆曲线上的所椭圆曲线上的所有点和无穷远点有点和无穷远点操作：操作：点加法点加法R=P+Q（或或R=P*Q）运算法则：任意取椭圆曲线上两点运算法则：任意取椭圆曲线上两点P、Q（若（若P、Q两点重合，则做两点重合，则做P点的点的切线）做直线交于椭圆曲线的另一点切线）做直线交于椭圆曲线的另一点R，过，过R做做y

4、轴的平行线交于轴的平行线交于R。我们规定我们规定P+Q=R 这里的这里的“+”不是实数中普通的加法，而是从普通加法中抽象出来不是实数中普通的加法，而是从普通加法中抽象出来的加法，他具备普通加法的一些性质，但具体的运算法则显然与的加法，他具备普通加法的一些性质，但具体的运算法则显然与普通加法不同。普通加法不同。12/29/20226椭圆曲线上的形式加法椭圆曲线上的形式加法如果椭圆曲线上的三个点处于一条直线上，那么它们的和如果椭圆曲线上的三个点处于一条直线上，那么它们的和为为O O。加法规则：加法规则：1.O是加法的单位元是加法的单位元(additiveidentity)，O=O；对于椭圆曲线上的

5、任一点；对于椭圆曲线上的任一点P，有，有P+O=P。2.一条垂直线与曲线相交于一条垂直线与曲线相交于P1=(x,y)和和P2=(x,y)，也相交于无穷点，也相交于无穷点O，有，有P1+P2+O=O和和P1=P2。3.对具有不同的对具有不同的x坐标的坐标的Q和和R相加，先在它们之间画一相加，先在它们之间画一条直线求出第三个交点条直线求出第三个交点P1，这种交点是唯一的。因为，这种交点是唯一的。因为Q+R+P1=O,因此因此Q+R=P1。4.对点对点Q加倍，画一切线求出另一交点加倍，画一切线求出另一交点S，则，则Q+Q=2Q=S。5.一条椭圆曲线上的一点一条椭圆曲线上的一点P被一个正整数被一个正整

6、数k相乘的乘法相乘的乘法被定义为被定义为k个个P的相加。的相加。12/29/20227单位元和逆元逆元P(x,-y)=P(x,y)关于X轴对称点。P+P=O单位元 P+O=P12/29/20228点的累加二倍过点P(x,y)的切线R=P+P12/29/20229反复累加kP=P+P或写为：12/29/202210数学描述直线直线g:y=sx+y0其中其中：与曲线相交：与曲线相交：(sx+y0)2=x3+ax+bR点坐标：点坐标：12/29/202211切线切线g：y=sx+y0与曲线相交：与曲线相交：(sx+y0)2=x3+ax+bR点坐标：点坐标：12/29/202212提醒大家注意一点，以

7、提醒大家注意一点，以前提供的图像可能会给前提供的图像可能会给大家产生一种错觉，即大家产生一种错觉，即椭圆曲线是关于椭圆曲线是关于x轴对轴对称的。称的。事实上，椭圆曲线并不事实上，椭圆曲线并不一定关于一定关于x轴对称。轴对称。12/29/202213我们现在基本上对椭圆曲线有了初步的认识，但请注意，我们现在基本上对椭圆曲线有了初步的认识，但请注意，前面学到的椭圆曲线是连续的，并不适合用于加密；所以，前面学到的椭圆曲线是连续的，并不适合用于加密；所以，我们必须把椭圆曲线变成离散的点。我们必须把椭圆曲线变成离散的点。让我们想一想，为什么椭圆曲线为什么连续？是因为椭让我们想一想，为什么椭圆曲线为什么连

8、续？是因为椭圆曲线上点的坐标，是实数的（也就是说前面讲到的椭圆圆曲线上点的坐标，是实数的（也就是说前面讲到的椭圆曲线是定义在实数域上的），实数是连续的，导致了曲线曲线是定义在实数域上的），实数是连续的，导致了曲线的连续。因此，我们要把椭圆曲线定义在有限域上（顾名的连续。因此，我们要把椭圆曲线定义在有限域上（顾名思义，有限域是一种只有由有限个元素组成的域）。思义，有限域是一种只有由有限个元素组成的域）。域的概念是从我们的有理数，实数的运算中抽象出来的，域的概念是从我们的有理数，实数的运算中抽象出来的，严格的定义请参考近世代数方面的数。简单的说，域中的严格的定义请参考近世代数方面的数。简单的说，域

9、中的元素同有理数一样，有自己得加法、乘法、除法、单位元元素同有理数一样，有自己得加法、乘法、除法、单位元(1)，零元，零元(0),并满足交换率、分配率。并满足交换率、分配率。12/29/202214下面，我们给出一个有限域下面，我们给出一个有限域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/

10、bc(modp)；即即ab-1c(modp)；（b-1也是一个也是一个0到到p-1之间的整数，但满足之间的整数，但满足bb-11(modp)；）。；）。Fp的单位元是的单位元是1，零元是，零元是0。12/29/202215同时，并不是所有的椭圆曲线都适合加密。同时，并不是所有的椭圆曲线都适合加密。y2=x3+ax+b是一类可以用来加密的椭圆曲线，也是最是一类可以用来加密的椭圆曲线，也是最为简单的一类。为简单的一类。下面我们就把下面我们就把y2=x3+ax+b这条曲线定义在这条曲线定义在Fp上：上：选择两个满足下列条件的小于选择两个满足下列条件的小于p(p为素数为素数)的非负整数的非负整数a、b

11、4a3+27b20(modp)则满足下列方程的所有点则满足下列方程的所有点(x,y)，再加上，再加上无穷远点无穷远点O，构成一条椭圆曲线。，构成一条椭圆曲线。y2=x3+ax+b(modp)其中其中x,y属于属于0到到p-1间的整数，并将这条椭圆曲线记间的整数，并将这条椭圆曲线记为为Ep(a,b)。12/29/202216有限域上的椭圆曲线有限域上的椭圆曲线Elliptic curve cryptography uses curves whose variables&coefficients are finite.Have two families commonly used:prime cu

12、rves Ep(a,b)defined over Zp use integers modulo a primebest in softwarebinary curves E2n(a,b)defined over GF(2n)use polynomials with binary coefficientsbest in hardwareEp(a,b)表示满足下列条件的模表示满足下列条件的模p椭圆群，群中元素椭圆群，群中元素(x,y)是是满足如下方程的小于满足如下方程的小于p的非负整数另外加上无穷点的非负整数另外加上无穷点O：y2x3+ax+b(modp).例如：例如：P=23,y2=x3+x+1

13、,有有4x13+27x12mod23=80,满足满足条件条件Finite Elliptic CurvesE E2323(1,1)(1,1)12/29/202217椭圆曲线椭圆曲线椭圆曲线椭圆曲线E E2323(1,1)(1,1)上的点上的点上的点上的点对于每个满足对于每个满足0=xp的的x，计算，计算x3+ax+bmodp对于上一步得到的每个结果确定它是否有一个模对于上一步得到的每个结果确定它是否有一个模p的平方根，如果没有，的平方根，如果没有，在在Ep(a,b)中就没有具有这个中就没有具有这个x值的点，如果有，就有两个满足平方根值的点，如果有，就有两个满足平方根运算的运算的y值值(除非这个值

14、是单个的除非这个值是单个的y值值0)。这些。这些(x,y)就是就是Ep(a,b)中的中的点点12/29/20221812/29/202219 c=a*b mod 11的乘法表对于上一步得到的每个结果确定它是否对于上一步得到的每个结果确定它是否有一个模有一个模p的平方根的平方根12/29/202220椭圆曲线上的点在GF11上找出满足椭圆曲线方程的点 P(x,y):y2=x3+x+6 mod 11有12个点，加上无穷远点O共有n=13个元素如果椭圆曲线上一点如果椭圆曲线上一点P，存在最小的，存在最小的正整数正整数n，使得数乘，使得数乘nP=O，则将，则将n称为称为P的的阶，若阶，若n不存在，我们

15、说不存在，我们说P是无限阶的。是无限阶的。事实上，在有限域上定义的椭圆事实上，在有限域上定义的椭圆曲线上所有的点的阶曲线上所有的点的阶n都是存在的都是存在的（证明，请参考近世代数方面的书）（证明，请参考近世代数方面的书）12/29/202221椭圆曲线点加运算将将y2=x3+x+6mod11上的点上的点(2,4)反反复累加复累加计算计算2P=P+P（或记为或记为P2=P*P)计算计算3P=P+P+P=2P+P（或记为或记为P3=P*P*P=P2*P)所有运算均在所有运算均在GF11上进行上进行12/29/202222椭圆曲线点加运算取取P(2,4),计算计算2P=P+P（或记为或记为P2=P*

16、P)再计算再计算3P=P+P+P=2P+P（或记为或记为P3=P2*P)y2=x3+x+6mod1112/29/202223椭圆曲线离散对数问题给定曲线给定曲线y2=x3+ax+bmodp以及其上一点以及其上一点P，我们可以我们可以通过连续自加通过连续自加k-1次计算次计算Q=kP，(或或Q=Pk)。目前存在这样的快速算法。目前存在这样的快速算法。问题：当问题：当Q已知时能否计算已知时能否计算k?答案：答案：这是一个被称为这是一个被称为椭圆椭圆 曲线离散对数曲线离散对数的难题。的难题。12/29/202224椭圆曲线密码系统的定义域标识：定义椭圆曲线采用的有限域域标识：定义椭圆曲线采用的有限域

17、椭圆曲线：系数椭圆曲线：系数a和和b基准点基准点(base):指定的椭圆曲线上的点指定的椭圆曲线上的点P(x,y)阶阶(order):P点的阶点的阶n，使得：使得：nP=OE(a,b),GFP选择选择e作为私有密钥作为私有密钥公开密钥为公开密钥为Q=eP12/29/202225ElGamal算法g属于属于GF(q),g为非为非0元素。元素。用户用户A随机选择随机选择a,0aq,a保密，保密，ga公公开开。B向向A发送消息发送消息m:B:选择选择k,发送发送(gk,mgak)到到AA：m=mgak/(gk)a=mgak(gak)-1modq12/29/202226ElGamal算法在椭圆曲线上实

18、现E(a,b),basepointG属于属于EA选择选择a并保密并保密,0aN，N为为G的阶的阶(order),aG公开公开B向向A发送消息发送消息m:B将将m嵌入点嵌入点Pm，选择随机数选择随机数k,A(kG,Pm+k(aG)BA：Pm=(Pm+k(aG)a(kG)12/29/202227Equivalent Cryptographic Strength12/29/202228ECCadditionisanalogofmodulomultiplyECCrepeatedadditionisanalogofmoduloexponentiationneed“hard”problemequivtoD

19、LPQ=kP,whereQ,PbelongtoEp(a,b),kPis“easy”tocomputeQgivenk,Pbut“hard”tofindkgivenQ,Pknownastheellipticcurvelogarithmproblemexample:E23(9,17)Elliptic Curve Cryptography12/29/202229Several alternatives,will consider simplestMust first encode any message M as a point on the elliptic curve Pm,a point of

20、x-y,which is to be encrypted and decrypted Select suitable curve&point G as in D-HEach user chooses private key nAn and computes public key PA=nAGTo encrypt Pm:Cm=kG,Pm+kPA,k randomDecrypt Cm,B computes:Pm+kPAnA(kG)=Pm+k(nAG)nA(kG)=PmECC Encryption/Decryption12/29/202230Ex:P=751;Ep(-1,188),equals to

21、 y2=x3-x+188,G=(0,376)A sends a message to B,Pm=(562,201)A selects k=386 randomly and PA=(201,5)Thus kG=386(0,376)=(676,558)Pm+kPA=(562,201)+386(201,5)=(385,328)Therefore,the ciphertext is Cm=kG,Pm+kPA=(676,558)，(385,328)公钥（公钥（G，PA）12/29/202231Relies on elliptic curve logarithm problemFastest method is“Pollard rho method”Compared to factoring,can use much smaller key sizes than with RSA etcFor equivalent key lengths computations are roughly equivalentHence for similar security ECC offers significant computational advantagesECC Security12/29/202232Comparison with RSA12/29/202233