计算机RSA加密毕业论文.doc

目目 录录 摘摘 要要 .1 前前 言言 .3 第第 1 章章 rsa 应用现状及应用于文件加密的分析应用现状及应用于文件加密的分析.4 1.11.1 rsarsa 算法介绍与应用现状算法介绍与应用现状.4 1.21.2 rsarsa 应用于文件加密的分析应用于文件加密的分析.5 第第 2 2 章章 rsarsa 文件加密软件的设计与实现文件加密软件的设计与实现9 2.12.1 需求分析与总体设计需求分析与总体设计9 2.22.2 各部分的设计与开发各部分的设计与开发12 第第 3 3 章章 软件整体测试与分析改进软件整体测试与分析改进28 3.13.1 编写测试各项性能需要的精确计时类编写测试各项性能需要的精确计时类28 3.23.2 测试数据与分析改进测试数据与分析改进28 3.33.3 使用中国余数定理使用中国余数定理40 第第 4 4 章章 可移植模块的简要说明与开发前景可移植模块的简要说明与开发前景42 总结与体会总结与体会44 致谢词致谢词 .45 【参考文献参考文献】 46 摘摘 要要 分析 rsa 算法的应用现状，论证文件加密应用 rsa 算法的可行性和意 义。设计一套完整实用的 rsa 文件加密解决方案，具体编码实现。对 rsa 算 法进行研究，从常规 rsa 算法出发，用 c+实现 rsa 加密算法类库，并在 32 位 windows 平台封装成组件。在.net 平台引用此组件，实现可以对任意文件进 行 rsa 加密操作的窗体应用程序。经过加密的文件以及密钥文件都是文本文 件。给出关键类类图、整个应用程序的结构描述文档、关键模块流程图、较详 细的接口文档、所有源代码。对应用程序进行测试，对测试结果进行分析研究， 进而对应用程序进行改进，对关键算法进行尽可能的优化，最终得到一个在 windows 运行的可以用指定密钥对任意文件进行 rsa 加密并可解密的完整应 用程序，和一些相关的可移植组件。 【关键词】 rsa rsa 算法 文件加密 加密成文本 abstract do research about the application area of rsa encryption and reason that rsa can be used for file encryption. design a rsa file-encrypt solution and complete an application on microsoft windows. design a c+ class based on normal rsa algorithm. and make a dll module based on the class. then complete a .net framework window-application using that dll. the application can encrypt any file and decrypt them. the file after encryption can be saved as a text file. and the encryption-keys also can be saved as text.provide pivotal classes chart, project description, core algorithm flowchart, all source code, and module interfaces document. do application performance test and record the performance data. analyze the result then optimize core algorithm and improve the application. finally, create a practical application using rsa algorithm that can encrypt and decrypt any file. and several modules in the project can be reuse by other applications. for instance, the c+ class can be cross-compiled for handheld devices, the dll can be referenced by other win32 applications, and the .net class can be easily referenced by web server applications or web services. 【 【key words】 】 rsa rsa algorithm file encryption encrypt to text 前前 言言 rsa 公钥加密算法是第一个既能用于数据加密也能用于数字签名的算法。 它易于理解和操作，也十分流行。算法的名字以发明者的姓氏首字母命名： ron rivest, adi shamir 和 leonard adleman。虽然自 1978 年提出以来， rsa 的安全性一直未能得到理论上的证明，但它经历了各种攻击，至今 （2007 年）未被完全攻破。随着越来越多的商业应用和标准化工作，rsa 已 经成为最具代表性的公钥加密技术。visa、mastercard、ibm、microsoft 等 公司协力制定的安全电子交易标准（secure electronic transactions，set）就采用了标准 rsa 算法，这使得 rsa 在我们的生活中几 乎无处不在。网上交易加密连接、网上银行身份验证、各种信用卡使用的数 字证书、智能移动电话和存储卡的验证功能芯片等，大多数使用 rsa 技术。 当今公钥加密更广泛应用于互联网身份认证，本课题将公钥加密算法 rsa 应用于小型文件加密。将任意文件加密成文本的解决方案，使其使用更 加灵活。整个工程的分层设计，给引用移植和后续开发带来便利。 第 1 章 rsa 应用现状及应用于文件加密的分析 1.11.1 rsarsa 算法介绍与应用现状算法介绍与应用现状 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). (具体的 rsa 算法协议见 .au/rsa_alg.html ， 提及的算法中的字母与协议文档中的一致，不再另做解释) rsa 公开密钥加密算法自 20 世纪 70 年代提出以来，已经得到了广泛认 可和应用。发展至今，电子安全领域的各方面已经形成了较为完备的国际规 范。rsa 作为最重要的公开密钥算法，在各领域的应用数不胜数。rsa 在硬件 方面，以技术成熟的 ic 应用于各种消费类电子产品。 rsa 在软件方面的应用，主要集中在 internet 上。加密连接、数字签名 和数字证书的核心算法广泛使用 rsa。日常应用中，有比较著名的工具包 open ssl(ssl，security socket layer,是一个安全传输协议，在 internet 上进行数据保护和身份确认。open ssl 是一个开放源代码的实现了 ssl 及相 关加密技术的软件包，由加拿大的 eric yang 等发起编写的。相关详细介绍 见 /about/ )。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 算法的各种数据加密规范(rsa 算法应用规范介绍 参见： /rsalabs/node.asp?id=2146 ，这些 api 内部支持的算法不仅仅只有 rsa，但是 rsa 是数字签名和证书中最常用的)， 用户程序可以直接使用 java 标准库中提供的 api 进行数字签名和证书的各种 操作。 单机应用程序使用 rsa 加密尚比较少见，例如使用 rsa 加密任意一个文 件。 1.21.2 rsarsa 应用于文件加密的分析应用于文件加密的分析 1.2.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 章将根据实际调试好的软件，测试给出具体的时间消耗数据。 例如，在一台配置为 amd athron2800+，外频 333mhz，物理内存 512mb 的 pc 上测试实现的软件，以 560bit 的 n 逐字节加密一个 1kb 大小的文件需要 55 秒。通常记录如银行帐号密码等重要数据的文本文件大小不足百字节，加密 只需要数秒钟。所以对于小型文件，进行较长密钥的 rsa 加密是完全可行的。 1.2.2 文件加密使用 rsa 的意义 如 1.2.1 节所述，小型文件加密可以使用 rsa。比如，因担心遗忘而用 普通文本记录的银行帐号和密码、不应被陌生人知道的重要电话号码、几千 字节大的重要小图片等。可行的方法未必是必要的，本小节讨论何种文件适 合用非对称密钥加密，即 rsa 加密文件的意义所在。 对于前面叙述的带有重要信息的小型文本和二进制数据的维护，如果 不加密，将无法放心的保存在计算机上，尤其是连网的或机房里的公共计算 机。如果借助功能强大的大型多用户数据保护程序维护几个小型文件，显 得十分烦琐，好比杀鸡用牛刀。如果采用对称密钥加密，即加密解密的密 钥相同，只适合部分情况。在某些情况下，使用对称密钥加密文件，交流使 用不够方便。比如，张三由于某种原因，需要将自己的某个文件在公共计算 机上留给李四，而不希望别人看到内容。如果采用对称密钥加密，张三和李 四提前约好一个密码就可以。但是如果张三想要在同一台公共计算机上再留 一个秘密文件给王五，而不希望别人看到，就要和王五另外约定一个密码。 如果需要在这台公共计算机上留十个文件给不同的人，自己就要记和十个人 约定好的密码，这样以来交流起来不够方便，因为对于张三，要自己维护太 多的密钥。非对称密钥(公开密钥方式)恰好解决这样的问题。只要大家都在 这台计算机或这台计算机可以访问到的地方，留下自己的公开密钥，一切就 变的容易解决了。张三要留给李四的文件，就用李四的公开密钥加密，要留 给王五的文件，就用王五的公开密钥加密。李四和王五只要把留给自己的文 件用自己的私有密钥解密，就可以得到留给自己的文件了。显然，非对称密 钥体制更适合多用户交流，而将这种加密方式直接应用于文件加密，使我们 在公开场合的交流更加灵活方便。 一种更实际的情况是，我们想通过 internet 上的公众论坛或邮件发送重 要保密信息给某人。例如发送一个银行帐号和密码给某人。这种情况要保证 安全，在当今互联网络上是比较棘手的。如果用公众论坛直接留言给指定 用户，论坛管理员和服务器管理员通常有方法看到数据。如果发送邮件， 虽然传送过程是加密的，但是密码毕竟是由邮件服务器维护，所以系统管理 员通常也有办法看到内容。问题的关键在于我们所有的数据包括密钥保存在 服务器之上。在这种情况下，我们需要使用公开密钥方式，并自己维护私有 密钥。rsa 文件加密可以灵活的解决这些问题。例如，我们可以将任意一个 文件用某人的公开密钥加密变换成一段可以复制粘贴的文本，然后粘贴在公 众互联网上，对方只需把需要解密的文本复制保存成一个文本文件，在本地 机用自己的私有密钥解密即可。我们可以将自己的私有密钥通过 des 加密后 保存在自己的移动磁盘上，使用的时候只要将其解密读取即可，用完后立即 从当前操作环境清除。这样，我们自己维护自己的私有密钥，利用简单并且 公开的方式，可以安全传送任意小型数据，包括一切二进制文件。 所以，对于使用小型文件进行数据交换的情况，更好的方案是通过一个 小型应用程序对这些文件进行非对称密钥加密。为了适合前面叙述的在公共 bbs 与特定的某人交流重要保密信息的情况，加密生成的数据应该是文本， 这样可以方便复制粘贴。 综上所述，使用前面叙述的方式加密文件有两点重要意义：应用非对 称密钥加密任意文件，使非对称密钥的应用不仅仅局限于互联网络。非对 称加密后的数据变换成文本，使得我们可以通过几乎任何方式安全传递任意 文件，比如在只有 http 的环境使用 xml 方式。 第第 2 2 章章 rsarsa 文件加密软件的设计与实现文件加密软件的设计与实现 2.12.1 需求分析与总体设计需求分析与总体设计 2.1.1 功能分析 经过 1.2.2 节的论述，我们可以将对软件的要求总结如下： 可以按要求的位数生成非对称密钥。 可以保存密钥和装载密钥，密钥保存为纯文本。 可以用指定密钥以 rsa 算法加密任意一个文件，加密生成的数据为纯 文本。 可以装载加密过的文件，并用指定的密钥解密还原出原文件。 提示信息完整、操作舒适、图形界面雅观 按上述描述，给出 use case 和 statechart 如图 2-1。 图 2-1 本项目的 use case 和 statechart 根据以上分析，一般来说，需要进行编码的程序有 rsa 密钥生成 rsa 加密解密 任意文件的读取和保存操作 各环 节必要的数据编码转换 图形操作界面。 2.1.2 工程方案选择 结合现有的常见开发模式综合分析，有多种实现方案，下面陈述其中几 种，并分析选择一种解决方案，并给出工程框架。 1. 整个工程使用 java 平台实现 rsa 密钥生成、rsa 加密解密的功能实现十分简单，因为标准库中集成几 乎所有功能，不需要从 rsa 算法出发进行编码。在 j2se 标准库中， javax.crypto 中的 cipher 类用于具体的加密和解密，java.security 包直接 提供了数字签名的相关方法。因为有强大的标准库支持，文件的读取和保存 操作、各环节必要的数据编码转换、图形操作界面的实现也很简单(使用 java.io java.awt 或 javax.swing 等包)，如果结合一种快速开发的 ide， 比如 jbuilder，整个软件可以在很短的时间内编码完成。如果不考虑非 pc 设备和机器效率等问题，java 平台几乎是最佳解决方案。但是缺点也很明显， 如果想把核心算法和功能应用到非 pc 设备(例如嵌入式手持设备)，则要求设 备上有支持前面提及的加密类库的 cvm；对于在 pc 上运行，jvm 的数据运算 速度要远远落后于本地化代码在 pc 上的运算速度，本软件需要进行大量运算， 这一点不适合由 java 完成。 2. 整个工程使用.net 平台实现 与使用 java 平台完全类似，加密等有.net 基础类库的支持，不需要大 量编码实现，另外由于 visual studio 的强大便利，这种规模的工程可以十 分迅速的完成。缺点是只能在有微软.net framework 的环境运行，在 windows 操作系统，.net framework 的机器效率好于 java 平台，但是相比于 本地化的代码，还是十分拖沓的。 3. 整个工程使用 windows 本地化程序实现 在不应用 windows 或第三方现成组件的情况下，需从 rsa 算法出发编码 实现。其他各功能的设计开发，如文件操作、数据编码转换和图形界面等， 可以使用 atl、mfc 或 windows api 实现。这种工程几乎是为 windows 量身订 做，执行效率最好。但是对于非 pc 设备，只能方便的移植到运行 windows 嵌 入式操作系统的设备，向其他操作系统移植困难，需要重新编写大量代码。 通常解决本地化代码的移植问题，都是使用 c+标准库，即功能尽量多的由 c+标准库完成，这样在移植的时候，只需要重新编写操作系统相关的代码即 可。这种开发方式比起前两种，缺点就是设计开发模式陈旧，代码烦琐，不 方便维护；流行的.net 上的语言引用各种功能比较麻烦。 4. 考虑可能的复用，针对具体情况分层开发实现 综合考虑复用性、可维护性和执行效率，较妥当的方法是分层设计。核 心的 rsa 算法由 c+类库实现，针对用户所在的操作系统封装成本地化组件。 其他各功能如文件操作、数据编码转换和图形界面等，由托管代码借助虚拟 机平台标准库的功能快速开发实现(本文针对选用.net 上的 c#论述，选用 java 由 jni 或其他方式调用本地组件，设计模式上是完全类似的)。这种开 发方式，核心功能集中在最底层，在不断的封装中针对具体环境对组件功能 不断扩充，任意一个层面的封装都可以被直接应用到其他项目，比如在 web 使用以前为某窗体程序写的组件、给嵌入式设备交叉编译算法库等。但是每 一层都需要依赖底层的所有组件。图 2-2 形象的说明了分层设计给复用带来 的好处。 图 2-2 综合考虑复用性、可维护性和执行效率的分层设计 选用第四种设计方案，上层使用 c#，底层算法使用 c+，可以由一个 visual studio 解决方案管理，给调试带来极大的方便。整个工程分四层， 实现 rsa 加密算法的 c+核心类库、封装 c+核心类库的 dll 组件、引用 dll 的.net 类、实现文件操作功能的.net 窗体应用程序。2.2 节详细介绍各部分 的设计与开发。 考虑到工作量，本软件加解密数据没有严格遵从 rsa 标准 pkcs #1，而 是在满足设计要求的前提下，以一种尽可能简单的方式实现加密和解密。 2.22.2 各部分的设计与开发各部分的设计与开发 2.2.1 实现 rsa 加密算法的 c+核心类库 1. 大数存储和四则运算 根据 rsa 算法的要求，为了实现大数的各种复杂运算，需要首先实现大 数存储和基本四则运算的功能。当今开源的大数运算 c+类有很多，多用于 数学分析、天文计算等，本文选用了一个流行的大数类型，并针对 rsa 算法 和本项目的具体需要对其进行了扩充和改进。下面简单介绍大数存储和四则 运算的实现原理。 最先完成的功能是大数的存储，存储功能由 flex_unit 类提供。和普通 的类型一样，每一个大数对应一个 flex_unit 的实例。类 flex_unit 中，用 一个无符号整数指针 unsigned * a 指向一块内存空间的首地址，这块内存空 间用来存储一个大数，所以可以说，大数是被存储在一个以 unsigned 为单元 的线性组中。在方法 void reserve( unsigned x )中通过 c+的 new 来给 a 开辟空间，当 flex_unit 的实例中被存入比当前存储的数更大的数时，就会 调用 reserve 来增加存储空间，但是当 flex_unit 的实例中被存入比当前存 储的数更小的数时，存储空间并不会自动紧缩，这是为了在运算的时候提高 执行效率。结合指针 a，有两个重要的无符号整数来控制存储，unsigned z 和 unsigned n，z 是被分配空间的单元数，随数字变大不断增大，不会自己 紧缩，而 n 是当前存储的大数所占的单元数，组成一个大数的各 unsigned 单 元的存入和读出由 set、get 方法完成，变量 n 是只读的。类型 unsigned 在 32 位机是 32 位的，所以对于 flex_unit 这个大数类来说，每个大数最大可 以达到 个字节长，这已经超过了 32 位机通常的最大内存容量，所以是足够 进行 rsa 所需要的各种运算的。图 2-3 形象的说明了大数存储类 flex_unit 对大数的管理。 *a unsigned 类型的指针类型的指针 大数占大数占 n 个单元个单元 开辟了开辟了 z 个单元大的内存个单元大的内存 内存空间内存空间 图 2-3 flex_unit 对大数的管理 在 flex_unit 的存储功能基础上，将其派生，得到 vlong_value，在 vlong_value 中实现四则运算函数，并实现强制转换运算符 unsigned，以方 便大数类型和普通整数的互相赋值。当大数被强制转换为 unsigned 时，将取 其最低四字节的值。四则运算实现的原理十分简单，都是按最基本的算术原 理实现的，四则运算过程的本质就是按一定数制对数字的计算，比如相加， 就是低位单元对齐，逐单元相加并进位，减法同理。而乘除法和取余也都是 按照竖式运算的原理实现，并进行了必要的优化。虽然实现了四则运算函数， 但是若是程序里的运算都要调用函数，显得烦琐而且看起来不美观，所以我 们另写一个类 vlong，关联(associate，即使用 vlong_value 类型的对象或 其指针作为成员)vlong_value，在 vlong 重载运算符。这样，当我们操作 vlong 大数对象的时候，就可以像使用一个简单类型一样使用各种运算符号 了。之所以将 vlong_value 的指针作为成员而不是直接构造的对象，也是为 了提高执行效率，因为大型对象的拷贝要消耗不少机器时间。 2. 大数幂模与乘模运算montgomerymontgomery 幂模算法 在实现了 vlong 类型后，大数的存储和四则运算的功能都完成了。考虑 到 rsa 算法需要进行幂模运算，需要准备实现这些运算的方法。所以写一个 vlong 的友元，完成幂模运算功能。幂模运算是 rsa 算法中比重最大的计算， 最直接地决定了 rsa 算法的性能，针对快速幂模运算这一课题，西方现代数 学家提出了很多的解决方案。经查阅相关数学著作，发现通常都是依据乘模 的性质，先将幂模运算化简为乘模nnbnanbamod)mod()mod(mod)( 运算。 通常的分解习惯是指数不断的对半分，如果指数是奇数，就先减去一变 成偶数，然后再对半分，例如求 d=，e=15，可分解为如下 6 个乘模nc e mod 运算。 ncncccmodmod 2 1 ncncccmodmod 3 12 ncncccmodmod 6 223 ncncccmodmod 7 34 ncncccmodmod 14 445 ncncccmodmod 15 56 归纳分析以上方法，对于任意指数 e，可采用如图 2-4 的算法流程计算 。 开始 d=1;p=c mod n e0? e 为奇数? npddmod)( e=e-1 npppmod)( e 为偶数? e=e/2 yes no result=d 结束 yes yes no no 图 2-4 幂模运算分解为乘模运算的一种流程 按照上述流程，列举两个简单的幂模运算实例来形象的说明这种方法。 求的值17mod215 开始d = 1p = 2 mod 17 = 2 e = 15 e 奇数d = dp mod n = 2p = pp mod n = 4e = (e-1)/2 =7 e 奇数d = dp mod n = 8p = pp mod n = 16e = (e-1)/2 =3 e 奇数d = dp mod n = 9p = pp mod n = 1e = (e-1)/2 =1 e 奇数d = dp mod n = 9p = pp mod n = 1e = (e-1)/2 =0 最终 d = 9 即为所求。 求的值13mod28 开始d = 1p = 2 mod 17 = 2 e = 8 e 偶数d = 1p = pp mod n = 4e = e/2 =4 e 偶数d = 1p = pp mod n = 3e = e/2 =2 e 偶数d = 1p = pp mod n = 9e = e/2 =1 e 奇数d = dp mod n = 9p = 不需要计算 e = (e-1)/2 =0 最终 d = 9 即为所求。 观察上述算法，发现 e 根据奇偶除以二或减一除以二实际就是二进制的 移位操作，所以要知道需要如何乘模变量，并不需要反复对 e 进行除以二或 减一除以二的操作，只需要验证 e 的二进制各位是 0 还是 1 就可以了。同 样是计算，下面给出从右到左扫描二进制位进行的幂模算法描ncd e mod 述，设中间变量 d,p,e 的二进制各位下标从左到右为 u,u-1,u-2,0。 powmod(c,e,n) d=1; p=c mod n; for i=0 to u do if(ei=1)d=d*p(mod n); p=p*p(mod n); return d; 有些文献将上述算法称为平方乘积二进制快速算法，例如参考文献中的 基于 rsa 算法的一种新的加密核设计 ，其实这种算法本质上和图 2-4 的流 程完全一致，只是把根据指数奇偶分开的减一和除以二合并成对指数二进制 各位的判断而已。在本软件的代码中采用直接扫描 vlong 二进制各位的办法。 剩下的问题就是乘模运算了。提高乘模运算的速度是提高模幂运算速度 的关键。一般情况下，n 是数百位乃至千位以上的二进制整数，用普通的除 法求模而进行乘模运算是不能满足速度的要求的。为此，montgomery 在 1983 年提出了一种模加右移的乘模算法（主要著作发表于 1985 年） ，从而避免了 通常求模算法中费时的除法步骤。本软件仅仅是应用 montgomery(蒙哥马利) 算法，算法的具体推导证明需要颇多数论知识，不在本文的讨论范围内，如 需了解可参见蒙哥马利的相关著作。下面简单描述 rsa 中常用的 montgomery(蒙哥马利)算法供参考理解源程序。 选择与模数 n 互素的基数 r=2k，n 满足 2k1n2k， n 应为奇数。并且 选择 r-1及 n ，满足 0 r-1n, 0 nn,使得 rr-1-nn1。对于 0mrn 的任意整数,montgomery 给出求模乘法 mr-1 mod n 的快速算法 m(m): m(m) rnmt rrnrm / )( 0 ;mod)mod( if (tn) return (t-n); else return t; 因为，故 t 为整数；同时，得rmmnnnmodnmtrmod 。由于，m(m) 中 t 结果范围是nmrtmod 1 rnrnnm0 0t=n) x -= n; return x; exp(c,e,n) d=r-n; p=c*r mod n; i=0; while(true) if(e 的当前二进制位 ei=1)d=m(d*p); /从低位到高位 检测二进制位 i+=1; if(i=e 的二进制位数)break; p=m(p*p); return d*r-1 (mod n); 在具体的实现中，对应 monty 类的 mul 和 exp 方法。全局函数 modexp 初 始化 monty 对象并调用其 exp 方法，使用的时候直接调用 modexp 即可。 3. 寻找素数eratostheneseratosthenes 筛选与 fermatfermat 素数测试 首先要说明的是，事实上，当今的计算机还不足以聪明到立刻计算生成 一个很大的随机素数。一般来说，要得到 100%准确的大素数，都是通过查已 经计算好的素数表的方式。但是素数表的方式给 rsa 的安全性带来隐患，因 为攻击者如果得到了密钥生成时所使用的素数表，攻破 rsa 加密的难度将会 大大降低。本程序起初使用素数表的方式，后来考虑到安全性问题，生成密 钥的方式改为随机计算生成。这样，短时间内如果要得到一个 100%准确的大 素数是很困难的，只能以尽可能高的概率得到一个大素数。 经过 和 小节，所有的大数运算功能都准备完毕，在此 基础上，本工程将寻找素数的功能置于类 prime_factory_san 之中。外部只 要调用本类实例的成员 vlong find_prime( vlong inp;i+) unsigned p = pli; unsigned r = start % vlong(p); if (r) r = p - r; while ( r 0 x=r 图 2-5 在素数搜索范围内剔除小素数因子 p 的倍数 接下来，对可能为素数的数(即标记数组 b中值为 1 的元素对应的数) 进行素数测试。数论学家利用费马小定理研究出了多种素数测试方法，本程 序使用一种最简单的方式，直接应用费马小定理。取一个与 p 互素的整数 a，对于大素数 p 来说应该满足 ap-1mod p=1，但是我们把 p 代入一个大整数， 满足这个关系的数不一定是素数。这时我们改变 a，进行多次测试，如果多 次测试都通过，这个数是素数的概率就比较大。按这种原理，我们编写素数 测试函数如下。 int is_probable_prime_san( const vlong /测试次数 const unsigned anyrep = 2,3,5,7 ; /测试用的底数 for ( unsigned i=0; irep; i+=1 ) if ( modexp( anyi, p-vlong(1), p ) != vlong(1) ) return 0; /modexp 是幂模函数，按上一小节叙述的算法编码。 /这里 modexp 计算 anyip-1mod p。 return 1; 测试通过，程序就判定这个数为找到的素数，将找到的素数返回给上层 程序使用。在这里其实有一个不可忽视的问题，就是得到一个测试通过的合 数。对于这种情况，rsa 算法加密解密是否还可以实现，是一个需要从数学 角度论证的问题。因为得到素数的概率很高，经过一整天的生成密钥和加密 操作，没有发现失败的密钥， 所以本文暂没有对这个问题进行讨论。 综上所述，总结素数寻找的流程，如图 2-6 所示。 开始 按 start 参数初始化标记数组 bss ; i=0 计数 i8。 以上公式其实也可以从理论上得到，因为模数 n 取 8 位时，幂模运算的 结果仍然近似为 8 位，这时一个字节的数据经过加密，得到的数据大小近似 不变，转换成十六进制文本，大小就增加了 1 倍。按此原理，幂模运算结果 长度近似为加密模数 n 的长度，加密后数据长度是加密前的 n/8 倍（n 是加 密位数） ，而转换为十六进制文本后长度又增大 1 倍，加密后得到的文本长度 就是加密前原始数据大小的 n/4 倍，所以 b=an/4，这与前面从实验结果总 结得到的公式基本一致，可以把公式中的 260 修正为更精确一些的 256。 3. 以多字节为步长，对文件进行加密 默认的设置是加密时逐个字节进行 rsa 运算，可以通过设置窗体把分块 的大小更改为其他长度，比如 2 字节一组、4 字节一组，进行 rsa 运算。下 面测试多字节为步长的加密执行效率。取一个 480 字节长的文件作为加密对 象，对其进行 512bit rsa 公钥加密、私钥解密还原，记录所消耗的时间。统 计数据如表 3-6 所示。 表 3-6 加密分段大小改变对效率的影响测试(消耗时间单位：秒) 加密方 式 步 长 2 字节4 字节6 字节8 字节10 字节 512bit 公钥加 密 23.555112.82057.81175.91855.1848 512bit 私钥解 密 46.308323.608916.108311.48209.2541 可见，增大加密步长使加密解密速度大幅增加，而且大步长的加密生成 的文本文件体积也比小步长的小。这都是因为增大了步长后，文件被分成的 块数少了，幂模运算次数下降。所以在使用 rsa 加密时，设置使用合适的数 据分块也是提高加密速度的关键。 4. 在更快的 pc，对进行文件加密测试 在一些性能更好的 pc 上，本软件可以获得更好的性能，测试数据同样可 以分析得到以上段落叙述的结论。下面对照表 3-4，给出一组其他 pc 上同样 的测试得到的数据，测试 pc 配置为 cpu amd athron2800+，外频 333mhz，物 理内存 512mb。数据见表 3-7。 表 3-7 待加密文件大小与加密时间的关系再次测试(时间单位：秒) n 位数 文件大 小 50byte100byte150byte200byte250byte 512bit 公钥加 密 2.43474.89757.17289.450811.9837 512bit 私钥解 密 4.77259.442714.00219.012523.6544 1024bit 公钥加 密 6.350112.236418.245924.300130.1284 1024bit 私钥解 密 20.010139.875460.212679.335199.5482 对于这组数据，表 3-4 后的推理分析仍都成立。在此 pc 测试填写表 3- 6，同样得到了类似规律的数据，在此不再罗列。经过一系列各种机型、各种 windows 操作系统（包括 windows xp/2000sp4/me/98，均需.net 框架）上的 测试，本软件均能正常运行。在 2006 年初主流配置的 pc 上运行此软件，逐 字节加密 1kb 大小的文件，消耗时间均在 1 分钟以内。 3.2.4 性能分析与改进优化 经过一系列的 rsa 密钥生成、文件输入输出和加密解密测试，做简要的 性能分析如下。 软件消耗时间的运算，大部分集中在 c+核心类库，即 rsa 相关的各 种运算。其中，幂模运算和寻找素数对时间的消耗最大，在核心优化时应优 先考虑。 文件输入输出消耗时间其次，因为磁盘读写速度要远远低于内存读写 速度。所以，应该将频繁的读写操作尽量集中到内存，然后一次性写入磁盘。 针对以上两点，软件应进行一系列改进和优化。主要有以下几方面。 在要对文件进行加密解密的时候，先将文件按一定的数据结构读入内 存，然后进行加密或解密操作。运算数据都读取自内存。 在对加密或解密完成的数据进行写出的时候，都是将其直接写到指定 好的文件，即直接写入磁盘。这是因为，考虑到中途可能因为意外断电等原 因引起操作中断，为了保护已经花费时间运算完成的数据，将其直接写入磁 盘。 在关键算法上做进一步优化，例如在寻找素数时，素数测试使用更快 速的算法；还有 3.3 节提到的，在用私有密钥进行幂模运算时使用中国余数 定理等。 对 c+核心类库进行重点优化，使其运算效率尽可能提高。其中包括 对各类之间的组织细节、各程序模块的具体编写等，进行全面细致的检查和 修改，例如将大数据类型以对象指针传递而不拷贝，将简单的 for 循环展开 等。 由于开发时间仓促等因素，在书写本文时，软件并未完成全面细致的优 化。 3.33.3 使用中国余数定理使用中国余数定理 对于用 rsa 加密解密的一方，是计算 mod d mcn 。这里 npq，p 和 q 是两个二进制长度接近的大素数。由于用私密密钥加密或解密的一方实 际知道 n 的分解，即 p 和 q，所以这一计算可以分解为以下两部分分别进行 (附录中有中国余数定理的简单介绍) 。 12 1122mod ,mod dd mcp mcq 其中的 c1、c2、d1、d2 如下： 1 2 1 2 mod , mod , mod(1), mod(1), ccp ccq ddp ddq 根据 rsa 算法的要求，私密密钥 d 的二进制长度接近 n 的长度，因此， d1 和 d2 的二进制长度仅有 n 的一半左右，这样就节省了大量的计算工作。 最后，应用中国余数定理就能计算出的值 m。，其npymqymmmod)( 2211 中.qpypqymod1,mod1 21 如果应用中国余数定理计算幂模，主要工作花在计算 12 1122mod ,mod dd mcp mcq 上，计算 c1、c2、d1、d2 和 m 的运算与幂摸 运算相比，计算时间较短可以不计。而位数对幂摸运算速度影响很大，因此 分开计算 12 1122mod ,mod dd mcp mcq 比计算 mod d mcn 要快很多。经过 测试，使用中国余数定理来简化一些幂模运算，速度比不使用中国余数定理 时有很大的提高。 在书写本文时软件中尚未使用中国余数定理。 第第 4 4 章章 可移植模块的简要说明与开发前景可移植模块的简要说明与开发前景 如 2.1.2 节所叙述，分层设计给移植带来方便，下面简要叙述各层可能 的移植方式。 实现 rsa 加密算法的 c+核心类库，是基于 c 和 c+的标准库创建的， 没有用到 c+泛型计算、stl 相关内容，代码中没有任何与操作系统相关的内 容。这是一种移植特性最好的程序模块，因为现今多数非 pc 设备支持 c+编 译。一般可以直接将本模块交叉编译给嵌入式设备，或在其他操作系统编译 使用。在编译前，将 rsa_san.cpp 和 vlong.cpp 文件中的#include “stdafx.h“一行去掉，然后连同各自的头文件拷贝出来，仅这四个文件即为 实现 rsa 加密算法的