Partial Key Exposure on RSA with Private Exponents Larger Than N

Marc Joye Tancrède Lepoint 1, 2
2 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.
Type de document :
Communication dans un congrès
Mark D. Ryan; Ben Smyth; Guilin Wang. ISPEC 2012 - 8th International Conference Information Security Practice and Experience, Apr 2012, Hangzhou, China. Springer, 7232, pp.369-380, 2012, lncs. 〈10.1007/978-3-642-29101-2_25〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01111656
Contributeur : Brigitte Briot <>
Soumis le : vendredi 30 janvier 2015 - 17:02:03
Dernière modification le : jeudi 11 janvier 2018 - 01:49:23

Identifiants

Collections

Citation

Marc Joye, Tancrède Lepoint. Partial Key Exposure on RSA with Private Exponents Larger Than N. Mark D. Ryan; Ben Smyth; Guilin Wang. ISPEC 2012 - 8th International Conference Information Security Practice and Experience, Apr 2012, Hangzhou, China. Springer, 7232, pp.369-380, 2012, lncs. 〈10.1007/978-3-642-29101-2_25〉. 〈hal-01111656〉

Partager

Métriques

Consultations de la notice

82