RSA公钥密码算法的一种快速实现
摘 要
RSA作为最重要的公开密钥算法，在各领域的应用数不胜数。然而，RSA算法加密速度很慢，难以像其他加密算法那样得到更广泛的应用。幂模运算是RSA的速度瓶颈，在全过程中都有使用。蒙哥马利算法对幂模运算的改进大大的提高了RSA的加解密效率。本课题将RSA公钥加密算法用蒙哥马利算法实现。通过对幂模运算的改进，简化，提高RSA加密效率。本文主要论述RSA基本原理以及相关函数类的设计与实现，使用Microsoft Visual C++ 6.0 操作平台，实现RSA加密算法，界面友善，操作方便。http://www.16sheji8.cn/
关键词: 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;
目 录http://www.16sheji8.cn/
论文总页数：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
附 录 19http://www.16sheji8.cn/
致 谢 21
声 明 22
前言
RSA公钥加密算法是第一个既能用于数据加密也能用于数字签名的算法。它易于理解和操作，也十分流行。算法的名字以发明者的姓氏首字母命名：Ron Rivest, Adi Shamir 和Leonard Adleman。虽然自1978年提出以来，RSA的安全性一直未能得到理论上的证明，但它经历了各种攻击，至今（2006年）未被完全攻破。随着越来越多的商业应用和标准化工作，RSA已经成为最具代表性的公钥加密技术。VISA、MasterCard、IBM、Microsoft等公司协力制定的安全电子交易标准（Secure Electronic Transactions，SET）就采用了标准RSA算法，这使得RSA在人们的生活中几乎无处不在。网上交易加密连接、网上银行身份验证、各种信用卡使用的数字证书、智能移动电话和存储卡的验证功能芯片等，大多数使用RSA技术。http://www.16sheji8.cn/
当今公钥加密更广泛应用于互联网身份认证，本课题将公钥加密算法RSA进行蒙哥马利改进。通过对幂模运算的改进，简化，提高RSA加密效率。
幂模运算是RSA的速度瓶颈，在全过程中都有使用。蒙哥马利算法是其中一种。影响模乘运算速度关键在于模运算，模运算其实是除法运算，除运算相对与加减乘运算要费时的多。因此，如果在模乘运算中不用除法或尽量少用除法将大大提高RSA处理的速度。1985年，Peter Montgomery发现了一种只要乘法和数的位移就可以实现模乘运算的灵巧算法，这就是著名的蒙哥马利模乘算法。
1 RSA应用现状及蒙哥马利模幂运算
1.1 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)作为私有密钥．
<加密解密>http://www.16sheji8.cn/
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进行数字签名和证书的各种操作。http://www.16sheji8.cn/
1.2 RSA算法加密的安全分析
RSA的安全性依赖于大数分解，但是否等同于大数分解一直未能得到理论上的证明，因为没有证明破解 RSA就一定需要作大数分解。假设存在一种无须分解大数的算法，那它肯定可以修改成为大数分解算法。目前， RSA 的一些变种算法已被证明等价于大数分解。不管怎样，分解n是最显然的攻击方法。现在，人们已能分解多个十进制位的大素数。因此，模数n 必须选大一些，因具体适用情况而定。
1.3 利用蒙哥马利算法对RSA幂模运算进行改进
由于进行的都是大数计算，使得RSA最快的情况也比DES慢上百倍，无论是软件还是硬件实现。速度一直是RSA的缺陷。一般来说只用于少量数据加密。
幂模运算是RSA的速度瓶颈，在全过程中都有使用。蒙哥马利算法是其中一种。影响模乘运算速度关键在于模运算，模运算其实是除法运算，除运算相对与加减乘运算要费时的多。因此，如果在模乘运算中不用除法或尽量少用除法将大大提高RSA处理的速度。1985年，Peter Montegomery发现了一种只要乘法和数的位移就可以实现模乘运算的灵巧算法，这就是著名的蒙哥马利模乘算法。
蒙哥马利算法被认为是计算大数模乘的最快算法。RSA加解密运算都是模幂运算，而模幂运算xªmodn又可以转化为平均(3e)/2次的模乘运算,所以提高RSA加解密速度的关键在于提高模乘运算的速度，影响模乘运算速度关键在于模运算,模运算其实是除法运算,除法运算相对于加减乘运算要费时得多"因此如果在模乘运算中不用除法或尽量少用除法将大大提高处理的速度。
调用方式：N.mon(A,B)
返回值：X=N^A MOD Bhttp://www.16sheji8.cn/
（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即为所求结果
