Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question
    
do you speak of textbook RSA encryption? –  DrLecter Feb 19 at 15:24
    
@DrLecter Yes. Let's account padding as just part of plaintext. –  catpnosis Feb 19 at 15:26
1  
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. –  fgrieu Feb 19 at 15:46
1  
@fgrieu Thanks, I corrected my statement. Reference imgur.com/a/ozrQo –  catpnosis Feb 19 at 16:09
    
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. –  fgrieu Feb 19 at 17:13

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.