It is known, for example, that exposing 50% of the most significant bits of RSA private exponent does not provide security risk (when a small public exponent is used). So how to qualify security degradation of partial exposure of plaintext in RSA encryption? Can we say, for example, that exposing 50% of plaintext does not reduce security? And, is there a limit when it starts to actually reduce it?

I think that, probably, the answer should be related to 1) how many remaining bits are left to brute force (if 99% of plaintext is exposed it will be easy to just brute force the remaining 1%, so if non-exposed bits size is above 128 then security is 'not reduced'), and maybe 2) exposure for Coppersmith’s methods (if non-exposed bits size is more than $N^{1/e}$ than security is not degraded), but this should not even be relevant for $e=65537$ which is common.

Thus, can we say that the security of partial plaintext exposure of properly done RSA encryption is bound to as much is left for brute force?

  • $\begingroup$ do you speak of textbook RSA encryption? $\endgroup$
    – DrLecter
    Feb 19 '14 at 15:24
  • $\begingroup$ @DrLecter Yes. Let's account padding as just part of plaintext. $\endgroup$
    – catpnosis
    Feb 19 '14 at 15:26
  • 1
    $\begingroup$ Any pointer, or better short proof, that "exposing 50% of most significant bits of RSA private exponent does not provide security risk"? It seems there could be some additional conditions not stated here for this to hold. $\endgroup$
    – fgrieu
    Feb 19 '14 at 15:46
  • 1
    $\begingroup$ @fgrieu Thanks, I corrected my statement. Reference imgur.com/a/ozrQo $\endgroup$
    – catpnosis
    Feb 19 '14 at 16:09
  • 1
    $\begingroup$ It could be that "exposing 1/2 of the most significant bits of the private exponent is not a security risk when a small exponent is used" in your reference (with no accompanying proof) is to be read in the meaning it would have in the work of the Boneh et al. references cited; that is disclosing$$\big\lfloor d/2^{\lceil\log_2(N)/2\rceil}\big\rfloor.$$Conceivably, that could make some difference with disclosing$$\big\lfloor d/2^{\lceil\log_2(d)/2\rceil}\big\rfloor$$when $d=e^{−1}\bmod λ(n)$, and $p−1$, $q−1$ share a big factor, which can be by design, or (with not so small odd) by accident. $\endgroup$
    – fgrieu
    Feb 19 '14 at 17:13

Your Answer

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

Browse other questions tagged or ask your own question.