RSA公钥密码算法的一种快速实现—毕业设计论文.doc

毕毕 业业 设设 计计 论论 文文 RSARSA 公钥密码算法的一种快速实现公钥密码算法的一种快速实现 论文作者姓名 论文作者姓名 申请学位专业 申请学位专业 申请学位类别 申请学位类别 指指导导教教师师姓姓名名 职职称称 论文提交日期 论文提交日期 RSARSA 公钥密码算法的一种快速实现公钥密码算法的一种快速实现 摘摘 要要 RSA 作为最重要的公开密钥算法 在各领域的应用数不胜数 然而 RSA 算 法加密速度很慢 难以像其他加密算法那样得到更广泛的应用 幂模运算是 RSA 的速度瓶颈 在全过程中都有使用 蒙哥马利算法对幂模运算的改进大大 的提高了 RSA 的加解密效率 本课题将 RSA 公钥加密算法用蒙哥马利算法实现 通过对幂模运算的改进 简化 提高 RSA 加密效率 本文主要论述 RSA 基本原 理以及相关函数类的设计与实现 使用 Microsoft Visual C 6 0 操作平台 实现 RSA 加密算法 界面友善 操作方便 关键词关键词 RSA RSA 算法 蒙哥马利算法 加密 解密 A Rapid Way to Implement RSA Public Key Cryptography Algorithm Abstract The RSA encryption speed is very slow and to apply it is difficult So it constrained the development of the RSA algorithm Modular multiplication is the speed bottleneck of algorithm in the whole using process The advancing of Montgomery algorithm for the computation power module greatly improves the RSA encryption efficiency The task implement RSA public key encryption algorithm with Montgomery algorithm With the improvements of modular multiplication it enhances the efficiency of RSA encryption This paper mainly discusses the basic tenets of RSA and the design and implementation of the correlation function The development platform for RSA encryption algorithm is Microsoft Visual C 6 0 Key words RSA RSA algorithm Montgomery algorithm Encryption Decryption 目目 录录 论文总页数 22 页 前言 1 1 RSA 应用现状及蒙哥马利模幂运算 2 1 1 RSA 算法介绍与应用现状 2 1 2 RSA 算法加密的安全分析 3 1 3 利用蒙哥马利算法对 RSA 幂模运算进行改进 3 2 RSA 公钥密码加密软件的设计与实现 4 2 1 需求分析与总体设计 4 2 1 1 功能分析 4 2 1 2 工程方案选择 5 2 2 各部分的设计与开发 6 2 2 1 实现 RSA 加密算法的 C 核心类库 6 3 软件整体测试与分析改进 13 3 1 编写测试各项性能需要的计时程序 13 3 2 测试数据与分析改进 13 3 2 1 密钥生成测试 13 3 2 1 加解密测试 14 3 3 性能分析与改进优化 16 参考文献 17 谢 辞 18 附 录 19 致 谢 21 声 明 22 前言前言 RSA 公钥加密算法是第一个既能用于数据加密也能用于数字签名的算法 它易于理解和操作 也十分流行 算法的名字以发明者的姓氏首字母命名 Ron Rivest Adi Shamir 和 Leonard Adleman 虽然自 1978 年提出以来 RSA 的安 全性一直未能得到理论上的证明 但它经历了各种攻击 至今 2006 年 未被 完全攻破 随着越来越多的商业应用和标准化工作 RSA 已经成为最具代表性 的公钥加密技术 VISA MasterCard IBM Microsoft 等公司协力制定的安全 电子交易标准 Secure Electronic Transactions SET 就采用了标准 RSA 算 法 这使得 RSA 在人们的生活中几乎无处不在 网上交易加密连接 网上银行 身份验证 各种信用卡使用的数字证书 智能移动电话和存储卡的验证功能芯 片等 大多数使用 RSA 技术 当今公钥加密更广泛应用于互联网身份认证 本课题将公钥加密算法 RSA 进行蒙哥马利改进 通过对幂模运算的改进 简化 提高 RSA 加密效率 幂模运算是 RSA 的速度瓶颈 在全过程中都有使用 蒙哥马利算法是其中 一种 影响模乘运算速度关键在于模运算 模运算其实是除法运算 除运算相 对与加减乘运算要费时的多 因此 如果在模乘运算中不用除法或尽量少用除 法将大大提高 RSA 处理的速度 1985 年 Peter Montgomery 发现了一种只要乘 法和数的位移就可以实现模乘运算的灵巧算法 这就是著名的蒙哥马利模乘算 法 1 1 RSARSA 应用现状及蒙哥马利模幂运算应用现状及蒙哥马利模幂运算 1 11 1 RSARSA 算法介绍与应用现状算法介绍与应用现状 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 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 算法的各种数据 加密规范 这些 API 内部支持的算法不仅仅只有 RSA 但是 RSA 是数字签名和 证书中最常用的 用户程序可以直接使用 java 标准库中提供的 API 进行数字签 名和证书的各种操作 1 21 2 RSARSA 算法加密的安全分析算法加密的安全分析 RSA 的安全性依赖于大数分解 但是否等同于大数分解一直未能得到理论 上的证明 因为没有证明破解 RSA 就一定需要作大数分解 假设存在一种无须 分解大数的算法 那它肯定可以修改成为大数分解算法 目前 RSA 的一些变 种算法已被证明等价于大数分解 不管怎样 分解 n 是最显然的攻击方法 现 在 人们已能分解多个十进制位的大素数 因此 模数 n 必须选大一些 因具 体适用情况而定 1 31 3 利用蒙哥马利算法对利用蒙哥马利算法对 RSARSA 幂模运算进行改进幂模运算进行改进 由于进行的都是大数计算 使得 RSA 最快的情况也比 DES 慢上百倍 无论 是软件还是硬件实现 速度一直是 RSA 的缺陷 一般来说只用于少量数据加密 幂模运算是 RSA 的速度瓶颈 在全过程中都有使用 蒙哥马利算法是其中 一种 影响模乘运算速度关键在于模运算 模运算其实是除法运算 除运算相 对与加减乘运算要费时的多 因此 如果在模乘运算中不用除法或尽量少用除 法将大大提高 RSA 处理的速度 1985 年 Peter Montegomery 发现了一种只要 乘法和数的位移就可以实现模乘运算的灵巧算法 这就是著名的蒙哥马利模乘 算法 蒙哥马利算法被认为是计算大数模乘的最快算法 RSA 加解密运算都是模 幂运算 而模幂运算 x modn 又可以转化为平均 3e 2 次的模乘运算 所以提高 RSA 加解密速度的关键在于提高模乘运算的速度 影响模乘运算速度关键在于 模运算 模运算其实是除法运算 除法运算相对于加减乘运算要费时得多 因此如 果在模乘运算中不用除法或尽量少用除法将大大提高处理的速度 调用方式 N mon A B 返回值 X N A MOD B 1 X 1 2 若 A 为奇数 则 A A 1 X X N MOD B 3 若 A 为偶数 则 A A 2 N N N MOD B 4 重复 2 3 对 A 进行降阶 直至 A 0 5 此时的 X 即为所求结果 2 2 RSARSA 公钥密码加密软件的设计与实现公钥密码加密软件的设计与实现 2 12 1 需求分析与总体设计需求分析与总体设计 2 1 12 1 1 功能分析功能分析 经过 1 2 2 节的论述 可以将对软件的要求总结如下 软件一 可以按要求的位数 支持 128 位 256 位 512 位 1024 位 生成非对称 密钥 也可以用户输入密钥 可以用指定密钥以 RSA 算法加密简单文本文件 加密生成的数据为纯文 本 可以装载加密过的文件 并用指定的密钥解密还原出原文件 提示信息完整 操作舒适 图形界面雅观 可以对加密过程进行精确计时 反映在界面处 软件二 可以用指定密钥以包含蒙哥马利幂模运算的 RSA 算法加密简单文本文件 加密生成的数据为纯文本 可以对加密过程进行精确计时 反映在界面处 按上述描述 给出 Use Case 和 Statechart 如图 1 1 图 1 1 操作流程 根据以上分析 一般来说 需要进行编码的程序有 RSA 密钥生成 RSA 加密解密 文件的读取和保存操作 各环节必要 的数据编码转换 图形操作界面 程序计时单元 蒙哥马理算法实现 2 1 22 1 2 工程方案选择工程方案选择 1 利用 BORLAND C BUILDER 平台 C BUILDER 界面制作功能强大 操作方便 但由于现在大多数公开 C RSA 算法代码都是用 VC 编写 在调用函数上有诸多麻烦 牵涉到很多动态联 结 调试比较困难 2 利用 MICROSOFT VISUAL C 平台 从最初的 Visual C 1 0 到最近的 Visual C NET Visual C 经过近 十年的发展 现已成为 Windows 操作系统环境下最主要 最权威的软件开发工 具 内部集成众多算法实现函数 可方便的调用 给编程及调试带来极大的方 便 最终本工程选定以 VC 做为平台 进行本软件的开发工作 2 22 2 各部分的设计与开发各部分的设计与开发 2 2 12 2 1 实现实现 RSARSA 加密算法的加密算法的 C C 核心类库核心类库 大数四则运算与运算符重载大数四则运算与运算符重载 根据 RSA 算法的要求 为了实现大数的各种复杂运算 需要首先实现大数 存储和基本四则运算的功能 当今开源的大数运算 C 类有很多 多用于数学 分析 天文计算等 本文选用了一个流行的大数类型 并针对 RSA 算法和本项 目的具体需要对其进行了扩充和改进 下面简单介绍四则运算的实现原理 大数的四则运算由 CBIGINT 类实现 类中申明了以下若干函数 基本操作与运算 Mov 赋值运算 可赋值为大数或普通整数 可重载为运算符 Cmp 比较运算 可重载为运算符 a mod n a mod n mod n 实际上 连 mod n 这样的运算最后也被转化到 mod r 这样模运 算就方便多了 蒙哥马利算法求乘方的模 调用方式 N Mon A B 返回值 X N A MOD B 1 X 1 2 若 A 为奇数 则 A A 1 X X N MOD B 3 若 A 为偶数 则 A A 2 N N N MOD B 4 重复 2 3 对 A 进行降阶 直至 A 0 5 此时的 X 即为所求结果 CBigInt CBigInt RsaTrans CBigInt X Mov 1 Y Mov this Z Mov A if A Mod 2 1 Z Mov Z Sub 1 A A 1 X X N MOD B X Mov X Mul Y X Mov X Mod B else if A Mod 2 0 Z Mov Z Div 2 A A 2 N N N MOD B Y Mov Y Mul Y Y Mov Y Mod B return X 寻找素数与素数测试寻找素数与素数测试 首先要说明的是 事实上 当今的计算机还不足以聪明到立刻计算生成一 个很大的随机素数 一般来说 要得到 100 准确的大素数 都是通过查已经计 算好的素数表的方式 经过 2 2 1 1 和 2 2 1 2 小节 所有的大数运算功能都准备完毕 在此基 础上 本工程将寻找素数的功能置于类 CBigint 之中 外部只要调用本类实例 的成员函数 void GetPrime int bits 就可以以 bits 为起点 得到一个数 这个数是素数的概率很大 下面介绍寻找素数的原理 本工程在素数生成时 通过数组 m ulValue i 来存储生成的素数 调用 C 已有的函数 Rand 产生随即数 再通过素数表排除非素数 最终得到待测 试之素数 代码如下 void CBigInt GetPrime int bits unsigned i m nLength bits begin for i 0 i0 i m ulValue i m ulValue i 1 if m ulValue i 1 m ulValue 0 m ulValue 0 1 m ulValue 0 for i 0 i 550 i if Mod PrimeTable i 0 goto begin CBigInt S A I K K Mov this K m ulValue 0 for i 0 i 5 i A Mov rand rand S Mov K Div 2 I Mov A RsaTrans S this if I m nLength 1 I m ulValue 0 1 接下来 对可能为素数的数用拉宾米勒算法进行测试 测试通过 程序就 判定这个数为找到的素数 将找到的素数返回给上层程序使用 拉宾米勒算法 是公开的测试素数算法 直接通过函数的调用实现 这里就不详细介绍 综上所述 总结素数寻找的流程 如图 2 1 所示 图 2 1 寻找素数流程 得到了大素数 即 RSA 算法中的 p q 就可以计算出密钥 进行加密等操 作了 二元一次不定方程二元一次不定方程 开始 利用 Bits 初始化 m ulValue i m ulValue i rand 0 x10000 rand Mod PrimeTable i 0 为真 Y O N K Mov this K m ulValue 0 K m ulValue 0 Rab 测试素数 N Y 完成 结束 开始 在 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 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 即为所求 程序中 函数 Euc CBigInt用来完成这种算法 对应前面的叙述 参 数 a 对应 A 函数返回值即为 X 的最小值 文件操作文件操作 本工程的核心是利用蒙哥马利算法快速实现 RSA 加密 为了便于研究对字 符串的加密过程 以及记录字符串的密文样本 程序把字符串写入 TXT 文档 再进行加密解密操作 这样就需要对文件进行操作 以二进制数据流对文件进 行读出写入操作 在这里使用一个 CFILE 类 使用 CFILE 类对文件进行简单的 读写操作十分方便 本工程以一个 char 型的指针 data 来存放获得的字符串 用 DWORD 型变量 flen 来存放 Cfile 类中成员函数 GetLength 获得的字符串长 度 然后直接使用成员函数 read write 来进行文件的读写操作 文件的读写操作代码见附 按常规按常规 RSARSA 算法实现加密与解密算法实现加密与解密 最后 类 CDemoDlg 基于前面的准备工作 实现 RSA 密钥生成和加解密的界 面化功能 界面代码多由 C 编译器自动生成 在此不再赘述 在类 CDemoDlg 的构造函数里 执行准备一对随机密钥的操作 之后可以直接使用类 的其他成员进行 RSA 加解密操作 也可以载入用户写入的密钥或再次随机生成 密钥 类中各成员频繁的用到字符串和 vlong 类型的转换 因为大数是用字符 串置入的 而把大数读出 也是保存在字符指针指向的一段内存空间里 所以 也是字符串 所以 需要实现一系列的编码转换函数 比如将 unsigned 指针指 向的一段空间里保存的一个大数 表示成十六进制形式的字符串文本 编码转 换通常是用 C 风格的指针操作 由于是对文件进行加密 所以涉及对文件内容进行读写操作 这里使用到 了 CFile 类 需要加密和解密的数据是通过字符串参数置入的 由于字符串的 结尾字符 0 实际上也可能是需要加密的数据 所以置入的串长度并不能以 0 来决定 程序里引入一个 unsigned 类型的参数来决定置入的串长度 通 过 Cfile 类中的 Getlength 函数获得文件中字符串的长度 这样就解决了加 密连 0 数据时候被截断的问题 加密解密流程均为标准 RSA 算法 具体过程和使用方法参见源程序和接口 文档 核心类库综述核心类库综述 综上几小节所述 实现 RSA 加密算法的 C 核心类库由两个类组成 类名和对 应的功能描述总结如表 2 1 和图 2 2 所示 表 2 1 RSA 加密算法的 C 类库中的类 CBigInt主要包含大数四则运算 素数生成 检测 密钥生成 存储 RSA 核心算法等 CDemoDlg主要包含界面功能的实现 按钮触发时间等 图 2 2 主要函数成员 3 3 软件整体测试与分析改进软件整体测试与分析改进 3 13 1 编写测试各项性能需要的计时编写测试各项性能需要的计时程序程序 由于对几个字符的字符串进行 RSA 加密 所用时间只需 10 几毫秒 一般的 程序计时函数无法达到要求测试结果很可能是 0 于是在这里定义了 2 个 long 型变量 t1 t2 来分别存储加密函数运行前后 GetTickCount 函数获得的系统时 间 然后将两个值相减获得消耗时间 这样做还会有较大误差 于是再次进行了 改进 通过一个简单的 for 循环让程序运行 1000 次 然后将 t2 t1 的值除 1000 以获得较为精确的时间 附录中给出了这段操作的源代码 3 23 2 测试数据与分析改进测试数据与分析改进 3 2 13 2 1 密钥生成测试密钥生成测试 生成密钥运算最费时的工作是寻找素数 如 2 2 1 3 小节所叙述 寻找素 数是一项颇为复杂的工作 其速度可能受以下影响 RSA 加密需要的 n 的位数 寻找素数的整数起点大小 bits 素数通过小素数表进行检查 通过拉宾米 勒算法测试素数 其中最具影响力的因素显然是 RSA 加密需要的 n 的位数 以 下对 N 的位数对生成密钥时间影响进行测试 暂且忽略操作系统调度对测试的 影响 测试 PC 配置为 CPU 奔腾 4 2 4GHZ 外频 100MHZ 物理内存 1024MDDR MSI6398 主板 845 Ultra AD 芯片组 下文测试中 未说明 PC 配置的 也都在同一 PC 完成 不再重复 密钥生成测试数据见表 3 1 表 3 1 RSA 加密模数 n 与密钥生成耗时的关系 加密位数 n bit 第一次 毫 秒 第二次 毫 秒 第三次 毫 秒 第四次 毫 秒 第五次 毫 秒 平均值 毫 秒 128222021212121 256126125118131130126 512844875812935770847 1024703032054785392663995069 红色为行中最大 兰色为行中最小 观察表上的统计数据 很容易发现随着加密位数的增加 密钥生成需要的 时间显著增加 在测试范围内 随着加密位数增大 每一行中的最大最小值差 距也呈粗略的增大趋势 也就是说对于长密钥来说 RSA 随机生成密钥消耗时 间的可能范围较大 这是因为对于大整数来说 可能出现在较长一段区间中没 有素数的情况 此表仅能从实验的角度直观理解 具体到一次密钥生成的运算 所需要的 时间是很不确定的 比如 一次 512 位的密钥生成 需要的时间完全可能比一 次 256 位的密钥生成时间短 由于素数分布规律非常奥妙 加上测试运算需要 的时间颇长 这里很难给出对于一个具体位数的密钥生成所需时间的统计模型 3 2 13 2 1 加解密测试加解密测试 加密解密测试是本工程的核心 重在反映 RSA 算法对小型文本文件加密的 可行性 以及蒙哥马利算法对 RSA 算法的提速效果 这里给出几组不同角度进 行测试的数据 用相同的密钥对不同长度的文件公钥加密 私钥解密 各自消耗的时间用相同的密钥对不同长度的文件公钥加密 私钥解密 各自消耗的时间 与待加密字符串大小的关系与待加密字符串大小的关系 随即生成两组密钥 一组 n 长 512bit 一组 n 长 1024bit 密钥具体数据 见附录 分别对一组不同大小的文件进行公钥加密 统计消耗时间情况如表 3 2 表 3 2 加密消耗时间测试 n 位数 文件 大小 20Byte 毫秒 40Byte60Byte80Byte100Byte 512bit 公钥 加密 119123125128138 512bit 私钥 解密 330453473503508 1024bit 公钥 加密 442464469473479 1024bit 私钥 解密 681721721741743 从表 3 可以看出 使用同一公开密钥加密不同大小的文件 消耗时间随着 文件大小的增加线性的增加 和 1 2 1 小节分析的完全一致 对于较大的文件 加密位数对时间的影响十分明显 对于 100 字节的文件来说 1024bit 的公钥 加密比 512bit 的耗时多 2 5 倍左右 1024bit 的私钥解密比 512bit 的耗时多 1 5 倍以上 对于一定的加密位数来说 私钥解密所需要的时间比公钥加密需要的 时间长 对于一定大小的文件 使用 512bit 的密钥 私有密钥解密需要的时间 是公开密钥加密需要时间的 3 倍左右 而如果使用 1024bit 的密钥 私有密钥 解密需要的时间是公开密钥加密需要时间的 1 5 倍以上 可见 本软件密钥长 度越长 私有密钥解密与公开密钥加密的耗时比越大 这和其他软件是一致的 因为根据 PCKS 1 的 RSA 的应用建议 e 是比较短的 而 d 和 n 的长度差不多 这就使得求与 d n 有关的幂模运算量比与 e n 有关的幂模运算量大很多 而 且随着 n 的增加 两组幂模运算的运算量差距也迅速加大 利用蒙哥马利算法进行幂模运算改进 加密时间与改进前利用蒙哥马利算法进行幂模运算改进 加密时间与改进前 RSARSA 加密时间的加密时间的 对比测试对比测试 蒙哥马利幂模运算是对 RSA 算法优化的最常见手段 是提高加密速度 实 现相对快速的 RSA 加密的关键 现测试蒙哥马利算法改进过的加密算法与普通 RSA 加密算法 使用相同密钥对 对相同文件加密所用时间 如表 3 3 表 3 3 蒙哥马利改进测试 文件大小 B 20406080100 Montgomery 所用时间 毫 秒 3535343742 512 位密 钥 普通 RSA 所用 时间 毫秒 119123 128133133 Montgomery 所用时间 毫 秒 707389101105 1024 为 密钥 普通 RSA 所用 时间 毫秒 442 461463469467 通过上表可以得出 使用蒙哥马利幂模运算确实一定程度上提高了 RSA 加 密速度 使用 512 位密钥加密文件蒙哥马利算法改进后的加密所需时间为为改 进的算法所用时间的三分之一左右 而 1024 位密钥加密文件时 仅为四分之一 左右 蒙哥马利幂模运算大大提高了加密效率 当文件大小更大 密钥长度更 长的情况下 蒙哥马利幂模运算的优势将更能体现 3 33 3 性能分析与改进优化性能分析与改进优化 经过一系列的 RSA 密钥生成 文件输入输出和蒙哥马利加密解密测试 做 简要的性能分析如下 软件消耗时间的运算 大部分集中在 C 核心类库 即 RSA 相关的各种 运算 其中 幂模运算和寻找素数对时间的消耗最大 在核心优化时应优先考 虑 文件输入输出消耗时间其次 因为磁盘读写速度要远远低于内存读写速 度 所以 应该将频繁的读写操作尽量集中到内存 然后一次性写入磁盘 蒙哥马利算法对 RSA 加密效率的提高非常明显 对于优化幂模运算起到 了非常重要的工作 针对以上三点 软件应进行一系列改进和优化 主要有以下几方面 在要对文件进行加密解密的时候 先将文件按一定的数据结构读入内存 然后进行加密或解密操作 运算数据都读取自内存 在对加密或解密完成的数据进行写出的时候 都是将其直接写到指定好 的文件 即直接写入磁盘 这是因为 考虑到中途可能因为意外断电等原因引 起操作中断 为了保护已经花费时间运算完成的数据 将其直接写入磁盘 在安全性上做进一步优化 例如在寻找素数时 素数测试使用更安全的 算法 例如 本系统采用的是查已经计算好的素数表的方式得到准确的素数 但是素数表的方式给 RSA 的安全性带来隐患 因为攻击者如果得到了密钥生成 时所使用的素数表 攻破 RSA 加密的难度将会大大降低 可以考虑使用几组小 素数 这些小素数用来当作因子 他们的倍数将被从大素数搜索范围内剔除 对 C 核心类库进行重点优化 使其运算效率尽可能提高 其中包括对 各类之间的组织细节 各程序模块的具体编写等 进行全面细致的检查和修改 例如将大数据类型以对象指针传递而不拷贝 将简单的 for 循环展开等 由于开发时间仓促等因素 在书写本文时 软件并未完成全面细致的优化 结束语结束语 RSA 应用于文件加密适合交流管理小型文件 将任意文件以非对称密钥加 密成文本可以对其更方便的交流和管理 有广阔的开发前景 而要实现较为快 速的 RSA 文件加密系统 对幂模运算的优化是核心 只要充分利用蒙哥马利幂 模运算原理 对 RSA 加密算法进行适当的改进 RSA 文件加密将通过瓶颈 在 小型文件加密上有着巨大的发展空间 参考文献参考文献 1 罗斌等 Visual c 编程技巧精选 500 例 M 北京 中国水利水电出版社 2005 年 1 月 193 205 2 张耀仁 C 程序设计彻底研究 M 北京 中国铁道出版社 2006 年 7 月 280 284 3 郑莉 董渊 C 语言程序设计 M 北京 清华大学出版社第 2 版 2001 年 7 月 4 丁有和 郑进 周怡军 Visual c 使用教程 北京 电子工业出版社 2007 年 1 月 5 于秋生 魏俊鹏 C Builder 6 实用编程 100 例 M 北京 中国铁道出版社 2004 年 7 月 6 王许书 王新辉 夏宏 Montgomery 方法及其在伪随机数发生器中的应用 J 计算机应用与 软件 2006 年 6 月 23 24 7 陈逢林 苏厚勤 Montgomery 算法的改进及其在 RSA 中的运用 J 计算机应用与软件 2006 年 4 月 25 26 8 CFile 操作详解 EB 2006 7 27 致致 谢谢 本论文的工作是 2006 年 2 月至 2007 年 6 月在成都信息工程学院网络工程 系完成的 文中除了特别加以标注地方外 不包含他人已经发表或撰写过的研 究成果 也不包含为获得成都信息工程学院或其他教学机构的学位或证书而使 用过的材料 除非另有说明 本文的工作是原始性工作 本文是在吴震老师的热情关心和指导下完成的 他渊博的知识和严谨的治 学作风使我受益匪浅 对顺利完成本课题起到了极大的作用 在此向他表示我 最衷心的感谢 在论文完成过程中 本人还得到了各论坛程序爱好者的热心帮助 本人向 他们表示深深的谢意 最后向在百忙之中评审本文的各位专家 老师表示衷心的感谢 作者简介 姓 名 时超 性别 男 出生年月 1984 年 9 月 25 日 民族 汉 E mail justsoso11 附录附录 1 1 对加密解密过程计时的代码 对加密解密过程计时的代码 long t1 GetTickCount for int j 1 jOpen m ED CFile shareDenyNone CFile modeReadWrite 打 开文件 flen file GetLength data new char int flen strset data 0 将缓冲区初始化为全 0 file SeekToBegin file Read data flen 写 int len1 m OUT GetLength UpdateData FALSE file SeekToBegin file Write m OUT len1 关闭文件 File close 3 加密解密测试时使用的两组密钥 512 位 3C54793AA7186DEFFD54A9352E929F5A6A78034F2133D367965467322585D2B2537DE D86DAB9A6A0E162A2B80A377CCDE790F221D15C917F9F821BDCBF71D045 34F7A974006EA75F1418F77274D0504E2EB9ED95D4BDCEB6DCBA7FDBFC2BB11EC3315 F0177DD500463E2F44535324BDF3CC25053E5BF38F74570A9A8A2CBF4A5 1024 位 B3839FCFB21E7B916B62C20B79075C549BD558465F66C9BC5682DCFDE7818C1504D0D 14AECEF1B1254C54CE36D7737EB34248E5F62B0FC4E34DA7C54AAC50CECBC9F3BF5C8 C40503E4DD67A6744E0E022B995128D3F8EB9DBCB9E8EF1A5CF48B9D3D601D2585030 7BFE0AA83E6CDBB4FA765BB0FE7880908A3B48A2956F12FA5 25DF04DE0A53C7F9DBCFCFE41FBA5FCE31BA068F821CEB3E6279E52963A7BEE7C8464 D81230F2684ED815A41389CC81D44B8D99861F7B8A2BF1FC0CF13DFD263DBF146D654 370D17869452FD010E2A63F21EBF7C5FCC8F77DD2807977F1B6ACF447A7277B76D138 19494EB6A892B0F7745D6215E5F08AB9D114749276AF51D19 4 RSA4 RSA 算法可行性的证明 求证 若 p q 是相异素数 e d 1 mod p 1 q 1 a 是任意一个正整数 mod mod qpbcqpab de 则有 c a mod p q 证明 d e 1 mod p 1 q 1 d e k p 1 q 1 1 其中 k 是整数 在 mod 中是 preserve 乘法的 x y mod z and u v mod z x u y v mod z mod 1 1 1 qpaaabc qpkedded 首先 素数 p q 要么能整除 a 要么与 a 互素 1 如果 a 不是 p 的倍数 也不是 q 的倍数时 则 pa p mod1 1 费马小定理 pa qpk mod1 1 1 根据质数算术 基本定理 a 与素数 p 互素 则 am也与 p 互素 m 是整数 qa q mod1 1 费马小定理 qa qpk mod1 1 1 p q 均能整除 1 1 qpk a 1 p q 1 1 qpk a 1 即 1 1 qpk a 1 mod p q c 1 1 1 qpk a a mod p q 2 如果 a 是 p 的倍数 但不是 q 的倍数时 则 qa q mod1 1 费马小定理 1 1 qpk a 1 mod q c 1 1 1 qpk a a mod q q c a p a c 1 1 1 qpk a 0 mod p p c a p q c a c a mod p q 3 如果 a 是 q 的倍数 但不是 p 的倍数时 证明同 2 理显然 4 如果 a 同时是 p 和 q 的倍数时 则 p q a c 1 1 1 qpk a 0 mod p q p q c a c a mod p q 证毕 费马小定理叙述 e 是任一素数 n 是任一整数 则 e n n mod e 即如 果 n 和 e 互质 则 1 e n 1 mod e 运用群论知识可以证出费马小定理 命题 1 1 说明 a 经过编码为 b 再经过解码为 c 时 a c mod n n p q 但在做编码解码时 由于限制 0 a n 0 c n 此时显然 a c 所以这个过程能做到编码解码的功能 致致 谢谢 本文是在吴震老师的热情关心和指导下完成的 他渊博的知识和严谨的治 学作风使我受益匪浅 对顺利完成本课题起到了极大的作用 在此向他表示我 最衷心的感谢 在论文完成过程中 本人还得到了张富贵老师和刘敏同学的热心帮助 本 人向他们表示深深的谢意 最后向在百忙之中评审本文的各位专家 老师表示衷心的感谢 作者简介 姓 名 时超 性别 男 出生年月 1983 04 01 民族 汉 E mail 声声 明明 本论文的工作是 2007 年 2 月至 2007 年 6 月在成都信息工程学院网络工程 系完成的 文中除了特别加以标注地方外 不包含他人已经发表或撰写过的研 究成果 也不包含为获得成都信息工程学院或其他教学机构的学位或证书而使 用过的材料 除非另有说明 本文的工作是原始性工作 关于学位论文使用权和研究成果知识产权的说明 本人完全了解成都信息工程学院有关保管使用学位论文的规定 其中包括 1 学校有权保管并向有关部门递交学位论文的原件与复印件 2 学校可以采用影印 缩印或其他复制方式保存学位论文 3 学校可以学术交流为目的复制 赠送和交换学位论文 4 学校可允许学位论文被查阅或借阅 5 学校可以公布学位论文的全部或部分内容 保密学位论文在解密后遵守 此规定 除非另有科研合同和其他法律文书的制约 本论文的科研成果属于成都信 息工程学院 特此声明 作者签名 年 月 日 t was not until mid afternoon that the inspector ambled up on his pony My father pulled himself together and went out to receive him the effort to be even formally polite nearly strangled him Even then the inspector was not brisk He dismounted in a leisurely fashion and strolled into the house chatting about the weather Father red in the face handed him over to Mary who took him along to mother s room Then followed the worst wait of all Mary said afterwards that he hummed and ha d for an unconscionable time while he examined the baby in minutest detail At last however he emerged with an expressionless face In the little used sitting room he sat down at the table and fussed for a while about getting a good point on his quill At last he took a form from his pouch and in a slow deliberate hand wrote that he officially found the child to be a true female human being free from any detectable form of deviation He regarded that thoughtfully for some moments as though not perfectly satisfied He let his hand hesitate before he actually dated and signed it then he sanded it carefully and handed it to my enraged father still with a faint air of uncertainty He had of course no real doubt in his mind or he would have called for another opinion my father was perfectly well aware of that too At last Petra s existence could be admitted I was formally told that I had a new sister and presently I was taken to see her where she lay in a crib beside my mother s bed She looked so pink and wrinkled to me that I did not see how the inspector could have been quite sure about her However there was nothing obviously wrong with her so she had got her certificate Nobody could blame the inspector for that she did appear to be as normal as a new born baby ever looks While we were taking turns to look at her somebody started to ring the stable bell in the customary way Everyone on the farm stopped work and very soon we were all assembled in the kitchen for prayers of thanksgiving Two or it may have been three days after Petra was born I happened upon a piece of my family s history that I would prefer not to have known I was sitting quietly in the room next to my parents bedroom where my mother still lay in bed It was a matter of chance and strategy too It was the latest place that I had found to stay hidden awhile after the midday meal until the coast was clear and I could slip away without being given an afternoon job so far nobody had thought of l