An attack on RSA given a small fraction of the private key bits
Authors: D. Boneh, G. Durfee, and Y. Frankel
Abstract:
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.
Reference:
In proceedings AsiaCrypt '98,
Lecture Notes in Computer Science, Vol. 1514, Springer-Verlag,
pp. 25--34, 1998
Full paper: PostScript