RSA加解密算法

RSA加解密算法1实验目的了解RSA加解密算法2实验内容编程实现RSA加解密算法3实验步骤3.1选择素数p,q选择p,q，p,q都是素数，p≠q。由于P和q都是大素数，所以为了方便由程序自动生成。//产生随机素数p和qvoidprime_random(int*p,int*q){inti,k;time_tt;p[0]=1;q[0]=3;//p[19]=1;//q[18]=2;p[MAX-1]=10;q[MAX-1]=11;do{t=time(NULL);srand((unsignedlong)t);for(i=1;ip[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;ip[MAX-1];i++){printf(%d,p[p[MAX-1]-i-1]);}printf(\n\n);do{t=time(NULL);srand((unsignedlong)t);for(i=1;iq[MAX-1];i++){k=rand()%10;q[i]=k;}}while((is_prime_san(q))!=1);printf(素数q为:);for(i=0;iq[MAX-1];i++){printf(%d,q[q[MAX-1]-i-1]);}printf(\n\n);return;}3.2选择整数e∅(𝐧)=(𝑝−1)(𝑞−1)整数e满足gcd(∅(𝑛),𝑒)=1;1𝑒∅(𝑛)。//产生与（p-1）*（q-1）互素的随机数voiderand(inte[MAX],intm[MAX]){inti,k;time_tt;e[MAX-1]=5;printf(随机产生一个与(p-1)*(q-1)互素的e:);do{t=time(NULL);srand((unsignedlong)t);for(i=0;ie[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;ie[MAX-1];i++){printf(%d,e[e[MAX-1]-i-1]);}printf(\n\n);return;}3.3确定d确定d使得de≡1mod∅(𝑛)。∅(𝐧)=(𝑝−1)(𝑞−1)//根据上面的p、q和e计算密钥dvoidrsad(inte[MAX],intg[MAX],int*d){intr[MAX],n1[MAX],n2[MAX],k[MAX],w[MAX];inti,t[MAX],b1[MAX],b2[MAX],temp[MAX];mov(g,n1);mov(e,n2);for(i=0;iMAX;i++)k[i]=w[i]=r[i]=temp[i]=b1[i]=b2[i]=t[i]=0;b1[MAX-1]=0;b1[0]=0;//b1=0;b2[MAX-1]=1;b2[0]=1;//b2=1;while(1){for(i=0;iMAX;i++)k[i]=w[i]=0;divt(n1,n2,k,w);//k=n1/n2;for(i=0;iMAX;i++)temp[i]=0;mul(k,n2,temp);//temp=k*n2;for(i=0;iMAX;i++)r[i]=0;sub(n1,temp,r);if((r[MAX-1]==1)&&(r[0]==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++)temp[i]=0;mul(k,b2,temp);//b2=b1-k*b2;for(i=0;iMAX;i++)b2[i]=0;sub(b1,temp,b2);mov(t,b1);}}for(i=0;iMAX;i++)t[i]=0;add(b2,g,t);for(i=0;iMAX;i++)temp[i]=d[i]=0;divt(t,g,temp,d);printf(由以上的(p-1)*(q-1)和e计算得出的d:);for(i=0;id[MAX-1];i++)printf(%d,d[d[MAX-1]-i-1]);printf(\n\n);}3.4加密函数利用上面的函数我们可以得到e和n=p×q。加密使用的公钥KU={𝑒,𝑛}。加密函数如下所示：MnC=𝑀𝑒(𝑚𝑜𝑑𝑛)加密函数：//加密模块儿，例如C=P^emodnstructslink*jiami(inte[MAX],intn[MAX],structslink*head){structslink*p;structslink*h;structslink*p1,*p2;intm=0,i;printf(\n);printf(加密后形成的密文内容：\n);p1=p2=(structslink*)malloc(LEN);h=NULL;p=head;if(head!=NULL)do{expmod(p-bignum,e,n,p1-bignum);for(i=0;ip1-bignum[MAX-1];i++){printf(%d,p1-bignum[p1-bignum[MAX-1]-1-i]);}m=m+1;if(m==1)h=p1;elsep2-next=p1;p2=p1;p1=(structslink*)malloc(LEN);p=p-next;}while(p!=NULL);p2-next=NULL;p=h;printf(\n);return(h);}3.5解密函数利用之前的函数我们可以得到d,n=p×q。解密的私钥为KR={𝑑,𝑛}解密函数如下：CM=𝐶𝑑(𝑚𝑜𝑑𝑛)解密函数：//解密模块儿，例如P=C^dmodnvoidjiemi(intd[MAX],intn[MAX],structslink*h){inti,j,temp;structslink*p,*p1;charch[65535];p1=(structslink*)malloc(LEN);p=h;j=0;if(h!=NULL)do{for(i=0;iMAX;i++)p1-bignum[i]=0;expmod(p-bignum,d,n,p1-bignum);temp=p1-bignum[0]+p1-bignum[1]*10+p1-bignum[2]*100;if((p1-bignum[MAX-2])=='0'){temp=0-temp;}ch[j]=temp;j++;p=p-next;}while(p!=NULL);printf(\n);printf(解密密文后所生成的明文:\n);for(i=0;ij;i++)printf(%c,ch[i]);printf(\n);return;}4实验结果运行程序，系统自动生成公钥和私钥：公钥为：KU={𝑒=74839,𝑛=104431747060337906333}私钥为：KR={𝑑=71385439185127612219,𝑛=104431747060337906333}加密操作：输入明文：wangxinijfioajfioahgiuhaijfalijgoaijrgfiahguajdnandijuhaifhfuiah输出密文，程序运行结果如下所示：解密操作：解密所用的密文就是上面加密得到的密文。输出明文，程序运行结果如下所示：5实验完整代码#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,y,x,z,w,l1,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[