OBLIVI - Editorial

PROBLEM LINK:

Practise

Contest

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:

  1. Congruence of squares

  2. Continued fraction factorization

  3. Dixon’s factorization method

  4. Euler’s factorization method

  5. Fermat’s factorization method

  6. Pollard’s p-1 algo

  7. Shank’s square forms factorization

  8. Trial division

  9. 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.

ACCEPTED SOLUTION:

cheaters_x’s Solution

//