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?

• You are all forgetting PKCS1.5, if the message M is less than 256 bytes then there is padding before encryption. So you really don't know what the value of M^c is (unless chosen to be exactly 256 bytes). Feb 7, 2017 at 4:44
• This is a different question. The initial question never mentioned the use of PKCS #1 v1.5. Feb 7, 2017 at 6:18

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.

• The $\gcd()$ is a multiple of N, so it may be of the form $kN$ for some small $k.$
– 111
Feb 5, 2017 at 16:57
• In fact if N has 2048 bits, then you expect $a=C_1^2-C3,b=C_2^2-C_4$ to have $\approx 4090$ bits. So you assumed, that $\gcd(a,b)/N$ is small. I believe that in general is small, and your attack is practical, but I am wondering what is the probability of success of your attack (say if you choose $M_1, M_2$ uniformly)?
– 111
Feb 5, 2017 at 17:07
• @111 Thank for your comment. I added Remark 2 to address it. Feb 5, 2017 at 17:08
• You have a 2048 bit certificate and $1<N<2^{2048}$ so many values can be discarded right away. You can also make sure you have the smallest possible $N$ ($k=1$) if you choose a message that is the smallest integer $I$ below the $c$th root of $N'$ for a candidate $N'=kN$. If the ciphertext is different from $I^c$, $N'$ is a multiple of the actual $N$. May 31, 2021 at 21:30

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.

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\%$.