Paper 2008/510

Reconstructing RSA Private Keys from Random Key Bits

Nadia Heninger and Hovav Shacham

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. An important application of this work is to the "cold boot" attacks of Halderman et al. 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. Our algorithm itself is elementary and does not make use of the lattice techniques used in other RSA key reconstruction problems. We give an analysis of the running time behavior of our algorithm that matches the threshold phenomenon observed in our experiments.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Extended abstract in the proceedings of Crypto 2009
Keywords
RSAcold bootcryptanalysisbranching process
Contact author(s)
hovav @ cs ucsd edu
History
2010-02-26: last of 4 revisions
2008-12-02: received
See all versions
Short URL
https://ia.cr/2008/510
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2008/510,
      author = {Nadia Heninger and Hovav Shacham},
      title = {Reconstructing RSA Private Keys from Random Key Bits},
      howpublished = {Cryptology ePrint Archive, Paper 2008/510},
      year = {2008},
      note = {\url{https://eprint.iacr.org/2008/510}},
      url = {https://eprint.iacr.org/2008/510}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.