It is known, for example, that exposing 50% of most significant bits of RSA private exponent does not provide security risk (when a small public exponent it 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 limit when it start to actually reduce it?

I think that, probably, answer should be related to 1) how much remaining bits is left to brute force (if 99% of plaintext is exposed it will be easy to just brute force 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 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
  • $\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.