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 de l'École normale supérieure, 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

https://hal.inria.fr/hal-01111656
Contributor : Brigitte Briot <>
Submitted on : Friday, January 30, 2015 - 5:02:03 PM
Last modification on : Thursday, July 1, 2021 - 5:58:06 PM

Identifiers

Collections

Citation

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⟩

Share

Metrics

Record views

268