/*椭圆曲线公钥密码系统*/
#include<stdio.h>
struct point
{
int xp;
int yp;
};
/*求倒数*/
int egcd(int a,int b)
{
if(b<0) b=b%a+a;
int c=0;
int d=1;
int q=a/b;
int r=a%b;
int temp;
int mod=a;
while(r!=0)
{
temp=(c-q*d)%mod;
c=d;
d=temp;
a=b;
b=r;
q=a/b;
r=a%b;
}
return (d<0)?(d+mod):d;
}
/*点的幂运算*/
struct point power(struct point po,int n,int a,int p)
{
if(n<=1) return po;
else
{
int t=0;
int x=po.xp;
int y=po.yp;
int temp=0;
int x1=x;
int y1=y;
/*算出平方*/
if(((3*x*x+a)%(2*y))!=0) t=((3*x*x+a)*egcd(p,2*y))%p;
else t=((3*x*x+a)/(2*y))%p;
if(t<0) t=t+p;
temp=x;
int x2=(t*t-temp-temp)%p;
if(x2<0) x2=x2+p;
int y2=(t*(temp-x2)-y)%p;
if(y2<0) y2=y2+p;
n=n-2;
x=x2;
y=y2;
/*每次乘以点的平方*/
while(n>=2)
{
temp=x;
if(x==x2 && y+y2==p)
{
x=x2;
y=y2;
n=n-2;
}
else if(x!=x2||y!=y2)
{
if(((y2-y)%(x2-x))!=0) t=((y2-y)*egcd(p,x2-x))%p;
else t=((y2-y)/(x2-x))%p;
x=(t*t-temp-x2)%p;
if(x<0) x=x+p;
y=(t*(temp-x)-y)%p;
}
else if(x==x2||y==y2)
{
if(((3*x*x+a)%(2*y))!=0) t=((3*x*x+a)*egcd(p,2*y))%p;
else t=((3*x*x+a)/(2*y))%p;
x=(t*t-temp-x2)%p;
if(x<0) x=x+p;
y=(t*(temp-x)-y)%p;
}
if(y<0) y=y+p;
n=n-2;
}
if(n==1)
{
temp=x;
if(x!=x1||y!=y1)
{
if(((y1-y)%(x1-x))!=0) t=((y1-y)*egcd(p,x1-x))%p;
else t=((y1-y)/(x1-x))%p;
x=(t*t-temp-x1)%p;
if(x<0) x=x+p;
y=(t*(temp-x)-y)%p;
}
else if(x==x1||y==y1)
{
if(((3*x*x+a)%(2*y))!=0) t=((3*x*x+a)*egcd(p,2*y))%p;
else t=((3*x*x+a)/(2*y))%p;
x=(t*t-temp-x1)%p;
if(x<0) x=x+p;
y=(t*(temp-x)-y)%p;
}
if(y<0) y=y+p;
}
struct point b={x,y};
return b;
}
}
/*主函数*/
int main()
{
int p;
int c,d;
printf("请输入椭圆曲线方程y^2=x^3+cx+d(mod p)中c,d,p的值:");
scanf("%d,%d,%d",&c,&d,&p);
printf("椭圆曲线方程为y^2=x^3+%dx+%d(mod%d)\n",c,d,p);
/*取明文*/
struct point x;
printf("请输入所取明文x的x1,x2:");
scanf("%d,%d",&x.xp,&x.yp);
int x1,x2;
x1=x.xp;
x2=x.yp;
/*选择椭圆曲线上的点*/
struct point a0;
printf("请输入选择的椭圆曲线上的点a0的x,y:");
scanf("%d,%d",&a0.xp,&a0.yp);
/*加密*/
struct point b0,y0,c0;
int a,t;
/*取私钥a的值和选取t的值*/
printf("请输入私钥a=");
scanf("%d",&a);
printf("选取t=");
scanf("%d",&t);
b0=power(a0,a,c,p);
y0=power(a0,t,c,p);
c0=power(b0,t,c,p);
int c1,c2;
c1=c0.xp;
c2=c0.yp;
int y1,y2;
y1=(x1*c1)%p;
y2=(x2*c2)%p;
printf("加密的结果是(y0,y1,y2) = ((%d,%d),%d,%d)\n",y0.xp,y0.yp,y1,y2);
/*解密*/
c0=power(y0,a,c,p);
c1=c0.xp;
c2=c0.yp;
x1=(y1*egcd(p,c1))%p;
x2=(y2*egcd(p,c2))%p;
printf("实施解密:\n(c1,c2)=(%d,%d)\nx1=%d\nx2=%d\n",c1,c2,x1,x2);
getchar();
getchar();
return 0;
}
评论14