人人文库网 > 毕业设计 > JSJ01-016@ASP.NETRSA可视化算法程序的实现与研究(源代码+论文)
ASP.NETRSA可视化算法程序的实现与研究(源代码+论文).doc
JSJ01-016@ASP.NETRSA可视化算法程序的实现与研究(源代码+论文)
收藏
资源目录
压缩包内文档预览：(预览前20页/共39页)
编号：507801
类型：共享资源
大小：1.91MB
格式：ZIP
上传时间：2015-11-10
上传人：QQ28****1120
认证信息
个人认证
孙**（实名认证）
辽宁
IP属地：辽宁
12
积分
- 关 键 词：
-
毕业设计计算机
- 资源描述：
-
JSJ01-016@ASP.NETRSA可视化算法程序的实现与研究(源代码+论文),毕业设计计算机
- 内容简介：
-
=动态链接库 : rsa 项目概况=应用程序向导已为您创建了这个 rsa DLL。此文件包含组成 rsa 应用程序的每个文件的内容摘要。rsa.vcproj这是用应用程序向导生成的 VC+ 项目的主项目文件。它包含有关生成此文件的 Visual C+ 版本的信息，以及有关用应用程序向导选择的平台、配置和项目功能的信息。sanpack_rsa.cpp这是主 DLL 源文件。/其他标准文件:StdAfx.h、StdAfx.cpp这些文件用于生成名为 sanpack_rsa.pch的预编译头(PCH)文件以及名为 StdAfx.obj 的预编译类型文件。nts 分类号： TP309.7 U D C： D10621-408-(2007) 6056-0 密 级：公 开 编 号： 2003212004 成都信息工程学院 学位论文 RSA算法 的 实现 论文作者姓名： 吴俊杰 申请学位专业： 计算机科学与技术 申请学位类别： 工 学学士 指导教师姓名（职称）： 游 洪 跃（副教授） 论文提交日期： 2007 年 06 月 09 日 nts RSA算法 的 实现 摘 要 本文 设计的是一套完整实用的 RSA 文件加密解决方案，并具体编码实现。本文采用费马小定理测试素数，使用 Montgomery 加快大数模乘运算，用 C+实现RSA 加密算法类库，并在 32 位 windows 平台封装成组件。在 .Net 平台引用此组件，实现可以对任意文件进行 RSA 加密操作的窗体应用程序。经过加密的文件以及密钥文件都是文本文件。本文首先给出关键类类图、整个应用程序的结构描述文档，然后对关键模块流程图、详细的接口文档进行阐述，并给出关键的实现代码，最后对应用程序进行测试，对测试结果进行分析研究 ，进而对应用程序进行改进，对关键算法进行尽可能的优化，最终得到一个在 windows 运行的可以用指定密钥对任意文件进行 RSA 加密并可解密的完整应用程序，和一些相关的可移植组件。 关键词 ： RSA； 文件加密 ； Montgomery； 费马定理 nts Implement of RSA Algorithm Abstract In this paper, a solution of encrypting file with RSA algorithm and the codes of this system are introduced. Fermat theory is used to test prime number. Montgomery is used to cut short the time of modular multiplication of large number. The class library of RSA is implemented in C+, and packaged to component on the platform of 32 bits windows. On the platform of .Net, the application is implemented with reference of this component and can encrypt any file with RSA. Both encrypted files and key files are text files. In this paper, core class figures and the framework are first introduced. Then the flow of core modules and detail interfaces are stated and the kernel codes are showed also. Finally, it analyzes the result of test, then optimizes core algorithm. In the conclusion, an entire application which can encrypt any files with RSA algorithm using given key and some transplanted components are implemented. Key words: RSA ; File Encryption ; Montgomery ; Fermat nts 目 录 论文总页数： 35 页 1 引言 .1 1.1 课题背景 .1 1.2 RSA 算法介绍与应用现状 .1 1.3 RSA 应用于文件加密的分析 .2 1.3.1 文件加密使用 RSA 的可行性 .2 1.3.2 文件加密使用 RSA 的意义 .3 2 RSA 文件加密软件的设计与实现 .4 2.1 需求分析与总体设计 .4 2.1.1 功能分析 .4 2.1.2 工程方案选择 .4 2.2 各部分的设计与开发 .5 2.2.1 实现 RSA 加密算法的 C+核心类库 .5 2.2.2 封装 C+核心类库的 DLL 组件 .25 2.2.3 引用 DLL 的 .Net 类与实现文件操作功能的窗体应用程序 .26 3 软件整体测试与分析改进 .27 3.1 编写测试各项性能需要的精确计时类 .27 3.2 测试数据与分析改进 .27 3.2.1 密钥生成测试 .27 3.2.2 数据输入输出测试 .28 3.2.3 加密解密测试 .29 结 论 .31 参考文献 .32 附 录 .33 致 谢 .34 声 明 .35 nts 第 1 页 共 35 页 1 引 言 1.1 课题背景 RSA 公钥加密算法是第一个既能用于数据加密也能用于数字签名的算法。它易于理解和操作，也十分流行。算法的名字以发明者的姓氏首字母命名： Ron Rivest, Adi Shamir 和 Leonard Adleman。虽然自 1978 年提出以来， RSA 的安全性一直未能得到理论上的证明，但它经历了各种攻击，至今（ 2006 年）未被完全攻破。随着越来越多的商业应用和标准化工作， RSA 已经成为最具代表性的公钥加密技术。 VISA、 MasterCard、 IBM、 Microsoft 等公司协力制定的安全电子交易标准（ Secure Electronic Transactions， SET）就采用了标准 RSA 算法，这使得 RSA 在我们的生活中几乎无处不在。网上交易加密连接、网上银行身份验证、各种信用卡使用的数字证书、智能移动电话和存储卡的验证功能芯片等，大多数使用 RSA 技术。 当今公钥加密更广泛应用于互联网身份认证，本课题将公钥加密算法 RSA应用于小型文件加密。将任意文件加密成文本的解决方案，使其使用更加灵活。整个工程的分层设计，给引用移植和后续开发带来便利。 1.2 RSA 算法介绍与 应用现状 RSA 算法可以简单叙述如下： 取素数 p， q，令 n=p q. 取与 (p-1) (q-1)互素的整数 e， 由方程 d e=1 (mod (p-1) (q-1)解出 d， 二元组 (e,n)作为公开密钥 ， 二元组 (d,n)作为私有密钥 b=ae mod n， c=bd mod n. 附录中 给出 了 证明 a=c (mod n). RSA 公开密钥加密算法自 20 世纪 70 年代提出以来，已经得到了广泛认可和应用。发展至今，电子安全领域的各方面已经形成了较为完备的国际规范。RSA 作为 最重要的公开密钥算法，在各领域的应用数不胜数。 RSA 在硬件方面，以技术成熟的 IC 应用于各种消费类电子产品。 RSA 在软件方面的应用，主要集中在 Internet 上。加密连接、数字签名和数字证书的核心算法广泛使用 RSA。日常应用中，有比较著名的工具包 Open SSL(SSL， Security Socket Layer,是一个安全传输协议，在 Internet 上进行数据保护和身份确认。 Open SSL 是一个开放源代码的实现了 SSL 及相关加密技术的软nts 第 2 页 共 35 页 件包，由加拿大的 Eric Yang 等 发 起 编 写 的 。 相 关 详 细 介 绍 见/about/ )。 Open SSL 应用 RSA 实现签名和密钥交换，已经在各种操作系统得到非常广泛的应用。另外，家喻户晓的 IE 浏览器，自然也实现了 SSL 协议，集成了使用 RSA 技术的加密功能，结合 MD5 和 SHA1，主要用于数字证书和数字签名，对于习惯于使用网上购物和网上银行的用户来说，几乎天天都在使用 RSA 技术。 1.3 RSA 应用于文件加密的分析 1.3.1 文件加密使用 RSA 的可行性 通过 1.2 节的论述，不难看出 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 用几百位以上的长密钥nts 第 3 页 共 35 页 RSA 加密文件，文件不能过大，一般可以接受的上限是几 KB。如果要在较短时间内加密大文件，需要缩短密钥长度以减小运算量，这将带来安全性隐患。 本文的第 3 章将根据实际调试好的软件，测试给出具体的时间消耗数据。例如，在一台配置为 AMD Athron2800+，外频 333MHZ，物理内存 512MB 的 PC上测试实现的软件，以 560bit 的 n 逐字节加密一个 1KB 大小的文件需要 55 秒。通常记录如银行帐号密码等重要数据的文 本文件大小不足百字节，加密只需要数秒钟。所以对于小型文件，进行较长密钥的 RSA 加密是完全可行的。 1.3.2 文件加密使用 RSA 的意义 如 1.3.1 节所述，小型文件加密可以使用 RSA。比如，因担心遗忘而用普通文本记录的银行帐号和密码、不应被陌生人知道的重要电话号码、几千字节大的重要小图片等。可行的方法未必是必要的，本小节讨论何种文件适合用非对称密钥加密，即 RSA 加密文件的意义所在。 对于前面叙述的带有重要信息的小型文本和二进制数据的维护，如果不加密，将无法放心的保存在计算机上，尤其是连网的或机房里的公共 计算机。如果借助功能强大的大型多用户数据保护程序维护几个小型文件，显得十分烦琐，好比杀鸡用牛刀。如果采用对称密钥加密，即加密解密的密钥相同，只适合部分情况。在某些情况下，使用对称密钥加密文件，交流使用不够方便。比如，张三由于某种原因，需要将自己的某个文件在公共计算机上留给李四，而不希望别人看到内容。如果采用对称密钥加密，张三和李四提前约好一个密码就可以。但是如果张三想要在同一台公共计算机上再留一个秘密文件给王五，而不希望别人看到，就要和王五另外约定一个密码。如果需要在这台公共计算机上留十个文件给不同的人 ，自己就要记和十个人约定好的密码，这样以来交流起来不够方便，因为对于张三，要自己维护太多的密钥。非对称密钥 (公开密钥方式 )恰好解决这样的问题。只要大家都在这台计算机或这台计算机可以访问到的地方，留下自己的公开密钥，一切就变的容易解决了。张三要留给李四的文件，就用李四的公开密钥加密，要留给王五的文件，就用王五的公开密钥加密。李四和王五只要把留给自己的文件用自己的私有密钥解密，就可以得到留给自己的文件了。显然，非对称密钥体制更适合多用户交流，而将这种加密方式直接应用于文件加密，使我们在公开场合的交流更加灵活方便 。 综上所述，使用前面叙述的方式加密文件有两点重要意义：应用非对称密钥加密任意文件，使非对称密钥的应用不仅仅局限于互联网络。非对称加密后的数据变换成文本，使得我们可以通过几乎任何方式安全传递任意文件，比如在只有 http 的环境使用 xml 方式。 nts 第 4 页 共 35 页 2 RSA文件加密软件的设计与实现 2.1 需求分析与总体设计 2.1.1 功能分析 经过 1.3.2 节的论述，我们可以将对软件的要求总结如下： 可以按要求的位数生成非对称密钥。 可以用指定密钥以 RSA 算法加密任意一个文件，加密生成的数据为纯文本。 可以 装载加密过的文件，并用指定的密钥解密还原出原文件。 提示信息完整、操作舒适、图形界面雅观 按上述描述，给出 Use Case 和 Statechart 如图 2-1。 图 2-1 本项目的 Use Case 和 Statechart 根据以上分析，一般来说，需要进行编码的程序有 RSA 密钥生成 RSA 加密解密 任意文件的读取 各环节必要的数据编码转换 图形操作界面。 2.1.2 工程方案选择 综合考虑复用性、可维护性和执行效率，较妥当的方法是分层设计。核心的RSA 算法由 C+类库实现，针对用户所在的操 作系统封装成本地化组件。其他各功能如文件操作、数据编码转换和图形界面等，由托管代码借助虚拟机平台标准库的功能快速开发实现 (本文针对选用 .Net 上的 C#论述，选用 java 由 JNI 或其他方式调用本地组件，设计模式上是完全类似的 )。这种开发方式，核心功能集中在最底层，在不断的封装中针对具体环境对组件功能不断扩充，任意一个层面的封装都可以被直接应用到其他项目，比如在 Web 使用以前为某窗体程序写的nts 第 5 页 共 35 页 组件、给嵌入式设备交叉编译算法库等。但是每一层都需要依赖底层的所有组件。图 2-2 形象的说明了分层设计给复用带来的好处。 图 2-2 综合考虑复用性、可维护性和执行效率的分层设计 选用这 种设计方案，上层使用 C#，底层算法使用 C+，可以由一个 Visual Studio 解决方案管理，给调试带来极大的方便。整个工程分四层，实现 RSA 加密算法的 C+核心类库、封装 C+核心类库的 DLL 组件、引用 DLL 的 .Net 类、实现 文件操作功能的 .Net 窗体应用程序。 2.2 节详细介绍各部分的设计与开发。 考虑到工作量，本软件加解密数据没有严格遵从 RSA 标准 PKCS #1，而是在满足设计要求的前提下，以一种尽可能简单的方式实现加密和解密。 2.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 来增加存储空间，但是nts 第 6 页 共 35 页 当 flex_unit 的实例中被存入比当前存储的数更小的数时，存储空间并不会自动紧缩，这是为了在运算的时候提高执行效率。结合指针 a，有两个重要的无符号整数来控制存储， unsigned z和 unsigned n， z是被分配空间的单元数，随数字变大不断增大，不会自己紧缩，而 n 是当前存储的大数所占的单元数，组成一个大数的各 unsigned 单元的存入和读出由 set、 get 方法完成，变量 n 是只读的。类型unsigned 在 32 位机是 32 位 的，所以对于 flex_unit 这个大数类来说，每个大数最大可以达到 2*32 个字节长，这已经超过了 32 位机通常的最大内存容量，所以是足够进行 RSA 所需要的各种运算的。图 2-3 形象的说明了大数存储类 flex_unit对大数的管理。 图 2-3 flex_unit 对大数的管理 在 flex_unit 的存储功能基础上，将其派生，得到 vlong_value，在vlong_value 中实现四则运算函数，并实现强制转换运算符 unsigned，以方便大数类型和普通 整数的互相赋值。当大数被强制转换为 unsigned 时，将取其最低四字节的值。四则运算实现的原理十分简单，都是按最基本的算术原理实现的，四则运算过程的本质就是按一定数制对数字的计算，比如相加，就是低位单元对齐，逐单元相加并进位，减法同理。而乘除法和取余也都是按照竖式运算的原理实现，并进行了必要的优化。虽然实现了四则运算函数，但是若是程序里的运算都要调用函数，显得烦琐而且看起来不美观，所以我们另写一个类 vlong，关联(Associate，即使用 vlong_value 类型的对象或其指针作为成员 )vlong_value，在 vlong 重载运算符。这样，当我们操作 vlong 大数对象的时候，就可以像使用一个简单类型一样使用各种运算符号了。之所以将 vlong_value 的指针作为成员而不是直接构造的对象，也是为了提高执行效率，因为大型对象的拷贝要消耗不少机器时间。 2. 大数幂模与乘模运算 Montgomery 幂模算法 在实现了 vlong 类型后，大数的存储和四则运算的功能都完成了。考虑到RSA 算法需要进行幂模运算，需要准备实现这些运算的方法。所以写一个 vlong*a unsigned 类型的指针 大数占 n 个单元 开辟了 z 个单元大的内存 内存空间 nts 第 7 页 共 35 页 的友元，完成幂模运算功能。幂模运算是 RSA 算法中比重最大的计 算，最直接地决定了 RSA 算法的性能，针对快速幂模运算这一课题，西方现代数学家提出了很多的解决方案。经查阅相关数学著作，发现通常都是依据乘模的性质nnbnanba m o d)m o d()m o d(m o d)( ，先将幂模运算化简为乘模运算。 通常的分解习惯是指数不断的对半分，如果指数是奇数，就先减去一变成偶数，然后再对半分，例如求 D= nCE mod ， E=15， 可分解为如下 6 个乘模运算。 nCnCCC m o dm o d 21 nCnCCC m o dm o d 312 nCnCCC m o dm o d 6223 nCnCCC m odm od 734 nCnCCC m o dm o d 14445 nCnCCC m o dm o d 1556 归纳分析以上方法，对于任意指数 E，可采用如图 2-4的算法流程计算 。 nts 第 8 页 共 35 页 图 2-4 幂模运算分解为乘模运算的一种流程 按照上述流程，列举两个简单的幂模运算实例来形象的说明这种方法。 求 17mod215 的值 开始 D = 1 P = 2 mod 17 = 2 E = 15 E 奇数 D = DP mod n = 2 P = PP mod n = 4 E= (E-1)/2 =7 E 奇数 D = DP mod n = 8 P = PP mod n = 16 E= (E-1)/2 =3 开始 D=1;P=C mod n E0? E 为奇数 ? nPDD mod)( E=E-1 nPPP mod)( E 为偶数 ? E=E/2 Yes No Result=D 结束 Yes Yes No No nts 第 9 页 共 35 页 E 奇数 D = DP mod n = 9 P = PP mod n = 1 E= (E-1)/2 =1 E 奇数 D = DP mod n = 9 P = PP mod n = 1 E= (E-1)/2 =0 最终 D = 9 即为所求。 求 13mod28 的值 开始 D = 1 P = 2 mod 13 = 2 E = 8 E 偶数 D = 1 P = PP mod n = 4 E = E/2 =4 E 偶数 D = 1 P = PP mod n = 3 E = E/2 =2 E 偶数 D = 1 P = PP mod n = 9 E = E/2 =1 E 奇数 D = DP mod n = 9 P = 不需要计算 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(蒙哥马利 )算法，算法的具体nts 第 10 页 共 35 页 推导证明需要颇多数论知识，不在本文的讨论范围内，如需了解可参见蒙哥马利的相关著作。下面简单描述 RSA 中常用的 Montgomery(蒙哥马利 )算法供参考理解源程 序。 选择与模数 n互素的基数 R=2k， n 满足 2k 1 n=n) x -= n; return x; exp(C,E,n) /蒙哥马利幂模 D=R-n; P=C*R mod n; i=0; nts 第 11 页 共 35 页 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. 寻找素数 Eratosthenes 筛选与 Fermat 素数测试 首先要说明的是，事实上，当今的计算机还不足以聪明到立刻计算生成一个很大的随机素数。一般来说，要得到 100%准确的大素数，都是通过查已经计算好的素 数表的方式。但是素数表的方式给 RSA 的安全性带来隐患，因为攻击者如果得到了密钥生成时所使用的素数表，攻破 RSA 加密的难度将会大大降低。本程序起初使用素数表的方式，后来考虑到安全性问题，生成密钥的方式改为随机计算生成。这样，短时间内如果要得到一个 100%准确的大素数是很困难的，只能以尽可能高的概率得到一个大素数。 经过 和 小节，所有的大数运算功能都准备完毕，在此基础上，本工程将寻找素数的功能置于类 Prime_factory_san 之中。外部只要调用本类实例的成员 vlong find_prime( vlong & start )就可以以大数 start 为起点，得到一个数，这个数是素数的概率很大。下面介绍寻找素数的原理。 首先在需要寻找素数的整数范围内对整数进行筛选，把所有确知为合数的整数排除出去。程序中构造了一个数组 b，大小为一轮素数搜索的范围，记搜索范围大小为 SS。 b0到 bSS分别对应大数 start 到 start+SS。 b中所有元素先初始化为 1，如果对应的大数确定为合数，就将 b中对应的元素置为 0。最后，只需对那些 b中为 1 的元素对应的大数进行比较确切的素数测试即可，只 要被测试的数是素数概率达到一定门限，就判这个数为素数。这样做既保证了这段程序可以在短时间内执行完，又保证了可以以比较高的准确度得到素数。 函数 find_prime 先把 b的所有元素赋值为 1，然后按参数 start 给标记数组b的各元素赋 0 值。下面描述标记数组 b的赋 0 值算法。首先，在类Prime_factory_san 被构造的时候，构造函数中从 2 开始搜寻一些小素数，记录在nts 第 12 页 共 35 页 数组 pl中，共记录 NP 个。这些小素数用来当作因子，他们的倍数将被从大素数搜索范围内剔除 (即把数组 b的对应元素标记为 0)，剔除的 程序代码如下。 for (i=0;inp;i+) unsigned p = pli; unsigned r = start % vlong(p); if (r) r = p - r; while ( r SS ) br = 0; r += p; 这里利用 start 对各小素数因子 p 求模的办法，得到当前 p 在素数搜索范围内的最小倍数在 b中的对应位置，将 其剔除后，不断后移 p 个位置，将这个小素数因子 p 在搜索范围内的所有倍数全部剔除，如图 2-5 所示。在完成对所有小素数因子的类似操作后，他们的倍数在搜索范围内的位置标记 br被全部标记为0。 实际上这就是 Eratosthenes 筛选法。 图 2-5 在素数搜索范围内剔除小素数因子 p 的倍数 接下来，对可能为素数的数 (即标记数组 b中值为 1 的元素对应的数 )进行素数测试。数论学家利用费马小定理研究出了多种素数测试方法，本程序使用一种最简单的方式，直接应用费马小定理。取一个与 p 互素的整数 A，对于大素数 p来说应该满 足 Ap-1mod p=1，但是我们把 p 代入一个大整数，满足这个关系的数不一定是素数。这时我们改变 A，进行多次测试，如果多次测试都通过，这个数是素数的概率就 比较大 。按这种原理，我们编写素数测试函数如下。 int is_probable_prime_san( const vlong &p ) const rep = 4; /测试次数 nts 第 13 页 共 35 页 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 算法加密解密是否还可以实现，是一个需要从数学角度论证的问题。因为得到素数的概率很高， 经过一整天 的生成密钥和加密操作，没有发现失败的密钥 ， 所以 本文暂没有对这个问题进行讨论。 实际得到素数的流程 ： (1) 先得到一个随机的大整数 N 当作寻找的起点 (2) 确定一个寻找范围的大小 SS，把 (N,N+SS)范围内的小素数倍数去掉，即前面叙述的古希腊某人发明的筛选法小素数因子从开始取，取几百个 (论文中将小素数因子个数记为 NP) (3) 对范围内没有去掉的数逐一进行素数测试，一个数如果通过测试次数达到一定标准，就判为素数 (4) 如果范围内没找到素数，就令 N=N+SS，回到 (2)继续寻找 用以上算法，直到以某成功概率得到素数为止 综上所述，总结素数寻找的流程，如图 2-6 所示。 nts 第 14 页 共 35 页 图 2-6 函数 find_prime 寻找素数的流程框图 得到了大素数，即 RSA 算法中的 p、 q，我们就可以计算出密钥，进行加密等操作了。 4. 二元一次不定方程 在 RSA 算法中，往往要在已知 A、 M 的情况下，求 B 的最小值，使得 (AB) mod M = 1。即相当于求解 B、 N 都是未知数的二元一次不定方程 AB-MN=1 的最小整数解。 而针对不定方程 ax-by=1 的最小整数解，古今中外都进行过详尽的研究 ，西方有著名的欧几里德算法，即一种辗转相除法，中国有秦九韶的“大衍求一术”。欧几里德算法是一种递归算法，较容易理解。下面举例说明用欧几里德算法求解二元一次不定方程的最小整数解。 给定不定方程 11x-49y=1，求最小的 x （ 1） 11 x - 49 y = 1 49 mod 11 = 5 （ 2） 11 x - 5 y = 1 11 mod 5 = 1 开始 按 start 参数初始化标记数组 bSS ; i=0 计数 iSS? bi=1? 判定为素数 ? start+=1;i+=1 结束 返回素数寻找结果 start Yes Yes Yes No No No nts 第 15 页 共 35 页 （ 3） x - 5 y = 1 5 mod 1 = 0 逆向代入： 令 y=0 代入（ 3）得 x=1 令 x=1 代入（ 2）得 y=2 令 y=2 代入 （ 1）得 x=9 x=9;y=2 即为所求。 程序中，全局函数 vlong modinv( const vlong &a, const vlong &m )用来完成这种算法。对应前面的叙述，参数 a对应 A，参数 m对应 M，函数返回值即为 B的最小值。 5. RSA 算法实现加密与解密 最后，类 RSA_san 基于前面的准备工作，实现 RSA 密钥生成和加解密的功能( 算 法 在 此 不 再 赘 述 ， RSA 算 法 协 议 见（ .au/rsa_alg.html)。为了方便阅读，整个类的源程序中，所使用的变量字母 均和 RSA 算法协议中一致。在类 RSA_san 的构造函数里，执行准备一对随机密钥的操作。之后可以直接使用类的其他成员进行 RSA 加解密操作。类中各成员频繁的用到字符串和 vlong 类型的转换，因为大数是用字符串置入的，而把大数读出，也是保存在字符指针指向的一段内存空间里，所以也是字符串。所以，需要实现一系列的编码转换函数，比如将 unsigned 指针指向的一段空间里保存的一个大数，表示成十六进制形式的字符串文本。编码转换通常是用 C风格的指针操作和 sprintf 函数来完成。 需要加密和解密的数据也是通过字符串参数置入 的。由于字符串的结尾字符“ 0”实际上也可能是需要加密的数据，所以置入的串长度并不能以“ 0”来决定，程序里引入一个 unsigned 类型的参数来决定置入的串长度，这样就解决了加密连 0数据时候被截断的问题。 因为是对文件加密的软件，需要加密的数据通常并不止几字节， 本软件默认的分块大小是 1 字节，即逐个字节作为参数，调用 C+核心模块中的方法。 加密解密流程均为标准 RSA 算法，具体过程 见下图： 生成密钥： nts 第 16 页 共 35 页 图 2-7 随机 生成密钥 相关代码： public static int GetRandomString()/实现随机字串的获得 Random rnd = new Random(); Byteb=new ByteSystem.Math.Max(RSAprimeplen1,RSAprimeplen2); s1=; s2=; for(int i=0;iRSAprimeplen1;i+) Byte tmp=System.Convert.ToByte(254.0*rnd.NextDouble(); if(tmp!=0)bi=tmp;else bi=1; s1=wujunjie_rsa.FromASCIIByteArray(b); for(int i=0;iRSAprimeplen2;i+) Byte tmp=System.Convert.ToByte(254.0*rnd.NextDouble(); if(tmp!=0)bi=tmp;else bi=1; s2=wujunjie_rsa.FromASCIIByteArray(b); return 1; nts 第 17 页 共 35 页 加密过程： 图 2-8 载入待加密的文本 图 2-9 准备加密文本 nts 第 18 页 共 35 页 图 2-10 加密后生成的文本 图 2-11 加密过程完成 相关 代码： private void menuItem10_Click(object sender, System.EventArgs e)/公钥加密 if(wujunjie_rsa.charlist.Count=0) emptymsg em=new emptymsg(this); em.Show(); return; nts 第 19 页 共 35 页 Stream myStream ; SaveFileDialog saveFileDialog1 = new SaveFileDialog(); saveFileDialog1.Filter = Hex text files (*.hextxt)|*.hextxt|All files (*.*)|*.* ; saveFileDialog1.FilterIndex = 1 ; saveFileDialog1.RestoreDirectory = true ; if(saveFileDialog1.ShowDialog() = DialogResult.OK) if(myStream=saveFileDialog1.OpenFile() != null) textBox1.Text+=rn正在对读入的文件进行处理，请稍候：） rn; System.Threading.Thread.Sleep(500); HighResolutionTimer timer = new HighResolutionTimer(); timer.Start(); using (StreamWriter sw = new StreamWriter(myStream) sw.WriteLine(# RSA.HexText); sw.WriteLine(#_); Byte b=new Bytewujunjie_rsa.RSAstep; wujunjie_rsa.result_hexstrings.Clear(); progressBar1.Minimum=0; progressBar1.Maximum=wujunjie_rsa.charlist.Count; for(int i=0;iwujunjie_rsa.charlist.Count;i+=System.Convert.ToInt32(wujunjie_rsa.RSAstep) for(int j=0;jwujunjie_rsa.RSAstep;j+) nts 第 20 页 共 35 页 bj=System.Convert.ToByte(wujunjie_rsa.charlisti+j); string s; wujunjie_rsa.RSA_san_en(b,wujunjie_rsa.RSAstep); s=wujunjie_rsa.get_result_hexstring(); wujunjie_rsa.result_hexstrings.Add(s); progressBar1.Value=i+1; for(int i=0;iwujunjie_rsa.result_hexstrings.Count;i+) string hs=System.Convert.ToString(wujunjie_rsa.result_hexstringsi); if(hs=null|hs=)sw.WriteLine(0); else sw.WriteLine(hs); sw.WriteLine(#_); sw.Write(# ); sw.WriteLine(DateTime.Now); wujunjie_rsa.result_hexstrings.Clear(); myStream.Close(); timer.Stop(); textBox1.Text+=rn 消 耗 时 间 ：+timer.ElapsedTime+rn; textBox1.Text+=rn 处理完成，新生成文件rn+saveFileDialog1.FileName+r
- 温馨提示:
1: 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
2: 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
3.本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
人人文库网所有资源均是用户自行上传分享，仅供网友学习交流，未经上传用户书面授权，请勿作他用。
|
2:不支持迅雷下载,请使用浏览器下载
3:不支持QQ浏览器下载,请用其他浏览器
4:下载后的文档和图纸-无水印
5:文档经过压缩，下载后原文更清晰
|
川公网安备: 51019002004831号