2024年RSA算法实验报告

实

验

报

告姓名：XXXXXXXXX學号：0XXXXX班级：XXXXXXXXX曰期：/12/*題目：RSA算法试验一、试验环境1．硬件配置：处理器：Inter(R)Core(TM)i5-2430MCPU@2.40GHz(4CPUs),~2.4GHz内存：2048MBRAM2．使用软件：(1)操作系统：win7旗舰版(2)软件工具：MicrosoftVisualc++6.0二、试验波及的有关概念或基本原理它是第一种既能用于数据加密也能用于数字签名的算法。算法的名字以发明者的名字命名：RonRivest,AdiShamir和LeonardAdleman。但RSA的安全性一直未能得到理论上的证明。它經历了多种袭击，至今未被完全攻破。RSA的安全性依赖于大数分解。公钥和私钥都是两個大素数（不小于100個拾進制位）的函数。從一种密钥和密文推断出明文的难度等同于分解两個大素数的积。密钥對的产生。选择两個大素数，p和q。计算：n=p*q然後随机选择加密密钥e，规定e和(p-1)*(q-1)互质。最终，运用Euclid算法计算解密密钥d,满足e*d=1(mod(p-1)*(q-1))其中n和d也要互质。数e和n是公钥，d是私钥。两個素数p和q不再需要，应當丢弃，不要让任何人懂得。加密信息m（二進制表达）時，首先把m提成等長数据块m1,m2,...,mi，块長s，其中<=n,s尽量的

大。對应的密文是：ci=mi^e(modn)(a)解密時作如下计算：mi=ci^d(modn)(b)RSA可用于数字签名，方案是用(a)式签名，(b)式验证。详细操作時考虑到安全性和m信息量较大等原因，一般是先作HASH运算。RSA的安全性。RSA的安全性依赖于大数分解，但与否等同于大数分解一直未能得到理论上的证明，由于没有证明破解RSA就一定需要作大数分解。假设存在一种不必分解大数的算法，那它肯定可以修改成為大数分解算法。目前，RSA的某些变种算法已被证明等价于大数分解。不管怎样，分解n是最显然的袭击措施。目前，人們已能分解多种拾進制位的大素数。因此，模数n必须选大某些，因详细合用状况而定。RSA的速度。由于進行的都是大数计算，使得RSA最快的状况也比DES慢上倍，無论是软件還是硬件实現。速度一直是RSA的缺陷。一般来說只用于少許数据加密。RSA的选择密文袭击。RSA在选择密文袭击面前很脆弱。一般袭击者是将某一信息作一下伪装(Blind)，让拥

有私钥的实体签订。然後，通過计算就可得到它所想要的信息。实际上，袭击运用的都是同一种弱點，即存在這样一种事实：乘幂保留了输入的乘法构造：(XM)^d=X^d*M^dmodn前面已經提到，這個固有的問題来自于公钥密码系统的最有用的特性--每個人都能使用公钥。但從算法上無法处理這一問題，重要措施有两条：一条是采用好的公钥协议，保证工作過程中实体不對其他实体任意产生的信息解密，不對自已一無所知的信息签名；另一条是决不對陌生人送来的随机文档签名，签名時首先使用One-WayHashFunction對文档作HASH处理，或同步使用不一样的签名算法。在中提到了几种不一样类型的袭击措施。RSA的公共模数袭击。若系统中共有一种模数，只是不一样的人拥有不一样的e和d，系统将是危险的。最普遍的状况是同一信息用不一样的公钥加密，這些公钥共模并且互质，那末该信息無需私钥就可得到恢复。设P為信息明文，两個加密密钥為e1和e2，公共模数是n，则：C1=P^e1modnC2=P^e2modn密码分析者懂得n、e1、e2、C1和C2，就能得到P。由于e1和e2互质，故用Euclidean算法能找到r和s，满足：r*e1+s*e2=1假设r為负数，需再用Euclidean算法计算C1^(-1)，则(C1^(-1))^(-r)*C2^s=Pmodn此外，尚有其他几种运用公共模数袭击的措施。總之，假如懂得給定模数的一對e和d，一是有助于袭击者分解模数，一是有助于袭击者计算出其他成對的e’和d’，而無需分解模数。处理措施只有一种，那就是不要共享模数n。RSA的小指数袭击。有一种提高RSA速度的提议是使公钥e取较小的值，這样會使加密变得易于实現，速度有所提高。但這样作是不安全的，對付措施就是e和d都取较大的值。三、试验内容重要的措施：（1）、publicstaticvoidGetPrime()措施名称：产生大数的措施。阐明： 运用Java語言的中的java.math.BigInteger类的措施中随机产生大数。（2）、publicstaticbooleanMillerRobin(BigIntegernum)措施名称：判断与否是素数的措施。参数阐明：num是由GetPrime措施产生的大数。阐明：這個措施判断GetPrime措施传過来的与否是一种素数，是就返回true,否就返回false。 （3）、publicstaticBigIntegerpowmod(BigIntegera,BigIntegert,BigIntegernum)措施名称：大数的幂运算措施。阐明： 這個措施對传入的大数進行幂运算。（4）、publicstaticBigIntegerinvmod(BigIntegera,BigIntegerb)措施名称：大数的取模运算措施。 阐明：這個措施對大数進行取模运算。（5）、publicstaticStringEncode(StringinStr,BigIntegerPrimeP,BigIntegerPrimeQ,BigIntegern,intnLen,intm,JTextFieldd)措施名称：加密算法。参数阐明： inStr是從界面输入的明文。 PrimeP和PrimeQ是由GetPrime措施产生的两個大素数。 n是由PrimeP和PrimeQ得到的值。 nLen為n的長度。 d為公钥。（6）、publicstaticStringDecode(StringinStr,BigIntegerPrimeP,BigIntegerPrimeQ,BigIntegern,intnLen,intm,JTextFielde)措施名称：解密算法。参数阐明： inStr是從界面输入的明文。 PrimeP和PrimeQ是由GetPrime措施产生的两個大素数。 n是由PrimeP和PrimeQ得到的值。 nLen為n的長度。 e為私钥。流程图：RSA公钥加密算法流程图：RSA私钥解密算法流程图：重要代码：鉴定一种数与否為素数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;}②将拾進制数据转化為二進制数组voidswitch_to_bit(Elemtypeb,Elemtypebin[32]){intn=0;while(b>0){ bin[n]=b%2; n++; b/=2;}③求最大公约数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){returna[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;i<3;i++){ t[i]=a[i]-q*b[i]; a[i]=b[i]; b[i]=t[i]; }}⑤迅速模幂算法Elemtypemodular_multiplication(Elemtypea,Elemtypeb,Elemtypen){Elemtypef=1;Elemtypebin[32];switch_to_bit(b,bin);for(inti=31;i>=0;i--){ f=(f*f)%n; if(bin[i]==1){ f=(f*a)%n; }}returnf;}⑥产生密钥voidproduce_key(){cout<<"输入素数p和q:";cin>>p>>q;while(!(test_prime(p)&&test_prime(q))){ cout<<"输入錯误，請重新输入!"<<endl; cout<<"输入素数p和q:"; cin>>p>>q;};pr.n=p*q;pu.n=p*q;fn=(p-1)*(q-1);cout<<"fn為："<<fn<<endl;cout<<"输入随机数e:";cin>>e;while((gcd(fn,e)!=1)){ cout<<"e输入錯误，請重新输入!"<<endl; cout<<"输入随机数e:"; cin>>e;}pr.d=(extend_euclid(fn,e)+fn)%fn;pu.e=e;flag=1;cout<<"公钥(e,n）:"<<pu.e<<","<<pu.n<<endl;cout<<"私钥d:"<<pr.d<<endl;cout<<"請输入下一步操作序号:"<<endl;}⑦加密voidencrypt(){if(flag==0){cout<<"setkeyfirst:"<<endl;produce_key(); }cout<<"输入明文m:";cin>>m;c=modular_multiplication(m,pu.e,pu.n);cout<<"密文c為:"<<c<<endl;cout<<"請输入下一步操作序号:"<<endl;}⑧解密voiddecrypt(){if(flag==0){ cout<<"setkeyfirst:"<<endl; produce_key();}cout<<"输入密文