8
$\begingroup$

Consider the following:

  1. $i$th message, $m_i$, in its original state.
  2. $i$th message, $M_i$, encrypted message $m_i$ using public key.
  3. Public key, $p$, in a $b$-bit RSA encryption setup. We can access it at all times.
  4. Secret key, $s$.
  5. Signature, signed by $s$. We will denote it as $sg$.

The scenario is such that we are presented with an encrypted message $M$, the public key with which it was encrypted, and the message $m$, which has been decrypted using the secret key and returned to its original state. We also have a signature, signed as $sg$.

I understand that given simply $m_i$, $M_i$, and $p$, it is not possible to work backwards to obtain $s$. However, would it be possible to work backwards and obtain the secret key $s$ given enough instances of corresponding messages? Suppose we are given pairs of messages, $(m_1, M_1), (m_2, M_2), \ldots (m_n, M_n)$, then would we get anywhere nearer towards obtaining the secret key (or maybe even increase our chances for a bruteforce search) as we approach a certain $n$? In that case how high an $n$ are we talking about?

Now consider we can vary $n$ to as much as we want. $n \rightarrow \infty$ Essentially, we have been given a frontend for the RSA implementation such that we can give it a message and it will return the encrypted message to us, as many times as we want but will not reveal $s$ (obviously). In this case, will we be able to reverse engineer $s$?

I have recently got to know about asymmetric encryption and these questions are a part of understanding it better, so I would appreciate it if anyone can offer some valuable insights!

$\endgroup$
  • 2
    $\begingroup$ You generally should not use the same key for both encryption and signature, because you then are open to attacks like "please decrypt this thing" (which actually signs it) or the other way around. However, this doesn't allow to recover the key. $\endgroup$ – Paŭlo Ebermann Feb 12 '17 at 16:31
  • $\begingroup$ @PaŭloEbermann thanks for your comment. Could you give me an example of how such an attack would work? I do not understand its mechanism. For instance, if someone sent me a file saying "please decrypt", and I attempt to decrypt it, wouldn't I simply obtain a bunch of nonsensical data? Or if I'm using, say, GnuPG, wouldn't it just tell me that "there's no valid encryption data in this file"? $\endgroup$ – Aalok Feb 12 '17 at 16:34
10
$\begingroup$

In RSA, assuming knowledge of the public key but not the private key, analyzing any number of triplets of matching message, encrypted message, and signature $(m,M,sg)$, does not help (as far as we know) towards recovering the private key $s$ (nor an equivalent). That's regardless of the sensible padding or RSA variant used (as long as neither the padding nor choice of $m$, $M$, or $sg$ directly leak information about the private key, e.g. in some supposedly truly random padding field that really is not).

In fact, the stronger hypothesis that one with knowledge of the public key also temporarily can use a black box containing the private key $s=(N,d)$ that freely allows computing the raw RSA private key function $x\to x^d\bmod N$ for any $x$ (which in turn allows decrypting or signing any message), does not (as far as we know) help in any way towards finding a private key, nor factorizing $N$, nor otherwise building a black box independent of the original one computing the raw RSA private key function $x\to x^d\bmod N$ for random $x$ with sizable odds.

There is no proof of that; proving (or disproving) it is an open research problem.

Note: as pointed in another answer, access to a "frontend for the RSA implementation such that we can give it a message and it will return the encrypted message" demonstrably does not help, for it is possible to perform the same using the public key, with cost growing slower than $O(b^3)$. However, the question mentions that we are also given some signature, and we lack a proof that this does not help.


All the attacks on RSA that we know:

  • decipher or sign messages without finding a private key (only if improper use of RSA is made, e.g. poor encryption or signature padding);
  • or find a private key from the public key (typically, by computing a private exponent from the public exponent and the factors of the public modulus $N$, recovered by factorization, because $N$ was too small or its factors improperly chosen);
  • or extract the/a private key using some information leak.
$\endgroup$
  • $\begingroup$ Thank you for your answer. However, one aspect is still not clear to me: will having arbitrarily large number of $m_i,M_i$ pairs yield us any advantage at all in a bruteforce attempt to crack $s$? Additionally, how would an arbitrary number of $sg_i$ signatures help in this case, or is that not yet known/proven either? $\endgroup$ – Aalok Feb 13 '17 at 16:38
  • 1
    $\begingroup$ @zakoda: The answer is NO to both of your questions above (with additional reasonable assumptions about how the pairs are chosen). That follows from the first paragraph of the answer, and is valid for any variant of RSA, including using insecure padding. For the first question, there's a generic argument for any asymmetric encryption scheme, given in the first sentence of the note. For the second question, that's a conjecture, as told in the third paragraph of the answer, and is quite specific to RSA and secure signature schemes. $\endgroup$ – fgrieu Feb 13 '17 at 17:16
  • 1
    $\begingroup$ If you know the public key $(N,e)$, you can generate as many pairs as you want. So just knowing any pairs does not help at all. However, "arbitrary large number" is hard to grasp - especially if you consider that polynomially limited attackers can only process a polynomial number of those pairs. $\endgroup$ – tylo Feb 13 '17 at 17:19
2
$\begingroup$

Such a sequence of message pairs $(m_i,M_i)$ is obviously not sufficient to obtain the private key, because if you have my public key, you can generate as many such pairs as you like.

$\endgroup$
  • 3
    $\begingroup$ Adding some required hypothesis (that neither the padding, choice of plaintext or ciphertext leak information about the private key), the argument in that answer is valid for given plaintext/ciphertext pairs. But the question mentions "We also have a signature, signed as $sg$"; and with that, the argument that we can not obtain the private key falls apart; in particular it can fail for Rabin signature (a close cousin of RSA with $e=2$), sometimes quite sneakily. $\endgroup$ – fgrieu Feb 12 '17 at 20:40
  • $\begingroup$ The question is not clear about this: do we have a signature $sg_i$ for each plaintext $m_i$? $\endgroup$ – TonyK Feb 12 '17 at 20:57
  • $\begingroup$ Agreed, the question in unclear on that. Also, it says "we have been given a frontend for the RSA implementation such that we can give it a message and it will return the encrypted message to us", that's an encryption oracle, redundant with the public key. So it is plausible that the intention in the question really is a decryption or/and signing oracle; and nothing is told about padding. I elected to answer a large class of what could be meant by the question. Your reasoning holds if the adversary is deprived from any signature, and of the ability to decipher a single chosen message. $\endgroup$ – fgrieu Feb 12 '17 at 21:14
  • $\begingroup$ @TonyK would the answer change if you had $sg_i \foreach m_i,\:M_i$? $\endgroup$ – Aalok Feb 13 '17 at 2:30

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.