RSA-低加密指数攻击

源码：

from Crypto.Util.number import *
from gmpy2 import *

flag = b'NSSCTF{******}'

p = getPrime(512)
q = getPrime(512)

n = p*q
e = 3
phi = (p-1)*(q-1)
m = bytes_to_long(flag)

c = powmod(m, e, n)

print(f'n = {n}')
print(f'e = {e}')
print(f'c = {c}')

'''
n = 111573371787314339229652810703380127177507745009618224416171957526984270337589283887959174610818933914845556276472159360153787395638087723501889651641965684241070152541291185349571453536221312112508437223801640552330390095266644485311958102687735113533739324296417077804219395793942670324182191309872918900717
e = 3
c = 90782646242308381145716338972639920044710403094882163620436540965475107006005657722222634294458956650085252212452241377251397323707019480880284004845674260662647720809672266571040936376737882878688872281858048646517100139303896804340224961592424635124272549514473232731744884837572128596217771005209683966262
'''

姿势

$\because p，q是512位的数不考虑直接分解n$
$\because flag短 \rightarrow m小， 又e小 \rightarrow m^e小。p,q大 \rightarrow n大$

$c \equiv m^e \mod n$

尝试小明文攻击，结果错误
$\therefore 说明m^e > n(因为此处的p，q不是极大)$
消去取模，有：

$m^e = kn + c$

$\because 推断出m^e不大$
$\therefore 遍历k的值，当kn+c恰好是e的完全平方数时，可以还原出m$

iroot(x, n)[0][1]
对x开n次方，返回整数[0]和布尔值[1]（能被完全开方为整数，则返回True；不能，则返回False）

exp

from Crypto.Util.number import *
from gmpy2 import *

e = 3
n = 111573371787314339229652810703380127177507745009618224416171957526984270337589283887959174610818933914845556276472159360153787395638087723501889651641965684241070152541291185349571453536221312112508437223801640552330390095266644485311958102687735113533739324296417077804219395793942670324182191309872918900717
e = 3
c = 90782646242308381145716338972639920044710403094882163620436540965475107006005657722222634294458956650085252212452241377251397323707019480880284004845674260662647720809672266571040936376737882878688872281858048646517100139303896804340224961592424635124272549514473232731744884837572128596217771005209683966262

for k in range(1,100):
    cc = c + k*n
    res = iroot(cc, e)
    if res[1]:
        m = res[0]
        break

print(long_to_bytes(m))
print('k:',k)