ECC加密算法.doc

c++ 容易的实现椭圆曲线加密算法
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;
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)   if P != Q;
k = (3x1^2 + a)/(2*y1) if P == Q;
椭圆曲线在素域上的运算用到除法,而在除法的规则是a / b = c mod p 即计算 a x b^-1 = c mod p ,其中 b^-1为b的乘法逆元, 即 b x b^-1 = 1 mod p。对于乘法逆元,当b与p互素时,存在唯一解,而这里p是一个素数,且b不可能为1,则肯定有解。对于求乘法逆元,一般使用欧几里德算法,如下:
int getX_1(int x,int mod){
int Q,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;
}
return Y2;
}
乘法运算规则:
1. 对于任意 k 属于 Zp,有 k