Deduce modulus N from public exponent and encrypted data

Question

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?

Answer 1

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.

Answer 2

By construction, we have $$ M^c = X + k\cdot N $$ for some $k\in\mathbb Z$. Thus, given two plaintext-ciphertext pairs $(M_1,X_1),(M_2,X_2)$, the integer $$ A:=\gcd(M_1^c-X_1,M_2^c-X_2) $$ will be a multiple of $N$. Moreover, unless the numbers were specially crafted, it is likely that the factors $k_i$ in the relations $M_i^c=X_i+k_i\cdot N$ share only a few small prime factors, thus stripping small factors from $A$ should yield the correct modulus $N$ most of the time.

Note that in practice, the numbers get quite large: For a 4096-bit message $M_i$ and the common public exponent $c=65537$, the number $M_i^c-X_i$ is approximately 268 million bits long. While that is still manageable on a normal computer, much larger $c$ will probably give you trouble.

Answer 3

To answer to the second part of your question, about programming the attack, it is very easy to implement the attack of user94293 in sagemath

from Crypto.PublicKey import RSA
RSAkey = RSA.generate(1024)
N,e = RSAkey.n,RSAkey.e
m1=2^(10)+1 # or any message you want
m2=2^(10)-1
m3=m1^2
m4=m2^2
c1=power_mod(m1, e, N)
c2=power_mod(m2, e, N)
c3=power_mod(m3, e, N)
c4=power_mod(m4, e, N)

and you check

gcd(c2^2-c4,c1^2-c3)==N

Remark that, you may not always get True, but if you get False you will start to check relations of the form

gcd(c2^2-c4,c1^2-c3)/a==N

for some $a$ small.

In practice the attack works (as you can check).

==EDIT==

Playing with the previous code, heuristically we can say that on average the success rate is $55\%$. That is, in (almost) half of the instances, there is no need to search for small factors.

If you consider three messages then the success rate increases to $\approx 80\%$.