zbMATH — the first resource for mathematics

Reconstructing RSA private keys from random key bits. (English) Zbl 1252.94072
Halevi, Shai (ed.), Advances in cryptology – CRYPTO 2009. 29th annual international cryptology conference, Santa Barbara, CA, USA, August 16–20, 2009. Proceedings. Berlin: Springer (ISBN 978-3-642-03355-1/pbk). Lecture Notes in Computer Science 5677, 1-17 (2009).
Summary: 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.
For the entire collection see [Zbl 1173.94004].

94A60 Cryptography
Full Text: DOI