[RSA2]P2 低加密指数攻击

main.py:

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
'''

尝试分解N发现无法分解

接下来是推理时间：
我们知道c=pow(m,e,n)实际上为c=m**e%n因为e很小为3所以直接爆破循环'k'让k*n+c=m**3并且对m**3开立方根，只要能成功开根，就说明我们算对了m即可得到flag

exp:

import gmpy2
from Crypto.Util.number import *

n = 1095193501314071508992184356698396498575993903902645176736824248626203423178058582980052056709470835349461883611907327333787476380807006829079149314187911076379180537479205152791331657276201370436693788845669156157605617438343332630668947137747409198034213068554850351851691
e = 3
c = 26957748170151919359681404117038763858559543976167222472065679376272566294346163463362841607862769232841859888042233434558282075299993159865541365966460870384341918224255038862662419746644668349966761257524859531569439368239059072753259426203046522626624370137714579366927
k = 0
while 1:
    m1 = k * n + c
    m, t = gmpy2.iroot(m1, e)
    if t:
        print(m)
        print(k)
        print(long_to_bytes(m))
        break
    k += 1

结果

13040004482819711557923021822109014599680292408188055032244663565248373742290221635099244669
2
b'flag{20d6e2da95dcc1fa5f5432a436c4be18}'