RSA算法C++实现源码

#include "StdAfx.h" #include "RSA.h" RSA::RSA(void) { } RSA::~RSA(void) { } /*----------------------------创建自己的大数运算库---------------------------------*/ int RSA::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 RSA::mov(int a[MAX],int *b) { int j; for(j=0;j<MAX;j++) b[j]=a[j]; return ; } void RSA::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 RSA::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 RSA::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字符不显示了，如1000-20=0980--->显示为980了*/ { len=l1-1; i=2; while (c[l1-i]==0)/*111456-111450=00006，消除0后变成了6；*/ { 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 RSA::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 RSA::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 RSA::mulmod(int a[MAX] ,int b[MAX] ,int n[MAX],int *m)/*解决 了 m=a*b mod n;*/ { int c[MAX],d[MAX]; int i; for(i=0;i<MAX;i++) d[i]=c[i]=0; mul(a,b,c); divt(c,n, d,m); //for(i=0;i<m[MAX-1];i++) // printf("%d",m[m[MAX-1]-i-1]); //printf("\nm length is : %d \n",m[MAX-1]); } /*-------------接下来的重点任务是要着手解决 m=a^p mod n的函数问题------------*/ void RSA::expmod(int a[MAX] ,int p[MAX] ,int n[MAX],int *m) { int t[MAX],l[MAX],temp[MAX]; /*/t放入2，l放入1；*/ int w[MAX],s[MAX],c[MAX],b[MAX],i; for(i=0;i<MAX-1;i++)