密码学实验&＃xff1a;ECC算法实现
1.实验内容
2.运行结果&＃xff1a;
1.椭圆曲线上的点集
2.椭圆曲线生成元以及对应的阶
3.加解密算法
代码如下&＃xff1a;
/*
(1)编程计算该椭圆曲线上所有在有限域GF(89)上的点&＃xff1b;
(2)编程实现椭圆曲线上任意一个点P(例如P&＃61;(12,5))的倍点运算的递归算法&＃xff0c;即计算k*P( k&＃61;2,3,…)&＃xff1b;(重点&＃xff01;)
(3)利用此递归算法找出椭圆曲线上的所有生成元G以及它们的阶n&＃xff0c;即满足n*G&＃61;O&＃xff1b;
(4)设计实现某一用户B的公钥、私钥算法&＃xff0c;即得到public key&＃61;(n, G, PB, Ep(a, b))
secure key&＃61;nB(小于n)
(5)假如用户A发送明文消息“yes”并加密传输给用户B&＃xff0c;用户B接收消息后要能解密为明文。试用ECC密码体制实现此功能。
*/
#include
#include
#include
#include
#include
#define MAX 100
typedef struct point{
int point_x;
int point_y;
}Point;
typedef struct ecc{
struct point p[MAX];
int len;
}ECCPoint;
typedef struct generator{
Point p;
int p_class;
}GENE_SET;
void get_all_points();
int int_sqrt(int s);
Point timesPiont(int k,Point p);
Point add_two_points(Point p1,Point p2);
int inverse(int n,int b);
void get_generetor_class();
void encrypt_ecc();
void decrypt_ecc();
int mod_p(int s);
void print();
int isPrime(int n);
char alphabet[26]&＃61;"abcdefghijklmnopqrstuvwxyz";
int a&＃61;-1,b&＃61;0,p&＃61;89;//椭圆曲线为E89(-1,0)&＃xff1a; y2&＃61;x3-x (mod 89)
ECCPoint eccPoint;
GENE_SET geneSet[MAX];
int geneLen;
char plain[]&＃61;"yes";
int m[MAX];
int cipher[MAX];
int nB;//私钥
Point P1,P2,Pt,G,PB;
Point Pm;
int C[MAX];
int main()
{
get_generetor_class();
encrypt_ecc();
decrypt_ecc();
return 0;
}
//task4:加密
void encrypt_ecc()
{
int num,i,j;
int gene_class;
int num_t;
int k;
srand(time(NULL));
//明文转换过程
for(i&＃61;0;i
{
for(j&＃61;0;j<26;j&＃43;&＃43;) //for(j&＃61;0;j<26;j&＃43;&＃43;)
{
if(plain[i]&＃61;&＃61;alphabet[j])
{
m[i]&＃61;j;//将字符串明文换成数字&＃xff0c;并存到整型数组m里面
}
}
}
//选择生成元
num&＃61;rand()%geneLen;
gene_class&＃61;geneSet[num].p_class;
while(isPrime(gene_class)&＃61;&＃61;-1)//不是素数
{
num&＃61;rand()%(geneLen-3)&＃43;3;
gene_class&＃61;geneSet[num].p_class;
}
//printf("gene_class&＃61;%dn",gene_class);
G&＃61;geneSet[num].p;
//printf("G:(%d,%d)n",geneSet[num].p.point_x,geneSet[num].p.point_y);
nB&＃61;rand()%(gene_class-1)&＃43;1;//选择私钥
PB&＃61;timesPiont(nB,G);
printf("n公钥&＃xff1a;n");
printf("{y^2&＃61;x^3%d*x&＃43;%d,%d,(%d,%d),(%d,%d)}n",a,b,gene_class,G.point_x,G.point_y,PB.point_x,PB.point_y);
printf("私钥&＃xff1a;n");
printf("nB&＃61;%dn",nB);
//加密
//
k&＃61;rand()%(gene_class-2)&＃43;1;
P1&＃61;timesPiont(k,G);
//
num_t&＃61;rand()%eccPoint.len; //选择映射点
Pt&＃61;eccPoint.p[num_t];
//printf("Pt:(%d,%d)n",Pt.point_x,Pt.point_y);
P2&＃61;timesPiont(k,PB);
Pm&＃61;add_two_points(Pt,P2);
printf("加密数据&＃xff1a;n");
printf("kG&＃61;(%d,%d),Pt&＃43;kPB&＃61;(%d,%d),C&＃61;{",P1.point_x,P1.point_y,Pm.point_x,Pm.point_y);
for(i&＃61;0;i
{
//num_t&＃61;rand()%eccPoint.len; //选择映射点
//Pt&＃61;eccPoint.p[num_t];
C[i]&＃61;m[i]*Pt.point_x&＃43;Pt.point_y;
printf("{%d}",C[i]);
}
printf("}n");
}
//task5:解密
void decrypt_ecc()
{
Point temp,temp1;
int m,i;
temp&＃61;timesPiont(nB,P1);
temp.point_y&＃61;0-temp.point_y;
temp1&＃61;add_two_points(Pm,temp);//求解Pt
//printf("(%d,%d)n",temp.point_x,temp.point_y);
//printf("(%d,%d)n",temp1.point_x,temp1.point_y);
printf("n解密结果&＃xff1a;n");
for(i&＃61;0;i
{
m&＃61;(C[i]-temp1.point_y)/temp1.point_x;
printf("%c",alphabet[m]);//输出密文
}
printf("n");
}
//判断是否为素数
int isPrime(int n)
{
int i,k;
k &＃61; sqrt(n);
for (i &＃61; 2; i <&＃61; k;i&＃43;&＃43;)
{
if (n%i &＃61;&＃61; 0)
break;
}
if (i <&＃61;k){
return -1;
}
else {
return 0;
}
}
//task3:求生成元以及阶
void get_generetor_class()
{
int i,j&＃61;0;
int count&＃61;1;
Point p1,p2;
get_all_points();
//p1.point_x&＃61;p2.point_x&＃61;3;
//p1.point_y&＃61;p2.point_y&＃61;2;
//while(1)
//{
//printf("(%d,%d)&＃43;(%d,%d)---%dn",p1.point_x,p1.point_y,p2.point_x,p2.point_y,count);
//p2&＃61;add_two_points(p1,p2);
//count&＃43;&＃43;;
//if(p2.point_x&＃61;&＃61;-1 && p2.point_y&＃61;&＃61;-1)
//{
//break;
//}
//}
//printf("nn(%d,%d)---%dn",p1.point_x,p1.point_y,count);
//
//do{
//printf("(%d,%d)&＃43;(%d,%d)---%dn",p1.point_x,p1.point_y,p2.point_x,p2.point_y,count);
//p2&＃61;add_two_points(p1,p2);
//count&＃43;&＃43;;
//
//} while(!((p2.point_x&＃61;&＃61;p1.point_x)&&(p2.point_y&＃61;&＃61;p1.point_y)));
//printf("(%d,%d)&＃43;(%d,%d)---%dn",p1.point_x,p1.point_y,p2.point_x,p2.point_y,count);
//count &＃43;&＃43; ;
//printf("nn(%d,%d)---%dn",p1.point_x,p1.point_y,count);
printf("n**********************************输出生成元以及阶&＃xff1a;*************************************n");
for(i&＃61;0;i
{
count&＃61;1;
p1.point_x&＃61;p2.point_x&＃61;eccPoint.p[i].point_x;
p1.point_y&＃61;p2.point_y&＃61;eccPoint.p[i].point_y;
while(1)
{
p2&＃61;add_two_points(p1,p2);
if(p2.point_x&＃61;&＃61;-1 && p2.point_y&＃61;&＃61;-1)
{
break;
}
count&＃43;&＃43;;
if(p2.point_x&＃61;&＃61;p1.point_x)
{
break;
}
}
count&＃43;&＃43;;
if(count<&＃61;eccPoint.len&＃43;1)
{
geneSet[j].p.point_x&＃61;p1.point_x;
geneSet[j].p.point_y&＃61;p1.point_y;
geneSet[j].p_class&＃61;count;
printf("(%d,%d)--->>%dt",geneSet[j].p.point_x,geneSet[j].p.point_y,geneSet[j].p_class);
j&＃43;&＃43;;
if(j % 6 &＃61;&＃61;0){
printf("n");
}
}
geneLen&＃61;j;
}
}
//task2:倍点运算的递归算法
Point timesPiont(int k,Point p0)
{
if(k&＃61;&＃61;1){
return p0;
}
else if(k&＃61;&＃61;2){
return add_two_points(p0,p0);
}else{
return add_two_points(p0,timesPiont(k-1,p0));
}
}
//两点的加法运算
Point add_two_points(Point p1,Point p2)
{
long t;
int x1&＃61;p1.point_x;
int y1&＃61;p1.point_y;
int x2&＃61;p2.point_x;
int y2&＃61;p2.point_y;
int tx,ty;
int x3,y3;
int flag&＃61;0;
//求
if((x2&＃61;&＃61;x1)&& (y2&＃61;&＃61;y1) )
{
//相同点相加
if(y1&＃61;&＃61;0)
{
flag&＃61;1;
}else{
t&＃61;(3*x1*x1&＃43;a)*inverse(p,2*y1) % p;
}
//printf("inverse(p,2*y1)&＃61;%dn",inverse(p,2*y1));
}else{
//不同点相加
ty&＃61;y2-y1;
tx&＃61;x2-x1;
while(ty<0)
{
ty&＃43;&＃61;p;
}
while(tx<0)
{
tx&＃43;&＃61;p;
}
if(tx&＃61;&＃61;0 && ty !&＃61;0)
{
flag&＃61;1;
}else{
t&＃61;ty*inverse(p,tx) % p;
}
}
if(flag&＃61;&＃61;1)
{
p2.point_x&＃61;-1;
p2.point_y&＃61;-1;
}else{
x3&＃61;(t*t-x1-x2) % p;
y3&＃61;(t*(x1-x3)-y1) % p;
//使结果在有限域GF(P)上
while(x3<0)
{
x3&＃43;&＃61;p;
}
while(y3<0)
{
y3&＃43;&＃61;p;
}
p2.point_x&＃61;x3;
p2.point_y&＃61;y3;
}
return p2;
}
//求b关于n的逆元
int inverse(int n,int b)
{
int q,r,r1&＃61;n,r2&＃61;b,t,t1&＃61;0,t2&＃61;1,i&＃61;1;
while(r2>0)
{
q&＃61;r1/r2;
r&＃61;r1%r2;
r1&＃61;r2;
r2&＃61;r;
t&＃61;t1-q*t2;
t1&＃61;t2;
t2&＃61;t;
}
if(t1>&＃61;0)
return t1%n;
else{
while((t1&＃43;i*n)<0)
i&＃43;&＃43;;
return t1&＃43;i*n;
}
}
//task1:求出椭圆曲线上所有点
void get_all_points()
{
int i&＃61;0;
int j&＃61;0;
int s,y&＃61;0;
int n&＃61;0,q&＃61;0;
int modsqrt&＃61;0;
int flag&＃61;0;
if (4 * a * a * a &＃43; 27 * b * b !&＃61; 0)
{
for(i&＃61;0;i<&＃61;p-1;i&＃43;&＃43;)
{
flag&＃61;0;
n&＃61;1;
y&＃61;0;
s&＃61; i * i * i &＃43; a * i &＃43; b;
while(s<0)
{
s&＃43;&＃61;p;
}
s&＃61;mod_p(s);
modsqrt&＃61;int_sqrt(s);
if(modsqrt!&＃61;-1)
{
flag&＃61;1;
y&＃61;modsqrt;
}else{
while(n<&＃61;p-1)
{
q&＃61;s&＃43;n*p;
modsqrt&＃61;int_sqrt(q);
if(modsqrt!&＃61;-1)
{
y&＃61;modsqrt;
flag&＃61;1;
break;
}
flag&＃61;0;
n&＃43;&＃43;;
}
}
if(flag&＃61;&＃61;1)
{
eccPoint.p[j].point_x&＃61;i;
eccPoint.p[j].point_y&＃61;y;
j&＃43;&＃43;;
if(y!&＃61;0)
{
eccPoint.p[j].point_x&＃61;i;
eccPoint.p[j].point_y&＃61;(p-y) % p;
j&＃43;&＃43;;
}
}
}
eccPoint.len&＃61;j;//点集个数
print(); //打印点集
}
}
//取模函数
int mod_p(int s)
{
int i;//保存s/p的倍数
int result;//模运算的结果
i &＃61; s / p;
result &＃61; s - i * p;
if (result >&＃61; 0)
{
return result;
}
else
{
return result &＃43; p;
}
}
//判断平方根是否为整数
int int_sqrt(int s)
{
int temp;
temp&＃61;(int)sqrt(s);//转为整型
if(temp*temp&＃61;&＃61;s)
{
return temp;
}else{
return -1;
}
}
//打印点集
void print()
{
int i;
int len&＃61;eccPoint.len;
printf("n该椭圆曲线上共有%d个点(包含无穷远点)n",len&＃43;1);
for(i&＃61;0;i
{
if(i % 8&＃61;&＃61;0)
{
printf("n");
}
printf("(%2d,%2d)t",eccPoint.p[i].point_x,eccPoint.p[i].point_y);
}
printf("n");
}
京公网安备 11010802041100号