椭圆曲线密码体制E

《椭圆曲线密码体制E》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、椭圆曲线密码（ECC）体制一般椭圆曲线有限域上的椭圆曲线椭圆曲线密码算法椭圆曲线密码体制的安全性ELGamal密码体制能够在任何离散对数难处理的有限群中实现。我们已经使用了乘法群Zp*，但其他群也是合适的候选者，如椭圆曲线群。椭圆曲线在代数学和几何学上已广泛研究了150多年之久，有丰富而深厚的理论积累。椭圆曲线密码体制（EllipseCurveCryptosystem，ECC）在l985年由Koblitz和Miller提出，不过一直没有像RSA等密码系统一样受到重视。纵观目前的发展趋势，椭圆曲线已经逐渐被采用，很可能是一个重要的发展方

2、向。椭圆曲线并非椭圆，这么命名是因为它们是由三次方程描述的，而这些三次方程类似于计算椭圆周长的方程。一般的，描述椭圆曲线方程的形式是y2+axy+by=x3+cx2+dx+e其中a、b、c、d和e是满足一些简单条件的实数一般来说，椭圆曲线还包含了一个特殊的点，即称为无穷远点(PointatInfinity)或零点(ZeroPoint)的O。4.4.1一般椭圆曲线对于椭圆曲线上的点可以定义一种形式的加法：如果一个椭圆曲线上的三个点处于一条直线上，那么它们的和为O。从这个定义可以导出椭圆曲线上点的加法法则。(1)O是加法的单位元，因而O＝

3、－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。显然，根

4、据定义，此类加法满足交换率和结合率.而一个点的倍乘定义为nP＝P+P+P+……+P4.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)如取p＝23，a=b=l，有4*13+27*12(mo

5、d23)＝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))。椭圆曲线E23(1，1)上的点（0，1）（5，4）（9，7）（17，3）（0

6、，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)，并且P≠Q，则P+Q=(x3，y3)由下列规则确定:x3≡λ2–x1–x2(modp)y3≡λ(x

7、1–x3)–y1(modp)其中：(y2-y1)/(x2－x1)如果P≠Qλ=(3x12－a)/2y1如果P=Q例子：考虑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)椭圆曲线

8、群中的离散对数也属于难解问题。与通常理解的对数概念不同，由于椭圆曲线群中的运算是加法，加法的倍数对应于原来乘法的指数，因而椭圆曲线群中的离散对数问题是指已知群中的Q和R，求解方程：R＝kQ中k值的问题。对基于F23的椭圆