ecc.zip_ECC算法_ecc 椭圆曲线_ecc算法参数_椭圆 加密_椭圆曲线加密算法

/* 加密得法： 现在我们描述一个利用椭圆曲线进行加密通信的过程： 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（编码方法很多，这里不作讨论），并产生一个随机整数r（r<n）。 5、用户B计算点C1=M+rK；C2=rG。 6、用户B将C1、C2传给用户A。 7、用户A接到信息后，计算C1-kC2，结果就是点M。因为 C1-kC2=M+rK-k(rG)=M+rK-r(kG)=M 再对点M进行解码就可以得到明文。 在这个加密通信中，如果有一个偷窥者H ，他只能看到Ep(a,b)、K、G、C1、C2 而通过K、G 求k 或通过C2、G求r 都是相对困难的。因此，H无法得到A、B间传送的明文信息。 密码学中，描述一条Fp上的椭圆曲线，常用到六个参量： T=(p,a,b,G,n,h)。 （p 、a 、b 用来确定一条椭圆曲线， G为基点， n为点G的阶， h 是椭圆曲线上所有点的个数m与n相除的整数部分） 这几个参量取值的选择，直接影响了加密的安全性。参量值一般要求满足以下几个条件： 1、p 当然越大越安全，但越大，计算速度会变慢，200位左右可以满足一般安全要求； 2、p≠n×h； 3、pt≠1 (mod n)，1≤t<20； 4、4a3+27b2≠0 (mod p)； 5、n 为素数； 6、h≤4。 签名算法： 签名过程 1、选择一条椭圆曲线Ep(a,b)，和基点G； 2、选择私有密钥k（k<n，n为G的阶），利用基点G计算公开密钥K=kG； 3、产生一个随机整数r（r<n），计算点R=rG； 4、将用户名和点R的坐标值x,y作为参数，计算SHA（Secure Hash Algorithm 安全散列算法，类似于MD5）值，即Hash=SHA(username,x,y)； 5、计算sn≡r - Hash * k (mod n) 6、将sn和Hash作为 用户名username的序列号 认证过程（认证方存有椭圆曲线Ep(a,b)，和基点G，公开密钥K） 1、从用户输入的序列号中，提取sn以及Hash； 2、计算点R≡sn*G+Hash*K ( mod p )，如果sn、Hash正确，其值等于软件作者签名过程中点R(x,y)的坐标，因为 sn≡r-Hash*k （mod n） 所以 sn*G + Hash*K =(r-Hash*k)*G+Hash*K =rG-Hash*kG+Hash*K =rG- Hash*K+ Hash*K =rG=R ； 3、将用户名和点R的坐标值x,y作为参数，计算H=SHA(username,x,y)； 4、如果H=Hash 则注册成功。如果H≠Hash ，则注册失败(为什么？提示注意点R与Hash的关联性)。 简单对比一下两个过程： 作者签名用到了：椭圆曲线Ep(a,b)，基点G，私有密钥k，及随机数r。 软件验证用到了：椭圆曲线Ep(a,b)，基点G，公开密钥K。 Cracker要想制作注册机，只能通过软件中的Ep(a,b)，点G，公开密钥K ，并利用K=kG这个关系获得k后，才可以。而求k是很困难的。 */ #include <stdio.h> #include <string.h> #include <stdlib.h> #include <iostream.h> #include "tommath.h" #include <time.h> #define BIT_LEN 800 #define KEY_LONG 128 //私钥比特长 #define P_LONG 200 //有限域P比特长 #define EN_LONG 40 //一次取明文字节数(x,20)(y,20) #define Max 0xfff //得到lon比特长素数 int GetPrime(mp_int *m,int lon); //得到B和G点X坐标G点Y坐标 void Get_B_X_Y(mp_int *x1,mp_int *y1,mp_int *b, mp_int *a, mp_int *p); //点乘 bool Ecc_points_mul(mp_int *qx,mp_int *qy, mp_int *px, mp_int *py,mp_int *d,mp_int *a,mp_int *p); //点加 int Two_points_add(mp_int *x1,mp_int *y1,mp_int *x2,mp_int *y2,mp_int *x3,mp_int *y3,mp_int *a,bool zero,mp_int *p); //二进制存储密文 int chmistore(mp_int *a,FILE *fp); //把读取的字符存入mp_int型数 int putin(mp_int *a,char *ch,int chlong); //ECC加密 void Ecc_encipher(mp_int *qx,mp_int *qy, mp_int *px, mp_int *py,mp_int *a,mp_int *p); //ECC解密 void Ecc_decipher(mp_int *k, mp_int *a,mp_int *p); //实现将mp_int数a中的比特串还原为字符串并赋给字符串ch： int chdraw(mp_int *a,char *ch); //取密文 int miwendraw(mp_int *a,char *ch,int chlong); //生成密钥对 void SetKey(mp_int*QX,mp_int*QY,mp_int*GX,mp_int*GY,mp_int*sk,mp_int*n,mp_int*A,mp_int*B,mp_int*P); //检验密钥 bool CheckKey(mp_int*QX,mp_int*QY,mp_int*sk,mp_int*n,mp_int*A,mp_int*B,mp_int*P); int myrng(unsigned char *dst, int len, void *dat) { int x; for (x = 0; x < len; x++) dst[x] = rand() & 0xFF; return len; } char temp[800]; char *Check(mp_int *mp) { mp_toradix(mp,temp,16); return temp; } bool Ecc_points_mul(mp_int *qx,mp_int *qy, mp_int *px, mp_int *py,mp_int *d,mp_int *a,mp_int *p) { mp_int X1, Y1; mp_int X2, Y2; mp_int X3, Y3; mp_int XX1, YY1; mp_int A,P; int i; bool zero=false; char Bt_array[800]={0}; char cm='1'; mp_toradix(d,Bt_array,2); mp_init_set_int(&X3, 0); mp_init_set_int(&Y3, 0); mp_init_copy(&X1, px); mp_init_copy(&X2, px); mp_init_copy(&XX1, px); mp_init_copy(&Y1, py); mp_init_copy(&Y2, py); mp_init_copy(&YY1, py); mp_init_copy(&A, a); mp_init_copy(&P, p); for(i=1;i<=KEY_LONG-1;i++) { mp_copy(&X2, &X1); mp_copy(&Y2, &Y1); Two_points_add(&X1,&Y1,&X2,&Y2,&X3,&Y3,&A,zero,&P); mp_copy(&X3, &X2); mp_copy(&Y3, &Y2); if(Bt_array[i]==cm) { mp_copy(&XX1, &X1); mp_copy(&YY1, &Y1); Two_points_add(&X1,&Y1,&X2,&Y2,&X3,&Y3,&A,zero,&P); mp_copy(&X3, &X2); mp_copy(&Y3, &Y2); } } if(zero) { cout<<"It is Zero_Unit!"; return false;//如果Q为零从新产生D } mp_copy(&X3, qx); mp_copy(&Y3, qy); mp_clear(&X1); mp_clear(&Y1); mp_clear(&X2); mp_clear(&Y2); mp_clear(&X3); mp_clear(&Y3); mp_clear(&XX1); mp_clear(&YY1); mp_clear(&A); mp_clear(&P); return true; } bool Testy(mp_int *temp2, mp_int *y1,mp_int *p) { int ret; mp_is_square(temp2,&ret); if(ret) { mp_sqrt(temp2,y1); return true; } mp_add(temp2,p,temp2); mp_is_square(temp2,&ret); if(ret) { mp_sqrt(temp2,y1); return true; } mp_add(temp2,p,temp2); mp_is_square(temp2,&ret); if(ret) { mp_sqrt(temp2,y1); return true; } //printf("ret=%d\n",ret); return false; } static mp_int *n; int GetPrime(mp_int *n,int lon){ mp_prime_random_ex(n, 10, lon, (rand()&1)?LTM_PRIME_2MSB_OFF:LTM_PRIME_2MSB_ON, myrng, NULL); return MP_OKAY; } //两点加 int Two_points_add(mp_int *x1,mp_int *y1,mp_int *x2,mp_int *y2,mp_int *x3,mp_int *y3,mp_int *a,bool zero,mp_int *p) { mp_int x2x1; mp_int y2y1; mp_int tempk; mp_int tempy; mp_int tempzero; mp_int k; mp_int temp1; mp_int temp2; mp_int temp3; mp_int temp4; mp_int temp5; mp_int temp6; mp_int temp7; mp_int temp8; mp_int temp9; mp_int temp10; mp_init(&x2x1); mp_init(&y2y1); mp_init(&tempk); mp_init(&tempy); mp_init(&tempzero); mp_init(&k); mp_init(&temp1); mp_init(&temp2); mp_init_set(&temp3,2); mp_init(&temp4); mp_init(&temp5); mp_init(&temp6); mp_init(&temp7); mp_init(&temp8); mp_init(&temp9); mp_init(&temp10); if(zero) { mp_copy(x1, x3); mp_copy(y1, y3); zero=false; goto L; } mp_zero(&tempzero); mp_sub(x2, x1, &x2x1); if(mp_cmp(&x2x1,&tempzero)==-1) { mp_add(&x2x1, p, &temp1); mp_zero(&x2x1); mp_copy(&temp1, &x2x1); } mp_sub(y2, y1, &y2y1); if(mp_cmp(&y2y1,&tempzero)==-1) { mp_add(&y2y1, p, &temp2); mp_zero(&y2y1); mp_copy(&temp2, &y2y1); } if(mp_cmp(&x2x1, &tempzero)!=0) { mp_invmod(&x2x1,p,&tempk); mp_mulmod(&y2y1, &tempk, p, &k); } else { if(mp_cmp(&y2y1, &tempzero)==0) { mp_mulmod(&temp3,y1,p,&tempy); mp_invmod(&tempy,p,&tempk); mp_sqr(x1, &temp4); mp_mul_d(&temp4, 3, &temp5); mp_add(&temp5, a, &temp6); mp_mulmod(&temp6, &tempk, p, &k); } else { zero=true; goto L; } } mp_sqr(&k, &temp7); mp_sub(&temp7, x1, &temp8); mp_submod(&temp8, x2, p, x3); mp_sub(x1, x3, &temp9); mp_mul(&temp9, &k, &temp10); mp_submod(&temp10, y1, p, y3); L: mp_clear(&x2x1); mp_clear(&y2y1); mp_clear(&tempk); mp_clear(&tempy); mp_clear(&tempzero); mp_clear(&k); mp_clear(&temp1); mp_clear(&temp2); mp_clear(&temp3); mp_clear(&temp4); mp_clear(&temp5); mp_clear(&temp6); mp_cl