RSA

RSA is one of the most used cryptographic algorithms and it is considered to be one of the most secure existing alternatives. Its basic operation is described below.

Two odd prime numbers P and Q are chosen and N = PQ is computed. Then the totient function φ(N) = (P − 1)(Q − 1) is computed and an integer e satisfying 1 < E < φ(N) is chosen so that gcd(φ(N), E) = 1. Finally the integer D, the inverse multiplicative of e module φ(N) is computed, that is, the integer D satisfying DE ≡ 1 mod φ(N).

In that way we obtain the public key, which consists of the pair of integers N and E, and the secret key, containing the integers N and D.

To encrypt a message M, with 0 < M < N, we calculate C = M^e mod N, and C is the encrypted message. To decrypt the message, that is, to recover the original message, it suffices to compute M = C^d mod N. Note that, in order to do that, the secret key must be known; knowing the public key is not enough to decrypt the message.

In this problem your task is to break the RSA cryptography.