第15次课-ECC.ppt

2020/6/281椭圆曲线密码编码学ECCEllipticCurveCryptography2020/6/2826.5EllipticCurveCryptography•椭圆曲线密码编码学ECC–大多数公开密钥密码系统如RSA,D-H都使用具有非常大数目的整数或多项式，计算量大，密钥和报文存储量也极大。因此，可以使用椭圆曲线密码系统ECC，达到同样安全但位数要小得多。•椭圆曲线–椭圆曲线并非椭圆，它指的是由Weierstrass方程所确定的平面曲线：y2+axy+by=x3+cx2+dx+e满足上述方程的数偶(x,y)称为椭圆曲线E上的点。同时定义无穷点(pointatinfinity)或零点(zeropoint)的O。椭圆曲线的形状，并不是椭圆的。只是因为椭圆曲线的描述方程，类似于计算一个椭圆周长的方程，故得名。2020/6/283椭圆曲线的一般形式•一般形式•具有不同根的条件•例子y2+axy+by=x3+cx2+dx+e2020/6/284y2=x3-x2020/6/285y2=x3+x+12020/6/286椭圆曲线加法•椭圆曲线上的点集及其上的加法操作构成一个群。•点集：–椭圆曲线上的所有点和无穷远点•操作：–点加法R=P+Q（或R=P*Q）运算法则：任意取椭圆曲线上两点P、Q（若P、Q两点重合，则做P点的切线）做直线交于椭圆曲线的另一点R’，过R’做y轴的平行线交于R。我们规定P+Q=R这里的“+”不是实数中普通的加法，而是从普通加法中抽象出来的加法，他具备普通加法的一些性质，但具体的运算法则显然与普通加法不同。2020/6/287•椭圆曲线上的形式加法如果椭圆曲线上的三个点处于一条直线上，那么它们的和为O。加法规则：1.O是加法的单位元(additiveidentity)，O=－O；对于椭圆曲线上的任一点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被一个正整数k相乘的乘法被定义为k个P的相加。2020/6/288单位元和逆元•逆元P’(x,-y)=P(x,y)关于X轴对称点。•P+P’=O•单位元P+O=P2020/6/289点的累加•二倍过点P(x,y)的切线R=P+P2020/6/2810反复累加kP=P+…+P或写为：2020/6/2811数学描述•直线g:y=sx+y0其中：与曲线相交：(sx+y0)2=x3+ax+bR点坐标：2020/6/2812•切线g：y=sx+y0与曲线相交：(sx+y0)2=x3+ax+bR点坐标：2020/6/2813•提醒大家注意一点，以前提供的图像可能会给大家产生一种错觉，即椭圆曲线是关于x轴对称的。•事实上，椭圆曲线并不一定关于x轴对称。2020/6/2814•我们现在基本上对椭圆曲线有了初步的认识，但请注意，前面学到的椭圆曲线是连续的，并不适合用于加密；所以，我们必须把椭圆曲线变成离散的点。•让我们想一想，为什么椭圆曲线为什么连续？是因为椭圆曲线上点的坐标，是实数的（也就是说前面讲到的椭圆曲线是定义在实数域上的），实数是连续的，导致了曲线的连续。因此，我们要把椭圆曲线定义在有限域上（顾名思义，有限域是一种只有由有限个元素组成的域）。•☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆域的概念是从我们的有理数，实数的运算中抽象出来的，严格的定义请参考近世代数方面的数。简单的说，域中的元素同有理数一样，有自己得加法、乘法、除法、单位元(1)，零元(0),并满足交换率、分配率。☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆2020/6/2815•下面，我们给出一个有限域Fp，这个域只有有限个元素。•Fp中只有p（p为素数）个元素0,1,2……p-2,p-1；•Fp的加法（a+b）法则是a+b≡c(modp)；即，(a+c)÷p的余数和c÷p的余数相同。•Fp的乘法(a×b)法则是a×b≡c(modp)；•Fp的除法(a÷b)法则是a/b≡c(modp)；即a×b-1≡c(modp)；（b-1也是一个0到p-1之间的整数，但满足b×b-1≡1(modp)；）。•Fp的单位元是1，零元是0。2020/6/2816•同时，并不是所有的椭圆曲线都适合加密。y2=x3+ax+b是一类可以用来加密的椭圆曲线，也是最为简单的一类。•下面我们就把y2=x3+ax+b这条曲线定义在Fp上：选择两个满足下列条件的小于p(p为素数)的非负整数a、b4a3+27b2≠0(modp)则满足下列方程的所有点(x,y)，再加上无穷远点O∞，构成一条椭圆曲线。y2=x3+ax+b(modp)其中x,y属于0到p-1间的整数，并将这条椭圆曲线记为Ep(a,b)。2020/6/2817•有限域上的椭圆曲线–Ellipticcurvecryptographyusescurveswhosevariables&coefficientsarefinite.–Havetwofamiliescommonlyused:•primecurvesEp(a,b)definedoverZp–useintegersmoduloaprime–bestinsoftware•binarycurvesE2n(a,b)definedoverGF(2n)–usepolynomialswithbinarycoefficients–bestinhardware•Ep(a,b)表示满足下列条件的模p椭圆群，群中元素(x,y)是满足如下方程的小于p的非负整数另外加上无穷点O：y2≡x3+ax+b(modp).例如：P=23,y2=x3+x+1,有4x13+27x12mod23=8≠0,满足条件FiniteEllipticCurvesE23(1,1)2020/6/2818椭圆曲线E23(1,1)上的点•对于每个满足0=xp的x，计算x3+ax+bmodp•对于上一步得到的每个结果确定它是否有一个模p的平方根，如果没有，在Ep(a,b)中就没有具有这个x值的点，如果有，就有两个满足平方根运算的y值(除非这个值是单个的y值0)。这些(x,y)就是Ep(a,b)中的点2020/6/28192020/6/2820c=a*bmod11的乘法表对于上一步得到的每个结果确定它是否有一个模p的平方根2020/6/2821椭圆曲线上的点•在GF11上找出满足椭圆曲线方程的点P(x,y):y2=x3+x+6mod11•有12个点，加上无穷远点O共有n=13个元素如果椭圆曲线上一点P，存在最小的正整数n，使得数乘nP=O，则将n称为P的阶，若n不存在，我们说P是无限阶的。事实上，在有限域上定义的椭圆曲线上所有的点的阶n都是存在的（证明，请参考近世代数方面的书）2020/6/2822椭圆曲线点加运算•将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上进行2020/6/2823椭圆曲线点加运算•取P(2,4),计算2P=P+P（或记为P2=P*P)•再计算3P=P+P+P=2P+P（或记为P3=P2*P)y2=x3+x+6mod112020/6/2824椭圆曲线离散对数问题•给定曲线y2=x3+ax+bmodp以及其上一点P，我们可以通过连续自加k-1次计算Q=kP，(或Q=Pk)。目前存在这样的快速算法。•问题：当Q已知时能否计算k?•答案：这是一个被称为椭圆曲线离散对数的难题。2020/6/2825椭圆曲线密码系统的定义•域标识：定义椭圆曲线采用的有限域•椭圆曲线：系数a和b•基准点(base):指定的椭圆曲线上的点P(x,y)•阶(order):P点的阶n，使得：nP=O•E(a,b),GFP•选择e作为私有密钥•公开密钥为Q=eP2020/6/2826ElGamal算法•g属于GF(q),g为非0元素。•用户A随机选择a,0aq,a保密，ga公开。•B向A发送消息m:B:选择k,发送(gk,mgak)到AA：m=mgak/(gk)a=mgak(gak)-1modq2020/6/2827ElGamal算法在椭圆曲线上实现•E(a,b),basepointG属于E•A选择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)2020/6/2828EquivalentCryptographicStrength2020/6/2829•ECCadditionisanalogofmodulomultiply•ECCrepeatedadditionisanalogofmoduloexponentiation•need“hard”problemequivtoDLP–Q=kP,whereQ,PbelongtoEp(a,b),kP–is“easy”tocomputeQgivenk,P–but“hard”tofindkgivenQ,P–knownastheellipticcurvelogarithmproblem•example:E23(9,17)EllipticCurveCryptography2020/6/2830•Severalalternatives,willconsidersimplest•MustfirstencodeanymessageMasapointontheellipticcurvePm,apointofx-y,whichistobeencryptedanddecrypted•Selectsuitablecurve&pointGasinD-H•EachuserchoosesprivatekeynAnandcomputespublickeyPA=nA×G•ToencryptPm:Cm={kG,Pm+kPA},krandom•DecryptCm,Bcomputes:Pm+kPA–nA(kG)=Pm+k(nAG)–nA(kG)=PmECCEncryption/Decryption2020/6/2831•Ex:–P=751;Ep(-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/6/2832•Reliesonellipticcurvelogarithmproblem•Fastestmethodis“Pollardrhomethod”•Comparedtofactoring,canusemuchsmallerkeysizesthanwithRSAetc•Forequivalentkeylengthscomputationsareroughlyequivalent•HenceforsimilarsecurityECCofferssignificantcomputationaladvantagesECCSecurity2020/6/2833ComparisonwithRSA