2
$\begingroup$

Say I have four files. Two are completely unencrypted, while the other two are the exact same files other than that they have been encrypted with (apparently) the same public key (via a ransomware virus). Is it possible to deduce the key from these files, so I can apply it to other files also encrypted with the same key?

Edit

Sorry, after searching through the questions related to my tags, I see the simple answer is no, because although the public key is easily discovered, it's probably a private key I'm looking for, which would be hosted elsewhere.

But to modify the question:

  • Does the length of the public key imply the length of the private key, or can they be unrelated?
  • Also, wouldn't more plaintext information provide a brute-force program a starting point to speed the process?

I don't understand why, given that all the files would be decrypted using the same key, we can't deduce said key by comparing encrypted files to unencrypted ones.

|improve this question
$\endgroup$
  • $\begingroup$ Thanks for the update. I’ve fine-tuned your edited question a bit to make it even more of a non-duplicate and re-opened the question accordingly. I hope my modifications still meet the point of your question. In case I messed something up somewhere, please don’t hesitate to undo or modify my edits… $\endgroup$ – e-sushi Jan 21 '16 at 15:33
  • $\begingroup$ You're basically asking why trapdoor one-way functions are possible, and well... if anyone produced a correct answer, then they have also proven that P != NP. $\endgroup$ – MickLH Dec 26 '16 at 20:03
5
$\begingroup$

Does the length of the public key imply the length of the private key, or can they be unrelated?

Yes.

The sizes of public and private keys depend on the cryptosystem. Usually they are related somehow, but not necessarily. For example, you can store a short value as a private key, which is then used as a PRNG seed to generate the private key used in the actual algorithms.

In RSA a private key file typically includes a lot more information than a public key - in addition to those modulus and public exponent that the public key contains, it includes the private exponent, as well as usually the original primes and some CRT values.

However, raw RSA keys only need to contain the modulus and the private or public exponent, so they can be the same size.

Also, wouldn't more plaintext information provide a brute-force program a starting point to speed the process?

No, typically not. An encryption algorithm where this is true (at least for values smaller than other attacks) is considered broken. Because of the below.

I don't understand why, given that all the files would be decrypted using the same key, we can't deduce said key by comparing encrypted files to unencrypted ones.

If you could do that, then the public key system would not be very useful would it? Anyone who has the public key can encrypt any number of files they want. Thus, they have any number of plaintext-ciphertext pairs they could want. If this made the algorithm weak, it would be completely useless (except maybe as a replacement for a symmetric, i.e. secret key algorithm).

You might find questions such as this helpful: Is there an intuitive explanation as to why only the private key can decrypt a message encrypted with the public key?

|improve this answer
$\endgroup$
  • $\begingroup$ Concerning discussion on RSA private key vs. public key length: RSA private exponent is typically much larger than public exponent, so private key if it includes modulus will still be larger than public key. However, storing material that allows quick computation of modulus and private exponent will allow RSA private keys presented in as many bytes as RSA public key or even less. For example, e.g., storing these values: $p$, $q$, $e$, will take pretty identical space to $n$, $e$. $\endgroup$ – user4982 Jan 21 '16 at 17:40
  • $\begingroup$ @user4982, true, there are many possible ways to store them, and like I wrote, you can go even lower than $p, q, e$ by storing a seed. The bottom line is that they are usually related but not in just a single well defined way. $\endgroup$ – otus Jan 22 '16 at 8:10
  • $\begingroup$ @user4982 Key word "typically" there, what you're implying is technically false in general. The RSA public and private exponents are elements of the same group, and therefore require the same storage in general. That we prefer a small value such as 3 or 65537 is only a technical detail, and you could in fact choose randomly instead and still obtain a perfectly valid RSA key. $\endgroup$ – MickLH Dec 26 '16 at 20:01
  • $\begingroup$ @MickLH: With word "typically" I mean that it is in theory possible to have public key that is similarly sized than private key, but that is not practical or compatible. Practical: Important benefits of RSA algorithm include fast public key operations. This goes away if you use large public key. As far as compatibility goes, many of the applicable standards require public key to be significantly smaller than private key should be, for instance, FIPS 186-4 requires public key to meet $$2^{16} < e < 2^{256}$$ $\endgroup$ – user4982 Dec 28 '16 at 16:13
  • $\begingroup$ Key word "FIPS 186-4" there, what you're referring to is... exactly as you said... "FIPS 186-4", not the whole of RSA itself. When speaking of the RSA function obvio... you know what good luck with life! $\endgroup$ – MickLH Dec 29 '16 at 22:21

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.