ECC加密算法.doc

c++简单的实现椭圆曲线加密算法椭圆曲线算法椭圆曲线密码体制来源于对椭圆曲线的研究,所谓椭圆曲线指的是由韦尔斯特拉斯(Weierstrass)方程:y2+a1xy+a3y=x3+a2x2+a4x+a6(1)所确定的平面曲线。其中系数ai(I=1,2,…,6)定义在某个域上,可以是有理数域、实数域、复数域,还可以是有限域GF(pr),椭圆曲线密码体制中用到的椭圆曲线都是定义在有限域上的。椭圆曲线上所有的点外加一个叫做无穷远点的特殊点构成的集合连同一个定义的加法运算构成一个Abel群。在等式mP=P+P+…+P=Q(2)中,已知m和点P求点Q比较容易,反之已知点Q和点P求m却是相当困难的,这个问题称为椭圆曲线上点群的离散对数问题。椭圆曲线密码体制正是利用这个困难问题设计而来。公钥算法是基于数学函数(如单向陷门函数),公钥密码体制根据其所依据的难题一般分为三类:大整数分解问题类、离散对数问题类、椭圆曲线类。本文是在素域Zp上的,以Menezes-Vanstone形式的椭圆加密算法。在素域上的曲线函数为y^2=x^3+a* x+b   a,b为小于p的非负数,且4*a^3+27*b^2!=0对于在素域上的加法中,对于所有的点P,Q属于E(Zp),有加法规则:1。P+O=O+P=P,P+(-P)=O;O为椭圆曲线上的零点或者称为无限远的点,但是O在椭圆曲线的加法域上。,对于s,t属于Zp,有(s+t)*P=s*P+t*P;=(x1,y1),Q=(x2,y2),并且P!=-Q,则P+Q=(x3,y3),x3=k^2-x1-x2;y3=k*(x1-x3)-y1;k=(y2-y1)/(x2-x1) ifP!=Q;k=(3x1^2+a)/(2*y1)ifP==Q;椭圆曲线在素域上的运算用到除法,而在除法的规则是a/b=cmodp即计算axb^-1=cmodp,其中b^-1为b的乘法逆元,即bxb^-1=1modp。对于乘法逆元,当b与p互素时,存在唯一解,而这里p是一个素数,且b不可能为1,则肯定有解。对于求乘法逆元,一般使用欧几里德算法,如下:intgetX_1(intx,intmod){ intQ,X1,X2,X3,Y1,Y2,Y3,T1,T2,T3; X1=1; X2=0; X3=mod; Y1=0; Y2=1; Y3=(x%mod+mod)%mod;//获得正整数 while(Y3!=1){ Q=X3/Y3; T1=X1-Q*Y1; T2=X2-Q*Y2; T3=X3-Q*Y3; X1=Y1; X2=Y2; X3=Y3; Y1=T1; Y2=T2; Y3=T3; } returnY2;}乘法运算规则:,有k*P=P+.....+P(k个P相加),t属于Zp,有s*(t*P)=(s*t)*P对于Menezes-Vanstone的椭圆加密算法:,任选一个整数k,0<k<p,为私钥,在曲线上任选一点A,并计算B=k*A,公钥为(A,,B)。其中又可称A为基钥,对于最小整数n以使n*A=O,则n称为周期,要是周期为素数,且为一个较大值才合理。:令明文为M=(m1,m2),M可以不是曲线E上的点。计算得到密文(C1,C2),其中任选一个数属于Zp:C1=r*A;;Y=(y1,y