《RSA算法课程设计报告.doc》由会员分享，可在线阅读，更多相关《RSA算法课程设计报告.doc（20页珍藏版）》请在三一办公上搜索。
1、摘要： RSA算法是基于数论的公钥密码体制，是公钥密码体制中最优秀的加密算法，同时也是第一个能同时用于加密和数字签名的算法，也易于理解和操作。 RSA是被研究得最广泛的公钥算法，从提出到现在已近二十年，经历了各种攻击的考验，逐渐为人们接受，普遍认为是目前最优秀的公钥方案之一。RSA的安全性依赖于大数的因子分解，但并没有从理论上证明破译RSA的难度与大数分解难度等价。本文主要研究的内容包括：第一,对RSA算法进行了全面系统的介绍，包括RSA算法的应用现状和原理大素数的产生、密钥对的产生、对明文的加密运算和密文的解密运算，为具体实现打下了理论基础；第二,介绍了RSA机密体制的一些基本概念及原理；第
2、三，详述了RSA加密的设计与实现，主要实现的模块包括RSA密钥的产生（一对公钥和私钥），RSA加密算法和解密算法的实现；第五,对该系统进行了整体的测试和分析改进； 关键词：RSA算法；公钥密码体制；加密；解密；VC+目录1 课题综述11.1 课题来源11.2 课题意义11.3 预期目标12 系统分析12.1 基础知识22.2 总体方案42.3 功能模块43 系统设计53.1 算法描述53.2 流程图74 代码编写95 运行与测试145.1 产生公钥和密钥145.2 加密与解密14总 结16致 谢17参考文献181 课题综述1.1 课题来源随着电子信息技术的迅速发展，人类已步入信息社会。但是由于
3、整个社会形成了一个巨大的计算机网络，任何一个计算机网络出现的安全问题，都会影响整个国家的网络安全，所以信息安全、计算机网络安全问题已引起了人类的高度重视。无论是在局域网还是在广域网中，都存在着自然和人为等诸多因素的脆弱性和潜在威胁。故此，网络的安全措施应是能全方位地针对各种不同的威胁和脆弱性，这样才能确保网络信息的保密性、完整性和可用性。现代密码学已成为信息安全技术的核心，密码学是以研究通信安全保密的学科，即研究对传输信息采用何种秘密的变换以防止第三者对信息的窃取。公钥密码体制的特点是：接收方B产生一对密钥（PK和）；公开，保密；从推出是很困难的；、双方通信时，通过任何途径取得的公钥，用的公钥
4、加密信息，加密后的信息可通过任何不安全信道发送。收到密文信息后，用自己私钥解密恢复出明文。公钥密码体制已成为确保信息的安全性的关键技术。RSA公钥密码体制到目前为止还是一种被认可为安全的体制。1.2 课题意义RSA公钥加密算法是第一个既能用于数据加密也能用于数字签名的算法。它易于理解和操作，也十分流行。算法的名字以发明者的姓氏首字母命名：Ron Rivest, Adi Shamir 和Leonard Adleman。虽然自1978年提出以来，RSA的安全性一直未能得到理论上的证明，但它经历了各种攻击，至今未被完全攻破。随着越来越多的商业应用和标准化工作，RSA已经成为最具代表性的公钥加密技术。
5、VISA、MasterCard、IBM、Microsoft等公司协力制定的安全电子交易标准（Secure Electronic Transactions，SET）就采用了标准RSA算法，这使得RSA在我们的生活中几乎无处不在。网上交易加密连接、网上银行身份验证、各种信用卡使用的数字证书、智能移动电话和存储卡的验证功能芯片等，大多数使用RSA技术。应用了RSA加密体制保证了秘密信息的安全。1.3 预期目标在充分理解RSA加密体制概念和原理的基础上，用Microsoft Visual C+ 6.0实现RSA加密与解密，演示公钥与密钥的生成及加密与解密的过程。2 系统分析2.1 基础知识2.1.1
6、素数称整数p(p1)是素数，如果p的因子只有1，p。称c是两个整数a、b的最大公因子，如果 c是a的因子也是b 的因子，即c是a、b的公因子。 a和b的任一公因子，也是c的因子。表示为c=gcd(a, b)。由于要求最大公因子为正，所以gcd(a,b)=gcd(a,-b)=gcd(-a,b)=gcd(-a,-b)。一般gcd(a,b)=gcd(|a|,|b|)。由任一非0整数能整除0，可得gcd(a,0)=|a|。如果将a，b都表示为素数的乘积，则gcd（a, b）极易确定。一般由c=gcd(a,b)可得： 对每一素数p，cp=min(ap,bp)。由于确定大数的素因子不很容易，所以这种方法不
7、能直接用于求两个大数的最大公因子，如何求两个大数的最大公因子在下面介绍。如果gcd(a,b)=1，则称a和b互素。2.1.2 模运算设n是一正整数，a是整数，如果用n除a，得商为q，余数为r，则a=qn+r,0rn, 其中x为小于或等于x的最大整数。用a mod n表示余数r如果(a mod n)=(b mod n)，则称两整数a和b模n同余，记为ab mod n。称与a模n同余的数的全体为a的同余类，记为a，称a为这个同余类的表示元素。2.2.3 欧拉函数和欧拉定理欧拉函数：设n是一正整数，小于n且与n互素的正整数的个数称为n的欧拉函数，记为(n)。若n是素数，则显然有(n)=n-1。若n是
8、两个素数p和q的乘积，则(n)=(p)(q)=(p-1)(q-1)。欧拉定理：若a和n互素，则a(n)1 mod n。2.1.4 欧几里德算法欧几里得（Euclid）算法是数论中的一个基本技术，是求两个正整数的最大公因子的简化过程。而推广的Euclid算法不仅可求两个正整数的最大公因子，而且当两个正整数互素时，还可求出其中一个数关于另一个数的乘法逆元。1. 求最大公因子：Euclid算法是基于下面一个基本结论： 对任意非负整数a和正整数b，有gcd(a, b)=gcd(b, a mod b)。2. 求乘法逆元：如果gcd(a, b)=1 ，则b在mod a下有乘法逆元（不妨设ba），即存在一x
9、 (xa)，使得bx1 mod a。2.1.5 RSA算法中的计算问题1. RSA的加密与解密过程RSA的加密、解密过程都为求一个整数的整数次幂，再取模。如果按其含义直接计算，则中间结果非常大，有可能超出计算机所允许的整数取值范围。如上例中解密运算6677 mod 119，先求6677再取模，则中间结果就已远远超出了计算机允许的整数取值范围。而用模运算的性质：(ab) mod n=(a mod n)(b mod n) mod n就可减小中间结果再者，考虑如何提高加、解密运算中指数运算的有效性。例如求x16，直接计算的话需做15次乘法。然而如果重复对每个部分结果做平方运算即求x，x2，x4，x8
10、，x16则只需4次乘法。2. RSA密钥的产生产生密钥时，需要考虑两个大素数p、q的选取，以及e的选取和d的计算。因为n=pq在体制中是公开的，因此为了防止敌手通过穷搜索发现p、q，这两个素数应是在一个足够大的整数集合中选取的大数。如果选取p和q为10100左右的大素数，那么n的阶为10200，每个明文分组可以含有664位（102002664），即83个8比特字节，这比DES的数据分组（8个8比特字节）大得多，这时就能看出RSA算法的优越性了。因此如何有效地寻找大素数是第一个需要解决的问题。寻找大素数时一般是先随机选取一个大的奇数（例如用伪随机数产生器），然后用素性检验算法检验这一奇数是否为素
11、数，如果不是则选取另一大奇数，重复这一过程，直到找到素数为止。素性检验算法通常都是概率性的，但如果算法被多次重复执行，每次执行时输入不同的参数，算法的检验结果都认为被检验的数是素数，那么就可以比较有把握地认为被检验的数是素数。2.1.6公钥密码体制的基本概念在公钥密码体制以前的整个密码学史中，所有的密码算法，包括原始手工计算的、由机械设备实现的以及由计算机实现的，都是基于代换和置换这两个基本工具。而公钥密码体制则为密码学的发展提供了新的理论和技术基础，一方面公钥密码算法的基本工具不再是代换和置换，而是数学函数；另一方面公钥密码算法是以非对称的形式使用两个密钥，两个密钥的使用对保密性、密钥分配、
12、认证等都有着深刻的意义。可以说公钥密码体制的出现在密码学史上是一个最大的而且是惟一真正的革命。公钥密码体制的概念是在解决单钥密码体制中最难解决的两个问题时提出的，这两个问题是密钥分配和数字签字。单钥密码体制在进行密钥分配时（看第5章），要求通信双方或者已经有一个共享的密钥，或者可籍助于一个密钥分配中心。对第一个要求，常常可用人工方式传送双方最初共享的密钥，这种方法成本很高，而且还完全依赖信使的可靠性。第二个要求则完全依赖于密钥分配中心的可靠性。第二个问题数字签字考虑的是如何为数字化的消息或文件提供一种类似于为书面文件手书签字的方法。1976年W.Diffie和M.Hellman对解决上述两个问
13、题有了突破，从而提出了公钥密码体制。2.2 总体方案要实现生成公钥和密钥的功能，必须先生成两个大素数。方法是先设定随机种子为系统当前时间，然后随即生成两个100以内的随机数，并判断其是否为素数，取出这两个素数。然后通过调用函数生成公钥对和密钥对，同时显示出结果到屏幕上。随后可以用公钥对明文进行加密，将加密后的秘闻显示出来。然后可以演示用密钥对密文进行解密，并将结果显示到屏幕上。2.3 功能模块本系统含有两个功能模块：（1）公钥和密钥生成模块：可以生成个100以内的素数p和q，以及n、e、d；（2）加密和解密模块：可以显示加密后的数据，点击解密可显示解密后数据。系统功能界面图如下：图2-1 系统
14、功能界面图3 系统设计3.1 算法描述RSA算法描述：(1) 密钥的产生 选两个保密的大素数p和q。 计算n=pq，(n)=(p-1)(q-1),其中(n)是n的欧拉函数值。 选一整数e，满足1e n的开方 ）返回n为宿舍；求最大公因子的算法：Euclid算法就是用这种方法，因gcd(a, b)=gcd(|a|, |b|)，因此可假定算法的输入是两个正整数，设为d，f，并设f d。Euclid（f, d）Xf; Yd； if Y=0 then return X=gcd(f,d)； R=X mod Y； X=Y； Y=R； goto 。求乘法逆元：推广的Euclid算法先求出gcd(a, b)，
15、当gcd(a, b)=1时，则返回b的逆元。Extended Euclid(f, d) （设 f d） (X1,X2,X3)(1,0,f);(Y1,Y2,Y3)(0,1,d); if Y3=0 then return X3=gcd(f, d)；no inverse; if Y3=1 then return Y3=gcd(f, d)；Y2=d-1 mod f; Q=X3Y3 ； (T1,T2,T3)(X1-QY1,X2-QY2,X3-QY3); (X1,X2,X3)(Y1,Y2,Y3); (Y1,Y2,Y3)(T1,T2,T3); goto 。处理明文：将明文的每个字符提取出来将其装换为数字。进
16、行加密处理，将处理后的数字字符用“+”号相连。其中加密的算法为：求am可如下进行，其中a，m是正整数： 将m表示为二进制形式bk bk-1b0，即m=bk2k+bk-12k-1+b12+b0因此：例如：19=124+023+022+121+120，所以a19=(a1)2a0)2a0)2a1)2a1从而可得以下快速指数算法：c=0; d=1；For i=k downto 0 d0 c=2c;d=(dd) mod n;if bi=1 then c=c+1;d=(da) mod nreturn d.其中d是中间结果，d的终值即为所求结果。c在这里的作用是表示指数的部分结果，其终值即为指数m，c对计算
17、结果无任何贡献，算法中完全可将之去掉。解密过程：将“+”连接的数字字符转换为数字并相加，用密钥做与加密相同的算法，即可得出明文。3.2 流程图开 始产生素数p和qp,q100且为素数N = (p - 1) * (q - 1)找出ee为素数与n互素求出d结 束是是否否图3-1 生成公钥和私钥流程图开 始明文不为空将明文转换为数字加密结 束取得明文是否 图3-2 明文加密流程图开 始密文不为空将密文转换为明文结 束取得密文是否图3-3 密文解密流程图4 代码编写在RSADlg.h中声明成员变量：intm_p;intm_q;intm_n;intm_code;intm_decode;CStringm_
18、dtxt;CStringm_etxt;CStringm_ptxt;1.产生公钥和密钥：void CRSADlg:OnButtonProduce() /产生公钥和密钥函数UpdateData(true);while(true)srand(time(0);m_p = rand() % 100;m_q = rand() % 100;if (isPrime(m_p) & isPrime(m_q)break;m_n = m_p * m_q;int fiN = (m_p - 1) * (m_q - 1);/int e;for (int i = 3; i fiN; i+)if (isPrime(i) & g
19、cd(fiN, i) = 1)m_code = i;break;Euler(m_code, fiN);UpdateData(false);代码分析：首先设置系统的当前时间为随机种子，循环找出p和q并且调用判断素数的函数isPrime(int)使p,q都为小于100的素数，然后fiN = (m_p - 1) * (m_q - 1)产生fiN，产生m_n = m_p * m_q，通过调用gcd(fiN, i)找出与fiN互素的数m_code，调用uler(m_code, fiN)找出m_decode，最后UpdateData(false)刷新文本框显示出结果。2.加密明文：void CRSADlg
20、:OnCode() /加密函数CString temp;UpdateData(true);CString encSt = ;CString e2st = ;if (m_ptxt.IsEmpty()return;for (int i = 0; i m_ptxt.GetLength(); i+)temp = encSt;encSt.Format(%s%d%s,temp,power(int)m_ptxt.GetAt(i), m_code, m_n),+);m_etxt = encSt;UpdateData(false);代码分析：首先判断明文文本框是否为空，若为空则返回。取出明文的每个字符，将其装换
21、为数字，通过加密函数power转换后，生成的数字字符用“+”号相连，即为密文。调用UpdateData(false)刷新文本框，显示加密后的结果。3.解密密文void CRSADlg:OnDecode() / 解密函数int ptr;int tok;CString temp = ;UpdateData(true);CString DecSt = ;/int t = m_etxt.GetLength();for (int i = 0; i 0; n=1) if (n%2=1) z=(z*t) % m; t=(t*t) % m; return(z);BOOL CRSADlg:isPrime(int
22、 x) /判断整数i是否为素数int i;for (i = 2; i (int)sqrt(x)return true;return false;int CRSADlg:gcd(int a, int b) /求出a与b的公因子if (a = 0)return b;elsereturn gcd(b % a, a);void CRSADlg:Euler(int e, int fin) /求出e相对模fin的乘法逆元int u1 = 1;int u2 = 0;int u3 = fin;int v1 = 0;int v2 = 1;int v3 = e;int v = 1;int t1, t2, t3;i
23、nt q;int uu, vv;int inverse, z;while (v3 != 0)q = (int)(u3 /v3);t1 = u1 - q * v1;t2 = u2 - q * v2;t3 = u3 - q * v3;u1 = v1;u2 = v2;u3 = v3;v1 = t1;v2 = t2;v3 = t3;z = 1;uu = u1;vv = u2;if (vv 0)inverse = vv + fin;elseinverse = vv;m_decode = inverse;5 运行与测试5.1 产生公钥和密钥点击密钥生成，运行效果如下图：图5-1 产生公钥和密钥效果图5.2
24、 加密与解密1.点击加密，运行效果如下图：图5-2 加密效果图2.点击解密，运行效果如下图：图5-3 解密效果图总 结通过这次课程设计，我对RSA加密体制有了更进一步的了解。遇到的主要问题是如何将明文按照比特分组并对其实现RSA加密，以及对大素数的处理。最终大素数的处理得以实现，但明文分组并没有找到合适的方法，这就要求我在课程设计后去学习怎样为明文分组机密。要想学好现代密码学不仅要学习好密码学相关知识，还要有很好的数学基础，还有很强的编程能力，这个课程设计是用Microsoft Visual C+ 6.0的开发环境写的，这对编程要求很高，不仅要会密码学中RSA的加密机制，算法还要熟知VC+的编
25、程方法，要对微软的MFC的基本编程方法要熟悉。课程设计时对学生个人综合能力的检验。任何知识和技术都不是孤立的。要学习好密码学要牵扯到线性代数，离散数学，概率统计等数学知识，为了验证加密解密算法的正确性，还要动手编制程序，这就要求学生要对至少一种编程技术有所熟知。对RSA加密体制还可以运用到手机等终端设备的加密，也可嵌入到其他小型化的设备中去，下一步我们讲进一步对这些方向进行研究。致 谢感谢老师给了这次机会给我们做这次课程设计，让我们能够把平时所学的东西用上，不至于让我们觉得平时学的东西没什么用，在这短短的时间里完成了本次课程设计，要感谢朋友们的帮忙，在我困惑的时候要不是你们，我可能早就放弃了，
26、因为你们的帮忙，我才能顺利的完成这次系统。其实最辛苦的还是老师，请允许我向你们说声谢谢，感谢你们对我们的教诲。在这次课程设计的过程中，我觉得我真的是获得了很多的东西，不仅仅是动手能力及编程能力得到了很大的提高，也不仅仅是在修改程序错误方面，主要是在程序编写过程中获得了大量的宝贵的经验。此外，在这次实践过程中发现数据库是一门十分实用的课程，也体会到学好数据库对我们以后的学习，工作是十分重要的。因而在此，我要感谢那些在实践过程中给过我帮助和鼓励的人。最后对所有在课程设计中帮助过我的老师和同学说一声谢谢。参考文献1 杨波.现代密码学.第2版.北京：清华大学出版社，20082 谷利泽，郑世慧，杨义先.现代密码学教程.北京：北京邮电大学出版社，20093丁存生，肖国镇.流密码学及其应用. 北京：国防工业出版社，19944冯登国，吴文玲.分组密码的设计与分析. 北京：清华大学出版社，20005张焕国.计算机安全保密技术. 北京：机械工业出版社，19956朱文余，孙琦.计算机密码应用基础北京：科学出版社，2000
