RSA算法介绍

RSA算法是第一个能同时用于加密和数字签名的算法，也易于理解和操作。 RSA也是被研究得最广泛的公钥算法，从提出到现在已近二十年，经历了各种攻击的考验，逐渐为人们接受，普遍认为是目前最优秀的公钥方案之一。

　　RSA的安全性依赖于大数的因子分解，但并没有从理论上证明破译RSA的难度与大数分解难度等价，即RSA的重大缺陷是无法从理论上把握它的保密性能如何，而且密码学界多数人士倾向于因子分解不是NPC问题。

　　RSA的缺点主要有：

(一) 产生密钥很麻烦，受到素数产生技术的限制，因而难以做到一次一密。

(二) 分组长度太大，为保证安全性，n 至少也要 600 bits以上，使运算代价很高，尤其是速度较慢，较对称密码算法慢几个数量级；且随着大数分解技术的发展，这个长度还在增加，不利于数据格式的标准化。

但RSA的缺点对软件注册码而言都不是问题，因为软件注册机可以选择一个已知的素数来生成公钥和私钥。至于运算代价很高的问题而言也不是问题，因为注册凭证信息量是很小的。

RSA理论的数学基础是数论中的欧拉定理，基本原理如下：

(一) 取两个相近的大素数p、q；

(二) 计算n=p*q，z=(p-1)*(q-1)；

(三) 任取一个与z互素的整数e；

(四) 计算满足e*d=1 mod z 的整数d；

(五) 将明文m分成字符块s加密，每个块s小于n。

(六) 加密：c=m^e mod n；解密：m=c^d mod n

(七)  (n，e)和(n，d)分别称为“公开密钥”和“秘密密钥”。根据Euler定理可得：m=c^d mod n=(m^e mod n)^d mod n=m；

举例说明：

(一) 取两个素数p=11和q=13

(二) 计算n=p*q=11*13=143，z=(p-1)*(q-1)=(11-1)*(13-1)=120；

(三) 选取与z=120互素的整数e，如e=7，现可计算出满足7*d=1 mod 120的整数d=103，即：7*103=1 mod 120、7*103/120余1，

(四) 整理如下：p=11、q=13、n=143、e=7、d=103

(五) 得出公钥 (n，e)=(143，7)和私钥 (n，d)=(143，103)

以数据加密为例：

(一) 甲向乙发送机密数据信息m=85，并已知乙的公钥(n，e)=(143，7)，于是可计算得出：c=m^e mod n=85^7 mod 143=123，甲将c发送至乙；

(二) 乙利用私钥(n,d)=(143，103)对c进行计算：m=c^d mod n=123^103 mod 143=85，现乙已经得到甲向其要发送的机密数据信息，而甲向乙发送信息时，甲所拥有的仅仅是乙的公钥；

由此可知，由(n，e)加密的数据只能用(n，d)解密，反之亦然，从而证明RSA加密算法是可逆的，但RSA的可逆是基于特定的数值对（即称为公钥和私钥）。

另外，RSA算法的安全性依赖于大数分解，公钥和私钥都是两个大素数(大于100个十进制位）的函数。从理论上讲，从一个密钥和密文推断出明文的难度等同于分解两个大素数的积，因此，只要选择足够大的素数、保证公钥或私钥的安全，则采用常规的破解难度是非常大的，基本上可以认定为不可能破解，由此可以认定RSA是安全的。

本文来自CSDN博客，转载请标明出处：http://blog.csdn.net/scollins/archive/2010/06/25/5694306.aspx