第04章椭圆曲线密码体制ECC

椭圆曲线密码（ECC）体制一般椭圆曲线有限域上的椭圆曲线椭圆曲线密码算法椭圆曲线密码体制的安全性2ELGamal密码体制能够在任何离散对数难处理的有限群中实现。我们已经使用了乘法群Zp*，但其他群也是合适的候选者，如椭圆曲线群。椭圆曲线在代数学和几何学上已广泛研究了150多年之久，有丰富而深厚的理论积累。椭圆曲线密码体制（EllipseCurveCryptosystem，ECC）在l985年由Koblitz和Miller提出，不过一直没有像RSA等密码系统一样受到重视。纵观目前的发展趋势，椭圆曲线已经逐渐被采用，很可能是一个重要的发展方向。3椭圆曲线并非椭圆，这么命名是因为它们是由三次方程描述的，而这些三次方程类似于计算椭圆周长的方程。一般的，描述椭圆曲线方程的形式是y2+axy+by=x3+cx2+dx+e其中a、b、c、d和e是满足一些简单条件的实数一般来说，椭圆曲线还包含了一个特殊的点，即称为无穷远点(PointatInfinity)或零点(ZeroPoint)的O。4.4.1一般椭圆曲线4对于椭圆曲线上的点可以定义一种形式的加法：如果一个椭圆曲线上的三个点处于一条直线上，那么它们的和为O。从这个定义可以导出椭圆曲线上点的加法法则。(1)O是加法的单位元，因而O＝－O；对于椭圆曲线上的任何一点P，有P+O＝P。(2)一条与x轴垂直的线和曲线相交于两个x坐标相同的点P1=(x，y)和P2＝(x,－y)，同时它也和曲线相交于无穷远点，因此P1+P2+O＝O。因而一个点的负值是与其有着相同x坐标和相反的y坐标的点，如图4.1(a)所示。56(3)要对具有不同x坐标的两个点Q与R进行相加，先在它们之间画一条直线并求出第三个交点P1。容易看出这种交点是惟一的。注意到Q+R+P1＝O，有Q+R＝－P。特别地，当Q=R时，相当于对一个点Q加倍，只需画出一条切线并求出另一个交点S，那么Q+Q=2Q=－S。显然，根据定义，此类加法满足交换率和结合率.而一个点的倍乘定义为nP＝P+P+P+……+P74.4.2有限域上的椭圆曲线密码学中关心的是有限域F上的椭园曲线。讨论比较多的是素域Fp上的椭圆曲线，这里P是一个素数。选择两个小于P的非负整数a和b满足4a3+27b2(modp)≠0用Ep(a，b)表示如下模p的椭圆群中的点(或如下有限域Fp上的椭圆曲线的点)，再加上一个无穷远点O。设(x，y)是Ep(a，b)中的点，x和y是小于p的非负整数，则有如下椭圆曲线方程：y2≡x3+ax+b(modp)8如取p＝23，a=b=l，有4*13+27*12(mod23)＝8≠0，则y2=x3+x+1是椭圆曲线。因此E23(1，1)是一个模23的椭圆群。产生E23(1，1)是中点的过程如下：(1)对x=0,1,2,…,p-1,计算x3+x+1(modp)；(2)对于上一步骤得到的每个结果确定它是否有一个模P的平方根，如果没有，则E23(1，1)中没有具有与该结果相应的x坐标的点。如果有，就有两个平方根y和p－y，从而点(x，y)和(x，p－y)是E23(1，1)中的点(特别情况下，如果结果是0，只有一个点(x，0))。9椭圆曲线E23(1，1)上的点（0，1）（5，4）（9，7）（17，3）（0，22）（5，19）（11，3）（17，20）（1，7）（6，4）（11，20）（18，3）（1，16）（6，19）（12，19）（18，20）（3，10）（7，12）（12，4）（19，5）（3，13）（7，11）（13，7）（19，18）（4，0）（9，16）（13，16）10Ep(a，b)上的加法规则P十O＝P；如果P＝(x,y)，则P+(x,y)=O，点(x，－y)是P的加法逆元，记为－P；如果P＝(x1，y1)，Q＝(x2，y2)，并且P≠Q，则P+Q=(x3，y3)由下列规则确定:x3≡λ2–x1–x2(modp)y3≡λ(x1–x3)–y1(modp)其中：(y2-y1)/(x2－x1)如果P≠Qλ=(3x12－a)/2y1如果P=Q11例子：考虑P=(3,10),Q=(9,7)则：λ=(7－10)/(9－3)=－3/6=－1/2=11mod23x3=112－3－9=10917mod23y3=11(3－(－6))－10=89=20mod23因而P+Q=(17,20).计算2P:λ=(3(32)+1)/(2*10)=5/20=1/4=6mod23x3=62－3－3=30=7mod23y3=6(3－7)－10=－34=12mod23因此2P=(7,12)12椭圆曲线群中的离散对数也属于难解问题。与通常理解的对数概念不同，由于椭圆曲线群中的运算是加法，加法的倍数对应于原来乘法的指数，因而椭圆曲线群中的离散对数问题是指已知群中的Q和R，求解方程：R＝kQ中k值的问题。13对基于F23的椭圆群y2＝x3+9x+17，求R=(4，5)对于Q=(16，5)的离散对数,最直接的方法就是计算Q的倍数，直到找到R。Q＝(16，5)，2Q=(20，20)，3Q＝(14，14),4Q=(19，20)，5Q＝(13，10)，6Q＝(7，3)，7Q＝(8，7)，8Q＝(12，17)，9Q＝(4，5)因此k关于Q的离散对数是9，对于大素数构成的群Fp，这样计算离散对数是不现实的，事实上现在也没有更好的(非指数级的)算法来解离散对数问题。144.4.3椭圆曲线密码算法基于上面讲的椭圆群上的离散对数问题，可以用椭圆曲线密码(ECC)算法加密，具体方法如下：首先选择—个点G和一个椭圆群Ep(a,b)作为参数，用户A选择一个私有密钥nA并产生一个公开密钥PA=nAG。发送者要加密并发送一个报义Pm给A，可选择一个随机整数k，并产生由如下点对组成的密文Cm＝(kG，Pm+kPA)。注意这里使用了A的公开密钥PA。要解密这个报文，A用这个点对的第一个点乘以A的私有密钥，再从第二个点中减去这个值Pm+kPA–nA(kG)=Pm+k(nAG)–nA(kG)=Pm15发送者通过对Pm加上kPA来保护Pm。除了发送者之外没有人知道k的值，因此即便PA是公开密钥也没有人能去掉kPA，当然只有知道nA的人才可以去掉kPA。攻击者在不知道nA的情况下要想得到报文只能在知道G和kG的情况下计算出k，这归结为求解椭圆曲线离散对数问题，是非常困难的。161、用户A选定一条椭圆曲线Ep(a,b)，并取椭圆曲线上一点，作为基点G。2、用户A选择一个私有密钥nA，并生成公开密钥PA=nAG。3、用户A将Ep(a,b)和点PA，G传给用户B。4、用户B接到信息后，将待传输的明文编码到Ep(a,b)上一点Pm，并产生一个随机整数k（kn,n为基点G的阶）。5、用户B计算点C1=Pm+kPA；C2=kG。6、用户B将C1、C2传给用户A。7、用户A接到信息后，计算C1-nAC2，结果就是点Pm。因为Pm+kPA–nA(kG)=Pm+k(nAG)–nA(kG)=Pm再对点Pm进行解码就可以得到明文。利用椭圆曲线进行加密通信的过程：17这个加密通信中，如果有一个偷窥者H，他只能看到Ep(a,b)、PA、G、C1、C2而通过K、G求nA或通过C2、G求k都是相对困难的。因此，H无法得到A、B间传送的明文信息。18注意到以上的过程并没有说明怎样将作为字符串(当然可以看成分段的整数)的消息编码嵌入到椭圆群的点中(将明文嵌入椭圆曲线)，实际中的转化方式多种多样，关键的步骤与其正确性证明都涉及到复杂的数学推导，可以参看相关文献。194.4.4椭圆曲线密码体制的安全性椭圆曲线密码体制的安全性依赖于求解椭圆曲线离散对数问题的困难性，即已知椭圆曲线上的点P和kP计算k的困难程度。下图比较了目前计算椭圆曲线对数和分解大数因子的难度。可以看出，与RSA相比，ECC可以用小得多的密钥取得与RSA相同的安全性。另外，在密钥大小相等时，ECC与RSA所需要的计算量相当。因此，在安全性相当的情况下，使用ECC比使用RSA具有计算上的优势。两者都可以用于加解密、密钥交换和数字签名。20椭圆曲线和RSA安全性的比较密钥大小150205234MIPS年3.8*10107.1*10181.6*1028密钥大小5127681024128015362048MIPS年3*1042*1083*10111*10143*10163*1020MIPS:21T=(p，a，b，G，n，h)。（p、a、b用来确定一条椭圆曲线，G为基点，n为点G的阶，h是椭圆曲线上所有点的个数m与n相除的整数部分）这几个参量取值的选择，直接影响了加密的安全性。参量值一般要求满足以下几个条件：1、p当然越大越安全，但越大，计算速度会变慢，200位左右可以满足一般安全要求；2、p≠n×h；3、pt≠1(modn)，1≤t20；4、4a3+27b2≠0(modp)；5、n为素数；6、h≤4。密码学描述一条Fp上的椭圆曲线用到六个参量：22椭圆曲线在软件注册保护的应用将公开密钥算法作为软件注册算法的好处是Cracker很难通过跟踪验证算法得到注册机。软件作者按如下方法制作注册机（也称为签名过程）1、选择一条椭圆曲线Ep(a,b)，和基点G；2、选择私有密钥nA（nAn，n为G的阶），利用基点G计算公开密钥PA=nAG；3、产生一个随机整数k（kn），计算点R=kG；4、将用户名和点R的坐标值x,y作为参数，计算SHA（SecureHashAlgorithm安全散列算法，类似于MD5）值，即Hash=SHA(username,x,y)；5、计算sn≡k－Hash*nA(modn)6、将sn和Hash作为用户名username的序列号23软件验证过程如下：（软件中存有椭圆曲线Ep(a,b)，和基点G，公开密钥PA）1、从用户输入的序列号中，提取sn以及Hash；2、计算点R≡sn*G+Hash*PA(modp)，如果sn、Hash正确，其值等于软件作者签名过程中点R(x,y)的坐标，因为sn≡k-Hash*nA（modn）所以sn*G+Hash*PA=(k-Hash*nA)*G+Hash*PA=kG-Hash*nAG+Hash*PA=kG-Hash*PA+Hash*PA=kG=R；3、将用户名和点R的坐标值x,y作为参数，计算H=SHA(username,x,y)；4、如果H=Hash则注册成功。如果H≠Hash，则注册失败(为什么？提示注意点R与Hash的关联性)。24作者签名用到：椭圆曲线Ep(a,b)，基点G，私有密钥nA，及随机数k。软件验证用到：椭圆曲线Ep(a,b)，基点G，公开密钥PA。Cracker要想制作注册机，只能通过软件中的Ep(a,b)，点G，公开密钥PA，并利用PA=nAG这个关系获得nA后，才可以。而求nA是很困难的。简单对比一下两个过程：