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
Flag : wsc{w13n3r5_wer3_bre4d_t0_hunt_b4dger5!}