PicoCTF 2022 — Crypto: Sum-O-Primes


We have so much faith in RSA we give you not just the product of the primes, but their sum as well!

gen.py output.txt


This problem can be solved as we have the product and sum of the 2 primes. This can be achieve by using a quadratic equation.

Here we can calculate the square root value as theta

theta = ((bb**2) - (4*nn)).sqrt()

Then solve for p and q

p = (bb+theta)//2
q = (bb-theta)//2

With p and q we can rebuild the private exponent and recover the plain text flag

phi = (int(p)-1)*(int(q)-1)
d = pow(e,-1,phi)
pt = pow(int(c,16),d,n)
print( long_to_bytes(pt))





Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store