关于RSA算法的研究与改进

中文题目：关于 RSA 算法的研究与改进外文题目：Research and improvement of RSA algorithms毕业设计（论文）共 64 页（其中：外文文献及译文 10 页）图纸共 0 张完成日期 2012 年 5 月 答辩日期 2012 年 6 月 摘要RSA 公钥加密算法已被 ISO 推荐为公钥数据加密标准。本论文分析 RSA 算法的应用现状，论证文件加密应用 RSA 算法的可行性和意义。设计一套完整实用的 RSA 文件加密解决方案，具体编码实现。对 RSA 算法进行研究，从常规 RSA 算法出发，用 C+实现RSA 加密算法类库，并在 32 位 windows 平台封装成组件。实现可以对任意文件进行RSA 加密操作的窗体应用程序，经过加密的文件以及密钥文件都是文本文件。论文给出整个应用程序的结构描述文档、关键模块流程图、较详细的接口文档、所有源代码。对应用程序进行测试，对测试结果进行分析研究，进而对应用程序进行改进，对关键算法进行尽可能的优化，最终得到一个在 windows 运行的可以用指定密钥对任意文件进行RSA 加密并可解密的完整应用程序，和一些相关的可移植组件。关键词： RSA 加密算法；公钥加密；RSA 实现ABSTRACTRSA public key encryption algorithms have been recommended for ISO public key data encryption standard. This paper analyzes the present situation of the application of RSA algorithms, prove file encryption application RSA algorithm is feasible and significance. Design a complete set of practical RSA file encryption solutions, specific code realization. RSA algorithms to are studied, and the RSA algorithms of conventional, realize the RSA encryption algorithm in c + + class library, and in the 32-bit Windows platform encapsulation into components. Can realize for any documents RSA encryption operation of the application form, encrypted files and key documents are a text file. Paper gives key kinds of Fig, the description of the structure of the application documents, key module flowcharts, a detailed interface file, all the source code. Use application test, the result of the test is studied and analyzed, and then the application was improved, and the key to the optimization of the algorithm is as far as possible, and finally get a Windows running of the specified key can be used for any documents and the declassified RSA encryption can be complete application, and some related portable components.Key words：RSA encryption algorithm; Public key encryption; RSA realize目录引言 .11 RSA 加密算法概述 .21.1 RSA 算法简介 .21.1.1 什么是 RSA 算法 .21.1.2 RSA 算法的缺点和攻 击办法 .31.2 国内外对于 RSA 算法的研究现状 .61.3 应用 RSA 算法对文件加密的可行性分析 .81.3.1 文件加密使用 RSA 的可行性 .81.3.2 RSA 算法对于文件加密的意 义 .92 RSA 文件加密软件的设计 .112.1 RSA 算法可行性的证明 .112.2 RSA 算法软件实现的需求分析和总体设计 .122.3 工程方案选择 .142.4 C+语言简介 .152.5 VC6.0 简介 .183 具体设计与开发 .203.1 实现 RSA 加密算法的 C+核心类库 .203.1.1 大数存储和四则运算 .203.1.2 大数幂模与乘模运算 Montgomery 幂模算法 .213.1.3 寻找素数 Eratosthenes 筛选与 Fermat 素数测试 .253.1.4 二元一次不定方程 .273.2 核心类库综述 .283.3 封装 C+核心类库的 DLL 组件 .294 RSA 算法的具体实现 .304.1 各运算的实现 .304.1.1 加法的实现 .304.1.2 减法的实现 .314.1.3 乘法的实现 .324.1.4 除法的实现 .344.1.5 取模的实现 .364.1.6 逆取模的实现 .374.1.7 幂模运算的实现 .374.2 RSA 算法验证程序各部分过程 .395 RSA 加密算法的分析 .435.1 RSA 加密算法的调试分析 .435.2 RSA 加密算法的实际应用分析 .455.3 设计的不足和继续开发的思路 .46结论 .48附录 A 中文译文 .51附录 B 英文原文 .55附录 C 使用 C 语言实现 RSA 算法 .59引言 RSA 公钥加密算法是 1977 年由 Ron Rivest、Adi Shamirh 和 LenAdleman 在（美国麻省理工学院）开发的。RSA 取名来自开发他们三者的名字。RSA 是目前最有影响力的公钥加密算法，它能够抵抗到目前为止已知的所有密码攻击，已被 ISO 推荐为公钥数据加密标准。RSA 在软件方面的应用，主要集中在 Internet 上。加密连接、数字签名和数字证书的核心算法广泛使用 RSA。日常应用中，有比较著名的工具包 Open SSL(SSL，Security Socket Layer,是一个安全传输协议，在 Internet 上进行数据保护和身份确认。Open SSL 是一个开放源代码的实现了 SSL 及相关加密技术的软件包，由加拿大的 Eric Yang 等发起编写的。Open SSL 应用 RSA 实现签名和密钥交换，已经在各种操作系统得到非常广泛的应用。另外，家喻户晓的 IE 浏览器，自然也实现了 SSL 协议，集成了使用 RSA 技术的加密功能，结合 MD5 和 SHA1，主要用于数字证书和数字签名，对于习惯于使用网上购物和网上银行的用户来说，几乎天天都在使用 RSA 技术。RSA 公钥加密算法是第一个既能用于数据加密也能用于数字签名的算法。它易于理解和操作，也十分流行。虽然自 1978 年提出以来，RSA 的安全性一直未能得到理论上的证明，但它经历了各种攻击，至今（2006 年）未被完全攻破。随着越来越多的商业应用和标准化工作，RSA 已经成为最具代表性的公钥加密技术。VISA、MasterCard、IBM、Microsoft 等公司协力制定的安全电子交易标准（Secure Electronic Transactions，SET）就采用了标准 RSA 算法，这使得 RSA 在我们的生活中几乎无处不在。网上交易加密连接、网上银行身份验证、各种信用卡使用的数字证书、智能移动电话和存储卡的验证功能芯片等，大多数使用 RSA 技术。当今公钥加密更广泛应用于互联网身份认证，本课题将公钥加密算法 RSA 应用于小型文件加密。将任意文件加密成文本的解决方案，使其使用更加灵活。整个工程的分层设计，给引用移植和后续开发带来便利。本设计致力于 RSA 算法的理论研究、RSA 算法的改进以及基于 RSA 算法的加密、解密软件的实现。1 RSA 加密算法概述 1.1 RSA 算法简介1.1.1 什么是 RSA 算法RSA 公钥加密算法是 1977 年由 Ron Rivest、Adi Shamirh 和 LenAdleman 在（美国麻省理工学院）开发的。RSA 取名来自开发他们三者的名字。RSA 是目前最有影响力的公钥加密算法，它能够抵抗到目前为止已知的所有密码攻击，已被 ISO 推荐为公钥数据加密标准。RSA 算法基于一个十分简单的数论事实：将两个大素数相乘十分容易，但那时想要对其乘积进行因式分解却极其困难，因此可以将乘积公开作为加密密钥。RSA 公开密钥加密算法自 20 世纪 70 年代提出以来，已经得到了广泛认可和应用。发展至今，电子安全领域的各方面已经形成了较为完备的国际规范。RSA 作为最重要的公开密钥算法，在各领域的应用数不胜数。RSA 在硬件方面，以技术成熟的 IC 应用于各种消费类电子产品。RSA 在软件方面的应用，主要集中在 Internet 上。加密连接、数字签名和数字证书的核心算法广泛使用 RSA。日常应用中，有比较著名的工具包 Open SSL(SSL，Security Socket Layer,是一个安全传输协议，在 Internet 上进行数据保护和身份确认。Open SSL 是一个开放源代码的实现了 SSL 及相关加密技术的软件包，由加拿大的 Eric Yang 等发起编写的。Open SSL 应用 RSA 实现签名和密钥交换，已经在各种操作系统得到非常广泛的应用。另外，家喻户晓的 IE 浏览器，自然也实现了 SSL 协议，集成了使用 RSA 技术的加密功能，结合 MD5 和 SHA1，主要用于数字证书和数字签名，对于习惯于使用网上购物和网上银行的用户来说，几乎天天都在使用 RSA 技术。RSA 更出现在要求高度安全稳定的企业级商务应用中。在当今的企业级商务应用中，不得不提及使用最广泛的平台 j2ee。事实上，在 j2se 的标准库中，就为安全和加密服务提供了两组 API：JCA 和 JCE。 JCA (Java Cryptography Architecture)提供基本的加密框架，如证书、数字签名、报文摘要和密钥对产生器； JCA 由几个实现了基本的加密技术功能的类和接口组成，其中最主要的是 java.security 包，此软件包包含的是一组核心的类和接口，Java 中数字签名的方法就集中在此软件包中。JCE(Java Cryptography Extension) 在JCA 的基础上作了扩展，JCE 也是由几个软件包组成，其中最主要的是 javax.crypto 包，此软件包提供了 JCE 加密技术操作 API。javax.crypto 中的 Cipher 类用于具体的加密和解密。在上述软件包的实现中，集成了应用 RSA 算法的各种数据加密规范用户程序可以直接使用 java 标准库中提供的 API 进行数字签名和证书的各种操作。 RSA 的 安 全 性RSA 的安全性依赖于大数分解，但是否等同于大数分解一直未能得到理论上的证明，因为没有证明破解 RSA 就一定需要作大数分解。假设存在一种无须分解大数的算法，那它肯定可以修改成为大数分解算法。目前， RSA 的一些变种算法已被证明等价于大数分解。不管怎样，分解 n 是最显然的攻击方法。现在，人们已能分解多个十进制位的大素数。因此，模数 n 必须选大一些，因具体适用情况而定。 RSA 的 速 度由于进行的都是大数计算，使得 RSA 最快的情况也比 DES 慢上好几倍，无论是软件还是硬件实现。速度一直是 RSA 的缺陷。一般来说只用于少量数据加密。RSA 的速度比对应同样安全级别的对称密码算法要慢 1000 倍左右。RSA 算法可以简单叙述如下：取素数 p，q，令 n=pq.取与(p-1)(q-1)互素的整数 e，由方程 de=1 (mod (p-1)(q-1)解出 d，二元组(e,n)作为公开密钥，二元组(d,n)作为私有密钥b=ae mod n， c=bd mod n.1.1.2 RSA 算法的缺点和攻击办法虽然 RSA 算法算法是这样的成功和出色，但是 RSA 算法毕竟是人想出来的算法，所以它也不是十分的完美，RSA 算法也有很多的缺点。RSA 的安全性依赖于大数的因子分解，但并没有从理论上证明破译 RSA 的难度与大数分解难度等价。即 RSA 的重大缺陷是无法从理论上把握它的保密性能如何，而且密码学界多数人士倾向于因子分解不是 NPC问题。 RSA 的缺点主要有：产生密钥很麻烦，受到素数产生技术的限制，因而难以做到一次一密。分组长度太大，为保证安全性，n 至少也要 600bits 以上，使运算代价很高，尤其是速度较慢，较对称密码算法慢几个数量级；且随着大数分解技术的发展，这个长度还在增加，不利于数据格式的标准化。目前，SET(Secure Electronic Transaction)协议中要求 CA 采用 2048bits 长的密钥，其他实体使用 1024 比特的密钥。RSA 密钥长度随着保密级别提高，增加很快。下表列出了对同一安全级别所对应的密钥长度。具体缺点如下：1)产生密钥很麻烦，受到素数产生技术的限制，因而难以做到一次一密。 2)安全性 , RSA 的安全性依赖于大数的因子分解，但并没有从理论上证明破译 RSA 的难度与大数分解难度等价，而且密码学界多数人士倾向于因子分解不是 NPC 问题。目前，人们已能分解 140 多个十进制位的大素数，这就要求使用更长的密钥，速度更慢；另外，目前人们正在积极寻找攻击 RSA 的方法，如选择密文攻击，一般攻击者是将某一信息作一下伪装(Blind)，让拥有私钥的实体签署。然后，经过计算就可得到它所想要的信息。实际上，攻击利用的都是同一个弱点，即存在这样一个事实：乘幂保留了输入的乘法结构：( XM )d = Xd *Md mod n （1-1）前面已经提到，这个固有的问题来自于公钥密码系统的最有用的特征-每个人都能使用公钥。但从算法上无法解决这一问题，主要措施有两条：一条是采用好的公钥协议，保证工作过程中实体不对其他实体任意产生的信息解密，不对自己一无所知的信息签名；另一条是决不对陌生人送来的随机文档签名，签名时首先使用 One-Way Hash Function 对文档作 HASH 处理，或同时使用不同的签名算法。除了利用公共模数，人们还尝试一些利用解密指数或 （n）等攻击。 3)速度太慢，由于 RSA 的分组长度太大，为保证安全性，n 至少也要 600 bitx 以上，使运算代价很高，尤其是速度较慢，较对称密码算法慢几个数量级；且随着大数分解技术的发展，这个长度还在增加，不利于数据格式的标准化。目前，SET(Secure Electronic Transaction)协议中要求 CA 采用 2048 比特长的密钥，其他实体使用 1024 比特的密钥。为了速度问题,目前人们广泛使用单,公钥密码结合使用的方法,优缺点互补:单钥密码加密速度快,人们用它来加密较长的文件,然后用 RSA 来给文件密钥加密,极好的解决了单钥密码的密钥分发问题。对于 RSA 算法的攻击主要由两种：R SA 的 选 择 密 文 攻 击 和 RSA 的 公 共 模 数 攻 击 。 RSA 的选择密文攻击RSA 在选择密文攻击面前很脆弱。一般攻击者是将某一信息作一下伪装( Blind)，让拥有私钥的实体签署。然后，经过计算就可得到它所想要的信息。实际上，攻击利用的都是同一个弱点，即存在这样一个事实：乘幂保留了输入的乘法结构： ( XM )d = Xd *Md mod n （1-2）前面已经提到，这个固有的问题来自于公钥密码系统的最有用的特征-每个人都能使用公钥。但从算法上无法解决这一问题，主要措施有两条：一条是采用好的公钥协议，保证工作过程中实体不对其他实体任意产生的信息解密，不对自己一无所知的信息签名；另一条是决不对陌生人送来的随机文档签名，签名时首先使用 One-Way HashFunction 对文档作 HASH 处理，或同时使用不同的签名算法。 RSA 的公共模数攻击若系统中共有一个模数，只是不同的人拥有不同的 e 和 d，系统将是危险的。最普遍的情况是同一信息用不同的公钥加密，这些公钥共模而且互质，那么该信息无需私钥就可得到恢复。设 P 为信息明文，两个加密密钥为 e1 和 e2，公共模数是 n，则： C1 = Pe1 mod n （1-3）C2 = Pe2 mod n （1-4）密码分析者知道 n、e1 、 e2、C1 和 C2，就能得到 P。 因为 e1 和 e2 互质，故用 Euclidean 算法能找到 r 和 s，满足： r * e1 + s * e2 = 1 （1-5）假设 r 为负数，需再用 Euclidean 算法计算 C1(-1)，则 ( C1(-1) )(-r) * C2s = P mod n （1-6）另外，还有其它几种利用公共模数攻击的方法。总之，如果知道给定模数的一对 e和 d，一是有利于攻击者分解模数，一是有利于攻击者计算出其它成对的 e和 d，而无需分解模数。解决办法只有一个，那就是不要共享模数 n。 RSA 的小指数攻击。 有一种提高 RSA 速度的建议是使公钥 e 取较小的值，这样会使加密变得易于实现，速度有所提高。但这样作是不安全的，对付办法就是 e 和 d 都取较大的值。针对 RSA 最流行的攻击一般是基于大数因数分解。1999 年，RSA-155(512 bits)被成功分解，花了五个月时间（约 8000 MIPS 年）和 224 CPU hours 在一台有 3.2G 中央内存的 Cray C916 计算机上完成 。 2002 年，RSA-158 也被成功因数分解。 2009 年 12 月 12 日，编号为 RSA-768 （768 bits, 232 digits）数也被成功分解。 北京时间 2 月 15 日上午消息，据纽约时报周二报道，欧美数学家和密码学家偶然发现，目前被全世界广泛应用的公钥加密算法 RSA 存在漏洞。 他们发现，在 700 万个实验样本中有 2.7 万个公钥并不是按理论随机产生的。也就是说，或许有人可以找出产生公钥的秘密质数。 该研究项目是由美国独立密码学家 James P.Hughes 和荷兰数学家 Arjen K. Lenstra 牵头的。他们的报告称：“ 我们发现绝大多数公钥都是按理论产生的，但是每一千个公钥中会有两个存在安全隐患。 ” 报告称，为防止有人利用该漏洞，有问题的公钥已从公众访问的数据库中移除。为确保系统的安全性，网站需要在终端做出改变。1.2 国内外对于 RSA 算法的研究现状密码学以研究秘密通信为目的,研究对传输信息采取何种的变换,以防止第三者对信息的截取。在密码学中,需要变换的原消息称为明文消息。明文经过变换成为另一种隐蔽的形式,称为密文消息。完成变换的过程称作加密,其逆过程(即由密文恢复出明文的过程)称作解密。对明文进行加密时所采取的一组规则称作加密算法。加密和解密操作通常在密钥的控制下进行,并有加密密钥和解密密钥之分。因为数据以密文的形式存储在计算机文件中,或在数据通信网络传输,因此数据被未授权者非法窃取,或因系统故障和操作人员误操作而造成数据泄漏,未授权者也不能理解它的真正含义,从而达到数据保密的目的。同样,未授权者也不能伪造合理的密文,因而不能篡改数据,从而达到数据真实性的目的。 国外研究现状：Whitfield Diffie 和 Martin Hellman 在密码学的新方向一文中包含了设计一个具有公钥私钥对系统的协议的详细信息，随后这一算法以两位作者的姓名命名，即 Diffie-Hellman 算法，它被称为公钥系统的基础。公钥密码的新概念开创了现代密码学的新领域。这一领域虽然只有短短的二十几年时间,但投入研究人员之多,他们来自学科之广,发表的论文之众是其它任何一门学科所不能比的，所以很快便获得了一整套很系统的成果。1.传统密码在密钥分配与管理上是极困难的。在任何密文未发送之前,A 方和 B 方必须利用安全信道时行密钥 K 的预先通信,在实际应用中 ,这可能是非常困难的。因此,Diffie和 Hellman 提出了公钥密码体制的思想。2.在商业上有时不可能做得到通信双方事先预约使用相同密钥。公钥密码体制将加密密钥与解密密钥分开,并将加密密钥公开,解密密钥保密。这样,每个用户拥有两个密钥:公开钥和秘密钥,并且所有公开钥均被记录在类似电话簿的密码本中。这种密码体制的安全性是从已知的公开钥、加密算法与在信道上截获的密文不能求出明文或秘密钥。公钥体制的基础是陷门(单向函数) , 即某种实际处理过程的不可逆性。目前的公钥思想基于两种:一是依赖于大数的因数分解的困难性;二是依赖于求模离散对数的困难性。公开密钥密码体制开辟了密码学研究的新方向,此后,人们基于背包问题、因子分解问题和离散对数问题等数学难题提出了大量的公钥密码体制算法。在受 Diffie-Hellman 算法思想启发之后，美国麻省理工学院的三个研究人员：Ronald Rivest,AdiSharmir 和 Leonard Adleman 联合提出一种基于数论中欧拉定理的公钥密码系统,简称 RSA 公钥系统，并于 1983 年在美国获得专利。 国内研究现状RSA 公钥密码算法是迄今为止在理论上最为成熟、完善的公钥密码体制。从提出到现在已经历了各种攻击的考验，逐渐为人们接受，普遍认为是目前最优秀的公钥方案之一。它是第一个既能用于数据加密也能用于数字签名和密钥分配与管理的算法。它易于理解和操作，也很流行。因为它既可用于加密,又可用于签名,并为用户的公开密钥签发公钥证书、发放证书、管理证书等,提高了服务质量，所以, RSA 公开密钥密码在当今的信息交换过程中已得到广泛的应用和实践，RSA 公钥密码体制在世界许多地方已经成为事实上的标准。该算法的加密密钥和加密算法分开,使得密钥分配更为方便。而且它特别符合计算机网络环境。对于网上的大量用户,可以将加密密钥用电话簿的方式印出。如果某用户想与另一用户进行保密通信,只需从公钥簿上查出对方的加密密钥,用它对所传送的信息加密发出即可。对方收到信息后,用仅为自己所知的解密密钥将信息解密,了解明文的内容。由此可看出,RSA 算法解决了大量网络用户密钥管理的难题,这是公钥密码系统相对于对称密码系统最突出的优点。RSA 是一个基于数论的非对称密码体制,是一种分组密码体制，是一种基于因子分解的指数函数作为单向陷门函数的公钥体制算法。它基础是数论的欧拉定理,素数检测,它的安全性是基于大数分解,后者在数学上是一个困难问题。RSA 算法是第一个完善并且简单实用的公钥密码体制算法。近年来,国内外学者对RSA 密码算法提出了多种攻击方法,例如 Pollard p21 方法、二次筛法、椭圆曲线算法和数域筛法等。RSA 的安全性基于复杂性理论中的计算安全性, 依赖于大整数分解这一 NP 难题。可靠性与所用密钥的长度有很大关系, 假如有人找到一种很快的分解因子的算法, 即从一个公钥中通过因数分解得到私钥,那么用 RSA 加密的信息的可靠性肯定会极度下降。但由于其工作量巨大,按目前计算机的处理能力是不可能实现的。实践证明,在当前的技术和方法下,密钥不小于 1 024 bit 的 RSA 算法仍然是安全的。1.3 应用 RSA 算法对文件加密的可行性分析1.3.1 文件加密使用 RSA 的可行性通过 1.1 节的论述，不难看出 RSA 当今的应用多在于数字签名和证书等方面。之所以只应用于这些短小数据的加密解密，是因为 RSA 算法加密极慢，速度是 DES 对称密钥加密速度的千分之一左右。正是因为这样，把 RSA 应用于普通文件加密的想法一直被忽略。通常文件被想象成大数据块，但是实际上在日常应用中，有些极其重要的文本资料是并不太大的，比如因担心遗忘而用普通文本记录的银行帐号和密码、不应被陌生人知道的重要电话号码、几千字节大的重要小图片等。虽然 RSA 加密运算的速度十分慢，但是在 PC 性能越来越好的今天，对于几千字节的数据进行一次几百位密钥的 RSA 加密，所消耗的时间应该是可以接受的。下面结合大数运算程序的调试，从理论上简单的分析消耗时间。在一台普通配置的 PC 机上对一个整数进行幂模运算，因为公开密钥的 e 通常取的较小，所以指数取一个小整数，比如C353，模一个 70 字节长的整数(140 位十六进制，大数单元以线性组方式实现，对应到RSA 算法中，这相当于约 560bit 的 n)，调试一个函数测试，按初等数论中的知识对程序进行算法优化，最终在一台配置为 AMD Athron2800+，外频 333MHZ，物理内存 512MB的 PC 上测试需要约 45 毫秒时间。如果按这种速度，逐字节对 1KB 的数据进行同样的运算，所消耗的时间理论上为 45 毫秒的 1024 倍即约 45 秒。这个时间并不是非常长。其实从一个简单的角度来说，既然 RSA 用于数字签名可行，那就完全可以用于同样大小的普通文件。对于较大的文件，如果分成与数字签名同样大小的段(这里假设数字签名较短，不分段一次计算加密完成)，分开的各段逐一进行加密运算，那所需要的时间也只是按文件大小线性的增长。通常数字签名为几十字节，加密运算并不需要很长的等待，这就说明对于几百字节或一两 K 字节大小的文件来说，如果进行 RSA 加密，并不会是非常漫长的工作。当然，如果文件更大，加密就显得十分漫长了。比如按前面叙述的 45 毫秒大数运算程序推理，加密 1M 字节大小的文件需要约 1 天的时间。所以，要在普通 PC用几百位以上的长密钥 RSA 加密文件，文件不能过大，一般可以接受的上限是几 KB。如果要在较短时间内加密大文件，需要缩短密钥长度以减小运算量，这将带来安全性隐患。本文的第 3 章将根据实际调试好的软件，测试给出具体的时间消耗数据。例如，在一台配置为酷睿 2 核 CPU，主频 1.6GHZ，物理内存 1GB 的 PC 上测试实现的软件，以560bit 的 n 逐字节加密一个 1KB 大小的文件需要 25 秒。通常记录如银行帐号密码等重要数据的文本文件大小不足百字节，加密只需要数秒钟。所以对于小型文件，进行较长密钥的 RSA 加密是完全可行的。1.3.2 RSA 算法对于文件加密的意义如 1.3.1 节所述，小型文件加密可以使用 RSA。比如，因担心遗忘而用普通文本记录的银行帐号和密码、不应被陌生人知道的重要电话号码、几千字节大的重要小图片等。可行的方法未必是必要的，本小节讨论何种文件适合用非对称密钥加密，即 RSA 加密文件的意义所在。对于前面叙述的带有重要信息的小型文本和二进制数据的维护，如果不加密，将无法放心的保存在计算机上，尤其是连网的或机房里的公共计算机。如果借助功能强大的大型多用户数据保护程序维护几个小型文件，显得十分烦琐，好比杀鸡用牛刀。如果采用对称密钥加密，即加密解密的密钥相同，只适合部分情况。在某些情况下，使用对称密钥加密文件，交流使用不够方便。比如，小红由于某种原因，需要将自己的某个文件在公共计算机上留给小黑，而不希望别人看到内容。如果采用对称密钥加密，小红和小黑提前约好一个密码就可以。但是如果小红想要在同一台公共计算机上再留一个秘密文件给小明，而不希望别人看到，就要和小明另外约定一个密码。如果需要在这台公共计算机上留十个文件给不同的人，自己就要记和十个人约定好的密码，这样以来交流起来不够方便，因为对于小红，要自己维护太多的密钥。非对称密钥(公开密钥方式)恰好解决这样的问题。只要大家都在这台计算机或这台计算机可以访问到的地方，留下自己的公开密钥，一切就变的容易解决了。小红要留给小黑的文件，就用小黑的公开密钥加密，要留给小明的文件，就用小明的公开密钥加密。小黑和小明只要把留给自己的文件用自己的私有密钥解密，就可以得到留给自己的文件了。显然，非对称密钥体制更适合多用户交流，而将这种加密方式直接应用于文件加密，使我们在公开场合的交流更加灵活方便。一种更实际的情况是，我们想通过 Internet 上的公众论坛或邮件发送重要保密信息给某人。例如发送一个银行帐号和密码给某人。这种情况要保证安全，在当今互联网络上是比较棘手的。如果用公众论坛直接留言给指定用户，论坛管理员和服务器管理员通常有方法看到数据。如果发送邮件，虽然传送过程是加密的，但是密码毕竟是由邮件服务器维护，所以系统管理员通常也有办法看到内容。问题的关键在于我们所有的数据包括密钥保存在服务器之上。在这种情况下，我们需要使用公开密钥方式，并自己维护私有密钥。RSA 文件加密可以灵活的解决这些问题。例如，我们可以将任意一个文件用某人的公开密钥加密变换成一段可以复制粘贴的文本，然后粘贴在公众互联网上，对方只需把需要解密的文本复制保存成一个文本文件，在本地机用自己的私有密钥解密即可。我们可以将自己的私有密钥通过 DES 加密后保存在自己的移动磁盘上，使用的时候只要将其解密读取即可，用完后立即从当前操作环境清除。这样，我们自己维护自己的私有密钥，利用简单并且公开的方式，可以安全传送任意小型数据，包括一切二进制文件。所以，对于使用小型文件进行数据交换的情况，更好的方案是通过一个小型应用程序对这些文件进行非对称密钥加密。为了适合前面叙述的在公共 BBS 与特定的某人交流重要保密信息的情况，加密生成的数据应该是文本，这样可以方便复制粘贴。综上所述，使用前面叙述的方式加密文件有两点重要意义：应用非对称密钥加密任意文件，使非对称密钥的应用不仅仅局限于互联网络。非对称加密后的数据变换成文本，使得我们可以通过几乎任何方式安全传递任意文件，比如在只有 http 的环境使用xml 方式。2.RSA 文件加密软件的设计2.1 RSA 算法可行性的证明RSA 算法过程如下：取素数 p，q，令 n=pq.取与(p-1)(q-1)互素的整数 e，由方程 de=1 (mod (p-1)(q-1)解出 d，二元组(e,n)作为公开密钥，二元组(d,n)作为私有密钥b=ae mod n， c=bd mod n.现在证明 a=c (mod n)，以下是证明过程：问题：若 p, q 是相异素数, ed 1 mod (p-1)(q-1), a 是任意一个正整数 , )mod(),o(qpbcqpabe 则有 c a mod (pq)证明： de 1 mod (p-1)(q-1) de k(p-1)(q-1) + 1, 其中 k 是整数 在 mod 中是 preserve 乘法的 (x y mod z and u v mod z xu yv mod z), )mod()( )1()()( qpaabcqpkeded 首先，素数 p、q 要么能整除 a，要么与 a 互素。1. 如果 a 不是 p 的倍数 , 也不是 q 的倍数时, 则 (费马小定理) (根据质数算术基本定理，apmod1)( pqpkod1)(1(与素数 p 互素，则 am 也与 p 互素，m 是整数)(费马小定理 ) qaqod1)( qaqpkmod1)(1( p, q 均能整除 - 1 pq | - 1 (1qpk )(pk即 1 mod pq )(1(qpk c a mod pq )(a2. 如果 a 是 p 的倍数, 但不是 q 的倍数时, 则 (费马小定理 ) qqmod1)( 1 mod q )(pk c a mod q )(qa q | c - a p | a c 0 mod p )1()(qpk p | c - a pq | c - a c a mod pq 3. 如果 a 是 q 的倍数，但不是 p 的倍数时，证明同 2 理显然 4. 如果 a 同时是 p 和 q 的倍数时, 则 pq | a c 0 mod pq )1()(qpk pq | c - a c a mod pq 证毕！ 费马小定理叙述：e 是任一素数, n 是任一整数, 则 n mod e (即如果 n 和 e e互质, 则 1 mod e) 运用群论知识可以证出费马小定理。)(en以上说明 a 经过编码为 b 再经过解码为 c 时, a c mod n (n = pq)，但在做编码解码时, 由于限制 0 0 ？E 为奇数 ？D = ( D P ) m o d nE = E - 1E 为偶数 ？P = （ P P ） m o d nE = E / 2R e s u l t = D结束Y e sY e sY e sN oN oN o图 3-2 Montgomery 幂模算法流程图Fig 3-2 Montgomery power mold flow chart algorithm按照上述流程，列举两个简单的幂模运算实例来形象的说明这种方法。1. 求 的值17mod25开始 D = 1 P = 2 mod 17 = 2 E = 15E 奇数 D = DP mod n = 2 P = PP mod n = 4 E = (E-1)/2 =7E 奇数 D = DP mod n = 8 P = PP mod n = 16 E = (E-1)/2 =3E 奇数 D = DP mod n = 9 P = PP mod n = 1 E = (E-1)/2 =1E 奇数 D = DP mod n = 9 P = PP mod n = 1 E = (E-1)/2 =0最终 D = 9 即为所求。2. 求 的值13mod28开始 D = 1 P = 2 mod 17 = 2 E = 8E 偶数 D = 1 P = PP mod n = 4 E = E/2 =4E 偶数 D = 1 P = PP mod n = 3 E = E/2 =2E 偶数 D = 1 P = PP mod n = 9 E = E/2 =1E 奇数 D = DP mod n = 9 P = 不需要计算 E =