搜索
实验三RSA算法代码实现代码实现结果:四、实验要求1、在RSA算法中，求解私钥d可以采用扩展欧几里得算法和线性代入法两种方法，但这两种方法的计算效率很低（即计算d要花费很多时间，特别是数次乘积运算占用了大量计算时间，使得RSA时间复杂度增加），请你通过网络或自己设计一种及一种以上更为高效的求解d的方法，并写出详细计算过程。2、用VC调试实验步骤给出的RSA加解密程序，结合原理分析程序中密钥是如何产生的？如何加密的？如何解密的？并在程序中给于解释。3、你还能采用别的方法自主设计RSA公钥密码算法吗？如果能请列出相关代码。【参考答案】1.在RSA算法中，求解私钥d可以采用以下方法：①扩展欧几里得算法(模幂乘法运算)②线性代入法(模幂乘法运算)③平方-乘法：按平方计算模指数运算④一种二进制查表方幂模快速计算方法：该方法根据指数二进制形式结构进行分组计算，记忆典型操作数，通过查表法大量减少了乘法次数。⑤采用分解计算和内联汇编方法加速RSA算法的执行⑥设计规划密钥空间2.【代码分析】#includeiostream#includevector#includestringusingnamespacestd;intEuclid(inta,intn)//na,求n和a的最大公因数为1{intx,y,r;x=n;y=a;for(inti=0;;){if(y==0)returnx;//a=0if(y==1)returny;//a=1r=x%y;//a≠0,1,r=n%ax=y;y=r;}}doubleextenEuclid(doublea,doublen)//利用扩展的Euclid计算a^-1modn的乘法逆元{doublex1=1,x2=0,x3=n,y1=0,y2=1,y3=a,Q;doublet1,t2,t3;for(inti=0;;){if(y3==0){returnx3;coutnoreverseendl;//a=0,无乘法逆元}if(y3==1)returny2;//a=1,a%n=1Q=int(x3/y3);//Q=[n/a]t1=x1-Q*y1;//t1=x1=1t2=x2-Q*y2;//t2=Qt3=x3-Q*y3;//t3=n-Qa,相当于d原理中的1=de-xfnx1=y1;x2=y2;x3=y3;y1=t1;y2=t2;y3=t3;//返回d的结果}}boolRabin(inta,intn)//Miler-Rabin素性测试算法对一个给定的大数进行测试{vectorintb;//判断一个变量b是否是素数unsignedintN=n-1;for(inti=0,j=1;;i++){if(jN)break;if((Ni)&(unsignedint)1)b.push_back(1);elseb.push_back(0);j*=2;}//将n-1表示成二进制形式for(intk=0;kb.size();k++)coutb[k];coutendl;intd=1,x=0;for(intii=b.size()-1;ii=0;ii--){x=d;d=(d*d)%n;if(d==1&&x!=1&&x!=n-1)returnfalse;if(b[ii]==1)d=(d*a)%n;}//b为素数if(d!=1)returnfalse;//不为素数returntrue;}doublequickindex1(doublea,doublem,doublen)//实现a^mmodn的运算{vectorintb;unsigneddoubleN=m;//公钥m=efor(intii=0,j=1;;ii++){if(jN)break;if((Nii)&(unsigneddouble)1)b.push_back(1);elseb.push_back(0);j*=2;}//将m表示成二进制形式doublec=0,d=1;for(inti=b.size()-1;i=0;i--){c*=2;d=(d*d)-int((d*d)/n)*n;if(b[i]==1){c+=1;d=(d*a)-int((d*a)/n)*n;}}returnd;}voidtransfer(charcypher[],doublec[])//字母变数字的过程{intm[100]={0};for(inti=0,j=0;cypher[j]!='\0';i+=2){if(cypher[j]==''){m[i]=0;m[i+1]=0;}//空格变为00else{m[i]=cypher[j]-64;//A的ASCII码为65，65-64=1if(m[i]10){m[i+1]=m[i];//m[i+1]=1,m[i]=0,所以A为01m[i]=0;}else{m[i+1]=m[i]%10;//例如Z的ASCII码为90，90-64=26，m[i+1]=26%10=6,m[i]=[26/10]=2,所以Z对应的数字为26m[i]=m[i]/10;}}j++;}for(intk2=0;k22*strlen(cypher);k2++)coutm[k2];coutendl;//输出明文字母变换数据的结果for(intk=0,n=0;k2*strlen(cypher);k+=4){c[n]=m[k]*1000+m[k+1]*100+m[k+2]*10+m[k+3];//两个字母一组，例如AB为0102n++;}for(;c[n-1]1000;)//最后一个数填充零，不过此例可要可不要c[n-1]*=10;}voidmain(){doublec[100]={0};//存放密文doublea[100]={0};//存放加解密中间变量doubleb[100]={0};//存放明文charcypher[]=ILOVETHEPEOPLE'SREPUBLICOFCHINA;//明文字符//对“我爱中华人民共和国”加解密transfer(cypher,c);//明文字母变数字的过程，输出结果将ILOVE......变为090012152205....for(intk1=0;c[k1]!='\0';k1++)coutc[k1];//将4位数字整理成有效的十进制数并再次输出，目的在于后面加密计算，例如“I”的数字0900整理后为900，“LO”的数字1215整理后为1215“L”0020整理为20//选取两个素数p=563，q=823doublen=0,fn=0,p=563,q=823,d=0;n=p*q;fn=(q-1)*(p-1);for(doublee=2;efn;e+=3){if(Euclid(e,fn)==1)break;}//选e使得与fn的最大公因数为1d=extenEuclid(e,fn);//求d=e^-1modfncoutendl密码和密钥edandn:;coutednendl;//加密过程coutendl加密：;for(inti=0;c[i]!='\0';i++){a[i]=quickindex1(c[i],e,n);//实现c=E(m)=m^emodn的运算,例如第一个加密为900^5mod563*823=389807couta[i];//输出密文信息}coutendl解密:;//解密过程for(intj=0;a[j]!='\0';j++){b[j]=quickindex1(a[j],d,n);//实现m=D(c)=c^dmodn,例如第一个解密为389807^92393mod563*823=900coutb[j];}coutendl;}