RSA算法课程设计报告

摘要： 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,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 是两个素数 p 和 q 的乘积，则 (n)=(p)(q)=(p-1)(q-1)。 欧拉定理：若 a 和 n 互素，则 a(n)1 mod n。 2.1.4 欧几里德算法 现代密码学课程设计报告 3 欧几里得（Euclid）算法是数论中的一个基本技术，是求两个正整数的最大公因子 的简化过程。而推广的 Euclid 算法不仅可求两个正整数的最大公因子，而且当两个正 整数互素时，还可求出其中一个数关于另一个数的乘法逆元。 1. 求最大公因子： Euclid 算法是基于下面一个基本结论： 对任意非负整数 a 和正整数 b，有 gcd(a, b)=gcd(b, a mod b)。 2. 求乘法逆元： 如果 gcd(a, b)=1 ，则 b 在 mod a 下有乘法逆元（不妨设 ba） ，即存在一 x (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，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 算 法的优越性了。因此如何有效地寻找大素数是第一个需要解决的问题。寻找大素数时 一般是先随机选取一个大的奇数（例如用伪随机数产生器） ，然后用素性检验算法检 验这一奇数是否为素数，如果不是则选取另一大奇数，重复这一过程，直到找到素数 为止。素性检验算法通常都是概率性的，但如果算法被多次重复执行，每次执行时输 入不同的参数，算法的检验结果都认为被检验的数是素数，那么就可以比较有把握地 认为被检验的数是素数。 现代密码学课程设计报告 4 2.1.6 公钥密码体制的基本概念 在公钥密码体制以前的整个密码学史中，所有的密码算法，包括原始手工计算的、 由机械设备实现的以及由计算机实现的，都是基于代换和置换这两个基本工具。而公 钥密码体制则为密码学的发展提供了新的理论和技术基础，一方面公钥密码算法的基 本工具不再是代换和置换，而是数学函数；另一方面公钥密码算法是以非对称的形式 使用两个密钥，两个密钥的使用对保密性、密钥分配、认证等都有着深刻的意义。可 以说公钥密码体制的出现在密码学史上是一个最大的而且是惟一真正的革命。公钥密 码体制的概念是在解决单钥密码体制中最难解决的两个问题时提出的，这两个问题是 密钥分配和数字签字。单钥密码体制在进行密钥分配时（看第 5 章） ，要求通信双方 或者已经有一个共享的密钥，或者可籍助于一个密钥分配中心。对第一个要求，常常 可用人工方式传送双方最初共享的密钥，这种方法成本很高，而且还完全依赖信使的 可靠性。第二个要求则完全依赖于密钥分配中心的可靠性。第二个问题数字签字考虑 的是如何为数字化的消息或文件提供一种类似于为书面文件手书签字的方法。1976 年 W.Diffie 和 M.Hellman 对解决上述两个问题有了突破，从而提出了公钥密码体制。 2.2 总体方案总体方案 要实现生成公钥和密钥的功能，必须先生成两个大素数。方法是先设定随机种子 为系统当前时间，然后随即生成两个 100 以内的随机数，并判断其是否为素数，取出 这两个素数。然后通过调用函数生成公钥对和密钥对，同时显示出结果到屏幕上。随 后可以用公钥对明文进行加密，将加密后的秘闻显示出来。然后可以演示用密钥对密 文进行解密，并将结果显示到屏幕上。 2.3 功能模块功能模块 本系统含有两个功能模块： （1）公钥和密钥生成模块：可以生成个 100 以内的素数 p 和 q，以及 n、e、d； （2）加密和解密模块：可以显示加密后的数据，点击解密可显示解密后数据。 系统功能界面图如下： 现代密码学课程设计报告 5 图 2-1 系统功能界面图 3 系统设计系统设计 3.1 算法描述算法描述 RSA 算法描述： (1) 密钥的产生 选两个保密的大素数 p 和 q。 计算 n=pq，(n)=(p-1)(q-1),其中 (n)是 n 的欧拉函数值。 选一整数 e，满足 1d。 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,q100 且为素数 N = (p - 1) * (q - 1) 找出 e e 为素数与 n 互素 求出 d 结 束 是 是 否 否 图 3-1 生成公钥和私钥流程图 现代密码学课程设计报告 9 开 始 明文不为空 将明文转换为数字加密 结 束 取得明文 是 否 图 3-2 明文加密流程图 开 始 密文不为空 将密文转换为明文 结 束 取得密文 是 否 图 3-3 密文解密流程图 4 代码编写代码编写 现代密码学课程设计报告 10 在 RSADlg.h 中声明成员变量： intm_p; intm_q; intm_n; intm_code; intm_decode; CStringm_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) 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) break; 现代密码学课程设计报告 11 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:OnCode() /加密函数 CString temp; UpdateData(true); CString encSt = ; CString e2st = ; if (m_ptxt.IsEmpty() return; for (int i = 0; i =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 的加密机制，算法