526互联

RSA之低指数攻击------2023.5.22

发布时间 2023-05-22 21:09:13作者: 木偶2313

1，e=3的小明文攻击：

特点：

  1. 当 e=3 时，如果明文过小，导致明文的三次方仍然小于n，那么通过直接对密文开三次方即可得到明文。

 

即：C=m^e mod n,如果e=3,且m^e<n,则C=m^e,m=c^(1/3)

 

2.如果明文的三次方比n大，但不是足够大，那么设k有： C=m^e+k∗n

 

爆破k，如果 C−k∗n 或者 C+k∗n 能开三次根式，那么就可以直接得到明文。

关键代码：

i=0
while 1:
    if(iroot(c+i*n,3)[1]==1):           #或者 iroot(c-i*n,3)
        print(iroot(c+i*n,3)[0])
        break
    i=i+1

例题：buuctf dangerous rsa
#n:  0x52d483c27cd806550fbe0e37a61af2e7cf5e0efb723dfc81174c918a27627779b21fa3c851e9e94188eaee3d5cd6f752406a43fbecb53e80836ff1e185d3ccd7782ea846c2e91a7b0808986666e0bdadbfb7bdd65670a589a4d2478e9adcafe97c6ee23614bcb2ecc23580f4d2e3cc1ecfec25c50da4bc754dde6c8bfd8d1fc16956c74d8e9196046a01dc9f3024e11461c294f29d7421140732fedacac97b8fe50999117d27943c953f18c4ff4f8c258d839764078d4b6ef6e8591e0ff5563b31a39e6374d0d41c8c46921c25e5904a817ef8e39e5c9b71225a83269693e0b7e3218fc5e5a1e8412ba16e588b3d6ac536dce39fcdfce81eec79979ea6872793L
#e:  0x3
#c:0x10652cdfaa6b63f6d7bd1109da08181e500e5643f5b240a9024bfa84d5f2cac9310562978347bb232d63e7289283871efab83d84ff5a7b64a94a79d34cfbd4ef121723ba1f663e514f83f6f01492b4e13e1bb4296d96ea5a353d3bf2edd2f449c03c4a3e995237985a596908adc741f32365
so,how to get the message?

解题脚本：
from libnum import*   #python第三方库
from gmpy2 import*    #python第三方库

n = 0x52d483c27cd806550fbe0e37a61af2e7cf5e0efb723dfc81174c918a27627779b21fa3c851e9e94188eaee3d5cd6f752406a43fbecb53e80836ff1e185d3ccd7782ea846c2e91a7b0808986666e0bdadbfb7bdd65670a589a4d2478e9adcafe97c6ee23614bcb2ecc23580f4d2e3cc1ecfec25c50da4bc754dde6c8bfd8d1fc16956c74d8e9196046a01dc9f3024e11461c294f29d7421140732fedacac97b8fe50999117d27943c953f18c4ff4f8c258d839764078d4b6ef6e8591e0ff5563b31a39e6374d0d41c8c46921c25e5904a817ef8e39e5c9b71225a83269693e0b7e3218fc5e5a1e8412ba16e588b3d6ac536dce39fcdfce81eec79979ea6872793
c = 0x10652cdfaa6b63f6d7bd1109da08181e500e5643f5b240a9024bfa84d5f2cac9310562978347bb232d63e7289283871efab83d84ff5a7b64a94a79d34cfbd4ef121723ba1f663e514f83f6f01492b4e13e1bb4296d96ea5a353d3bf2edd2f449c03c4a3e995237985a596908adc741f32365

i=0
while 1:
    if(iroot(c+i*n,3)[1]==1):           #或者 iroot(c-i*n,3)
        print(n2s(iroot(c+i*n,3)[0]))
        break
    i=i+1
2，e=2时的小明文攻击：
特点：

e=2时，直接将密文C开平方获得解

由于e只有2，相当于把明文m平方而已，得到的C也比n小很多。尝试直接将C开根号看能否得到明文。

关键代码：

from libnum import*   #python第三方库
from gmpy2 import*    #python第三方库

c=......              #C的值
m=isqrt(c)            #开平方根
#m=iroot(c,2)[0]      #开C的二次方根

print(n2s(m))

3，e=1时的小明文攻击：
特点：

加密过程：

C≡m mod n ,明文与密文同模

所以有：m=C+n*k,爆破k

关键代码：

from libnum import*

n=....
c=....
max_num = 7   #设置遍历上限

for k in range(max_num):
    m = c + n*k
    print(n2s(m))