Attaques algébriques du problème du logarithme discret sur courbes elliptiques
Institution:
Versailles-St Quentin en YvelinesDisciplines:
Directors:
Abstract EN:
The main subject of this Ph. D. Thesis is the discrete logarithm problem on elliptic curves, which is of major interest in public-key cryptography. Several new methods for solving this problem over finite field extensions are proposed. After a complete description of the GHS transfer techniques and of the decomposition attacks introduced by Gaudry and Diem, we present variants of these methods, enlarging the range of extension fields over which the elliptic curve DLP is weak. A new approach based on a combination of cover and decomposition methods is also proposed, allowing to compute discrete logarithms on elliptic curves defined over sextic extensions whose sizes had never been reached before. An important ingredient is the use of Gröbner bases for polynomial system solving. We introduce an algorithm optimized for the algebraic cryptanalysis context, that outperforms in this setting standard algorithms.
Abstract FR:
Le sujet principal de cette thèse est le problème du logarithme discret sur courbes elliptiques, d'importance pratique considérable en cryptographie asymétrique. On propose plusieurs nouvelles méthodes pour attaquer ce problème sur des extensions de corps finis. Après une description complète des techniques GHS puis des attaques par décompositions introduites par Gaudry et Diem, on présente des variantes fragilisant le DLP sur courbes elliptiques pour une gamme plus large d'extensions de corps finis. Une nouvelle approche combinant les méthodes de recouvrements et décompositions est aussi proposée : elle permet de résoudre le logarithme discret sur courbes elliptiques pour des extensions sextiques de taille jamais atteinte auparavant. Un ingrédient important est l'utilisation des bases de Gröbner pour la résolution de systèmes polynomiaux ; à cet effet, on introduit un algorithme adapté au contexte de la cryptanalyse algébrique, plus performant dans ce cadre que les algorithmes standards.