Reconstructing RSA Private Keys from Random Key Bits

By Nadia Heninger and Hovav Shacham.

In Proceedings of Crypto 2009, vol. 5677 of LNCS. pages 1–17. Springer-Verlag, Aug. 2009.

Abstract

We show that an RSA private key with small public exponent can be efficiently recovered given a 0.27 fraction of its bits at random. We make new observations about the structure of RSA keys that allow our algorithm to make use of the redundant information in the typical storage format of an RSA private key. We give an analysis of the running time behavior of our algorithm that closely matches the sharp threshold phenomenon observed in our experiments.

Material

Reference

@InProceedings{HS09, author = {Nadia Heninger and Hovav Shacham}, title = {Reconstructing {RSA} Private Keys from Random Key Bits}, booktitle = {Proceedings of Crypto 2009}, editor = {Shai Halevi}, series = {LNCS}, year = 2009, month = aug, publisher = {Springer-Verlag}, volume = 5677, pages = {1-17} }

Navigation: Hovav Shacham // Publications // [HS09]