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

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