Inferring Sequences Produced by Nonlinear Pseudorandom Number Generators Using Coppersmith's Methods

Aurélie Bauer 1 Damien Vergnaud 2, 3, 4 Jean-Christophe Zapalowicz 5
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
5 CELTIQUE - Software certification with semantic analysis
Inria Rennes – Bretagne Atlantique , IRISA-D4 - LANGAGE ET GÉNIE LOGICIEL
Abstract : Number-theoretic pseudorandom generators work by iterating an algebraic map F (public or private) over a residue ring ℤ N on a secret random initial seed value v 0 ∈ ℤ N to compute values for n ∈ ℕ. They output some consecutive bits of the state value v n at each iteration and their efficiency and security are thus strongly related to the number of output bits. In 2005, Blackburn, Gomez-Perez, Gutierrez and Shparlinski proposed a deep analysis on the security of such generators. In this paper, we revisit the security of number-theoretic generators by proposing better attacks based on Coppersmith's techniques for finding small roots on polynomial equations. Using intricate constructions, we are able to significantly improve the security bounds obtained by Blackburn et al..
Type de document :
Communication dans un congrès
Marc Fischlin, Johannes Buchmann & Mark Manulis. PKC 2012 - 15th International Conference on Practice and Theory in Public Key Cryptography, May 2012, Darmstadt, Germany. Springer, Lecture Notes in Computer Science, 7293, pp.609-626, 2012, Public Key Cryptography – PKC 2012. 〈10.1007/978-3-642-30057-8_36〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00871331
Contributeur : Damien Vergnaud <>
Soumis le : mercredi 9 octobre 2013 - 14:38:11
Dernière modification le : vendredi 25 mai 2018 - 12:02:05

Identifiants

Citation

Aurélie Bauer, Damien Vergnaud, Jean-Christophe Zapalowicz. Inferring Sequences Produced by Nonlinear Pseudorandom Number Generators Using Coppersmith's Methods. Marc Fischlin, Johannes Buchmann & Mark Manulis. PKC 2012 - 15th International Conference on Practice and Theory in Public Key Cryptography, May 2012, Darmstadt, Germany. Springer, Lecture Notes in Computer Science, 7293, pp.609-626, 2012, Public Key Cryptography – PKC 2012. 〈10.1007/978-3-642-30057-8_36〉. 〈hal-00871331〉

Partager

Métriques

Consultations de la notice

334