【密码学】RSA的攻与防_1.0

1 直接分解N

1.1 介绍

虽然RSA的安全性依赖于大数的因子分解，但并没有从理论上证明破译RSA的难度与大数分解难度等价。如果随着数学研究的发展，发现“大数分解”问题能够解决，则RSA系统将不再安全。随着计算机处理能力的不断提升，包括量子计算机的加持，特别是通过Internet使大量计算机协同工作，解决一个具体的“大数分解”问题需要的时间越来越短。

1.2 防御措施

为了应对直接分解N的安全问题，可以选取较高的公钥模长来提升系统安全强度。理论上来讲N越大，安全强度越高，算法运算速度越慢。另外p和q需要足够大，使N的分解更加困难；其次p和q之差也尽量大，否则容易根据N猜测p和q的规模。

2 低指数攻击

2.1 介绍

加密指数指的是e，当e很小，可直接破解。例如e=3时，

2.2 防御措施

加密指数e应该尽量避免选取得太小的情况发生，一般情况下e选取65535。

3 模不互素

3.1 介绍

如果在多次RSA加密中选取了不同的模数，存在两个或更多模数 ，且gcd(N1,N2)!=1，多个模数N共用质数，则可以很容易利用欧几里得算法求得他们的质因数之一exgcd(N1,N2) ，然后这个最大公约数可用于分解模数分别得到对应的p和q，即可进行解密。

3.2 防御措施

在模数N的选取上要注意避免上述情况的发生，邻近的RSA加密的模N尽量互素。

4 共模攻击

4.1 介绍

对同一明文的多次加密使用相同的模数和不同的公钥指数可能导致共模攻击。即为在两次RSA加密中，明文m和模数n相同，公钥指数e和密文c不同，且gcd(e1,e2)==1。

4.2 防御措施

密钥产生中心（KGC）应该采取相应方法避免共模攻击，例如不定时更新使用的模数N，当然这意味着要消耗一些额外的资源。

5 迭代攻击

5.1 介绍

5.2 防御措施

Rivest证明，当p-1和q-1中含有大素数因子，且n足够大时，这种攻击法成功的概率趋于0。

6 伪造签名

6.1 介绍

对于想要伪造签名的消息Mtarget，根据在模N数域上的乘法同态原理，如果我们能从已知消息中找到M1和M2满足条件

Mtarget=M1M2(mod N)

及其对应的数字签名

sig(M1)=M1d(mod N)

sig(M2)=M2d(mod N)

进而可得

sig(Mtarget)=(M1M2)d(mod N)=M1dM2d(mod N)=sig(M1)sig(M2)

所以我们的目标就明确了，只要找到符合条件的M1和M2及二者对应的签名，就可以利用公式推导的结果伪造出目标消息Mtarget的RSA电子签名sig(Mtarget)。

6.2 防御措施

签名者对消息的哈希值进行数字签名而非直接对消息本身进行签名，将伪造签名的困难基于Hash算法的抗碰撞性。