Reconstructing RSA Private Keys from Random Key Bits
The authors 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. They make new observations about the structure of RSA keys that allow their algorithm to make use of the redundant information in the typical storage format of an RSA private key. Their algorithm itself is elementary and does not make use of the lattice techniques used in other RSA key reconstruction problems.