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语言在程序开发上的便利，又能够发挥汇编语言速度快的特点。 第七章从整体和局部两方面阐述了几种程序优化的方法，并给出了一段具体优化的程序实例。

目录

文摘

英文文摘

声明

第一章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程序优化示例

结束语

参考文献

致谢