<reponame>userElaina/SpiritCTF-2021
from Crypto.Util.number import *

e = 65537
c = 80022895914976184204780920922135317333935981197797824696840082352675958974646602905511540139800010844912499996468426037122058520287520832193832379625077808937358040905826453443117048690770248639871597119584984247050374045314814699861881095723936814019327266946774727837877342390982884057300263091206024813280
n = 155576181324562378353982897182978537588869972956242129246841350173252616672165607016662407537358283618963479863552879215926569567093652733260443532264139516470285922169392447645822382497459523267845212208221506556840255541351045822292343764763821357438013545532666952868879835047419530972377647384637639940049
h1 = 10174536387336832121997274588305344979197254627987945879322344555545163466179502018896233064264676843247986842983466158297107837250414088435496508457442687

x=e*h1-1

for _i in range(e):
    i=e-_i
    if x%i:
        continue
    p=x//i+1
    if n%p:
        continue
    break
else:
    assert True

q=n//p
phi=(p-1)*(q-1)
d=inverse(e,phi)
m=pow(c,d,n)
print(long_to_bytes(m).decode('utf8'))
# Spirit{2dfc2bf9-59eb-43b8-8495-7498cdeb4f41}

from Crypto.Util.number import *

e = 65537
c = 80022895914976184204780920922135317333935981197797824696840082352675958974646602905511540139800010844912499996468426037122058520287520832193832379625077808937358040905826453443117048690770248639871597119584984247050374045314814699861881095723936814019327266946774727837877342390982884057300263091206024813280
n = 155576181324562378353982897182978537588869972956242129246841350173252616672165607016662407537358283618963479863552879215926569567093652733260443532264139516470285922169392447645822382497459523267845212208221506556840255541351045822292343764763821357438013545532666952868879835047419530972377647384637639940049
h1 = 10174536387336832121997274588305344979197254627987945879322344555545163466179502018896233064264676843247986842983466158297107837250414088435496508457442687

x=e*h1-1

for _i in range(e):
    i=e-_i
    if x%i:
        continue
    p=x//i+1
    if n%p:
        continue
    break
else:
    assert True

q=n//p
phi=(p-1)*(q-1)
d=inverse(e,phi)
m=pow(c,d,n)
print(long_to_bytes(m).decode('utf8'))
# Spirit{2dfc2bf9-59eb-43b8-8495-7498cdeb4f41}
# Spirit{2dfc2bf9-59eb-43b8-8495-7498cdeb4f41}