Skip to Main content Skip to Navigation
Conference papers

Partial Key Exposure on RSA with Private Exponents Larger Than N

Marc Joye 1 Tancrède Lepoint 2, 3 
3 CASCADE - Construction and Analysis of Systems for Confidentiality and Authenticity of Data and Entities
DI-ENS - Département d'informatique - ENS Paris, Inria Paris-Rocquencourt, CNRS - Centre National de la Recherche Scientifique : UMR 8548
Abstract : In 1998, Boneh, Durfee and Frankel described several attacks against RSA enabling an attacker given a fraction of the bits of the private exponent d to recover all of d. These attacks were later improved and extended in various ways. They however always consider that the private exponent d is smaller than the RSA modulus N. When it comes to implementation, d can be enlarged to a value larger than N so as to improve the performance (by lowering its Hamming weight) or to increase the security (by preventing certain side-channel attacks). This paper studies this extended setting and quantifies the number of bits of d required to mount practical partial key exposure attacks. Both the cases of known most significant bits (MSBs) and least significant bits (LSBs) are analyzed. Our results are based on Coppersmith’s heuristic methods and validated by practical experiments run through the SAGE computer-algebra system.
Document type :
Conference papers
Complete list of metadata
Contributor : Brigitte Briot Connect in order to contact the contributor
Submitted on : Friday, January 30, 2015 - 5:02:03 PM
Last modification on : Thursday, March 17, 2022 - 10:08:38 AM




Marc Joye, Tancrède Lepoint. Partial Key Exposure on RSA with Private Exponents Larger Than N. ISPEC 2012 - 8th International Conference Information Security Practice and Experience, Apr 2012, Hangzhou, China. pp.369-380, ⟨10.1007/978-3-642-29101-2_25⟩. ⟨hal-01111656⟩



Record views