Author, Tester, Editorialist: Vaibhav Gupta
Find a private key from an RSA public key.
In breaking RSA mainly you need to factorize N which is of the form N = p*q. And finally use extended euclidean algorithm to find the private key.
For factorizing integers these algorithms will help you:
Congruence of squares
Continued fraction factorization
Dixon’s factorization method
Euler’s factorization method
Fermat’s factorization method
Pollard’s p-1 algo
Shank’s square forms factorization
William’s p+1 algorithm
The Extended Euclidean Algorithm is essentially the Euclidean algorithm (for GCD’s) ran backwards. Your goal is to find d such that ed≡1(modφ(n)).
Recall the EED calculates x and y such that ax+by=gcd(a,b). Now let a=e, b=φ(n), and thus gcd(e,φ(n))=1 by definition (they need to be coprime for the inverse to exist). Then you have:ex+φ(n)y=1
Take this modulo φ(n), and you get:ex≡1(modφ(n))
And it’s easy to see that in this case, x=d. The value of y does not actually matter, since it will get eliminated modulo φ(n) regardless of its value. The EED will give you that value, but you can safely discard it.