密码学-RSA加密解密算法的实现课程设计报告

1密码学课程报告《RSA加密解密算法》专业：信息工程（信息安全）班级：1132102学号：201130210214姓名：周林指导老师：阳红星时间：2014年1月10号2一、课程设计的目的当前最著名、应用最广泛的公钥系统RSA是在1978年，由美国麻省理工学院(MIT)的Rivest、Shamir和Adleman在题为《获得数字签名和公开钥密码系统的方法》的论文中提出的。RSA算法是第一个既能用于数据加密也能用于数字签名的算法，因此它为公用网络上信息的加密和鉴别提供了一种基本的方法。它通常是先生成一对RSA密钥，其中之一是保密密钥，由用户保存；另一个为公开密钥，可对外公开，甚至可在网络服务器中注册，人们用公钥加密文件发送给个人，个人就可以用私钥解密接受。为提高保密强度，RSA密钥至少为500位长，一般推荐使用1024位。公钥加密算法中使用最广的是RSA。RSA算法研制的最初理念与目标是努力使互联网安全可靠，旨在解决DES算法秘密密钥的利用公开信道传输分发的难题。而实际结果不但很好地解决了这个难题；还可利用RSA来完成对电文的数字签名以抗对电文的否认与抵赖；同时还可以利用数字签名较容易地发现攻击者对电文的非法篡改，以保护数据信息的完整性。此外，RSA加密系统还可应用于智能IC卡和网络安全产品。二、RSA算法的编程思路1.确定密钥的宽度。2.随机选择两个不同的素数p与q，它们的宽度是密钥宽度的1/2。3.计算出p和q的乘积n。4.在2和Φ(n)之间随机选择一个数e,e必须和Φ(n)互素，整数e用做加密密钥（其中Φ(n)=(p-1)*(q-1)）。5.从公式ed≡1modΦ(n)中求出解密密钥d。6.得公钥（e，n）,私钥(d,n)。7.公开公钥，但不公开私钥。8.将明文P(假设P是一个小于n的整数)加密为密文C，计算方法为：C=Pemodn9.将密文C解密为明文P，计算方法为：P=Cdmodn然而只根据n和e（不是p和q）要计算出d是不可能的。因此，任何人都可对明文进行加密，但只有授权用户（知道d）才可对密文解密三、程序实现流程图：1、密钥产生模块：32、解加密流程模块：4四、部分算法代码判定一个数是否为素数booltest_prime(Elemtypem){if(m=1){returnfalse;}elseif(m==2){returntrue;}else{for(inti=2;i=sqrt(m);i++){if((m%i)==0){returnfalse;break;}}returntrue;}}求最大公约数Elemtypegcd(Elemtypea,Elemtypeb){order(a,b);intr;if(b==0){returna;}else{while(true){r=a%b;a=b;b=r;if(b==0){returna;break;}用扩展的欧几里得算法求乘法逆元Elemtypeextend_euclid(Elemtypem,Elemtypebin){order(m,bin);Elemtypea[3],b[3],t[3];a[0]=1,a[1]=0,a[2]=m;b[0]=0,b[1]=1,b[2]=bin;if(b[2]==0){5returna[2]=gcd(m,bin);}if(b[2]==1){returnb[2]=gcd(m,bin);}while(true){if(b[2]==1){returnb[1];break;}intq=a[2]/b[2];for(inti=0;i3;i++){t[i]=a[i]-q*b[i];a[i]=b[i];b[i]=t[i];}}}加密voidencrypt(){if(flag==0){coutsetkeyfirst:endl;produce_key();}label3:coutinputm:;cinm;while(!cin){cin.clear();chara;cina;coutwronginput,Pleaseenteraninteger!endl;gotolabel3;}c=modular_multiplication(m,pu.e,pu.n);coutcis:cendl;}解密voiddecrypt(){if(flag==0){coutsetkeyfirst:endl;produce_key();}label4:coutinputc:;cinc;6while(!cin){cin.clear();chara;cina;coutwronginput,Pleaseenteraninteger!endl;gotolabel4;}m=modular_multiplication(c,pr.d,pr.n);coutmis:mendl;五、部分截图78六、程序代码#includeiostream.h#includeconio.h#includemath.h#includestdlib.h#includestring.hintgo(intk,charbk[16]);intTransform(intm,intk,intn);intgcd(inta,intb);intIsPrime(inta);go(intk,charbk[16]){intn=0;while(k0){bk[n]=k%2;n++;k/=2;}returnk;}intTransform(intm,intk,intn){longintr=1;charbk[16];go(k,bk);for(inti=15;i=0;i--){r=(r*r)%n;if(bk[i]==1){r=(r*m)%n;}}returnr;}intgcd(inta,intb){for(inti=2;i=sqrt(ab?a:b);i++)if((a%i==0)&&(b%i==0))return0;9return1;}intIsPrime(inta){for(inti=2;i=sqrt(a);i++)if(a%i==0)return0;return1;}voidmain(){intc,e,d,m,n,z,p,q;cout\t************简单RSA加密解密算法***********\n\n;cout请输入p:;cinp;while(!IsPrime(p)){cout您输入的p不是素数，请重新输入:;cinp;}cout请输入q:;cinq;while(!IsPrime(q)){cout您输入的q不是素数，请重新输入:;cinq;}cout\n由p和q求得n和ф(n)endl;n=p*q;z=(p-1)*(q-1);coutn=nandф(n)=zendl;coutendl请输入e:;cine;while(!gcd(e,z)){coute应该和ф(n)互素:;cine;}cout求得解密密钥;d=1;while(((e*d)%z)!=1)d++;10coutd=dendl;coutendl请输入明文m:;cinm;while(m=n||m=0){cout请重新输入明文m（0mn）;cinm;}cout求得密文为：;c=Transform(m,e,n);coutc=cendl;coutendl请输入密文c:;cinc;cout求得明文为：;m=Transform(c,d,n);coutm=mendl;getch();}七、心得体会通过做此次课程设计，对RSA加密解密算法有了更近一步的了解。RSA通过使用公钥加密、私钥解密，完成了乙方到甲方的一次数据传递，通过私钥加密、公钥解密，同时通过私钥签名、公钥验证签名，完成了一次甲方到乙方的数据传递与验证，两次数据传递完成一整套的数据交互！掌握了RSA算法的基本原理、体验应用效果，以及如何判断一个数是否为素数，以及用扩展的欧几里得算法求乘法逆元问题，以及解密和加密算法。虽然中间遇到了一些难题，但是在老师及同学的帮助下，顺利完成此次课程设计。