PROBLEM LINK:
Author, Tester, Editorialist: Vaibhav Gupta
PROBLEM
Find a private key from an RSA public key.
QUICK EXPLANATION
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.
EXPLANATION
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
-
Trial division
-
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=1Take 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.