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

1、RSA加密解密算法C语言代码#include#include#include #include #include #include #define MAX 100#define LEN sizeof(struct slink)void sub(int aMAX,int bMAX ,int cMAX );struct slink int bignumMAX; /*bignum98用来标记正负号，1正，0负bignum99来标记实际长度*/ struct slink *next;/*/-自己建立的大数运算库-*/void print( int aMAX ) int i; for(i=0;il2)

2、return 1; if (l1=0;i-) if (a1ia2i) return 1 ; if (a1ia2i) return -1; return 0;void mov(int aMAX,int *b) int j; for(j=0;jMAX;j+) bj=aj; return ;void mul(int a1MAX,int a2MAX,int *c) int i,j; int y; int x; int z; int w; int l1, l2; l1=a1MAX-1; l2=a2MAX-1; if (a1MAX-2=-& a2MAX-2=-) cMAX-2=0; else if (a1

3、MAX-2=-) cMAX-2=-; else if (a2MAX-2=-) cMAX-2=-; for(i=0;il1;i+) for(j=0;jl2;j+) x=a1i*a2j; y=x/10; z=x%10; w=i+j; cw=cw+z; cw+1=cw+1+y+cw/10; cw=cw%10; w=l1+l2; if(cw-1=0)w=w-1; cMAX-1=w; return; void add(int a1MAX,int a2MAX,int *c) int i,l1,l2; int len,tempMAX; int k=0;l1=a1MAX-1;l2=a2MAX-1;if(a1M

4、AX-2=-)&(a2MAX-2=-) cMAX-2=-;else if (a1MAX-2=-) mov(a1,temp); tempMAX-2=0; sub(a2,temp,c); return;else if (a2MAX-2=-) mov(a2,temp); temp98=0; sub(a1,temp,c); return; if(l1l2)len=l1; else len=l2; for(i=0;ilen) for(i=len;il1;i+) ci=(a1i+k)%10; k=(a1i+k)/10; if(k!=0) cl1=k; len=l1+1; else len=l1; else

5、 for(i=len;il2;i+) ci=(a2i+k)%10; k=(a2i+k)/10; if(k!=0) cl2=k; len=l2+1; else len=l2; c99=len; return; void sub(int a1MAX,int a2MAX,int *c) int i,l1,l2; int len,t1MAX,t2MAX; int k=0;l1=a1MAX-1;l2=a2MAX-1;if (a1MAX-2=-) & (a2MAX-2=-) mov(a1,t1); mov(a2,t2); t1MAX-2=0; t2MAX-2=0; sub(t2,t1,c); return

6、;else if( a2MAX-2=-) mov(a2,t2); t2MAX-2=0; add(a1,t2,c); return;else if (a1MAX-2=-) mov(a2,t2); t2MAX-2=-; add(a1,t2,c); return; if(cmp(a1,a2)=1) len=l2; for(i=0;ilen;i+) if (a1i-k-a2i)0) ci=(a1i-a2i-k+10)%10; k=1; else ci=(a1i-a2i-k)%10; k=0; for(i=len;il1;i+) if (a1i-k)显示为980了*/ len=l1-1; i=2; wh

7、ile (cl1-i=0)/*111456-111450=00006，消除0后变成了6；*/ len=l1-i; i+; else len=l1; elseif(cmp(a1,a2)=(-1) cMAX-2=-; len=l1; for(i=0;ilen;i+) if (a2i-k-a1i)0) ci=(a2i-a1i-k+10)%10; k=1; else ci=(a2i-a1i-k)%10; k=0; for(i=len;il2;i+) if (a2i-k)0) ci=(a2i-k+10)%10; k=1; else ci=(a2i-k)%10; k=0; if(cl2-1=0) len=

8、l2-1; i=2; while (cl1-i=0) len=l1-i; i+; else len=l2; else if(cmp(a1,a2)=0) len=1; clen-1=0; cMAX-1=len;return;void mod(int aMAX,int bMAX,int *c)/*/c=a mod b/注意：经检验知道此处A和C的数组都改变了。*/ int dMAX; 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 ;void di

9、vt(int tMAX,int bMAX,int *c ,int *w)/*/试商法/调用以后w为a mod b, C为a div b;*/ int a1,b1,i,j,m;/*w用于暂时保存数据*/ int dMAX,eMAX,fMAX,gMAX,aMAX; mov(t,a); for(i=0;iMAX;i+) ei=0; for(i=0;iMAX;i+) di=0; for(i=0;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;jM

10、AX;j+) dj=0; di=1; dMAX-1=i+1; mov(b,g); mul(g,d,e); while (cmp(a,e)!=(-1) ci+; sub(a,e,f); mov(f,a);/*f复制给g*/ for(j=i;jMAX;j+)/*高位清零*/ ej=0; mov(a,w); if (cm=0) cMAX-1=m; else cMAX-1=m+1; return;void mulmod(int aMAX ,int bMAX ,int nMAX,int *m)/*解决 了 m=a*b mod n;*/ int cMAX,dMAX; int i; for(i=0;iMAX

11、;i+) di=ci=0; mul(a,b,c); divt(c,n, d,m); for(i=0;imMAX-1;i+) printf(%d,mmMAX-1-i-1); printf(nm length is : %d n,mMAX-1);/*接下来的重点任务是要着手解决 m=ap mod n的函数问题。*/void expmod(int aMAX ,int pMAX ,int nMAX,int *m) int tMAX,lMAX,tempMAX; /*/t放入2，l放入1；*/ int wMAX,sMAX,cMAX,bMAX,i; for(i=0;iMAX-1;i+) bi=li=ti=w

12、i=0; t0=2;tMAX-1=1; l0=1;lMAX-1=1; mov(l,temp); mov(a,m); mov(p,b);while(cmp(b,l)!=0) for(i=0;iMAX;i+) wi=ci=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;iMAX;i+) wi=0; mul(temp,m,w); mov(w,temp); for(i=0;iMAX;i+) wi=ci=0; divt(temp,n,w,c);/* /c为余c=te

13、mp % n，w为商w=temp/n */ mov(c,temp);for(i=0;iMAX;i+) si=0;mul(m,m,s);/s=a*afor(i=0;iMAX;i+) ci=0;divt(s,n,w,c);/*/w=s/n;c=s mod n*/mov (c,m);for(i=0;iMAX;i+) si=0;mul(m,temp,s);for(i=0;iMAX;i+) ci=0;divt(s,n,w,c);mov (c,m);/*余数s给m*/mMAX-2=aMAX-2;/*为后面的汉字显示需要，用第99位做为标记*/return;/*/k=temp*k%n;*/int is_pr

14、ime_san(int pMAX ) int i,aMAX,tMAX,sMAX,oMAX; for(i=0;iMAX;i+) si=oi=ai=ti=0; t0=1; tMAX-1=1; a0=2;/ 2,3,5,7 aMAX-1=1; sub(p,t,s); expmod ( a, s, p ,o); if ( cmp(o,t) != 0 ) return 0; a0=3; for(i=0;iMAX;i+) oi=0; expmod ( a, s, p ,o); if ( cmp(o,t) != 0 ) return 0; a0=5; for(i=0;iMAX;i+) oi=0; expmo

15、d ( a, s, p ,o); if ( cmp(o,t) != 0 ) return 0; a0=7; for(i=0;iMAX;i+) oi=0; expmod ( a, s, p ,o); if ( cmp(o,t) != 0 ) return 0; return 1;int coprime(int eMAX,int sMAX) /*/ 求两个大数之间是否互质/*/ int aMAX,bMAX,cMAX,dMAX,oMAX,lMAX; int i; for(i=0;iMAX;i+) li=oi=ci=di=0; o0=0;oMAX-1=1; l0=1;lMAX-1=1; mov(e,b

16、); mov(s,a);doif(cmp(b,l)=0) return 1;for(i=0;ia*/ mov(c,b);/*c-b*/while(cmp(c,o)!=0);/* printf(Ihey are not coprime!n);*/return 0;void prime_random(int *p,int *q) int i,k; time_t t; p0=1; q0=3; / p19=1;/ q18=2; pMAX-1=10; qMAX-1=11; do t=time(NULL); srand(unsigned long)t); for(i=1;ipMAX-1-1;i+) k=r

17、and()%10; pi=k; k=rand()%10; while (k=0) k=rand()%10; ppMAX-1-1=k; while(is_prime_san(p)!=1); printf(素数 p 为 : ); for(i=0;ipMAX-1;i+) printf(%d,ppMAX-1-i-1); printf(nn); do t=time(NULL); srand(unsigned long)t); for(i=1;iqMAX-1;i+) k=rand()%10; qi=k; while(is_prime_san(q)!=1); printf(素数 q 为 : ); for(i

18、=0;iqMAX-1;i+) printf(%d,qqMAX-1-i-1); printf(nn); return; void erand(int eMAX,int mMAX) int i,k; time_t t; eMAX-1=5; printf(随机产生一个与(p-1)*(q-1)互素的 e :); do t=time(NULL); srand(unsigned long)t); for(i=0;ieMAX-1-1;i+) k=rand()%10; ei=k; while(k=rand()%10)=0) k=rand()%10; eeMAX-1-1=k; while(coprime( e,

19、 m)!=1); for(i=0;ieMAX-1;i+) printf(%d,eeMAX-1-i-1); printf(nn); return ;void rsad(int eMAX,int gMAX,int *d) int rMAX,n1MAX,n2MAX,kMAX,wMAX; int i,tMAX,b1MAX,b2MAX,tempMAX; mov(g,n1); mov(e,n2); for(i=0;iMAX;i+) ki=wi=ri=tempi=b1i=b2i=ti=0; b1MAX-1=0;b10=0;/*/b1=0;*/ b2MAX-1=1;b20=1;/*/b2=1;*/ while

20、(1) for(i=0;iMAX;i+) ki=wi=0; divt(n1,n2,k,w);/*/k=n1/n2;*/ for(i=0;iMAX;i+) tempi=0; mul(k,n2,temp);/*/temp=k*n2;*/ for(i=0;iMAX;i+) ri=0; sub(n1,temp,r); if(rMAX-1=1) & (r0=0)/*/r=0*/ break; else mov(n2,n1);/*/n1=n2;*/ mov( r,n2);/*/n2=r;*/ mov(b2, t);/*/t=b2;*/ for(i=0;iMAX;i+) tempi=0; mul(k,b2,

21、temp);/*/b2=b1-k*b2;*/ for(i=0;iMAX;i+) b2i=0; sub(b1,temp,b2); mov(t,b1); for(i=0;iMAX;i+) ti=0; add(b2,g,t); for(i=0;iMAX;i+) tempi=di=0; divt(t,g,temp,d); printf(由以上的(p-1)*(q-1)和 e 计算得出的 d : ); for(i=0;idMAX-1;i+) printf(%d,ddMAX-1-i-1); printf(nn);unsigned long rsa(unsigned long p,unsigned long

22、q,unsigned long e) /*/求解密密钥d的函数(根据Euclid算法)*/unsigned long g,k,r,n1,n2,t;unsigned long b1=0,b2=1; g=(p-1)*(q-1); n1=g; n2=e; while(1) k=n1/n2; r=n1-k*n2; if(r!=0) n1=n2; n2=r; t=b2; b2=b1-k*b2; b1=t; else break; return (g+b2)%g;/*/-导入导出公钥和私钥-/*/void loadpkey(int eMAX,int nMAX) /导入公钥 FILE *fp; char filename25,strMAX,ch; int i,k; for(i=0;iMAX;i+) ei=ni=0; while(1) printf(n); printf(为导入(e,n)，请输入加密密钥对文件路径: n); scanf(%s