椭圆曲线加密算法代码

椭圆曲线加密算法代码及解析

在椭圆曲线加密中，利用了某种特殊形式的椭圆曲线，即定义在有限域上的椭圆曲线。其方程如下： y2=x3+ax+b(mod p)

这里p是素数，a和b为两个小于p的非负整数，它们满足： 4a3+27b2(mod p)≠0 其中，x,y,a,b ∈Fp,则满足式（2）的点（x,y）和一个无穷点O就组成了椭圆曲线E。

椭圆曲线离散对数问题ECDLP定义如下：给定素数p和椭圆曲线E，对 Q=kP,在已知P,Q的情况下求出小于p的正整数k。

现在我们描述一个利用椭圆曲线进行加密通信的过程：

1、用户A选定一条椭圆曲线Ep(a,b)，并取椭圆曲线上一点，作为基点G。 2、用户A选择一个私有密钥k，并生成公开密钥K=kG。 3、用户A将Ep(a,b)和点K，G传给用户B。

4、用户B接到信息后 ，将待传输的明文编码到Ep(a,b)上一点M（将M转化为十进制整数m，然后令椭圆曲线中点的横坐标为m，根据曲线方程计算出纵坐标，便得到了一个点。），并产生一个随机整数r（r

7、用户A接到信息后，计算C1-kC2，结果就是点M。因为 C1-kC2=M+rK-k(rG)=M+rK-r(kG)=M 再对点M进行解码就可以得到明文。 过程分析： 1、 将给出的椭圆上的两点G,K相加求得第三点M。P跟Q有两种情况。分P=Q和P不等于Q时。 2、 求M的过程中进行求模运算。第一，将分数利用最小公倍数求模。第二，负数求模，先将负号拿出来，求完再将负号加上。根据公式将λ解出。 3、 将X3Y3求出。循环算出nG，求出C1C2（密文）。C1=rG，C2=M+rK。M为明文，公开密钥K=kG 代码部分：

#include

using namespace std;

//求两数的最小公倍数 int f1(int a, int b) {

int c=a;

while( c%a!=0 || c%b!=0) c++;

return c; }

//求mod

int mod (int a, int b) {

int c; if(a>0) c=a%b; else {

while(a

return c; }

//求λ

int f2(int x1,int y1,int x2,int y2,int a,int p) {

int b,b1,b2,q;//b1为分子，b2为分母 if( x1==x2 && y1==y2)//如果λ两点相等 {

b1=3*x1*x1+a; b2=2*y1; if(b1<0)

b1=-mod(-b1,p); else

b1=mod(b1,p); if(b2<0) {

b2=mod(-b2,p); q=-f1(b2,p+1)/b2; } else {

b2=mod(b2,p); q=f1(b2,p+1)/b2; }

b2=f1(b2,p+1)/b2; b=b1*b2; b=mod(b,p); }

else {

b1=y2-y1; b2=x2-x1; if(b1<0)

b1=-mod(-b1,p); else

b1=mod(b1,p); if(b2<0) {

b2=mod(-b2,p); q=-f1(b2,p+1)/b2; } else {

b2=mod(b2,p); q=f1(b2,p+1)/b2; }

b=b1*q; b=mod(b,p); }

return b; }

//求两点横坐标的和

intsumx(int x1,int y1,int x2,int y2,int k,inta,int p) {

int x3,y3,i; if(k==1) {

x3=(f2(x1,y1,x2,y2,a,p))*(f2(x1,y1,x2,y2,a,p))-x1-x2; x3=mod(x3,p); } else {

for(i=1;i<=k-1;i++) {

x3=(f2(x1,y1,x2,y2,a,p))*(f2(x1,y1,x2,y2,a,p))-x1-x2; x3=mod(x3,p);

y3=(f2(x1,y1,x2,y2,a,p)*(x1-x3))-y1; y3=mod(y3,p); x2=x1; x1=x3; y2=y1;