Skip to content

Instantly share code, notes, and snippets.

@hakatashi

hakatashi/01-solve.sage

Last active March 10, 2021 12:46
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save hakatashi/7d5f4dfe1ddc417a3bbe00ae737aa6ad to your computer and use it in GitHub Desktop.
Save hakatashi/7d5f4dfe1ddc417a3bbe00ae737aa6ad to your computer and use it in GitHub Desktop.
Download ZIP
zer0pts CTF 2021 NOT Mordell primes solver script
Raw
01-solve.sage
p = 13046889097521646369087469608188552207167764240347195472002158820809408567610092324592843361428437763328630003678802379234688335664907752858268976392979073
a = 10043619664651911066883029686766120169131919507076163314397915307085965058341170072938120477911396027902856306859830431800181085603701181775623189478719241
b = 12964455266041997431902182249246681423017590093048617091076729201020090112909200442573801636087298080179764338147888667898243288442212586190171993932442177
Gx = 11283606203023552880751516189906896934892241360923251780689387054183187410315259518723242477593131979010442607035913952477781391707487688691661703618439980
Gy = 12748862750577419812619234165922125135009793011470953429653398381275403229335519006908182956425430354120606424111151410237675942385465833703061487938776991
N = 22607234899418506929126001268361871457071114354768385952661316782742548112938224795906631400222949082488044126564531809419277303594848211922000498018284382244900831520857366772119155202621331079644609558409672584261968029536525583401488106146231216232578818115404806474812984250682928141729397248414221861387
c = 15850849981973267982600456876579257471708532525108633915715902825196241000151529259632177065183069032967782114646012018721535909022877307131272587379284451827627191021621449090672315265556221217089055578013603281682705976215360078119427612168005716370941190233189775697324558168779779919848728188151630185987
R.<x> = PolynomialRing(GF(p))
L = (x * (Gy^2 + x^3 + a*x + b) - (N + x^2 + Gx*x) * (Gx - x)^2)^2 - 4 * Gy^2 * x^2 * (x^3 + a*x + b)
roots = L.roots()
print(roots)
rsa_p = int(roots[0][0])
assert(N % rsa_p == 0)
rsa_q = N // rsa_p
e = 0x10001
phi = (rsa_p - 1) * (rsa_q - 1)
d = pow(e, -1, phi)
m = pow(c, d, N)
print(int(m).to_bytes(40, 'big'))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment