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

摘? 要 RSA作为最重要的公开密钥算法，在各领域的应用数不胜数。然而，RSA算法加密速度很慢，难以像其他加密算法那样得到更广泛的应用。幂模运算是RSA的速度瓶颈，在全过程中都有使用。蒙哥马利算法对幂模运算的改进大大的提高了RSA的加解密效率。本课题将RSA公钥加密算法用蒙哥马利算法实现。通过对幂模运算的改进，简化，提高RSA加密效率。本文主要论述RSA基本原理以及相关函数类的设计与实现，使用Microsoft Visual C++ 6.0 操作平台，实现RSA加密算法，界面友善，操作方便。 关键词:? RSA；RSA算法；蒙哥马利算法；加密；解密； 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发现了一种只要乘法和数的位移就可以实现模乘运算的灵巧算法，这就是著名的蒙哥马利模乘算法。