12
$\begingroup$

Exactly what the title says. If I have a RSA encrypted file, and the exact same file but decrypted, can I tell the key that was used from that information?

$\endgroup$
  • $\begingroup$ @SEJPM You might be able to find the public key, and that wouldn't be a problem in typical scenarios. $\endgroup$ – Gilles 'SO- stop being evil' Aug 17 '15 at 20:30
  • $\begingroup$ Ohhh, sorry I didn't read the question carefully enough D: You're asking to get the public and not the private key! I really have to apologize. Retrieving the public key from comparing encrypted and unencrypted is of course not a security threat. $\endgroup$ – SEJPM Aug 17 '15 at 20:33
  • 2
    $\begingroup$ One thing that you should consider is that in most real-world cryptosystems built on RSA, the public key of the recipient is explicitly included. So even if the "textbook" answer were "no", the answer in the real-world is almost assuredly "yes". $\endgroup$ – Stephen Touset Aug 17 '15 at 21:17
  • 2
    $\begingroup$ Are you sure you mean the encryption key and not the decryption key? $\endgroup$ – otus Aug 18 '15 at 6:00
6
$\begingroup$

No, if the RSA cryptosystem is secure, i.e. when it uses random padding such as PKCS#1 v1.5 padding or OAEP, then you cannot. As Stephen already mused, it is pretty likely that you can find out the key simply because it is included or can be derived; generally public keys are not meant to be secure.

If textbook (raw modular exponentiation) RSA is used then you can encrypt with the public key. If you get the same value then it is pretty likely that you've found the public key. But usually textbook RSA isn't used because it is insecure in several other ways as well. Ciphertext distinguishablity is just one of the problems.

Now some information can of course still be extracted from the ciphertext. First of all, the length of the RSA ciphertext is generally identical to the key size. So you can distinguish between keys of several lengths. Furthermore, if you find an RSA ciphertext that is higher than the modulus of the public key then that key is certainly not used to generate the ciphertext.


You explicitly asked for the encryption key which is the public key. If you meant the private decryption key then, no, the key cannot be derived except for the little amount of data also available for the public key.


Note that RSA is never directly used to encrypt files. Instead a hybrid cryptosystem needs to be used. The usual RSA schemes are not secure to encrypt data larger than the modulus minus the padding overhead. Furthermore, encrypting large amounts of data with RSA would be very CPU intensive and decrypting it would be worse.

$\endgroup$
  • $\begingroup$ Well the files in question are encrypted with RSA-256, and one 100kb file took about 5 minutes to decrypt. Of course this was through the attackers site (These files are on a PC hijacked by CryptoWall :/) $\endgroup$ – aaro4130 Aug 18 '15 at 3:42
  • $\begingroup$ @aaro4130, CryptoWall seems to use RSA-2048 and AES-256, RSA-256 could be cracked. $\endgroup$ – otus Aug 18 '15 at 5:11
  • $\begingroup$ @aaro4130 If it was that easy to circumvent the encryption used by CryptoWall you would have known about it. $\endgroup$ – Maarten - reinstate Monica Aug 18 '15 at 7:27
  • $\begingroup$ Heh, I guess so $\endgroup$ – aaro4130 Aug 18 '15 at 13:44
4
$\begingroup$

The ciphertext should look like a random element within 1 and the modulus (since it is a value from within that range as Yehuda Lindell pointed out). Without knowing the modulus it should not be feasible to distinguish two ciphertexts encrypted with different keys.

If the public key is stored in some key-database you could ofc try to encrypt the decrypted text with all stored keys and test if the encryption matches the text. Anyway, finding the private key is not yet possible in polynomial time with classic computers.

Update: Thx @Yehuda Lindell for the remark.

$\endgroup$
  • 2
    $\begingroup$ Actually, from two (plaintext, ciphertext) RSA pairs, you have a good chance of finding the public key. It's only the private key that can't be found in any decent cryptosystem. $\endgroup$ – Gilles 'SO- stop being evil' Aug 17 '15 at 20:32
  • $\begingroup$ Would i not have to find 'randomly' the according primes out of the key space? ...reducing the chance of finding such a number to the cardinality of the set of matching primes? $\endgroup$ – Fleeep Aug 17 '15 at 20:51
  • 1
    $\begingroup$ This just is NOT correct. There is no requirement that a ciphertext be indistinguishable from random. It turns out to be true often in symmetric schemes and some people use this as a definition there for other reasons. However, it is NOT true for public-key schemes. An RSA or ElGamal or ECIES ciphertext does NOT at all look random. $\endgroup$ – Yehuda Lindell Aug 18 '15 at 5:37
3
$\begingroup$

Some information about the RSA public key is revealed by the ciphertext. This is due to the fact that the ciphertext is a value between 1 and the modulus. Beyond this, I don't know what is revealed. However, what I can prove is that whatever you can learn from the plaintext and ciphertext together, you can learn from the ciphertext only.

I can prove this via a reduction (I'll just give a sketch here). Assume, by contradiction, that there exists an adversary $A$ who outputs "more information" about the RSA public key given the plaintext and ciphertext, than what is possible when just given the ciphertext (a bit more formally, there is some efficiently computable function $f$ of the public key that $A$ can output when given the plaintext and ciphertext but cannot output when given just the ciphertext). First, I would argue that if $A$ is given the ciphertext and a different random plaintext, then it can output $f(pk)$ with probability that is no greater than when given the ciphertext only. This is quite easy to see. Next, I construct an adversary $A'$ who attacks RSA in the CPA experiment. $A'$ outputs two random plaintexts $m_0,m_1$ and is given a ciphertext $c$ which is an encryption of one of them. Note that $A'$ also knows $pk$. Then, $A'$ runs $A$ on $c,m_0$. If $A$ returns $f(pk)$, then $A'$ outputs 0; otherwise it outputs a random bit. A probabilistic calculation here will give that $A'$ will output 0 when $c$ is an encryption of $m_0$ with probability non-negligibly greater than $1/2$.

Summary: whatever you can learn about the public-key from the plaintext and ciphertext, you can learn from the ciphertext only.

Caveat: All of the above needs a formal proof, so I'm only 98% sure that it will all go through.

$\endgroup$
  • $\begingroup$ Well, let's quickly assume textbook RSA. Assume you're given two messages $m_1,m_2$ and two ciphertexts $c_1,c_2$. Now guess a value for $e$ (chances won't be too bad for $e<2^40$) and observe that $c\equiv m^e \pmod N$. Now use this to obtain the relation $m^e-c=rN$. Calculate the left side for all known plaintexts and compute the pair-wise GCD between them. The smallest result will likely be the modulus. Verify your guess by trying the public key parameters at additional known plaintexts. $\endgroup$ – SEJPM Aug 18 '15 at 7:01
  • 1
    $\begingroup$ Textbook RSA is not secure encryption. My proof is for something that is secure encryption. In any case, how do you know $N$ exactly? $\endgroup$ – Yehuda Lindell Aug 18 '15 at 12:58
  • $\begingroup$ I can find $N$ with high probability as the GCD of the results of the left side of the equation. See my answer for the details on how many known plaintexts are needed. $\endgroup$ – SEJPM Aug 19 '15 at 13:24
  • $\begingroup$ @SEJPM Nice! I like the method for finding N. $\endgroup$ – Yehuda Lindell Aug 20 '15 at 5:00
  • $\begingroup$ so you're saying that, if we only had the ciphertext and somehow computed all possible RSA public keys (assuming size < 2048), then encrypting the plaintext with any one of these keys would always result in the ciphertext? $\endgroup$ – woojoo666 Dec 14 '17 at 1:51
3
$\begingroup$

I'm quickly assuming your question asks how to retrieve the public (RSA-) key from a set of samples of unencrypted and encrypted messages.

If you're question is about: "How can I get my files back after being infected by CryptoWall?" I suggest you read the hits by the search function on InfoSec.

Please also note that in most use cases RSA isn't used to actually encrypt the messages (like files) but rather encrypt some keys which are subsequently used to encrypt the files symmetrically. This is what CryptoWall does.

Please note further that knowledge of the encryption key for RSA doesn't imply knowledge of the decryption key. So using the below method you'll be able to find the public (encryption= key for textbook RSA, but not the key neccessary for decryption. Note furthermore that retrieving the public key from secure RSA variants (used in practice) is impossible as outlined by Yehuda.


Now to the strategy of finding the public key for textbook RSA given a set of message-ciphertext pairs $\{(m_0,c_0),...,(m_k,c_k)\}$.

First observe that, by definition of RSA, $c_i\equiv m_i^e \pmod N$ holds for the (not) given public key $(e,N)$. We can't easily retrieve $e$, so we have to guess it to proceed. Usually $e=3$ or $e=2^{16}+1=65537$ holds and if not one can apply the below procedure to any guess of $e$. If $e$ is chosen at random the method doesn't work, but in practice $e$ takes the above fixed values.

Next observe that $m_i^e-c_i\equiv 0 \pmod N$, implying $m_i^e-c_i=a_i=r_i\times N$ for some quite random $r_i$. Now we can compute the $a_i$ for all our plaintext-ciphertext pairs. Now note that that all the $a_i$ have the $N$ as factor in common. We can now apply the pair-wise gcd to all pairs of $(a_i,a_j)$ we have and see that $gcd(a_i,a_j)\geq N$ and $gcd(a_i,a_j)=N$ if $gcd(r_i,r_j)=1$. Thus by computing all the GCDs and taking the smallest value we observe, we can find the correct modulus.

We can confirm that we indeed found the correct $(e,N)$ pair by simple computing $c'_i\equiv m_i^e \pmod N$ and confirming that $c'_i=c_i$ holds for all ciphertexts we have.

To get to the below formula, first observe that the probability that two random integers are co-prime is roughly $6/\pi^2$. Now the probability that they aren't co-prime is obviously $1-6/\pi^2$. The probability that all the pairs of $r$s we have aren't co-prime is $(1-6/\pi^2)^{\text{NumberOfPairs}}$. The $\text{NumberOfPairs}$ is the number of pairs we can build from our set of size $k$, meaning we can find $k(k-1)/2=(k^2-k)/2$ pairs of $r$s. Now finally observe that $\Pr[\text{At least one pair is co-prime}]=1-\Pr[\text{no pair is co-prime}]$. And finally bind this back to the above explanation and see that we find the modulus only if we hit at least one co-prime pair of $r$s, yielding the below equation:

$$\Pr[N=\text{modulus}]=1-(1-6/\pi^2)^{(k^2-k)/2}$$

So to achieve a given probability $P$ that we found the modulus (and not anything larger), we should have at least $k\geq5$ plaintext-ciphertext pairs (for probaility $\approx 0.9999$). If we want to be really sure $k\geq12$ should yield $\Pr[N=\text{modulus}]>1-2^{-80}$ (same with $k\geq20$ and $2^{-256}$)

$\endgroup$
  • $\begingroup$ I really hope that the $r$s are random enough and that the $a$s are large enough to use $6/\pi^2$. FYI, the $a$s should be roughly 16MiB large for $e=65537$ and $\log_2(N)\approx 2048$ $\endgroup$ – SEJPM Aug 19 '15 at 13:21
  • $\begingroup$ If anyone asks: The run-time should be polynomial as wee need a constant amount of guesses for $e$ (assuming $e$ is small or fixed), we need a constant amount (5,12,20) of modular exponentiations per guess, we need a constant amount of gcd computations (10,66,190) on linearly sized data (bitlength grows linearly by $e$). I'm pretty sure it won't be too fast but still feasibly fast. $\endgroup$ – SEJPM Aug 19 '15 at 13:28

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.