RSA加密解密算法C语言代码

#includestdio.h#includestring.h#includestdlib.h#includetime.h#includemath.h#includemalloc.h#defineMAX100#defineLENsizeof(structslink)voidsub(inta[MAX],intb[MAX],intc[MAX]);structslink{intbignum[MAX];/*bignum[98]用来标记正负号，1正，0负bignum[99]来标记实际长度*/structslink*next;};/*/--------------------------------------自己建立的大数运算库-------------------------------------*/voidprint(inta[MAX]){inti;for(i=0;ia[99];i++)printf(%d,a[a[99]-i-1]);printf(\n\n);return;}intcmp(inta1[MAX],inta2[MAX]){intl1,l2;inti;l1=a1[99];l2=a2[99];if(l1l2)return1;if(l1l2)return-1;for(i=(l1-1);i=0;i--){if(a1[i]a2[i])return1;if(a1[i]a2[i])return-1;}return0;}voidmov(inta[MAX],int*b){intj;for(j=0;jMAX;j++)b[j]=a[j];return;}voidmul(inta1[MAX],inta2[MAX],int*c){inti,j;inty;intx;intz;intw;intl1,l2;l1=a1[MAX-1];l2=a2[MAX-1];if(a1[MAX-2]=='-'&&a2[MAX-2]=='-')c[MAX-2]=0;elseif(a1[MAX-2]=='-')c[MAX-2]='-';elseif(a2[MAX-2]=='-')c[MAX-2]='-';for(i=0;il1;i++){for(j=0;jl2;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;}voidadd(inta1[MAX],inta2[MAX],int*c){inti,l1,l2;intlen,temp[MAX];intk=0;l1=a1[MAX-1];l2=a2[MAX-1];if((a1[MAX-2]=='-')&&(a2[MAX-2]=='-')){c[MAX-2]='-';}elseif(a1[MAX-2]=='-'){mov(a1,temp);temp[MAX-2]=0;sub(a2,temp,c);return;}elseif(a2[MAX-2]=='-'){mov(a2,temp);temp[98]=0;sub(a1,temp,c);return;}if(l1l2)len=l1;elselen=l2;for(i=0;ilen;i++){c[i]=(a1[i]+a2[i]+k)%10;k=(a1[i]+a2[i]+k)/10;}if(l1len){for(i=len;il1;i++){c[i]=(a1[i]+k)%10;k=(a1[i]+k)/10;}if(k!=0){c[l1]=k;len=l1+1;}elselen=l1;}else{for(i=len;il2;i++){c[i]=(a2[i]+k)%10;k=(a2[i]+k)/10;}if(k!=0){c[l2]=k;len=l2+1;}elselen=l2;}c[99]=len;return;}voidsub(inta1[MAX],inta2[MAX],int*c){inti,l1,l2;intlen,t1[MAX],t2[MAX];intk=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;}elseif(a2[MAX-2]=='-'){mov(a2,t2);t2[MAX-2]=0;add(a1,t2,c);return;}elseif(a1[MAX-2]=='-'){mov(a2,t2);t2[MAX-2]='-';add(a1,t2,c);return;}if(cmp(a1,a2)==1){len=l2;for(i=0;ilen;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;il1;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;}}elseif(cmp(a1,a2)==(-1)){c[MAX-2]='-';len=l1;for(i=0;ilen;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;il2;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++;}}elselen=l2;}elseif(cmp(a1,a2)==0){len=1;c[len-1]=0;}c[MAX-1]=len;return;}voidmod(inta[MAX],intb[MAX],int*c)/*/c=amodb//注意：经检验知道此处A和C的数组都改变了。*/{intd[MAX];mov(a,d);while(cmp(d,b)!=(-1))/*/c=a-b-b-b-b-b.......until(cb)*/{sub(d,b,c);mov(c,d);/*/c复制给a*/}return;}voiddivt(intt[MAX],intb[MAX],int*c,int*w)/*//试商法//调用以后w为amodb,C为adivb;*/{inta1,b1,i,j,m;/*w用于暂时保存数据*/intd[MAX],e[MAX],f[MAX],g[MAX],a[MAX];mov(t,a);for(i=0;iMAX;i++)e[i]=0;for(i=0;iMAX;i++)d[i]=0;for(i=0;iMAX;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;}elseif(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;jMAX;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;jMAX;j++)/*高位清零*/e[j]=0;}mov(a,w);if(c[m]==0)c[MAX-1]=m;elsec[MAX-1]=m+1;return;}voidmulmod(inta[MAX],intb[MAX],intn[MAX],int*m)/*解决了m=a*bmodn;*/{intc[MAX],d[MAX];inti;for(i=0;iMAX;i++)d[i]=c[i]=0;mul(a,b,c);divt(c,n,d,m);for(i=0;im[MAX-1];i++)printf(%d,m[m[MAX-1]-i-1]);printf(\nmlengthis:%d\n,m[MAX-1]);}/*接下来的重点任务是要着手解决m=a^pmodn的函数问题。*/voidexpmod(inta[MAX],intp[MAX],intn[MAX],int*m){intt[MAX],l[MAX],temp[MAX];/*/t放入2，l放入1；*/intw[MAX],s[MAX],c[MAX],b[MAX],i;for(i=0;iMAX-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;iMAX;i++)w[i]=c[i]=0;divt(b,t,w,c);/*//c=pmod2w=p/2*/mov(w,b);/*//p=p/2*/if(cmp(c,l)==0)/*/余数c==1*/{for(i=0;iMAX;i++)w[i]=0;mul(temp,m,w);mov(w,temp);for(i=0;iMAX;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;iMAX;i++)s[i]=0;mul(m,m,s);//s=a*afor(i=0;iMAX;i++)c[i]=0;divt(s,n,w,c);/*/w=s/n;c=smodn*/mov(c,m);}for(i=0;iMAX;i++)s[i]=0;mul(m,temp,s);for(i=0;iMAX;i++)c[i]=0;divt(s,n,w,c);mov(c,m);/*余数s给m*/m[MAX-2]=a[MAX-2];/*为后面的汉字显示需要，用第99位做为标记*/return;/*/k=temp*k%n;*/}intis_prime_san(intp[MAX]){inti,a[MAX],t[MAX],s[MAX],o[MAX];for(i=0;iMAX;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){return0;}a[0]=3;for(i=0;iMAX;i++)o[i]=0;expmod(a,s,p,o);if(cmp(o,t)!=0){return0;}a[0]=5;for(i=0