Pseudo-Random Generators and Pseudo-Random Functions: Cryptanalysis and Complexity Measures

Thierry Mefenza Nountu 1, 2, 3
1 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
Résumé : L’aléatoire est un ingrédient clé en cryptographie. Par exemple, les nombres aléatoires sont utilisés pour générer des clés, pour le chiffrement et pour produire des nonces. Ces nombres sont générés par des générateurs pseudo-aléatoires et des fonctions pseudo-aléatoires dont les constructions sont basées sur des problèmes qui sont supposés difficiles. Dans cette thèse, nous étudions certaines mesures de complexité des fonctions pseudo-aléatoires de Naor-Reingold et Dodis-Yampolskiy et étudions la sécurité de certains générateurs pseudo-aléatoires (le générateur linéaire congruentiel et le générateur puissance basés sur les courbes elliptiques) et de certaines signatures à base de couplage basées sur le paradigme d’inversion. Nous montrons que la fonction pseudo-aléatoire de Dodis-Yampolskiy est uniformément distribué et qu’un polynôme multivarié de petit dégré ou de petit poids ne peut pas interpoler les fonctions pseudo-aléatoires de Naor-Reingold et de Dodis-Yampolskiy définies sur un corps fini ou une courbe elliptique. Le contraire serait désastreux car un tel polynôme casserait la sécurité de ces fonctions et des problèmes sur lesquels elles sont basées. Nous montrons aussi que le générateur linéaire congruentiel et le générateur puissance basés sur les courbes elliptiques sont prédictibles si trop de bits sont sortis à chaque itération. Les implémentations pratiques de cryptosystèmes souffrent souvent de fuites critiques d’informations à travers des attaques par canaux cachés. Ceci peut être le cas lors du calcul de l’exponentiation afin de calculer la sortie de la fonction pseudo-aléatoire de Dodis-Yampolskiy et plus généralement le calcul des signatures dans certains schémas de signatures bien connus à base de couplage (signatures de Sakai-Kasahara, Boneh-Boyen et Gentry) basées sur le paradigme d’inversion. Nous présentons des algorithmes (heuristiques) en temps polynomial à base des réseaux qui retrouvent le secret de celui qui signe le message dans ces trois schémas de signatures lorsque plusieurs messages sont signés sous l’hypothèse que des blocs consécutifs de bits des exposants sont connus de l’adversaire.
Type de document :
Thèse
Computer Science [cs]. Paris Sciences et Lettres, 2017. English
Liste complète des métadonnées

Littérature citée [126 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/tel-01667124
Contributeur : Thierry Mefenza Nountu <>
Soumis le : mardi 19 décembre 2017 - 10:15:07
Dernière modification le : jeudi 11 janvier 2018 - 06:22:10

Fichier

thèse Thierry Mefenza.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : tel-01667124, version 1

Collections

Citation

Thierry Mefenza Nountu. Pseudo-Random Generators and Pseudo-Random Functions: Cryptanalysis and Complexity Measures. Computer Science [cs]. Paris Sciences et Lettres, 2017. English. 〈tel-01667124〉

Partager

Métriques

Consultations de la notice

46

Téléchargements de fichiers

23