密码算法安全分析与算法攻击分析解析

1、实验项目与实验报告（1 ）学科：信息与网络安全学号：20134088141姓名：羊波 时间：10月11日实验项目：RSA加密解密算法的实现（使用工具软件与代码实现）及 RSA的安全性分析实验目的： 通过利用RAS工具的使用实现加密和解密过程，加深对公钥（非对称）密码算法的认识。一、实验步骤：.完成实验教程1-3.登录网络平台修改作业发布密码，上传实验报告一.注册百度知道号，并加入知行网络团队。二、实验内容：实验原理：公钥密码算法是指一个加密系统的加密密钥和解密密钥是不同的，或者说不能用其中一个推导出另一个。在公 钥密码算法的两个密钥中，一个是用于加密的密钥，它是可以公开的，称为公钥；另一个是用

2、于解密的密钥， 是保密的，称为私钥。公钥密码算法解决了对称密码体制中密钥管理的难题，并提供了对信息发送人的身份进 行验证的手段，是现代密码学的最重要的发明。RAS算法描述如下：.公钥选择两个不同的大素数 p和q （一般都为100位左右的十进制数字），n是二者的乘积； 计算乘积：n=pq；计算欧拉函数值：4 n）= （p-1） （q-1）;随机选取正整数 e,使其满足1e:Exact size: 33 |BrtsPrriate Exp. (D.4540327133GenerateRfiftdorn data generationStal10CT：Faciormg mh Prime factors

3、 j：65S37 RSA-Tool 2 by tE!Keysize (Eits) Public txp. (E.Mu mfrer Ba se45371Random data generatcn1C0%Prime iP :Modulus (Hr：14E621D7110.在 “ KeySize(Bits)图78.记录下“Prime(P) ”编辑框中的十六进制文本内容：BCF39.再次重复第2步。Pt1日怕 Exp (D : 1205137DDPrime ：Q: I1C5CB”编辑框中输入你所希望的密钥位数，从 32到4096,位数越多安全性也高，但运算速度越慢，一般选择1024位足够了；单击“ G

4、enerate”按钮生成，如下图8,图9所图8图9.单击“Test”按钮测试，在“ Message to encrypt ”编辑框中随意输入一段文本，然后单击 “Encrypt”按钮加密，再单击“ Decrypt”按钮解密，看解密后的结果是否和所输入的一致，如果一致表示所生成的RSA密钥可用，否则需要重新生成，如图10所示：图10.到此生成完成，“ Private Exp.(D) ”编辑框中的内容为私钥如下图11,第7步所记录的内容 为公钥(BCF3 , “Modulus (N)”编辑框中的内容为公共模数如下图 12,请将上述三段十六进制 文本保存起来即可。Private Cap (D);eE

5、4B4DAC17CEDC764t89BE81S132S5CF860EEDA9703F49FD70F5W5AADia5379W7CEDI2CB1 *CCO7&E3at56E2430EDOOO1SOE7E BTaArSIOBeZBJCTCECJBCOSE 146325D1FC2E56ED1 A4E5A6692FB13BF2BZC6F3+05D57AC905D03a437A8L7405.B455E44e50F726EA70DB72EC&5E31S54 -图11Modulus (N):Eka ct size:1 0之3 帕帕 |7F73ie443OB94DDI=FDCW5F033rQ97Ft7F3AA

6、21334499 F9A7BA9F04TFO5322B72FC3A2：FF2CS39F a fij E23C0 B08&7613T721A522FE12F2AJ617F43AQtAj65C0 DE 7BA532716F5647 CEA33.7A 771 F 5D46 324& a6E3l6AFF9 02017936D13Q+AD954C21A7AE2 3C9456DB Q2 420Z2 5AA7E9A CE 9&F 1 /DT(JCD379日 1 BAB ，图12使用代码实现:#include #include unsigned long prime1,prime2,ee;unsigned l

7、ong *kzojld( unsigned long p, unsigned long q) / 扩展欧几里得算法求模逆 unsigned long i=0,a=1,b=0,c=0,d=1,temp,mid,ni2;mid=p;while (mid!=1)while (pq)p=p-q;mid=p;i+;a=c*(-1)*i+a;b=d*(-1)*i+b;temp=a;a=c;c=temp;temp=b;b=d;d=temp;temp=p;p=q;q=temp;i=0; ni0=c;ni1=d;return (ni);unsigned long momi( unsigned long a, u

8、nsigned long b, unsigned long p) / 模嘉算法 unsigned long c;c=1;if (ap) a=a%p;if (bp) b=b%(p-1);while (b!=0)while (b%2=0) b=b/2;a=(a*a)%p;b=b-1;c=(a*c)%p;return (c);void RSAjiami()RSA 加密函数 unsigned long c1,c2;unsigned long m,n,c;n=prime1*prime2;system( cls);printf( Please input the message : n);scanf( %

9、lu ,&m);getchar();c=momi(m,ee,n); printf( The cipher is : %lu ,c); return ;void RSAjiemi() /RSA 解密函数 unsigned long m1,m2,e,d,*ni;unsigned long c,n,m,o;o=(prime1-1)*(prime2-1);n=prime1*prime2;system( cls);printf( Please input the cipher : n);scanf( %lu ,&c);getchar();ni=kzojld(ee,o);d=ni0;m=momi(c,d,

10、n);printf( The original message is : %lu ,m);return ;void main() unsigned long m;char cho;printf( Please input the two prime you want to use:n);printf(P= );scanf(%lu,&prime1);getchar();printf(Q=);scanf(%lu,&prime2);getchar();printf(E= );scanf(%lu,&ee);getchar();if (prime1prime2)m=prime1;prime1=prime

11、2;prime2=m;while (1)system( cls);printf( t*RSA密码系统 *n);printf( Please select what do you want to do:n);printf( 1.Encrpt.n ); printf( 2.Decrpt.n ); printf( 3.Exit.n);printf( Your choice: );scanf( %c,&cho);getchar();switch (cho)case 1 :RSAjiami();break ;case 2 :RSAjiemi();break ;case 3 :exit(0);defaul

12、t :printf( Error input.n ); break;getchar();将以上代码复制到实验环境C+锻件中。算法结果分析如下：.主界面初始化如下图1所示：J C:LJsrsAdmi nistratorDesldopDebuga .ext|三亘巨lea&e input the twoyou unt to use图12.设置密钥，输入两个素数 p和q,还有e的值，如下图2所示:匚:U&ersA d ini r i str jtorDeskto pDeb ug a.exePlease imput the two pr-ine you uant 七0 useP-610=6?E=17图2

13、3.对明文加密，n=pq=4087,输入公钥（e, n） : 17,4087如下图3,并回车得到图4: C:U 5ersAdmin istra torD eskt o pDebuga 金）c/Please input the messdie ； ：17,4087121 X:User5Adm in istrato rDesktopDehuga. exe3tMXMMBS 后;号马系统*W MX 3JC注厂 Flease select uhat de yea uant to do 1 .Ehcrjpt.Decrpt.Exit.Vour clio ice:图4.选择1并回车对明文加密，输入明文M=12

14、34,得到密文C=2793,如下图5所示:*1 CAUse rsAd m rni strato rDe sktopDeb jga, exeF lease in put tJie nos&ag上： 1234 Tlie cipheT is： 2V93图5J3 C:U?ersAdministratorDesktopDebiig3.fweFlease input tThe cipher-B7?3 r)ie api9Inalis * 1234RSA的安全性分析：理论上，RSA的安全性取决于因式分解模数 N的困难性。从严格的技术角度上来说这是不 正确的，在数学上至今还未证明分解模数就是攻击RSA的最佳方法

15、， 也未证明分解大整数就是NP问题（表示那些能在多项式时间内利用“不确定性图灵机可以求解的问题）。事实情况是，大 整数因子分解问题过去数百年来一直是令数学家头疼而未能有效解决的世界性难题。人们设想了 一些非因子分解的途径来攻击 RSA体制，但这些方法都不比分解n来得容易。因此，严格地说， RSA的安全性基于求解其单向函数的逆的困难性。RSA单向函数求逆的安全性没有真正因式分解模数的安全性高，而且目前人们也无法证明这两者等价。许多研究人员都试图改进RSA体制使它的安全性等价于因式分解模数。实验内容：（写出实验步骤及实验结果或数据，不够可写在左边：前页反面）实验中出现的问题及解决方法：.问题：一开始不理解 RSA算法的原理。解决方