Is it possible to get an RSA encryption key by comparing the unencrypted and encrypted file?

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

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}$)