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却是相当困难的，这个问题称为椭圆曲线上点群的离散对数问题。椭圆曲线密码体制正是利用这个困难问题设计而来。

公钥算法是基于数学函数（如单向陷门函数），公钥密码体制根据其所依据的难题一般分为三类：大整数分解问题类、离散对数问题类、椭圆曲线类。

在素域上的曲线函数为

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在椭圆曲线的加法域上。

2.加法的分配率和结合律，对于s,t 属于zp,有（s + t ）* p = s * p + t* p;

3.对于 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，则肯定有解。对于求乘法逆元，一般使用欧几里德算法，如下：

乘法运算规则：

1. 对于任意 k 属于 zp，有 k * p = p + ..... + p (k个p相加）

2. 对于任意 s,t 属于 zp，有 s *(t *p) = (s*t)*p

对于menezes-vanstone的椭圆加密算法：

1. 产生密钥，

任选一个整数k ,0<k<p ,为私钥，在曲线上任选一点 a ，并计算 b = k*a ，公钥为（a,，b）。其中又可称a为基钥，对于最小整数n以使 n* a = o ，则n称为周期，要是周期为素数，且为一个较大值才合理。

2.加密过程：

令明文为 m = (m1,m2),m可以不是曲线e上的点。计算得到密文(c1,c2),其中任选一个数属于zp：

c1 = r * a;；

y= （y1,y2) = r * b;

c2 = (c21,c22) = (y1 * m1 mod p,y2* m2 mod p)

3 解密过程；

计算z = (z1,z2) = k*c1;计算明文 m = (c21 * z1^-1 mod p, c22 * z2 ^ -1 mod p).

c++中的模运算，当有负数存在时无法达到正确结果，简直是坑，如 -1 % 2，在使用vs2012进行测试，会返回-1，而不是1. c++中模运算结果的符号和被除数的符号一致。

参数选取：选取 p = 127,曲线函数为: y^2 = x^3 + 5* x + 37， a = 5 ,b= 37， r = 7.选取私钥 k = 9选取一个点a为（11,4)则 b = k*a = (120,41)

则源代码如下，这里直接对char进行加密，效果不佳