RSA With The Dogs

Challenge Description

I was doing RSA with the dogs so that we could send stuff to each other. Unfortunately the cats are stealing our messages... gen.sage


We are given this script

from random import getrandbits
from Crypto.Util.number import bytes_to_long
p = random_prime(2^(1024//2),False,2^(1023//2))
q = random_prime(2^(1024//2),False,2^(1023//2))
n = p*q
phi = (p-1) * (q-1)
done = False
while not done:
d = getrandbits(1024//4)
if (gcd(d,phi) == 1 and 36*pow(d,4) < n):
done = True
Flag = open('flag.txt').read().encode()
m=bytes_to_long(Flag)
e = Integer(d).inverse_mod(phi)
c=pow(m,e,n)
print("n =",n)
print("e =",e)
print("c =",c)
n = 80958280137410344469270793621735550547403923964041971008952114628165974409360380289792220885326992426579868790128162893145613324338067958789899179419581085862309223717281585829617191377490590947730109453817502130283318153315193437990052156404947863059961976057429879645314342452813233368655425822274689461707
e = 3575901247532182907389411227211529824636724376722157756567776602226084740339294992167070515627141715229879280406393029563498781044157896403506408797685517148091205601955885898295742740813509895317351882951244059944509598074900130252149053360447229439583686319853300112906033979011695531155686173063061146739
c = 80629080505342932586166479028264765764709326746119909040860609021743893395577080637958779561184335633322859567681317501709922573784403504695809067898870536224427948000498261469984511352960143456934810825186736399371084350678586129000118485271831798923746976704036847707653422361120164687989605124465224952493
assert(int(pow(c,d,n)) == m)

It’s Wiener's attack https://en.wikipedia.org/wiki/Wiener's_attack

I used RsaCtfTool https://github.com/Ganapati/RsaCtfTool to solve this challenge

python3 RsaCtfTool.py -e 3575901247532182907389411227211529824636724376722157756567776602226084740339294992167070515627141715229879280406393029563498781044157896403506408797685517148091205601955885898295742740813509895317351882951244059944509598074900130252149053360447229439583686319853300112906033979011695531155686173063061146739 -n 80958280137410344469270793621735550547403923964041971008952114628165974409360380289792220885326992426579868790128162893145613324338067958789899179419581085862309223717281585829617191377490590947730109453817502130283318153315193437990052156404947863059961976057429879645314342452813233368655425822274689461707 --uncipher 80629080505342932586166479028264765764709326746119909040860609021743893395577080637958779561184335633322859567681317501709922573784403504695809067898870536224427948000498261469984511352960143456934810825186736399371084350678586129000118485271831798923746976704036847707653422361120164687989605124465224952493 --attack wiener

Output

Untitled

Flag : wsc{w13n3r5_wer3_bre4d_t0_hunt_b4dger5!}