Reconstructing RSA Private Keys from Random Key Bits
作者： Nadia Heninger , Hovav Shacham
DOI: 10.1007/978-3-642-03356-8_1
关键词: Public-key cryptography 、 Public exponent 、 Mathematics 、 Key size 、 Cold boot attack 、 Reboot 、 Theoretical computer science 、 Running time
摘要: 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 this work is to the "cold boot" attacks Halderman et al. make new observations about structure keys allow our algorithm use redundant information in typical storage format key. Our itself elementary and does not lattice techniques used other reconstruction problems. give analysis running time behavior matches threshold phenomenon observed experiments.
springer.com
core.ac.uk 
sci-hub.st 参考文章(22)
Alexander May, Using LLL-Reduction for Solving RSA and Factorization Problems The LLL Algorithm. pp. 315- 348 ,(2009) , 10.1007/978-3-642-02295-1_10
Alexander May, New RSA Vulnerabilities Using Lattice Reduction Methods pp. 1- 159 ,(2003)
Mathias Herrmann, Alexander May, Solving Linear Equations Modulo Divisors: On Factoring Given Any Bits international conference on the theory and application of cryptology and information security. pp. 406- 424 ,(2008) , 10.1007/978-3-540-89255-7_25
Dan Boneh, Fast Variants of RSA ,(2007)
Ronald L. Rivest, Adi Shamir, Efficient factoring based on partial information theory and application of cryptographic techniques. pp. 31- 34 ,(1986) , 10.1007/3-540-39805-8_3
Moni Naor, Gil Segev, Public-Key Cryptosystems Resilient to Key Leakage international cryptology conference. pp. 18- 35 ,(2009) , 10.1007/978-3-642-03356-8_2
Phong Q. Nguyễn, Jacques Stern, Adapting Density Attacks to Low-Weight Knapsacks Lecture Notes in Computer Science. pp. 41- 58 ,(2005) , 10.1007/11593447_3
D. Boneh, TWENTY YEARS OF ATTACKS ON THE RSA CRYPTOSYSTEM Notices of the American Mathematical Society. ,vol. 46, pp. 203- 212 ,(1999)
Krzysztof Pietrzak, A Leakage-Resilient Mode of Operation international cryptology conference. pp. 462- 482 ,(2009) , 10.1007/978-3-642-01001-9_27
Shafi Goldwasser, Cryptography without (Hardly Any) Secrets international cryptology conference. pp. 369- 370 ,(2009) , 10.1007/978-3-642-01001-9_21