RSA加密解密的设计与实现

1、上海电力学院应用密码学课程设计题 目：RSAim密解密的设计与实现院 系：计算机科学与技术学院专业年级：2010级学生姓名：李正熹 学号:20103273指导教师：田秀霞2013年1月8日目录目录1. 设计要求2. 开发环境与工具3. 设计原理（算法工作原理）4. 系统功能描述与软件模块划分5. 设计核心代码6. 参考文献7. 设计结果及验证8. 软件使用说明9. 设计体会附录24 / 2210. 计要求1随机搜索大素数，随机生成公钥和私钥2用公钥对任意长度的明文加密3用私钥对密文解密4界面简洁、交互操作性强11. 发环境与工具Windows XP操作系统Microsoft Visual C+

2、 6.01.创建rsa工程2.在rsa工程中创建20103273李正熹cpp文件12. 计原理RS期法简介公开密码算法与其他密码学完全不同，它是基于数学函数而不是基于替换或 置换。与使用一个密钥的对称算法不同，公开密钥算法是非对称的，并且它使用 的是两个密钥，包括用于加密的公钥和用于解密的私钥。公开密钥算法有RSAElgamal 等。RSA公钥密码算法是由美国麻省理工学院（MIT）的Rivest, Shamir和Adleman 在1978年提出来的，并以他们的名字的有字母命名的。RSA是第一个安全、实用的公钥密码算法，已经成为公钥密码的国际标准，是目前应用广泛的公钥密码体 制。RSA勺基础是数

3、论的Euler定理，其安全性基于二大整数因子分解问题的困难 性，公私钥是一对大素数的函数。并且该算法已经经受住了多年深入的密码分析， 虽然密码分析者既不能证明也不能否定 RSA的安全性，但这不恰恰说明该算法有 其一定的可信度。13. 统功能描述与软件模块划分功能：1 .进行加密加密第一步，随机两个素数 p和q,并求出n = p*q,然后再求出n的欧拉函数值phi。第二步，在e, phi中选出一个与 phi互素的整数e,并根据e*d = 1 (mod phi),求出e 的乘法逆元。至此我们已经得到了公开密钥e, n和秘密密钥d, n。第三步，让用户输入要进行加密的小于n一组正整数(个数不超过 M

4、AXLENGTH,输入以-1为结束标志，实际个数存入size中，正整数以clearMAXLENGTH(呆存。第四步，对第三步所彳#的明文 clearMAXLENGTH进行力口密。遍历clearsize,对每一个整数用以下算法进行加密 ,并将加密后的密文保存在CiphertextMAXLENGTH 中。第五步，输出密文CiphertextMAXLENGTH2 . 进行解密第一步，输入加密后的密文Ciphertext1MAXLENGTH,输入以-1为结束标志第二步，输入解密密钥d,phi,对密文进行解密，结果保存在 DecryptionTextMAXLENGTH中。第三步，输出解密后明文Decry

5、ptionTextMAXLENGTH生成随机素数： 先生成一个随机数然后判断它是否为素数从而输出unsigned long foo() / 生成随机数int panduan(unsigned long b) /判断是否为素数unsigned long tiqu(unsigned long &p,unsigned long &q) / 从随机素数中选取两个为p和q求 e 时需要用到 e 与 phi 的互逆 所以在随机产生e 的同时需要作互逆判断若互逆则输出随机e 否则重新生成 eint gcd(int x,int y) / 判断两数是否为互素在 p 、 q、 e 都准备就绪的时候

6、就可以进行加解密的运算 因为考虑到溢出 所以 3个一组进行加解密void Encryption() / 加密算法void Decryption() / 解密算法5 .设计核心代码unsigned long foo()unsigned long random = 0;srand(int)time(0);random = rand() % 300;return random;srand 函数是随机数发生器的初始化函数需要提供一个种子这里使用 time 来获取系统当前时间rand() % 300是随机 0-299 的整数/ 以下为加密算法void Encryption()/ 加密算法cout <

7、;< "随机生成两个较大的素数："<<endl ;tiqu(p,q);n = p * q;/ 求解 n，phi = (p - 1) * ( q - 1 );/求解 n 的欧拉函数值cout << " n = " << n << ", phi = " << phi << endl;cout << " 请从 0 ， " << phi - 1 << "中选择一个与"<<phi&

8、lt;<"随机生成互素的数 e： "while(1)e=foo();if(gcd(e,phi)=1&&e>=100&&e<=300&&e!=q&&e!=p)break;cout<<e<<endl;float d0;for( int i = 1; ; i+)/求解乘法逆元 e * d = 1 (mod phi)d0 = (float)(phi*i+1) / e;if( d0 - (int)d0 = 0 )break;d = (int)d0;cout << en

9、dl;cout << " e = " << e << ", d = " << d << endl;cout << "公开密钥 Pk = e,n = " << e << "," << n << "" << endl;cout << "秘密密钥 Sk = d,n = " << d << ","

10、<< n << "" <4"录私钥"<< endl;cout << endl;cout << "请3位一组输入要加密的正整数(以-1结束)："<< endl;cout << "加密前的明文为："for( i = 0; i < MAXLENGTH; i+)Ciphertexti = 1;int count;for(int j = 0; j<MAXLENGTH; j+)cin >> clearj;if( c

11、learj = -1 )break;count = e;while(count > 0)/对明文进行加密 Ciphertext = (clear) A e mod nCiphertextj = (Ciphertextj * clearj) % n;/加密算法count- ;cout << " 密文为：size = j;/实际密文长度for(int k=0; k<j; k +)cout << Ciphertextk << " "cout << endl ;/ 以下为解密算法void Decryption()

12、/ 解密算法int pp,kk;for(int i = 0; i < MAXLENGTH; i+)DecryptionTexti = 1;int count;cout<<"请输入要解密的密文(以-1结束)："<<endl;for(int u = 0; u<MAXLENGTH; u+)cin >> Ciphertext1u;if( Ciphertext1u = -1 )break;cout<<"输入密钥解密(d,n)"<<endl;cin>>pp>>kk;for

13、(int j = 0; j < size; j+)count = pp;while(count > 0)/对密文进行解密 DecryptionText = (Ciphertext) A d (mod n) DecryptionTextj = (DecryptionTextj * Ciphertext1j) %kk); count- ;cout << " 解密后的明文为： "for( int k = 0; k < size; k +)cout << DecryptionTextk << " "cout

14、<< endl ;6 .参考文献1赛迪网RSA 2010:云安全需急迫解决的安全隐患.旧金山：赛迪网，2010.2赛迪网.RSA主席认为云安全成 2010安全领域趋势.旧金山：赛迪网，2010.3魏晨 . 安全风向标：品味RSA 2012信息安全大会.旧金山：赛迪网， 2012.4 四夕新的安全威胁而前需要新的安全架构. 旧金山：赛迪网，2012.5王茜.倪建伟，一种基于RSA的加密算法.重庆大学学报，2005, 28 (1): 68-72.6周升力.RSA密码算法的研究与改进实现.现代计算机，2008: 51-53.7管占明.邓亚娟.RSA加密算法的研究及应用.科技广场，2009

15、: 98- 99.8胡向东，魏琴芳等应用密码学北京市：电子工业出版社， 2008: 114-119 9卢开澄计算机密码学.北京市：清华大学出版社，2002: 73-7710 史予荣软件加密技术从入门到精通，北京市：清华大学出版社 2007: 74-77.7.设计结果及验证进行加密得到公钥( 113， 11021 )和私钥( 2105， 11021 )加密明文 123 587 114 56 18 9得到密文1453 385 7882 6329 4873 2744输入密文解密得到先前加密的明文123 587 114 56 18 9。晨*C ; XBuuiiLK&iit s Mil 5帽11

16、111&翅411*上11工静111程。工熹面新建文件夫：。匕1|114。.exe*请输入，卜机生成两个较大的素数士Egd-107n - 11021. phi - 10812清从3, 1HHL1J中选择一个与IkBIZ值机生成互素的数e：113t - 113, A - 2165公升密扁 P务-<e,n> - <113,11021>期密密期Sb = <d,n> = £2工醍，102一记录私钥昌加密的正整戮（以-1结束:123 58? 114 SE 18 9 -1385 7882 6329 4873 2744清如密R即加解密系统 由李正春壬赛共同

17、元成ci 7 l)ftcu»ftnt s and Eei'十 1id Mt rat 力r葛面*音建文件要tUehiiE、十了-疗r爵苫文为；140 28G 78824073 2744成完同钱共密密统晚李如仃出逑鼻a口 正 12 8RS手由*h人要颦密的密文（以-工结束）：1453 385 7882 6329 4873 2744 r输入密钥解密”，n>2105 11021解密后的明文为：123 587 114 £6 18 ?才密密统 ,If r有出 止12 0 李由8.软件使用说明1 .选才¥ RSA加解密系统功能1为加密2为解密0为退出输入其他错误重

18、新输入"C;'Document手 and SeEicg寻t Ad*i.ni3tetor、字面iZ口1032T铸F喜Dobue、？口1 .同嘴普密统 翻李停出 加熹用油.is s«止 1 2 Si blf2 .输入1进行加密过程cS -C: YDocuMent s and Ecttii113tA&ini.mt ratnrl桌面.2O1 0N2T3季iF喜tDcbug12(lR£ A龙解密系班由率让意李羲共同完成工.进.笳密?.进行施密 瓦退出素统请输入，施机生成两个较大的素数.p=103q=113n = £163?, phi = 11424

19、请从叽11423】中选译一个与11424随矶生成互素的数a.129e = 139, d = 1315裁开密包 Fk = <e,n> = <139,11639秘密密钥Ek - <drn> - £13韭4”39：记录私钥1蕊瑞霆潦加密的正整数（以-工结束）I输入需要加密的明文3个一组 空格空开-1结束c* *C: Docimen-ts and1口匕5且&1<11 st rat or0 卓面201 032 T 3季正喜、Debug，？01_请输入，遁机生成两个较大的素数：P-103q=113n = 11&39, phi = 11424请从

20、氏11423 中选择一个与1142 4随机生成红素的数e： 139e = 139, d = 1315公开密钥 Pk = <e.n> = <139,1163?>秘密密钥£k = <d,n> = 心1力116393记录私福请3位一组於胃加密的正整数C以-挂挑）；.加建刖的明文为：123 654 7S9 -1密文为：9663 5806 40110退出清瑜人t生成密文 并且返回主界面2.输入2进行解密随机生成两个较大的素如«=113n = 11639, phi = 11424请从丸114231中选择一个与11424殖机生成立素的效 139c -

21、139, d - 1315公开密福 Pk =飙，Q = <139,11629>超密密幅Sk - <d,n> - £1315.11639记录私钥请3位一组施江加密的正整数:加密前的明文为M 123 654 7HV -1密文为士 9663 5606 401J账0加解密系统由李壬鼠李蕾共同完成L .逆行加密2 .进拉睚密 比退出系统请输入输入要解密的密文（以-1结束）.输入加密好的密文-1结束0; DucuMtid s and 3nng苴uloiA泉面201 032T3聿正素* *p=103q=113n = 1163? phi = 114Z4-胄从1% U找3】中选

22、择一个与口也4随机生成互素的数e； 13?& - 139, d - 1315公开密朝 P* - <*nn> = £139Ji639)韶密密曲&1( - <d.n> = <1315.11639)记录私48清3位一组断人要加密的正整数(以T结束)：加密前的明文为1 123 654 787 -1密文为:9663 58K 4S11商共密密统 的车行行出 礴至量 bN止 L 2 H 爨由请输入，2请输入要解密的密文(以T结束)；9663 5806 4S11 -1输入密切解密Cd.n)输入密钥d n；Docu*cnt 3 and 5仁士 十 号腱#&

23、amp;(1*1111工土工01。工层面2口1。3273正苕'口£1>11.%201.1."加密制的明乂大：123 654 789 -1空文为：58幽4(011底完同颉我密密统 睡季彷仃出 蹄熹三卡E季由请输入2请箍人要解密的密又以-1结束)tY663 SUU6 Wil -1输入密钥解密7.2131S 1163?解密后的明文为：123萌4 789fg入辙清.第解系整一IX仃出统共解密得到加密前明文解密成功返回主界面9.设计体会RSA课程设计中，包含了加解密的过程，刚开始对做设计的时候，觉得对于RSA的力喉军密只要套用公式就可以很方便地进行，实现并不是非常困难。

24、但是在真正实现的时候还是碰到了不少的问题，在随机产生素数的时候，不同的实现方法会具有不同的复杂度，从而使得时间效率也有所不同，若直接生成素数，系统需要很长一段时间来生成，而随机生成一个数后再判断是否为素数可以减少很多时间，效率也就提高了。在加解密的时候， 起初使用的是int 型的整形变量， 但是发现 int 型只有 4 位长度 8 字节，所以在计算时， 数字一大就会产生溢出， 所以使用了数组进行了加解密。 而在大素数生成时，可以生成非常大的素数，但是在加密时，因为程序效率过于低以至于一天都没有算出结果，所以在实现时使用了可进行运算和实现较大的素数而并不是大素数。随机大素数进行RSA加解密的程序

25、还需要时间进行进一步改进。需要进一步调用大整数的加减乘除算法，素数明文密文密钥公钥都要使用数组才能加以实现，在此暂时保留这个程序，将用更充分的时间来实现。总结这次课程设计，不可否定又是一次对于自己编程能力的提升以及团队合作的加深，自己动手编程真的是一种成就感， 然而在这以外， 我还发现了自己会有一些突发奇想的思路，会发现和挖掘实现实验时某些过程的优化，而这些思路又可以帮助自己来完成程序。这次课程设计的不足是还没有完全完成课程设计所需要的任务要求，写的程序还是略微有点简单化了，可能自己能力还是有限，在静候的时间里还需要更加的磨练才行。附录#include <iostream>#inc

26、lude <ctime>#include <cstdlib>#include <cmath>using namespace std;#define MAXLENGTH 500 / 明文最大长度，即所允许最大整数个数int size = 0;/保存要进行加密的正整数的个数unsigned long p, q; / 两个大素数int n, phi; /n = p * q ， phi = (p-1) * (q-1) 是 n 的欧拉函数值int e;/e, n 为公开密钥int d;/d, n为秘密密钥long clearMAXLENGTH,CiphertextMA

27、XLENGTH,Ciphertext1MAXLENGTH办别用于存放加 / 密前的明 / 文和加密后的密文long DecryptionTextMAXLENGTH;修放解密后的明文/unsigned long foo()unsigned long random = 0;srand(int)time(0);random = rand() % 300;return random;int panduan(unsigned long b)int flag=1;if(flag)for(unsigned long j=2;j<=sqrt(b);j+)if(b%j=0)flag=0;/cout<

28、<b<<"bu 是素数 !"<<endl; if(flag)return 1;else return 0;unsigned long tiqu(unsigned long &p,unsigned long &q)label:while(1)p=foo();if(panduan(p)&&p>100&&p<300)/cout<<"p="<<p<<'t'break;while(1)q=foo();if(panduan(q

29、)&&q>100&&q<300)/cout<<"q="<<q<<'t'break;if(p!=q)cout<<"p="<<p<<endl;cout<<"q="<<q<<endl;else goto label;return 0;int gcd(int x,int y)int t;while (y)t=x;x=y;y=t%y;return x;/ 以下为加密算法void

30、Encryption()/ 加密算法cout << "随机生成两个较大的素数："<<endl ;tiqu(p,q);n = p * q;/ 求解 n，phi = (p - 1) * ( q - 1 );/求解 n 的欧拉函数值cout << " n = " << n << ", phi = " << phi << endl;cout << " 请从 0 ， " << phi - 1 << &quo

31、t;中选择一个与"<<phi<<"随机生成互素的数 e： "while(1)e=foo();if(gcd(e,phi)=1&&e>=100&&e<=300&&e!=q&&e!=p)break;)cout<<e<<endl;float d0;for( int i = 1; ; i+)/求解乘法逆元 e * d = 1 (mod phi)d0 = (float)(phi*i+1) / e;if( d0 - (int)d0 = 0 )break;)

32、d = (int)d0;cout << endl;cout << " e = " << e << ", d = " << d << endl;cout << "公开密钥 Pk = e,n = " << e << "," << n << "" << endl;cout << "秘密密钥 Sk = d,n = " <&l

33、t; d << "," << n << "" <4"录私钥"<< endl;cout << endl;cout << "请3位一组输入要加密的正整数(以-1结束)："<< endl;cout << "加密前的明文为："for( i = 0; i < MAXLENGTH; i+)Ciphertexti = 1;int count;for(int j = 0; j<MAXLENGTH;

34、j+)cin >> clearj;if( clearj = -1 )break;count = e;while(count > 0)/对明文进行加密 Ciphertext = (clear) A e mod nCiphertextj = (Ciphertextj * clearj) % n;/ 加密算法count- ;cout << " 密文为： " ;size = j;/实际密文长度for(int k=0; k<j; k +)cout << Ciphertextk << " "cout << endl ;/ 以下为解密算法void Decryption()/ 解密算法int pp,kk;for(int