programme Pierrick Gaudry

Pierrick Gaudry (École Polytechnique): Cryptographie asymétrique basée sur le problème du logarithme discret

Algorithmes de logarithme discret dans un groupe générique:

Un groupe générique est un groupe dont la loi de groupe est donnée par une boite noire. Dans ce contexte, on dispose d'une borne inférieure (exponentielle) pour le problème du logarithme discret, ainsi que d'algorithmes atteignants cette borne.

Quelques algorithmes cryptographiques basés sur le log discret:

Nous expliquerons brièvement le fonctionnement d'algorithmes de chiffrement, de signature et d'échange de clefs qui utilisent comme paramètre un groupe abélien fini dans lequel le problème du log discret est supposé difficile. Pour ces algorithmes, si le groupe se comporte comme un groupe générique, les seules attaques sont exponentielles, ce qui permet d'avoir de petites clefs.

Les groupes multiplicatifs de corps finis:

Les premiers exemples de groupe abélien fini ou le log discret n'est pas facile sont les groupes multiplicatifs de corps finis. Ils présentent l'avantage d'être très simple d'utilisation, mais malheureusement il existe des attaques en temps sous-exponentielles que nous tenterons d'expliquer.

Les courbes elliptiques

Les courbes elliptiques définies sur un corps fini fournissent une alternative intéressante aux groupes multiplicatifs. En effet, sauf dans quelques cas bien reconnaissables, il n'y a pas d'algorithme meilleur que les algorithmes génériques pour résoudre le log discret. Toutefois de nouveaux problèmes surgissent: - comment calculer le plus efficacement possible la loi de groupe - comment connaître le cardinal du groupe (c'est une donnée essentielle pour la sécurité) Nous ferons un survol des méthodes disponibles et insisterons éventuellement sur un algorithme particulier.

Les courbes hyperelliptiques

D'une manière générale, toute courbe algébrique définie sur un corps fini fournit un groupe abélien fini: sa jacobienne. Les courbes hyperelliptiques sont les plus simples algorithmiquement, après les courbes elliptiques. C'est pourquoi elles furent aussi très tot proposées pour un usage cryptographique. La loi de groupe et le problème du comptage de points sont un peu plus complexes. D'autre part, lorsque le genre (lié au degré de l'équation) devient grand, on retrouve des attaques sous-exponentielles, comme pour les corps finis.

Retour École de Cryptologie.