An attack on RSA given a small fraction of the private key bits

Authors: D. Boneh, G. Durfee, and Y. Frankel

We show that for low public exponent RSA, given a quarter of the bits of the private key an adversary can recover the entire private key. Similar results (though not as strong) are obtained for larger values of e. For instance, when e is a prime in the range [N^{1/4},N^{1/2], half the bits of the private key suffice to reconstruct the entire private key. Our results point out the danger of partial key exposure in the RSA public key system.

In proceedings AsiaCrypt '98, Lecture Notes in Computer Science, Vol. 1514, Springer-Verlag, pp. 25--34, 1998

Full paper: PostScript