简介对RSA算法的各种攻击

姓名：朱睿琦

学号：15180288015

参考：http://www.xzbu.com/8/view-6540335.htm

           http://www.doc88.com/p-982460038116.html

           http://www.cnblogs.com/7hat/p/3407897.html

【嵌牛导读】：RSA算法是迄今在网络安全领域应用最为广泛的非对称密码算法，其安全性是基于大整数的因数分解难问题的，算法的攻破一般被认为等同于大数分解。另一方面，对RSA算法的攻击可针对设计与应用该算法的系统的某些缺陷。本文研究了对RSA算法的攻击的主要方法，并对攻击防御提出了建议。

【嵌牛鼻子】：网络安全，RSA算法，算法攻击

【嵌牛提问】：RSA算法的加密原理是什么？为什么在现阶段RSA算法被认为是安全的？

【嵌牛正文】：

1>RSA算法基本原理：

1.1公钥与私钥的生成：

(1)随机挑选两个大质数 p 和 q，构造N = p*q；

(2)计算欧拉函数φ(N) = (p-1) * (q-1)；

(3)随机挑选e，使得gcd(e,φ(N)) = 1，即 e 与φ(N) 互素；

(4)计算d，使得 e*d ≡ 1 (modφ(N))，即d 是e 的乘法逆元。

此时，公钥为（e, N），私钥为（d, N），公钥公开，私钥自己保管。

1.2加密信息：

(1)待加密信息（明文）为 M，M < N；（因为要做模运算，若M大于N，则后面的运算不会成立，因此当信息比N要大时，应该分块加密）

(2)密文C = Memod N

(3)解密Cdmod N = (Me)dmod N = Md*emod N ；

要理解为什么能解密？要用到欧拉定理（其实是费马小定理的推广）aφ(n)≡ 1 (mod n)，再推广：aφ(n)*k≡ 1 (mod n)，得：aφ(n)*k+1≡ a (mod n)

注意到 e*d ≡ 1 mod φ(N)，即：e*d = 1 + k*φ(N)。

因此，Md*emod N = M1 + k*φ(N)mod N = M

简单来说，别人用我的公钥加密信息发给我，然后我用私钥解密。

1.3数字签名：

(1)密文C = Mdmod N

(2)解密M = Cemod N = (Md)emod N = Md*emod N  = M ；（原理同上）

简单来说，我用自己的密钥加密签名，别人用我的公钥解密可以看到这是我的签名。注意，这个不具有隐私性，即任何人都可以解密此签名。

算法的安全性：基于大整数N难以分解出p和q，构造φ(N)；或由N直接构造φ(N)同样难。

2>RSA算法的攻击方法:

RSA 算法的安全性依赖于大整数分解的困难性。 最直接的攻击方法是分解 n 得到 p,q，进而基于 e 计算 d，随着计算机运算能力的不断提高，通过二次筛法已能分解 180 多位的十进制素数，增加 p,q 的长度已成为许多安全应用系统的加密要求。 另一方面，利用系统设计和实现的缺陷， 人们也提出了一些基于非因子分解方式破解 RSA 算法的方案。 目前，对 RSA 算法的攻击主要有以下几种：

2.1 对模数 n 的因子分解

分解模数 n 是最直接的攻击方法，也是最困难的方法。 攻击者可以获得公钥 e 和模数 n；如果 n=pq 被成功分解，则攻击者可以计算出φ(n)=(p-1)(q-1)，进而从 ed≡1modφ(n)解得私钥 d。

2.2 对 RSA 的公共模数攻击

若一个多用户系统中只采用一个模数 n，不同的用户拥有不同的e 和 d，系统将是危险的。 在此系统中，若有同一消息用不同的公钥加密，这些公钥共模且互质，那该信息无需私钥就可解密。 举例来说，设P 为信息明文，两个加密公钥为 e1和 e2，公共模数是 n，有：C1=Pe1modn 和 C2=Pe2modn。如果攻击者获得 n、e1、e2、C1和 C2，就能得到 P。 因为 e1和 e2互质，故用欧几里德(Euclid)算法能找到 r 和 s，满足：r*e1+s*e2=1，设 r 为负数，则(C1-1)-r*C2s=(Pe1modn)r*(Pe2modn)s=(Pr*e1+s*e2)modn=Pmodn，如果 P

2.3 对 RSA 的小指数攻击

如果 RSA 系统的公钥 e 选取较小的值， 可以使加密和验证签名的速度有所提高。 但如果 e 取得太小，就容易受到小指数攻击。 例如，有同一系统的三个用户，分别使用不同的模数 n1，n2，n3，但都选取 e=3；另有一用户欲将同一明文消息 P 发送给以上三人，使用各人的公钥加密得：C1=P3(modn1)，C2=P3(modn2)和 C3=P3(modn3)一般地，n1，n2，n3互素（否则，会比较容易求出公因子，降低安全性），根据中国剩余定理，可由 C1，C2，C3计算：C=P3(modn1n2n3)如果 P

2.4 对 RSA 的选择密文攻击

选择密文攻击指的是攻击者能选择不同的密文，并拥有对应的明文，由此推出想要的信息。一般攻击者会伪装若干信息，让拥有私钥的用户签名，由此获得有用的明文-密文对，然后推算想要的信息。

例 1 攻击者想要伪造用户 u 对消息 x 的签名。 他可以先计算 x1,x2，使得 x≡(x1x2)(modn)，并骗取 u 对 x1和 x2的签名 s1=x1d(modn)和 s2=x2d(modn)， 则对 x 的签名可计算如：s=xd(modn)=(((x1x2)(modn))d)(modn)=((x1dmodn)(x2dmodn))modn=(s1s2)(modn)。

例 2 攻击者获得了用户 u 使用公钥 e 加密的密文 y=xe(modn)，想要得到 x。 他可以先计算 y′=re(modn)（r 是小于 n 的随机数），y″=(yy′)(modn)，然后骗取 u 对 y″的签名 s=y″d(modn)。 则通过计算(r-1s)(modn)可以恢复出 x，这是因为：(r-1s)(modn)=((y′dmodn)-1y″d)(modn)=(y′-dy″d)(modn)=(y′-dydy′d)(modn)=yd(modn)=x。

3对RSA算法的攻击的防御建议对于以上几种攻击，防御方案各不相同。攻击 1 源于 RSA 算法的数学安全基础， 增加初始化参数长度是有效的提高安全度的方法。而攻击 2 和攻击 3 源于应用 RSA 算法的系统的设计缺陷， 改进方法为：1）在多用户系统中必须采用多个模数；2）避免为了图求方便而使用取值太小的公钥 e。

攻击 4 最为复杂，从算法上无法解决这一问题，主要对应策略有两条：1）私钥持有者不对不信任的信息签名；2）签名信息时，先使用Hash 函数生成的摘要，再对摘要签名，避免直接对信息的签名。

以上防御方案并不能解决所有的 RSA 安全问题， 我们建议利用RSA 算法的系统仔细审核安全需求 ，投入使用先进行测试 ，并对系统安全做一个全面的审核。 必须对各种安全策略及程序进行合理优化，才能尽可能地降低风险，RSA 算法才能发挥最大的效用。