# 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). – Keliath Feb 7 '17 at 4:44
• This is a different question. The initial question never mentioned the use of PKCS #1 v1.5. – user94293 Feb 7 '17 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 '17 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 '17 at 17:07
• @111 Thank for your comment. I added Remark 2 to address it. – user94293 Feb 5 '17 at 17:08

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

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.