4
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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). $\endgroup$ – Keliath Feb 7 '17 at 4:44
  • $\begingroup$ This is a different question. The initial question never mentioned the use of PKCS #1 v1.5. $\endgroup$ – user94293 Feb 7 '17 at 6:18
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ The $\gcd()$ is a multiple of N, so it may be of the form $kN$ for some small $k.$ $\endgroup$ – 111 Feb 5 '17 at 16:57
  • $\begingroup$ 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)? $\endgroup$ – 111 Feb 5 '17 at 17:07
  • $\begingroup$ @111 Thank for your comment. I added Remark 2 to address it. $\endgroup$ – user94293 Feb 5 '17 at 17:08
4
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.