Algorithmique des courbes hyperelliptiques et applications à la cryptologie

The study of algorithmical aspects of hyperelliptic curves is the natural continuation of the case of elliptic curves, which is now well advanced. Most of the algorithms known for elliptic curves and their applications to cryptography can be more or less easily extended to Jacobians of hyperelliptic curves. In a first part, we investigate some aspects of Igusa's invariants which generalize the j-invariant of elliptic curves. For (2,2)-reducible Jacobians, we relate by explicit formulae the Igusa's invariants to the j-invariants of the quotient elliptic curves. Besides, we study these invariants by the way of Siegel modular forms with a view toward computing modular equations. The second part is dedicated to algorithms for computing the cardinality of a hyperelliptic curve over a finite field. This computation is the first step when one want to use these curves for cryptography. Beside generic algorithms which can be applied to other groups than Jacobians, we propose an effective version of à la Schoof algorithms in genus 2. We present also a first step toward an Elkies-Atkin approach, which has proven to be successful in the elliptic case. The third part deals with algorithms for discrete logarithm computations. The security of some cryptosystems relies on this problem, which is considered to be difficult: if one can solve it in a reasonable amount of time, then the system is weak. After a brief state of the art, we present some algorithms based on the classical ideas of index-calculus. Taking advantage of the particularities of the problems coming from cryptography, we demonstrate with complexity results and practical experiments that the systems based on curves of genus greater or equal to 4 are not secure. Moreover, when combined with the techniques of Weil descent, this allows to attack some elliptic cryptosystems.L'étude algorithmique des courbes hyperelliptiques est la suite naturelle de celle des courbes elliptiques qui est maintenant bien avancée. La plupart des algorithmes connus pour les courbes elliptiques ainsi que leurs applications à la cryptographie peuvent être étendus plus ou moins facilement aux Jacobiennes de courbes hyperelliptiques. Dans une première partie, nous étudions certains aspects des invariants d'Igusa, qui généralisent le j-invariant d'une courbe elliptique. Pour les Jacobiennes (2,2)-décomposables, nous relions les invariants d'Igusa aux j-invariants des courbes elliptiques quotients par des formules explicites. Par ailleurs nous étudions ces invariants sous l'angle des formes modulaires de Siegel dans le but de calculer des équations modulaires. La deuxième partie est consacrée à des algorithmes de calcul de cardinalité d'une courbe hyperelliptique sur un corps fini. Ce calcul est une étape nécessaire lorsque l'on désire mettre en oeuvre un cryptosystème hyperelliptique. Hormis les algorithmes génériques qui peuvent s'appliquer à des groupes autres que des Jacobiennes, nous proposons une version effective des algorithmes à la Schoof en genre 2. Nous présentons aussi un premier pas vers des améliorations du type Elkies-Atkin, qui ont fait leur preuve dans le cas des courbes elliptiques. La troisième partie traite d'algorithmes de calcul de logarithme discret. Ce problème, réputé difficile, est la clef de voûte des cryptosystèmes: si l'on sait le résoudre en temps raisonnable, le système est fragile. Après un bref état de l'art, nous présentons des algorithmes utilisant les idées classiques de calcul d'index. En tirant parti des spécificités des problèmes provenant de la cryptographie, nous démontrons par des résultats de complexité ainsi que des expériences pratiques que les systèmes à base de courbes de genre supérieur ou égal à 4 ne sont pas sûrs. De plus, combiné avec les techniques de descente de Weil, ceci permet d'attaquer certains cryptosystèmes elliptiques