RSA.rar_非对称加密_非对称算法

#include<stdio.h> #include<string.h> #include <stdlib.h> #include <time.h> #include <math.h> #include <malloc.h> #define MAX 100 #define LEN sizeof(struct slink) void sub(int a[MAX],int b[MAX] ,int c[MAX] ); struct slink { int bignum[MAX]; /*bignum[98]用来标记正负号，1正，0负bignum[99]来标记实际长度*/ struct slink *next; }; /*********************RSA大数运算***********************/ void print( int a[MAX] ) { int i; for(i=0;i<a[99];i++) printf("%d",a[a[99]-i-1]); printf("\n"); return; } int cmp(int a1[MAX],int a2[MAX]) { int l1, l2; int i; l1=a1[99]; l2=a2[99]; if (l1>l2) return 1; if (l1<l2) return -1; for(i=(l1-1);i>=0;i--) { if (a1[i]>a2[i]) return 1 ; if (a1[i]<a2[i]) return -1; } return 0; } void mov(int a[MAX],int *b) { int j; for(j=0;j<MAX;j++) b[j]=a[j]; return ; } void mul(int a1[MAX],int a2[MAX],int *c) { int i,j; int y; int x; int z; int w; int l1, l2; l1=a1[MAX-1]; l2=a2[MAX-1]; if (a1[MAX-2]=='-'&& a2[MAX-2]=='-') c[MAX-2]=0; else if (a1[MAX-2]=='-') c[MAX-2]='-'; else if (a2[MAX-2]=='-') c[MAX-2]='-'; for(i=0;i<l1;i++) { for(j=0;j<l2;j++) { x=a1[i]*a2[j]; y=x/10; z=x%10; w=i+j; c[w]=c[w]+z; c[w+1]=c[w+1]+y+c[w]/10; c[w]=c[w]%10; } } w=l1+l2; if(c[w-1]==0) w=w-1; c[MAX-1]=w; return; } void add(int a1[MAX],int a2[MAX],int *c) { int i,l1,l2; int len,temp[MAX]; int k=0; l1=a1[MAX-1]; l2=a2[MAX-1]; if((a1[MAX-2]=='-')&&(a2[MAX-2]=='-')) { c[MAX-2]='-'; } else if (a1[MAX-2]=='-') { mov(a1,temp); temp[MAX-2]=0; sub(a2,temp,c); return; } else if (a2[MAX-2]=='-') { mov(a2,temp); temp[98]=0; sub(a1,temp,c); return; } if(l1<l2) len=l1; else len=l2; for(i=0;i<len;i++) { c[i]=(a1[i]+a2[i]+k)%10; k=(a1[i]+a2[i]+k)/10; } if(l1>len) { for(i=len;i<l1;i++) { c[i]=(a1[i]+k)%10; k=(a1[i]+k)/10; } if(k!=0) { c[l1]=k; len=l1+1; } else len=l1; } else { for(i=len;i<l2;i++) { c[i]=(a2[i]+k)%10; k=(a2[i]+k)/10; } if(k!=0) { c[l2]=k; len=l2+1; } else len=l2; } c[99]=len; return; } void sub(int a1[MAX],int a2[MAX],int *c) { int i,l1,l2; int len,t1[MAX],t2[MAX]; int k=0; l1=a1[MAX-1]; l2=a2[MAX-1]; if ((a1[MAX-2]=='-') && (a2[MAX-2]=='-')) { mov(a1,t1); mov(a2,t2); t1[MAX-2]=0; t2[MAX-2]=0; sub(t2,t1,c); return; } else if( a2[MAX-2]=='-') { mov(a2,t2); t2[MAX-2]=0; add(a1,t2,c); return; } else if (a1[MAX-2]=='-') { mov(a2,t2); t2[MAX-2]='-'; add(a1,t2,c); return; } if(cmp(a1,a2)==1) { len=l2; for(i=0;i<len;i++) { if ((a1[i]-k-a2[i])<0) { c[i]=(a1[i]-a2[i]-k+10)%10; k=1; } else { c[i]=(a1[i]-a2[i]-k)%10; k=0; } } for(i=len;i<l1;i++) { if ((a1[i]-k)<0) { c[i]=(a1[i]-k+10)%10; k=1; } else { c[i]=(a1[i]-k)%10; k=0; } } if(c[l1-1]==0) //使得数组C中的前面所以0字符不显示 { len=l1-1; i=2; while (c[l1-i]==0) { len=l1-i; i++; } } else { len=l1; } } else if(cmp(a1,a2)==(-1)) { c[MAX-2]='-'; len=l1; for(i=0;i<len;i++) { if ((a2[i]-k-a1[i])<0) { c[i]=(a2[i]-a1[i]-k+10)%10; k=1; } else { c[i]=(a2[i]-a1[i]-k)%10; k=0; } } for(i=len;i<l2;i++) { if ((a2[i]-k)<0) { c[i]=(a2[i]-k+10)%10; k=1; } else { c[i]=(a2[i]-k)%10; k=0; } } if(c[l2-1]==0) { len=l2-1; i=2; while (c[l1-i]==0) { len=l1-i; i++; } } else len=l2; } else if(cmp(a1,a2)==0) { len=1; c[len-1]=0; } c[MAX-1]=len; return; } void mod(int a[MAX],int b[MAX],int *c) //c=a mod b(经检验知道此处A和C的数组都改变了) { int d[MAX]; mov (a,d); while (cmp(d,b)!=(-1)) //c=a-b-b-b-b-b.......until(c<b) { sub(d,b,c); mov(c,d); //c复制给a } return ; } void divt(int t[MAX],int b[MAX],int *c ,int *w) //试商法//调用以后w为a mod b, C为a div b { int a1,b1,i,j,m; //w用于暂时保存数据 int d[MAX],e[MAX],f[MAX],g[MAX],a[MAX]; mov(t,a); for(i=0;i<MAX;i++) e[i]=0; for(i=0;i<MAX;i++) d[i]=0; for(i=0;i<MAX;i++) g[i]=0; a1=a[MAX-1]; b1=b[MAX-1]; if (cmp(a,b)==(-1)) { c[0]=0; c[MAX-1]=1; mov(t,w); return; } else if (cmp(a,b)==0) { c[0]=1; c[MAX-1]=1; w[0]=0; w[MAX-1]=1; return; } m=(a1-b1); for(i=m;i>=0;i--) //例如：341245/3=341245-300000*1--->41245-30000*1--->11245-3000*3--->2245-300*7--->145-30*4=25--->25-3*8=1 { for(j=0;j<MAX;j++) d[j]=0; d[i]=1; d[MAX-1]=i+1; mov(b,g); mul(g,d,e); while (cmp(a,e)!=(-1)) { c[i]++; sub(a,e,f); mov(f,a);//f复制给g } for(j=i;j<MAX;j++)//高位清零 e[j]=0; } mov(a,w); if (c[m]==0) c[MAX-1]=m; else c[MAX-1]=m+1; return; } void expmod(int a[MAX] ,int p[MAX] ,int n[MAX],int *m)//计算 m=a^p mod n { int t[MAX],l[MAX],temp[MAX]; int w[MAX],s[MAX],c[MAX],b[MAX],i; for(i=0;i<MAX-1;i++) b[i]=l[i]=t[i]=w[i]=0; t[0]=2;t[MAX-1]=1; l[0]=1;l[MAX-1]=1; mov(l,temp); mov(a,m); mov(p,b); while(cmp(b,l)!=0) { for(i=0;i<MAX;i++) w[i]=c[i]=0; divt(b,t,w,c);// c=p mod 2 w= p /2 mov(w,b);//p=p/2 if(cmp(c,l)==0) //余数c==1 { for(i=0;i<MAX;i++) w[i]=0; mul(temp,m,w); mov(w,temp); for(i=0;i<MAX;i++) w[i]=c[i]=0; divt(temp,n,w,c);//c为余c=temp % n，w为商w=temp/n mov(c,temp); } for(i=0;i<MAX;i++) s[i]=0; mul(m,m,s); //s=a*a for(i=0;i<MAX;i++) c[i]=0; divt(s,n,w,c);//w=s/n;c=s mod n mov (c,m); } for(i=0;i<MAX;i++) s[i]=0; mul(m,temp,s); for(i=0;i<MAX;i++) c[i]=0; divt(s,n,w,c); mov (c,m);//余数s给m m[MAX-2]=a[MAX-2]; return; } int is_prime_san(int p[MAX] ) { int i,a[MAX],t[MAX],s[MAX],o[MAX]; for(i=0;i<MAX;i++) s[i]=o[i]=a[i]=t[i]=0; t[0]=1; t[MAX-1]=1; a[0]=2;// { 2,3,5,7 } a[MAX-1]=1; sub(p,t,s); expmod ( a, s, p ,o); if ( cmp(o,t) != 0 ) { return 0; } a[0]=3; for(i=0;i<MAX;i++) o[i]=0; expmod ( a, s, p ,o); if ( cmp(o,t) != 0 ) { return 0; } a[0]=5; for(i=0;i<MAX;i++) o[i]=0; expmod ( a, s, p ,o); if ( cmp(o,t) != 0 ) { return 0; } a[0]=7; for(i=0;i<MAX;i++) o[i]=0; expmod ( a, s, p ,o); if ( cmp(o,t) != 0 ) { return 0; } return 1; } int coprime(int e[MAX],int s[MAX]) // 判断两个大数之间是否互质 { int a[MAX],b[MAX],c[MAX],d[MAX],o[MAX],l[MAX]; int i; for(i=0;i<MAX;i++) l[i]=o[i]=c[i]=d[i]=0; o[0]=0; o[MAX-1]=1; l[0]=1; l[MAX-1]=1; mov(e,b); mov(s,a); do { if(cmp(b,l)==0) { return 1; } for(i=0;i<MAX;i++) c[i]=0; divt(a,b,d,c); mov(b,a); mov(c,b); }while(cmp(c,o)!=0); return 0; } void prime_random(int *p,int *q) //随机产生大素数p，q { int i,k; time_t t; p[0]=1; q[0]=3; p[MAX-1]=10; q[MAX-1]=11; do { t=time(NULL); srand((unsigned long)t); for(i=1;i<p[MAX-1]-1;i++) { k=rand()%10; p[i]=k; } k=rand()%10; while (k==0) { k=rand()%10; } p[p[MAX-1]-1]=k; }while((is_prime_san(p))!=1); printf("素数 p 为 : "); for(i=0;i<p[MAX-1];i++) { printf("%d",p[p[MAX-1]-i-1]); } printf("\n"); do { t=time(NULL); srand((unsigned long)t); for(i=1;i<q[MAX-1];i++) { k=rand()%10; q[i]=k; } }while((is_prime_san(q))!=1); printf("素数 q 为 : "); for(i=0;i<q[MAX-1];i++) { printf("%d",q[q[MAX-1]-i-1]); } printf("\n"); return; } void erand(int e[MAX],int m[MAX])//计算e { int i,k; time_t t; e[MAX-1]=5; printf("随机产生一个与(p-1)*(q-1)互素的 e :"); do { t=time(NULL); srand((unsigned long)t); for(i=0;i<e[MAX-1]-1;i++) { k=rand()%10; e[i]=k; } while((k=rand()%10)==0) k=rand()%10; e[e[MAX-1]-1]=k; }while(coprime( e, m)!=1); for(i=0;i<e[MAX-1];i++) { printf("%d",e[e[MAX-1]-i-1]); } printf("\n"); return ; } void rsad(int e[MAX],int g[MAX],int *d) //计算d { int r[MAX],n1[MAX],n2[MAX],k[MAX],w[MAX]; int