RSA算法课程设计报告.doc

摘要： rsa 算法是基于数论的公钥密码体制，是公钥密码体制中最优秀的加密算法，同 时也是第一个能同时用于加密和数字签名的算法，也易于理解和操作。 rsa 是被研究 得最广泛的公钥算法，从提出到现在已近二十年，经历了各种攻击的考验，逐渐为人 们接受，普遍认为是目前最优秀的公钥方案之一。rsa 的安全性依赖于大数的因子分 解，但并没有从理论上证明破译 rsa 的难度与大数分解难度等价。本文主要研究的内 容包括：第一,对 rsa 算法进行了全面系统的介绍，包括 rsa 算法的应用现状和原理 大素数的产生、密钥对的产生、对明文的加密运算和密文的解密运算，为具体实现 打下了理论基础；第二,介绍了 rsa 机密体制的一些基本概念及原理；第三，详述了 rsa 加密的设计与实现，主要实现的模块包括 rsa 密钥的产生（一对公钥和私钥） ， rsa 加密算法和解密算法的实现；第五,对该系统进行了整体的测试和分析改进； 关键词：rsa 算法；公钥密码体制；加密；解密；vc+ 目目 录录 1 课题综述 1 1.1 课题来源.1 1.2 课题意义.1 1.3 预期目标.1 2 系统分析 1 2.1 基础知识.2 2.2 总体方案.4 2.3 功能模块.4 3 系统设计 5 3.1 算法描述.5 3.2 流程图.7 4 代码编写 9 5 运行与测试 .14 5.1 产生公钥和密钥14 5.2 加密与解密14 总 结 .16 致 谢 .17 参考文献 18 现代密码学课程设计报告 1 1 课题综述课题综述 1.1 课题来源课题来源 随着电子信息技术的迅速发展，人类已步入信息社会。但是由于整个社会形成了 一个巨大的计算机网络，任何一个计算机网络出现的安全问题，都会影响整个国家的 网络安全，所以信息安全、计算机网络安全问题已引起了人类的高度重视。无论是在 局域网还是在广域网中，都存在着自然和人为等诸多因素的脆弱性和潜在威胁。故此， 网络的安全措施应是能全方位地针对各种不同的威胁和脆弱性，这样才能确保网络信 息的保密性、完整性和可用性。现代密码学已成为信息安全技术的核心，密码学是以 研究通信安全保密的学科，即研究对传输信息采用何种秘密的变换以防止第三者对信 息的窃取。公钥密码体制的特点是：接收方 b 产生一对密钥（pk 和） ；公开， 保密；从推出是很困难的；、双方通信时，通过任何途径取得 的公钥，用的公钥加密信息，加密后的信息可通过任何不安全信道发送。收到密 文信息后，用自己私钥解密恢复出明文。公钥密码体制已成为确保信息的安全性的关 键技术。rsa 公钥密码体制到目前为止还是一种被认可为安全的体制。 1.2 课题意义课题意义 rsa 公钥加密算法是第一个既能用于数据加密也能用于数字签名的算法。它易于 理解和操作，也十分流行。算法的名字以发明者的姓氏首字母命名：ron rivest, adi shamir 和 leonard adleman。虽然自 1978 年提出以来，rsa 的安全性一直未能得到 理论上的证明，但它经历了各种攻击，至今未被完全攻破。随着越来越多的商业应用 和标准化工作，rsa 已经成为最具代表性的公钥加密技术。 visa、mastercard、ibm、microsoft 等公司协力制定的安全电子交易标准（secure electronic transactions，set）就采用了标准 rsa 算法，这使得 rsa 在我们的生活中 几乎无处不在。网上交易加密连接、网上银行身份验证、各种信用卡使用的数字证书、 智能移动电话和存储卡的验证功能芯片等，大多数使用 rsa 技术。应用了 rsa 加密 体制保证了秘密信息的安全。 1.3 预期目标预期目标 在充分理解 rsa 加密体制概念和原理的基础上，用 microsoft visual c+ 6.0 实现 rsa 加密与解密，演示公钥与密钥的生成及加密与解密的过程。 现代密码学课程设计报告 2 2 系统分析系统分析 2.1 基础知识基础知识 2.1.1 素数 称整数 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)。 由于确定大数的素因子不很容易，所以这种方法不能直接用于求两个大数的最大公因 子，如何求两个大数的最大公因子在下面介绍。 如果 gcd(a,b)=1，则称 a 和 b 互素。 2.1.2 模运算 设 n 是一正整数，a 是整数，如果用 n 除 a，得商为 q，余数为 r，则 a=qn+r,0r 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)，当 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 。 处理明文：将明文的每个字符提取出来将其装换为数字。进行加密处理，将处理 后的数字字符用“+”号相连。其中加密的算法为：求 am 可如下进行，其中 a，m 是正 整数： 将 m 表示为二进制形式 bk bk-1b0，即 现代密码学课程设计报告 7 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 n return d. 其中 d 是中间结果，d 的终值即为所求结果。c 在这里的作用是表示指数的部分结果， 其终值即为指数 m，c 对计算结果无任何贡献，算法中完全可将之去掉。 解密过程：将“+”连接的数字字符转换为数字并相加，用密钥做与加密相同的算法， 即可得出明文。 3.2 流程图流程图 现代密码学课程设计报告 8 开 始 产生素数 p 和 q p,q0; n=1) if (n%2=1) z=(z*t) % m; t=(t*t) % m; 现代密码学课程设计报告 13 return(z); bool crsadlg:isprime(int 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; else return 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; 现代密码学课程设计报告 14 int v2 = 1; int v3 = e; int v = 1; int t1, t2, t3; int 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; else inverse = vv; m_decode = inverse; 5 运行与测试运行与测试 现代密码学课程设计报告 15 5.1 产生公钥和密钥产生公钥和密钥 点击密钥生成，运行效果如下图： 图 5-1 产生公钥和密钥效果图 5.2 加密与解密加密与解密 1.点击加密，运行效果如下图： 图 5-2 加密效果图 2.点击解密，运行效果如下图： 现代密码学课程设计报告 16 图 5-3 解密效果图 现代密码学课程设计报告 17 总总 结结 通过这次课程设计，我对 rsa 加密体制有了更进一步的了解。遇到的主要问题 是如何将明文按照比特分组并对其实现 rsa 加密，以及对大素数的处理。最终大素 数的处理得以实现，但明文分组并没有找到合适的方法，这就要求我在课程设计后去 学习怎样为明文分组机密。要想学好现代密码学不仅要学习好密码学相关知识，还要 有很好的数学基础，还有很强的编程能力，这个课程设计是用 microsoft visual c+ 6.0 的开发环境写的，这对编程要求很高，不仅要会密码学中 rsa 的加密机制，算法 还要熟知 vc+的编程方法，要对微软的 mfc 的基本编程方法要熟悉。课程设计时对 学生个人综合能力的检验。任何知识和技术都不是孤立的。要学习好密码学要牵扯到 线性代数，离散数学，概率统计等数学知识，为了验证加密解密算法的正确性，还要 动手编制程序，这就要求学生要对至少一种编程技术有所熟知。对 rsa 加密体制还 可以运用到手机等终端设备的加密，也可嵌入到其他小型化的设备中去，下一步我们 讲进一步对这些方向进行研究。 现代密码学课程设计报告 18 致致 谢谢 感谢老师给了这次机会给我们做这次课程设计，让我们能够把平时所学的东西用 上，不至于让我们觉得平时学的东西没什么用，在这短短的时间里完成了本次课程设 计，要感谢朋友们的帮忙，在我困惑的时候要不是你们，我可能早就放弃了，因为你 们的帮忙，我才能顺利的完成这次系统。其实最辛苦的还是老师，请允许我向你们说 声谢谢，感谢你们对我们的教诲。 在这次课程设计的过程中，我觉得我真的是获得了很多的东西，不仅仅是动手能 力及编程能力得到了很大的提高，也不仅仅是在修改程序错误方面，主要是在程序编 写过程中获得了大量的宝贵的经验。此外，在这次实践过程中发现数据库是一门十分 实用的课程，也体会到学好数据库对我们以后的学习，工作是十分重要的。因而在此， 我要感谢那些在实践过程中给过我帮助和鼓励的人。 最后对所有在课程设