ECC加密算法

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

乘法运算规则：

1. 对于任意 k 属于 Zp，有 k * P = P + ..... + P (k个P相加） 2. 对于任意 s,t 属于 Zp，有 s *(t *P) = (s*t)*P

对于Menezes-Vanstone的椭圆加密算法： 1. 产生密钥，

任选一个整数k ,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;

令明文为 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 \#include #include 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 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的算法：\ cout<<\在素域p=127上，私钥为k=9,公钥A(11,4),B(120,41),对明文字符串直接转换为int进行加密\ cout<<\请输入要加密的内容：\

cin>>s;

cout<<\密文如下：\ s = ECode(s); cout<>s; return 0; }

范围 本标准规定了龙腾公司合同管理工作的管理机构、职责、合同的授权委托、洽谈、承办、会签、订阅、履行和变更、终止及争议处理和合同管理的处罚、奖励；本标准适用于龙腾公司项目建设期间的各类合同管理工作，厂内各类合同的管理，厂内所属各具法人资格的部门，参照本标准执行。规范性引用 《中华人民共和国合同法》 《龙腾公司合同管理办法》 定义、符号、缩略语 无 职责 总经理：龙腾公司经营管理的法定代表人。负责对厂内各类合同管理工作实行统一领导。以法人代表名义或授权委托他人签订各类合法合同，并对电厂负责。工程部：是发电厂建设施工安装等工程合同签订管理部门；负责签订管理基建、安装、人工技术的工程合同。经营部：是合同签订管理部门，负责管理设备、材料、物资的订购合同。合同管理部门履行以下职责： 建立健全合同管理办法并逐步完善规范；参与合同的洽谈、起草、审查、签约、变更、解除以及合同的签证、公证、调解、诉讼等活动，全程跟踪和检查合同的履行质量；审查、登记合同对方单位代表资格及单位资质，包括营业执照、经营范围、技术装备、信誉、越区域经营许可等证件及履约能力（必要时要求对方提供担保），检查合同的履行情况；保管法人代表授权委托书、合同专用章，并按编号归口使用；建立合同管理台帐，对合同文本资料进行编号统计管理；合同管理制度

1 2 3 4 4.1 4.2 4.3 4.5 4.5.1 4.5.2 4.5.3 4.5.4 4.5.5 4.5.6 组织对法规、制度的学习和贯彻执行，定期向有关领导和部门报告工作； 4.5.7 在总经理领导下，做好合同管理的其他工作， 4.6 工程技术部：专职合同管理员及材料、燃料供应部兼职合同管理员履行以下职责： 4.6.1 在主任领导下，做好本部门负责的各项合同的管理工作，负责保管“法人授权委托书”； 4.6.2 签订合同时，检查对方的有关证件，对合同文本内容依照法规进行检查，检查合同标的数量、金额、日期、地点、质量要求、安全责任、违约责任是否明确，并提出补充及修改意见。重大问题应及时向有关领导报告，提出解决方案； 4.6.3 对专业对口的合同统一编号、登记、建立台帐，分类整理归档。对合同承办部门提供相关法规咨询和日常协作服务工作； 4.6.4 工程技术部专职合同管理员负责收集整理各类合同，建立合同统计台帐，并负责

本文来源：https://www.bwwdw.com/article/3ly6.html