Mise en œuvre de cryptosystèmes basés sur les codes correcteurs d’erreurs et de leurs cryptanalyses

Résumé : Cette thèse porte sur les problèmes algorithmiques qui apparaissent lorsque l’on souhaite mettre en œuvre un cryptosystème basé sur un code correcteur d’erreur ou bien une cryptanalyse d’un tel système. L’intérêt de ces système provient de leur excellente complexité algorithmique, meilleure de plusieurs ordres de grandeurs en termes de complexité que les schémas à clé publique traditionnels. Ils fournissent éga- lement une alternative crédible aux systèmes actuels qui pour la plupart se repose sur la théorie des nombres et sur le problème de la factorisation et celui du loga- rithme discret. Outre l’absence de preuve mathématique de la réelle difficulté de ces problèmes, P. Shor a montré que ces deux problèmes pouvaient être résolus en temps polynomial dans le modèle de l’ordinateur quantique. Cet ordinateur quantique est encore loin d’être fonctionnel mais il faudra, le jour venu, disposer d’alternatives de confiance et disposant de mises en œuvre performantes. Après une section introductive apportant les notions de cryptographie et de théorie des codes correcteurs requises, cette thèse présente dans une première partie une mise en œuvre du schéma de signature CFS, schéma proposé en 2001 par N. Courtois, M. Finiasz et N. Sendrier. Ce schéma est basé sur le cryptosystème de Niederreiter et s’appuie sur le problème du décodage par syndrome ainsi que sur l’indistinguabilité des codes de Goppa binaires. L’aspect encombrant de ce schéma (clé publique de grande taille) est peut-être ce qui a freiné l’étude des problèmes liés à sa mise en œuvre. Cette partie s’efforce de montrer que malgré cela, le schéma peut être utilisé en pratique en proposant en mise en œuvre générant une signature en un temps de l’ordre de la seconde. Dans une deuxième partie est présentée une mise en œuvre de plusieurs algo- rithmes de la famille appelée Information Set Decoding. Cette famille d’algorithme est utilisée pour décoder un code linéaire de façon générique c’est-à-dire sans utiliser la potentielle structure du code. La plupart des cryptosystèmes basés sur les codes reposent leur sécurité sur la difficulté de résoudre ce problème. Il est important de trouver les algorithmes permettant de le résoudre le plus efficacement possible afin de dimensionner les cryptosystèmes. Cette partie présente une mise en œuvre de deux algorithmes de cette famille (pouvant être étendue à d’autres) et montre les résultats de ces algorithmes appliqués à des challenges cryptographiques proposés par D. Bern- stein, T. Lange et C. Peters en 2011 ainsi que leur application lors de la cryptanalyse d’un schéma de chiffrement proposé par C. Löndahl et T. Johansson en 2012.
Type de document :
Thèse
Cryptographie et sécurité [cs.CR]. Université Pierre et Marie Curie, 2014. Français
Liste complète des métadonnées

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

https://hal.inria.fr/tel-01097806
Contributeur : Grégory Landais <>
Soumis le : lundi 22 décembre 2014 - 10:44:25
Dernière modification le : vendredi 25 mai 2018 - 12:02:05
Document(s) archivé(s) le : lundi 23 mars 2015 - 19:11:36

Fichier

Identifiants

  • HAL Id : tel-01097806, version 1

Collections

Citation

Grégory Landais. Mise en œuvre de cryptosystèmes basés sur les codes correcteurs d’erreurs et de leurs cryptanalyses. Cryptographie et sécurité [cs.CR]. Université Pierre et Marie Curie, 2014. Français. 〈tel-01097806〉

Partager

Métriques

Consultations de la notice

545

Téléchargements de fichiers

1094