La signature courte de Boneh Lynn et Shacham

Le début de l’histoire avec Diophante

Les courbes elliptiques sont de vieux objets d’etude mathematique. Outre la geometrie algebrique d’ou elles proviennent, ces courbes apparaissent aussi bien en theorie des nombres qu’en analyse. On verra dans cette these quelques applications de leur loi de groupe en cryptographie, mais on peut noter qu’elles interviennent egalement en mecanique des fluides, science des materiaux ou electrostatique. Pour resumer la riche histoire de ces courbes, je me suis base sur [24], [46], [8], [40]. La premiere apparition de ces courbes se trouve dans l’oeuvre la plus importante du mathematicien grec du IIIieme siecle Diophante : les Arithmétiques. Cette somme en 13 livres ne sera « redecouverte » en occident qu’apres la chute de Constantinople. Apres plus de 1000 ans d’absence, cet ouvrage influencera enormement les savants de la Renaissance et du siecle des Lumieres, faisant par exemple reflechir Newton ou Euler. Fermat travailla beaucoup sur les problemes poses par Diophante : c’est d’ailleurs dans une traduction latine de ces Arithmétiques que Fermat livrera en annotations son fameux dernier theoreme. Mais n’allons pas trop vite, et revenons a Diophante.

Diophante etudia a la Bibliotheque d’Alexandrie les mathematiques de son epoque : geometrie, trigonometrie, mecanique. Il s’interessa a trouver des methodes de construction (aujourd’hui on dirait des algorithmes) de solutions rationnelles a des equations algebriques a plusieurs variables. C’est dans ce cadre qu’il inventa, sans le savoir, la methode « corde-et-tangente » pour l’addition sur une courbe. Pour comprendre ce coup de force, prenons d’abord l’exemple des equations quadratiques. C’est un probleme bien plus vieux que Diophante : les babyloniens par exemple connaissaient deja les triplets pythagoriciens 1. Diophante fit pourtant une decouverte importante : Proposition 0.1.1. Soit f(x, y) ∈ Q[x, y] un polynôme quadratique. Si l’équation f(x, y) = 0 admet au moins une solution rationnelle, alors elle en admet une infinité. En effet, si on note P cette solution initiale, alors toute droite de pente rationnelle coupe la courbe d’equation f(x, y) = 0 en une autre solution rationnelle. Diophante appliqua cette meme methode aux cubiques. Plus precisement, le probleme 24 du livre IV de ses Arithmétiques se reecrit de facon moderne ainsi : Etant donne un parametre a, trouver les solutions rationnelles a l’equation y(a − y) = x3 − x. Diophante traite le cas a = 6 en faisant le changement de variable x = 3y − 1 : autrement dit, Diophante a regarde l’intersection entre la courbe et sa tangente au point (−1, 0). C’est bien la methode de doublement d’un point sur une courbe elliptique. Par la suite, il faudra attendre le XVIIieme siecle pour que Fermat donne en toute generalite les formules algebriques pour l’addition et le doublement ; puis ce sera Newton qui donnera l’interpretation geometrique (corde-et-tangente) de ces formules.

Les courbes elliptiques en cryptographie

En 1976, Diffie et Hellman inventerent la cryptographie a clef publique. Encore appelee cryptographie asymetrique, elle repose sur l’existence supposee de fonctions a sens unique, qui permettent de chiffrer facilement des messages, mais dont le calcul de l’inverse doit etre impossible pour qui ne connait pas le secret. On peut grosso modo diviser les protocoles de cryptographie asymetrique en deux familles. Le tres celebre RSA, invente en 1977, fut la premiere realisation pratique a clef publique. Le protocole commence par la multiplication de deux grands nombres premiers, et repose sur la difficulte, connaissant seulement le resultat du produit, de retrouver les deux facteurs. Les protocoles de la seconde famille reposent sur le probleme suivant, dit du logarithme discret : me donnant un groupe (G,×) et deux elements g et g′ de ce groupe relies par la relation g′ = gx, comment puis je retrouver x ? Il est par exemple a la base du protocole d’echange de clefs Diffie-Hellman (1976) ou du chiffrement Elgamal (1989). Dans les implementations originales de ces protocoles, le groupe utilise est le groupe multiplicatif d’un corps fini F∗ p, pour un grand premier p. En 1985, Koblitz et Miller proposerent tous deux de facon independante d’utiliser un autre groupe : celui des points d’une courbe elliptique definie sur un corps fini. La raison a cela est l’absence d’algorithme en temps sous-exponentiel pour attaquer le probleme du logarithme discret sur ces groupes (plus de details sont donnes dans le chapitre 4).

Ainsi, a niveau de securite egal, la taille du groupe de points d’une courbe elliptique a utiliser est plus petite que celle du groupe multiplicatif d’un corps fini. En pratique, cela signifie de plus petites tailles de clefs et de messages chiffres echanges. Ces avantages sont particulierement significatifs dans le domaine des systemes embarques qui sont tres restreints en capacite de memoire et de borne passante. Comme rappele dans [26], la cryptographie basee sur courbes elliptiques 3 divisa d’abord les cryptographes : du fait de son exotisme (les courbes elliptiques etant alors peu connues et peu etudiees par les cryptographes), elle suscita chez certains enthousiasme et curiosite, et chez d’autres scepticisme et mefiance. Ces derniers arguerent que les problemes de la factorisation et du logarithme discret sur corps finis avaient ete a ce moment la deja intensivement etudies, et qu’il faudrait at- tendre un certain temps avant que la communaute cryptographique s’empare et comprenne vraiment la nature des courbes elliptiques. Ainsi, ECDSA (Elliptic Curve Digital Signature Algorithm), propose en 1992 ([51]), ne fut finalement unanimement accepte et inclus dans les standards que presque 10 ans plus tard (en 2000 par la NSA : [37]). Finalement, juste quand l’utilisation des courbes elliptiques en cryptographie fut bien acceptee, apparurent les premiers protocoles bases sur les couplages 4. Vieil outil mathematique, le couplage de Weil n’etait pas a ce moment la inconnu des cryptographes, puisque Menezes, Okamoto et Vanstone dans [32] en 1993 avaient deja montre comment transporter le probleme du logarithme discret des points d’une courbe elliptique vers un groupe F∗ qk (ici k est le degre de plongement, notion definie dans le chapitre 1).

Cet article avait d’ailleurs a l’epoque jete un peu plus la suspicion sur les courbes elliptiques, notamment celles de petit degre de plongement. Ces nouveaux protocoles ([25], [6] et [7], presentes plus en detail au chapitre 1) marquerent les esprits en repondant de facon simple et elegante a de vieilles questions cryptographiques. Ainsi, les schemas d’echange de clef Diffie-Helman etaient bien connus et etudies avant Joux ([25]), mais ils necessitaient tous plus d’un tour d’echanges de donnees. Quant au chiffrement base sur l’identite, c’est une vielle question posee par Shamir en 1984 a laquelle Boneh et Franklin ([6]) repondirent pour la premiere fois. Ces articles ouvrirent une decennie de recherches actives sur les couplages : constructions de nouvelles primitives cryptographiques, impossibles sans l’utilisation de couplages, nouvelles techniques pour accelerer le calcul de couplages, nouvelles methodes de selections de courbes adaptees aux couplages (au passage, les courbes admettant un petit degre de plongement furent a cette occasion rehabilitees)… En 1989, soit quelques annees seulement apres l’introduction des courbes elliptiques en cryptographie, Koblitz suggera pour la premiere fois dans [27] d’utiliser leurs generalisations aux genres plus eleves : les courbes hyperelliptiques. Contrairement a la situation dans le cas elliptique, l’ensemble des points de ces courbes ne forme pas un groupe. Par contre, on peut toujours associer a chacune de ces courbes un groupe algebrique : sa jacobienne (la definition precise, et plus de details seront donnes dans le chapitre 1). L’interet de considerer ces nouveaux groupes reside dans leur cardinal : en effet, une courbe hyperelliptique de genre g definie sur un corps fini Fq admet une jacobienne de cardinal environ qg. Ainsi, utiliser une courbe de grand genre permet, a niveau de securite comparable, de travailler sur des corps finis plus petits, et ainsi de diminuer la taille des clefs et Quatre articles à la genèse d’une thèse en deux parties