RSA公钥密码实验报告

（网络安全方案设计基础）实验报告时间：2021年05月姓名班级学号指导教师实验成绩实验名称RSA公钥密码实验目的1、了解和掌握RSA加密算法原理及过程；2、了解生成大素数的方法；3、能够编写代码实现RSA算法。实验内容1、编写程序构造RSA密钥；2、编写程序生成大素数；3、实现RSA密码体制。实验过程#include<stdio.h>#include<stdlib.h>#include<time.h>#include<string.h>#defineACCURACY5#defineSINGLE_MAX100#defineEXPONENT_MAX1000#defineBUF_SIZE1024intmodpow(longa,longb,intc){intres=1;while(b>0){/*Needlongmultiplicationelsethiswilloverflow...*/if^b&1){res=(res*a)%c;}b=b>>1;a=(a*a)%c;/*Samedealhere*/}returnres;}intjacobi(inta,intn){inttwos,temp;intmult=1;while(a>1&&a！=n){a=a%n;if(a<=1||a==n)break;twos=0;while(a%2==0&&++twos)a/=2;/*Factoroutmultiplesof2*/if(twos>0&&twos%2==1)mult*=(n%8==111n%8==7)*2-1;if(a<=1||a==n)break;if(n%4!=1&&a%4!=1)mult*=-1;/*Coefficientforflipping*/temp=a;a=n;n=temp;}if(a==0)return0;elseif(a==1)returnmult;elsereturn0;/*a==n=>gcd(a,n)!=1*/}intsolovayPrime(inta,intn){intx=jacobi(a,n);if(x==-1)x=n-1;returnx!=0&&modpow(a,(n-1)/2,n)==x;}intprobablePrime(intn,intk){if(n==2)return1;elseif(n%2==0||n==1)return0;while(k-->0){if(!solovayPrime(rand()%(n-2)+2,n))return0;}return1;}intrandPrime(intn){intprime=rand()%n;n+=n%2;/*nneedstobeevensomodulowrappingpreservesoddness*/prime+=1-prime%2;while(1){if(probablePrime(prime,ACCURACY))returnprime;prime=(prime+2)%n;}intgcd(inta,intb){inttemp;while(b!=0){temp=b;b=a%b;a=temp;}returna;}intrandExponent(intphi,intn){inte=rand()%n;while(1){if(gcd(e,phi)==1)returne;e=(e+1)%n;if(e<=2)e=3;}}intinverse(intn,intmodulus){inta=n,b=modulus;intx=0,y=1,x0=1,y0=0,q,temp;while(b!=0){q=a/b;temp=a%b;a=b;b=temp;temp=x;x=x0-q*x;x0=temp;temp=y;y=y0-q*y;y0=temp;}if(x0<0)x0+=modulus;returnx0;}intreadFile(FILE*fd,char**buffer,intbytes){intlen=0,cap=BUF_SIZE,r;charbuf[BUF_SIZE];*buffer=(char*)malloc(BUF_SIZE*sizeof(char));while((r=fread(buf,sizeof(char),BUF_SIZE,fd))>0){if(len+r>=cap){cap*=2;*buffer=(char*)realloc(*buffer,cap);}memcpy(&(*buffer)[len],buf,r);len+=r;if(len+bytes-len%bytes>cap)*buffer=(char*)realloc(*buffer,len+bytes-len%bytes);do{(*buffer)[len]=''0';len++;}while(len%bytes!=0);returnlen;}intencode(intm,inte,intn){returnmodpow(m,e,n);}intdecode(intc,intd,intn){returnmodpow(c,d,n);}int*encodeMessage(intlen,intbytes,char*message,intexponent,intmodulus){int*encoded=(int*)malloc((len/bytes)*sizeof(int));intx,i,j;for(i=0;i<len;i+=bytes){x=0;for(j=0;j<bytes;j++)x+=message[i+j]*(1<<(7*j));encoded[i/bytes]=encode(x,exponent,modulus);#ifndefMEASUREprintf("%d",encoded[i/bytes]);#endif}returnencoded;}int*decodeMessage(intlen,intbytes,int*cryptogram,intexponent,intmodulus){int*decoded=(int*)malloc(len*bytes*sizeof(int));intx,i,j;for(i=0;i<len;i++){x=decode(cryptogram[i],exponent,modulus);for(j=0;j<bytes;j++){decoded[i*bytes+j]=(x>>(7*j))%128;#ifndefMEASUREif(decoded[i*bytes+j]!='\0')printf("%c",decoded[i*bytes+j]);#endifreturndecoded;…{intp,q,n,phi,e,d,bytes,len;int*encoded,*decoded;char*buffer;FILE*f;srand(time(NULL));while(1){p=randPrime(SINGLE_MAX);printf("p=%d\n",p);q=randPrime(SINGLE_MAX);printf("q=%d\n",q);n=p*q;printf("n=%d\n",n);if^n<128){}elsebreak;if(n>>21)bytes=3;elseif(n>>14)bytes=2;elsebytes=1;phi=(p-1)*(q-1);printf("phi=(p-1)*(q-1)=%d\n",phi);e=randExponent(phi,EXPONENT_MAX);printf("e=%d\n公钥：(％d,%d)\n",e,e,n);d=inverse(e,phi);prints”d=%d\n私钥：(％d,%d)\n”,d,d,n);f=fopen("text.txt","r");iff==NULL){

printf("Failedtoopenfile\"text.txt\".Doesitexist?\n");returnEXIT_FAILURE;}len=readFile(f,&buffer,bytes);/*lenwillbeamultipleofbytes,tosendwholechunks*/fclose(f);printf("\n密文是:");encoded=encodeMessage(len,bytes,buffer,e,n);printf("\n明文是：")；decoded=decodeMessage(len/bytes,bytes,encoded,d,n);printf("\n");free(encoded);free(decoded);free(buffer);returnEXIT_SUCCESS;}主程序运行(图1)：实验结果p=53实验结果q67n=3551phi=(p-1)*(q-1)=3432史=991公用：(991,3551)d=3103和助；(3103,S551)密文足：325217913066145714571791186618661S66353