RSA公钥密码算法的快速实现

论文摘要

自20世纪90年代以来,随着计算机互联网络的飞速发展,网络技术的应用几乎已经深入到人类社会生活的一切领域。在当前的网络环境下,敏感信息的保护成为一个很重要的问题,一个安全、健壮的信息系统离不开各种信息安全技术的支持。计算机网络中所采用的核心安全技术中有许多来源于现代密码学,这一技术的研究和发展是计算机技术发展的重要保障。R.L.Rivest,A.Shamir和L.Adleman于1977年提出的RSA公钥密码体制的安全性和性能不断得到人们的肯定,成为最流行的密码体制。但是大密钥加解密存在着运算速度缓慢、效率低下的问题,这成为制约它进一步推广的瓶颈。因此,找到一个快速的RSA的实现算法也是当前密码学的一个研究方向。本文主要针对RSA公钥密码体制中大整数模指数算法进行了深入的研究,将该问题分解为对乘法算法、模乘法算法、模指数算法的研究,并使用流行的面向对象软件开发工具Visual C++进行了相应的软件实现。本文总共分为七章,第一章系统地介绍了RSA算法,描述了RSA加密算法和签名算法,讨论了参数选取、安全性等问题。第二章整体介绍了RSA算法快速实现所用到的具体算法和大整数运算实现的方法,并对大整数的表示、存取、运算作了细致的阐述。第三章详细讨论了多精度乘法算法,对传统乘法、Karatsuba算法、Comba算法作了对比,并通过编程实现得到了实验数据。第四章给出了几种Montgomery模乘法算法,并对其进行分析和比较,其中,CIOS算法是最理想的软件实现算法,而FIPS算法在硬件实现上有着广泛的应用。第五章描述了指数运算用到的平方-乘算法,给出了二元指数运算和滑动窗口算法。第六章介绍了计算机软件实现中的“内联汇编”技术,即将汇编代码写入C语言程序中,既体现出C语言在程序开发上的便利,又能够发挥汇编语言速度快的特点。第七章从整体和局部两方面阐述了几种程序优化的方法,并给出了一段具体优化的程序实例。

论文目录

• 摘要
• Abstract
• 第一章 RSA公钥密码算法
• §1.1 RSA算法的数学基础
• 1.1.1 单向函数
• 1.1.2 欧拉定理及相关概念
• §1.2 RSA算法
• §1.3 RSA算法的安全性
• 1.3.1 对RSA的分解模数n攻击
• 1.3.2 对RSA的选择密文攻击
• 1.3.3 RSA的小指数攻击
• §1.4 小结
• 第二章 RSA算法与大整数运算的实现
• §2.1 参数选取
• 2.1.1 Miller-Rabin概率素判定算法
• 2.1.2 模逆算法
• §2.2 模指数运算
• §2.3 大整数运算的实现
• 2.3.1 大整数的进制表示
• 2.3.2 大整数的存储与读取
• 2.3.3 大整数的运算
• 第三章 乘法算法
• §3.1 传统乘法
• §3.2 Karatsuba算法
• §3.3 Comba算法
• 第四章 Montgomery模乘法
• §4.1 Montgomery模约减原理
• §4.2 SOS模乘法算法
• §4.3 CIOS模乘法算法
• §4.4 FIPS模乘法算法
• 第五章 指数算法
• §5.1 平方-乘算法
• §5.2 滑动窗口指数运算
• §5.3 指数算法与Montgomery模乘法的结合
• 第六章 内联汇编
• §6.1 内联汇编简介
• §6.2 内联汇编语法
• §6.3 内联汇编中使用C/C++元素
• 6.3.1 可用的C/C++元素
• 6.3.2 操作符使用
• 6.3.3 C/C++符号使用
• 6.3.4 转跳
• 第七章 程序优化与编程心得
• §7.1 整体优化
• §7.2 局部优化
• 7.2.1 汇编语言的使用
• 7.2.2 内联汇编优化
• 7.2.3 循环与函数的优化
• 7.2.4 分支结构的优化
• §7.3 空间优化
• §7.4 程序优化示例
• 结束语
• 参考文献
• 致谢
• 学位论文评阅及答辩情况表