Deduce modulus N from public exponent and encrypted data This is an RSA question, given data encrypted with a public key from an unknown RSA certificate of 2048 bit, let $X$ be the encrypted data, $M$ the unencrypted data, $c$ the public exponent and $N$ it's modulus. Knowing $X$, $M$ and $c$, can you deduce $N$?

$$
X = M^c \mod N
$$

You can have as many $M$ and corresponding $X$ as you want, hence:

$$
X_1 = M_1^c \mod N \\
X_2 = M_2^c \mod N \\
\dots
$$

I want to know if this is possible, mathematically and programatically. A brute force won't work here. Any ideas?
Given a message $M$, define the corresponding RSA ciphertext as $C = M^e \bmod N$.  We assume that the value of $N$ is kept secret.  However, the attacker is given oracle access to the encryption: on input a chosen message $M$, the attacker gets backs $C = M^e \bmod N$.

Question: How is possible for an attacker to recover the value of $N$?


Easy case (small exponent) Suppose the exponent $e$ is small (e.g., $e=3$) and known to the attacker.  Then, as detailed by yyyyyyy, given two ciphertexts $C_1 = M_1^e \bmod N$ and $C_2 = M_2^e \bmod N$, the value of $N$ can be obtained from $\gcd(M_1^e - C_1, M_2^e - C_2)$. 
General case  Consider now the case where $e$ is large.  The attacker chooses two messages $M_1$ and $M_2$ and forms the messages $M_1' = M_1^2$ and $M_2' = M_2^2$.  The attacker asks for the corresponding ciphertexts and gets $C_i = M_i^e \bmod N$ and $C_i' = M_i'^e \bmod N$(for $i \in \{1,2\}$).  Since $M_1' = M_1^2$, it follows that $C_1' \equiv C_1^2 \pmod N$ and thus $(C_1^2 - C_1')$ is a multiple of $N$.  Similarly, $(C_2^2 - C_2')$ is a multiple of $N$.  As a consequence, $N$ can be recovered from $\gcd(C_1^2 - C_1', C_2^2 - C_2')$.  




Remark 1  Note that the attacker does not need to know the value of $e$ to mount the second attack (general case).

Remark 2 Define $\tilde{N} := \gcd(C_1^2 - C_1', C_2^2 - C_2')$.
It might be the case that $\tilde{N}$ is not exactly equal to $N$.  The above description only implies that $\tilde{N}$ is a multiple of $N$.  However, knowing that $N$ is the product of large primes, it can be recovered from $\tilde{N}$ by removing extra small factors.  Yet, another option is to choose more messages and compute $N$ from $\gcd(C_1^2 - C_1', C_2^2 - C_2', C_3^2 - C_3', \dots)$.

Remark 3  There are several possible variants for the second attack.