椭圆曲线算法

椭圆曲线密码体制来源于对椭圆曲线的研究，所谓椭圆曲线指的是由韦尔斯特拉斯（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在椭圆曲线的加法域上。

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

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 * 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进行加密，效果不佳

#include "stdafx.h"
#include <string>
#include <iostream>
using namespace std;
const int k = 9;
const int a = 5;
const int b = 37;
const int p = 127;
const int r =7;

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;
}//获得其乘法逆元

struct point{
	int x;
	int y;
};
point A,B;//公钥
typedef pair<point,point> twopoint;
bool operator == (point pa,point pb){
	return pa.x == pb.x && pa.y == pb.y;
}
point operator + (point pa , point pb){
	int k;
	
	if(pa == pb)
		k = ((3 * pa.x * pa.x + a) * getX_1(2* pa.y ,p)) % p ;//必须使用正整数。这里pa.y的值不能取0.
	//当取0时，这就不能进行这个计算了，因为 pa = -pb了，则，应该进行一个判断。但是，这样的结果是 O，是不在椭圆曲线上的，不能进行输出的值。
	//这里是有一个周期数在，对于容易一个基值的也就是先给出的A来说，它有一个周期n，使nA = O，而这里所有参数的选取值
	//都小于n，使其不会达到O，保证了不会出错，应该是这样吧。。。
	else
		k = (pb.y - pa.y) * getX_1(pb.x - pa.x , p) %p;
		point c;
		c.x = (k*k - pa.x -pb.x) %p;
		c.y = (k * (pa.x - c.x) - pa.y)%p ;
		c.x = (c.x + p) %p; 
		c.y = (c.y + p) %p; 
		
		return c;
}
point operator * (point &b,int n){
		point q = b;
		n = n -1;
		for(int i = 1 ; i < n;i++){
			q = q + b ;
		}
		return q;
}
twopoint ECodePoint(point m){
	point c1,c2;
	c1 = A * r ;
	point Y = B * r ;
	c2.x = Y.x * m.x % p ;
	c2.y = Y.y * m.y % p ;
	return twopoint(c1,c2);
}
point DCodePoint(twopoint t){
	point Z = t.first * k;
	point m;
	m.x = t.second.x * getX_1(Z.x,p) % p ;
	m.y = t.second.y * getX_1(Z.y,p) % p ;
	return m;
}
string ECode(string input){//明文的输入是一个string类型，但是单个的操作应该是对单个的字符char转换成的int类型进行计算
	string output = "";
	point M;
	twopoint C;
	for(int i =0; i < input.length();i++){
		M.x = i;
		M.y = input[i];
		C = ECodePoint(M);
		output += (char)C.first.x ;
		output += (char)C.first.y ;
		output += (char)C.second.x ;
		output += (char)C.second.y ;
	}

	return output;
}
string DCode(string input){
	string output = "";
	point M;
	twopoint C;
	if(input.length()%4 != 0)
		return "错误输入";//因为密文肯定是4的倍数，如果不是，肯定出错了。
	for(int i = 0;i < input.length();){
		C.first.x = input[i++];
		C.first.y = input[i++];
		C.second.x = input[i++];
		C.second.y = input[i++];
		M = DCodePoint(C);
		output += (char)M.y;
	}
	return output;
}

int main()
{
	A.x = 11;
	A.y = 4;
	B = A*k;
	string s = "";
	//加密简单，随便输入点东西就可以加密了，但是解密不行啊，随便输入肯定是错误的结果，
	//程序肯定会出错，所以，只支持对之前加密的结果进行解密。
	cout<<"使用在素域上的曲线 y^2 = x^3 + 5*x +37   ，使用Menezes-Vanstone的算法："<<endl;
	cout<<"在素域p=127上，私钥为k=9,公钥A(11,4),B(120,41),对明文字符串直接转换为int进行加密"<<endl;
	cout<<"请输入要加密的内容："<<endl;
	cin>>s;
	cout<<"密文如下："<<"\r\n";
	s = ECode(s);
	cout<<s<<endl;
	cout<<"对之前密文解密，得到明文如下（由于输入密文不正确绝对会使这个程序出错，所以只能解密绝对安全的密文）："<<"\r\n";
	s = DCode(s);
	cout<<s<<"\r\n"<<"完成"<<endl;
	cin>>s;
	return 0;
}