Make it Possible

RSA大礼包(三)低解密指数攻击、共模攻击、低解密指数广播攻击

低加密指数广播攻击

如果选取的加密指数较低,并且使用了相同的加密指数给一个接受者的群发送相同的信息,那么可以进行广播攻击得到明文。
即,选取了相同的加密指数e(这里取e=3),对相同的明文m进行了加密并进行了消息的传递,那么有:
c_1\equiv m^e\ mod \ n_1
c_2\equiv m^e\ mod \ n_2
c_3\equiv m^e\ mod \ n_3
对上述等式运用中国剩余定理,在e=3时,可以得到:
c_x\equiv m^3mod\ n_1n_2n_3
所以m=\sqrt[3]{c_x}

中国剩余定理求解过程
假设有
y_1\equiv x\bmod n_1
y_2\equiv x\bmod n_2
y_3\equiv x\bmod n_3
那么我们可以构造z_1使
z_1=n_1n_2\ ((n_1n_2)^{-1}mod\ n_3)
对于z_1有这样几点性质
z_1\equiv0\bmod n_1, z_1\equiv0\bmod n_2, z_1\equiv1\bmod n_3
所以我们按相同的方法构造z_2, z_3
最后得到z=z_1y_1+z_2y_2+z_3y_3
同时满足x的性质
所以容易得到x\equiv z \bmod n_1n_2n_3

低解密指数攻击

轮子

import  RSAwienerHacker
d =  RSAwienerHacker.hack_RSA(e,n)
if d:
    print(d)

共模攻击

如果在RSA的使用中使用了相同的模n对相同的明文m进行了加密,那么就可以在不分解n的情况下还原出明文m的值。
c_1\equiv m^{e_1}\mod n
c_2\equiv m^{e_2}\mod n
此时不需要分解n,不需要求解私钥,如果两个加密指数互素,就可以通过共模攻击在两个密文和公钥被嗅探到的情况下还原出明文m的值。
过程如下,首先两个加密指数互质,则:
gcd(e_1,e_2)=1
即存在s_1,s_2使s_1e_1+s_2e_2=1
对上式代入化简可得
c_1^{s_1}c_2^{s_2}\equiv m^{s_1e_1+s_2e_2}\mod n
c_1^{s_1}c_2^{s_2}\equiv m\mod n
可以通过拓展欧几里得算法得出s_1,s_2,最终算出原文。

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据