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

rsa公钥密码算法的一种快速实现—毕业设计论文内容摘要：

用来完成这种算法。 对应前面的叙述，参数 a 对应 A，函数返回值即为 X 的最小值。 ⑸ .文件操作 本工程的核心是利用蒙哥马利算法快速实现 RSA 加密，为了便于研究对字符串的加密过程，以及记录字 符串的密文样本，程序把字符串写入 TXT文档，再进行加密解密操作，这样就需要对文件进行操作，以二进制数据流对文件进行读出写入操作。 在这里使用一个 CFILE 类，使用 CFILE 类对文件进行简单的读写操作十分方便，本工程以一个 char 型的指针 data 来存放获得的字符串，用 DWORD型变量 flen 来存放 Cfile 类中成员函数 GetLength()获得的字符串长度，然后直接使用成员函数 read(),write()来进行文件的读写操作。 文件的读写操作代码见附。 ⑹ . 按常规 RSA 算法实现加密与解密 最后，类 CDemoDlg 基于前面的准备工作，实现 RSA 密钥生成和加解密的界面化功能。 （界面代码多由 C++编译器自动生成，在此不再赘述）在类 CDemoDlg的构造函数里，执行准备一对随机密钥的操作。 之后可以直接使用类的其他成员进行 RSA 加解密操作，也可以载入用户写入的密钥或再次随机生成密钥。 类中各成员频繁的用到字符串和 vlong 类型的转换，因为大数是用字符串置入的，而把大数读出，也是保存在字符指针指向的一段内存空间里，所以也是字符串。 所以，需要实现一系列的编码转换函数，比如将 unsigned 指针指向的一段空间里保存的一个大数，表 示成十六进制形式的字符串文本。 编码转换通常是用 C风格的指针操作。 由于是对文件进行加密，所以涉及对文件内容进行读写操作，这里使用到了CFile 类。 需要加密和解密的数据是通过字符串参数置入的。 由于字符串的结尾字符“ \0”实际上也可能是需要加密的数据，所以置入的串长度并不能以“ \0”来决定，程序里引入一个 unsigned 类型的参数来决定置入的串长度，通过 Cfile 类中的 Getlength()函数获得文件中字符串的长度，这样就解决了加密连 \0数据时候被截断的问题。 加密解密流程均为标准 RSA 算法，具体过程和使用方 法参见源程序和接口文档。 ⑺ . 核心类库综述 综上几小节所述，实现 RSA 加密算法的 C++核心类库由两个类组成，类名和对应的功能描述总结如表 21 和图 22 所示。 表 21： RSA 加密算法的 C++类库中的类 CBigInt 主要包含大数四则运算，素数生成，检测，密钥生成，存储， RSA 核心算法等。 CDemoDlg 主要包含界面功能的实现，按钮触发时间等。 图 22：主要函数成员 编写测试各项性能需要的计时程序 由于对几个字符的字符串进行 RSA 加密，所用时间只需 10几毫秒，一般的程序计时函数无法达到要求测试结果很可能是 0，于是在这里定义了 2个 long型变量 t1,t2 来分别存储加密函数运行前后 GetTickCount()函数获得的系统时间 ,然后将两个值相减获得消耗时间，这样做还会有较大误差，于是再次进行了 改进，通过一个简单的 for循环让程序运行 1000 次 ，然后将 t2t1 的值除 1000，以获得较为精确的时间。 附录中给出了这段操作的源代码。 测试数据与分析改进 密钥生成测试 生成密钥运算最费时的工作是寻找素数。 如 小节所叙述，寻找素数是一项颇为复杂的工作，其速度可能受以下影响： RSA加密需要的 n的位数（寻找素数的整数起点大小 bits），素数通过小素数表进行检查，通过拉宾米勒算法测试素数。 其中最具影响力的因素显然是 RSA 加密需要的 n的位数。 以下对 N的位数对生成密钥时间影响进行测试，暂且忽略操作系统调度对测试的影响。 测试 PC 配置为 CPU 奔腾 4 845 UltraAD 芯片组，下文测试中，未说明 PC 配置的也都在同一 PC 完成，不再重复。 密钥生成测试数据见表 31。 表 31： RSA加密模数 n 与密钥生成耗时的关系 加密位数 n (bit) 第一次 （毫秒） 第二次（毫秒） 第三次（毫秒） 第四次（毫秒） 第五次（毫秒） 平均值（毫秒） 128 22 20 21 21 21 21 256 126 125 118 131 130 126 512 844 875 812 935 770 847 1024 7030 3205 4785 3926 6399 5069 （红色为行中最大，兰色为行中最小） 观察表上的统计数据，很容易发现随着加密位数的增加，密钥生成需要的时间显 著增加。 在测试范围内，随着加密位数增大，每一行中的最大最小值差距也呈粗略的增大趋势。 也就是说对于长密钥来说， RSA 随机生成密钥消耗时间的可能范围较大。 这是因为对于大整数来说，可能出现在较长一段区间中没有素数的情况。 此表仅能从实验的角度直观理解，具体到一次密钥生成的运算，所需要的时间是很不确定的，比如，一次 512 位的密钥生成，需要的时间完全可能比一次256 位的密钥生成时间短，由于素数分布规律非常奥妙，加上测试运算需要的时间颇长，这里很难给出对于一个具体位数的密钥生成所需时间的统计模型。 加解密测 试 加密解密测试是本工程的核心，重在反映 RSA算法对小型文本文件加密的可行性，以及蒙哥马利算法对 RSA 算法的提速效果。 这里给出几组不同角度进行测试的数据。 ⑴ .用相同的密钥对不同长度的文件公钥加密，私钥解密，各自消耗的时间与待加密字符串大小的关系 随即生成两组密钥，一组 n 长 512bit，一组 n 长 1024bit。 密钥具体数据见附录。 分别对一组不同大小的文件进行公钥加密。 统计消耗时间情况如表 32： 表 32：加密消耗时间测试 n 位数 文件大小 20Byte（毫秒） 40Byte 60Byte 80Byte 100Byte 512bit公钥加密 119 123 125 128 138 512bit私钥解密 330 453 473 503 508 1024bit公钥加密 442 464 469 473 479 1024bit私钥解密 681 721 721 741 743 从表 3可以看出，使用同一公开密钥加密不同大小的文件，消耗时间随着文件大小的增加线性的增加，和 小节分析的完全一致。 对于较大的文件，加密位数对时间的影响十分明显。 对于 100 字节的文件来说， 1024bit 的公钥加密比 512bit 的耗时多 倍左右； 1024bit 的私钥解密比 512bit 的耗时多 以上。 对于一定的加密位数来说，私钥解密所需要的时间比公钥加密需要的时间长。 对于一定大小的文件，使用 512bit 的密钥，私有密钥解密需要的时间是公开密钥加密需要时间的 3倍左右；而如果使用 1024bit 的密钥，私有密钥解密需要的时间是公开密钥加密需要时间的 倍以上。 可见，本软件密钥长度越长，私有密钥解密与公开密钥加密的耗时比越大，这和其他软件是一致的。 因为根据PCKS 1 的 RSA 的应用建议， e是比较短的，而 d和 n的长度差不多，这就 使得求与 d、 n有关的幂模运算量比与 e、 n有关的幂模运算量大很多，而且随着 n的增加，两组幂模运算的运算量差距也迅速加大。 ⑵ .利用蒙哥马利算法进行幂模运算改进，加密时间与改进前 RSA加密时间的对比测试 蒙哥马利幂模运算是对 RSA 算法优化的最常见手段，是提高加密速度，实现相对快速的 RSA 加密的关键。 现测试蒙哥马利算法改进过的加密算法与普通 RSA加密算法，使用相同密钥对，对相同文件加密所用时间。 如表 33： 表 33：蒙哥马利改进测试 文件大小（ B） 20 40 60 80 100 512位密钥 Montgomery所用时间（毫秒） 35 35 34 37 42 普通 RSA 所用时间（毫秒） 119 123 128 133 133 1024为密钥 Montgomery所用时间（毫秒） 70 73 89 101 105 普通 RSA 所用时间（毫秒） 442 461 463 469 467 通过上表可以得出，使用蒙哥马利幂模运算确实一定程度上提高了 RSA 加密速度，使用 512 位密钥加密文件蒙哥马利算法改进后的加密所需时间为为改进的算法所用时间的三分之一左右，而 1024 位密钥加密文件时，仅为四分之一左 右，蒙哥马利幂模运算大大提高了加密效率，当文件大小更大，密钥长度更长的情况下，蒙哥马利幂模运算的优势将更能体现。 性能分析与改进优化 经过一系列的 RSA 密钥生成、文件输入输出和蒙哥马利加密解密测试，做简要的性能分析如下。 ① 软件消耗时间的运算，大部分集中在 C++核心类库，即 RSA 相关的各种运算。 其中，幂模运算和寻找素数对时间的消耗最大，在核心优化时应优先考虑。 ② 文件输入输出消耗时间其次，因为磁盘读写速度要远远低于内存读写速度。 所以，应该将频繁的读写操作尽量集中到内存，然后一次性写入磁盘。 ③蒙 哥马利算法对 RSA 加密效率的提高非常明显，对于优化幂模运算起到了非常重要的工作。 针对以上三点，软件应进行一系列改进和优化。 主要有以下几方面。 ① 在要对文件进行加密解密的时候，先将文件按一定的数据结构读入内存，然后进行加密或解密操作。 运算数据都读取自内存。 ② 在对加密或解密完成的数据进行写出的时候，都是将其直接写到指定好的文件，即直接写入磁盘。 这是因为，考虑到中途可能因为意外断电等原因引起操作中断，为了保护已经花费时间运算完成的数据，将其直接写入磁盘。 ③ 在安全性上做进一步优化，例如在寻找素数时，素数 测试使用更安全的算法，例如，本系统采用的是查已经计算好的素数表的方式得到准确的素数，但是素数表的方式给 RSA 的安全性带来隐患，因为攻击者如果得到了密钥生成时所使用的素数表，攻破 RSA 加密的难度将会大大降低。 可以考虑使用几组小素数，这些小素数用来当作因子，他们的倍数将被从大素数搜索范围内剔除。 ④ 对 C++核心类库进行重点优化，使其运算效率尽可能提高。 其中包括对各类之间的组织细节、各程序模块的具体编写等，进行全面细致的检查和修改，例如将大数据类型以对象指针传递而不拷贝，将简单的 for 循环展开等。 由于开发时间 仓促等因素，在书写本文时，软件并未完成全面细致的优化。 结束语 RSA 应用于文件加密适合交流管理小型文件，将任意文件以非对称密钥加密成文本可以对其更方便的交流和管理，有广阔的开发前景。 而要实现较为快速的RSA 文件加密系统，对幂模运算的优化是核心，只要充分利用蒙哥马利幂模运算原理，对 RSA 加密算法进行适当的改进， RSA文件加密将通过瓶颈，在小型文件加密上有着巨大的发展空间。 参考文献 [1]罗斌等 . Visual c++ 编程技巧精选 500例 [M] .北京：中国水利水电出版社 ,2020 年 1月 ,193205 [2]张耀仁 . C++程序设计彻底研究 [M].北京：中国铁道出版社 2020年 7 月 280284 [3]郑莉，董渊 . C++语言程序设计 [M].北京：清华大学出版社第 2版 2020年 7 月 [4]丁有和 郑进 周怡军 . Visual c++使用教程 .北京：电子工业出版社 2020年 1 月 [5]于秋生，魏俊鹏 .C++Builder 6 实用编程 100例 [M].北京：中国铁道出版社 2020年 7 月 [6]王许书 ,王新辉 ,夏宏 . Montgomery 方法及其在伪随机数发生器中的应用 [J].计算机应用与软件 2020年 6 月 2324 [7]陈逢林 ,苏厚勤 .Montgomery算法的改进及其在 RSA 中的运用 [J].计算机应用与软件 2020年4 月 2526 [8]CFile 操作详解 [EB]。 致 谢 本论文的工作是 2020 年 2 月至 2020 年 6 月在成都信息工程学院网络工程 系完成的。 文中除了特别加以标注地方外，不包含他人已经发表或撰写过的 研究成果，也不包含为获得成都信息工程学院或其他教学机构的学位或证书而使用过的材料。 除非另有说明，本文的工作是原始性工作。 本文是在吴震老师的热情关心和指导下完成的，他渊博的知识和严谨的治学作风使我受益匪浅，对顺利完成本课题起到了极大的作用。 在此向他表示我最衷心的感谢。 在论文完成过程中，本人还得到了各论坛程序爱好者的热心帮助，本人向他们表示深深的谢意。 最后向在百忙之中评审本文的各位专家、老师表示衷心的感谢。 作者简介： 姓 名： 时超 性别： 男 出生年月： 1984 年 9 月 25 日 民族： 汉 Email: 附录 ： long t1=GetTickCount()。 for(。