RSA加密算法

1. 密钥的产生
① 选两个保密的大素数p和q。
② 计算n=p×q，φ(n)=(p-1)(q-1),其中φ(n)是n的欧拉函数值。
③ 选一整数e，满足1<e<φ(n)，且gcd(φ(n),e)=1。
④ 计算d，满足d·e≡1 mod φ(n),即d是e在模φ(n)下的乘法逆元，因e与φ(n)互素，由模运算可知，它的乘法逆元一定存在。
⑤ 以{e,n}为公开钥,{d,p,q}为秘密钥。

2. 加密
加密时首先将明文比特串分组，使得每个分组对应的十进制数小于n，即分组长度小于log2n。然后对每个明文分组m，作加密运算： c≡m^e mod n

3. 解密
对密文分组的解密运算为：
           m≡c^d mod n

例 选p=7，q=17。
解 n=p×q=119，
φ(n)=(p-1)(q-1)=96。
取e=5，满足1<e<φ(n)，且gcd(φ(n),e)=1。
确定满足d·e=1 mod 96且小于96的d，
因为77×5=385=4×96+1，所以d为77，
因此公开钥为{5，119}，
秘密钥为{77，119}。

设明文m=19，则由加密过程得密文为
c≡19^5mod119≡2476099 mod 119≡66

解密为 ：66^77mod 119≡19

RSA的安全性是基于分解大整数的困难性假定，之所以为假定是因为至今还未能证明分解大整数就是NP问题，也许有尚未发现的多项式时间分解算法。
如果RSA的模数n被成功地分解为p×q，则立即获得φ(n)=(p-1)(q-1)，从而能够确定e模φ(n)的乘法逆元d，即d≡e^(-1) mod φ(n)，因此攻击成功。

随着人类计算能力的不断提高，原来被认为是不可能分解的大数已被成功分解。例如RSA-129（即n为129位十进制数，大约428个比特）已在网络上通过分布式计算历时8个月于1994年4月被成功分解，RSA-130 已于1996年4月被成功分解。

因此在使用RSA算法时对其密钥的选取要特别注意其大小。估计在未来一段比较长的时期，密钥长度介于1024比特至2048比特之间的RSA是安全的。

为保证算法的安全性，还对p和q提出以下要求：
（1） p,q的长度应相差不大，处于10^75到10^100的数量级
（2） p-1和q-1都应有大素因子
（3）gcd{p-1,q-1}应该尽可能小

对RSA的攻击
RSA存在以下两种攻击，并不是因为算法本身存在缺陷，而是由于参数选择不当造成的。
1. 共模攻击
在实现RSA时，为方便起见，可能给每一用户相同的模数n，虽然加解密密钥不同，然而这样做是不行的。
设两个用户的公开钥分别为e1和e2，且e1和e2互素（一般情况都成立），
明文消息是m，
密文分别是
c1≡me1(mod n)
c2≡me2(mod n)
敌手截获c1和c2后，可如下恢复m。
用推广的Euclid算法求出满足
re1+se2=1
的两个整数r和s，其中一个为负，设为r。再次用推广的Euclid算法求出c^(-1)(1)，由此得(c^(-1)(1))-rc^s(2)≡m(mod n)。

2. 低指数攻击
假定将RSA算法同时用于多个用户（为讨论方便，以下假定3个），然而每个用户的加密指数（即公开钥）都很小。设3个用户的模数分别为ni(i=1,2,3)，当i≠j时，gcd(ni,nj)=1，否则通过gcd(ni,nj)有可能得出ni和nj的分解。设明文消息是m，密文分别是
c1≡m^3(mod n1)；
c2≡m^3(mod n2)；
c3≡m^3(mod n3)；
由中国剩余定理可求出m^3(mod n1n2n3)。由于m^3<n1n2n3，可直接由m3开立方根得到m。