Le groupe d'une courbe elliptique (étude élémentaire)

Les courbes elliptiques sont très utiles, à travers les structures de groupe qu’on peut y définir. En particulier, ils permettent de créer une méthode de cryptographie à clef publique analogue à la méthode RSA. Ici, nous nous proposons de le décrire de façon très élémentaire.
 
Une courbe elliptique est une courbe d’équation : y² = x^3 + a x + b où a et b sont des nombres réels. Si a < 0 et 4 a^3 + 27 b² < 0, son allure est donnée ci-dessous.

​On lui adjoint un point fictif dit point à l’infini que l’on note ici 0. Une construction géométrique permet alors de définir une loi interne sur une telle courbe : On note PQ la droite PQ si P ¹ Q et la tangente en P sinon. Si PQ recoupe la courbe en un point R, on note P + Q le point où la verticale en R la recoupe. Sinon, on pose P + Q = 0. De même, on pose : P + 0 = P.
Des calculs algébriques sont nécessaires pour montrer que cette loi munit bien la courbe elliptique d’une loi de groupe.
La généralité des calculs
Plus précisément, si P et Q sont distincts et ont pour coordonnées (xP, yP) et (xQ, yQ) tels que xQ différent de xP, une équation paramétrique de PQ est

Ce point appartient à la courbe elliptique si t est solution d’une équation du troisième degré dont le coefficient de degré 3 est (xP – xQ)^3 et celui de degré 2, 3 xQ (xP – xQ)² – (yP – yQ)². P et Q correspondent aux racines 0 et 1 de cette équation, l’autre (que nous noterons t) est donnée par la somme des racines égale à t + 1 d’un côté et au quotient de (yP – yQ)² –3 xQ (xP – xQ)² par (xP – xQ)^3 de l’autre. On en déduit t puis xR et yR d’abord et les coordonnées (xP+Q, yP+Q) de P +Q sont :

​

En tenant compte de y² = x^3 + a x + b, on trouve :

​On en déduit une formule valable même si P = Q. Cette formule a de plus le mérite de garder un sens dans un corps quelconque. Nous avons simplement besoin de conserver l’hypothèse 4 a^3 + 27 b² non nul et d’utiliser un corps de caractéristique différente de 2 et de 3.
Structure de groupe
À partir de ces formules, on démontre facilement que la loi est commutative, que O est élément neutre, que le symétrique du point P par rapport à l’axe des x est son symétrique pour la loi +. En fait, seule l’associativité est délicate à démontrer, ou plutôt longue et fastidieuse mais on peut la faire avec un logiciel de calcul formel puisqu’il s’agit de démontrer que les deux points (P + Q) + R et P + (Q + R) sont confondus.
Chiffrement
Les courbes elliptiques sur des corps Z/ N (avec N premier) permettent de définir des méthodes de cryptographie à clef publique analogue au système RSA. L’idée de départ est qu’un texte peut être transformé en une suite de points de la courbe. Cela revient à écrire dans un alphabet ayant autant de signes que la courbe a de points. Notons que le problème sous-jacent n’a rien de simple mais, théoriquement, la question est de transformer un point M de la courbe.

La clef secrète est constituée d’un point P de la courbe et d’un entier k. On calcule ensuite P ’ = k P. La clef publique est alors le couple de points (P, P ’). Pour chiffrer un point M, le chiffreur choisit un entier l et transmet le couple (U, V) défini par : U = l P et V = M + l P ’.
La connaissance de k suffit pour retrouver M : M = V – k U.
Il est facile de voir qu’elle est même nécessaire.
Logarithme discret
Pour retrouver k connaissant P et P ’, il suffit de savoir résoudre l’équation : P ’ = k P.
Ce nombre k est appelé logarithme discret ce qui n’est guère intuitif si on utilise la notation additive ci-dessus. Avec une notation multiplicative de la loi du groupe, cela devient plus habituel puisque l’équation s’écrit alors :
P ’ = Pk.
Dans le corps des réels, k correspondrait alors au logarithme de base P de P ’ d’où le nom dans le cadre d’un groupe fini.

À l’heure actuelle, ce problème est considéré comme très difficile. On estime qu’une clef de 200 bits (valeur de N) pour les courbes elliptiques est plus sûre qu’une clef de 1024 bits pour la méthode RSA. Comme les calculs sur les courbes elliptiques ne sont pas compliqués à réaliser, c’est un gros avantage pour les cartes à puces où on dispose de peu de puissance, et où la taille de la clef influe beaucoup sur les performances. Les inconvénients sont de deux ordres. D’une part, la théorie des fonctions elliptiques est complexe et relativement récente. Il n’est pas exclu que l’on puisse contourner le problème du logarithme discret. D’autre part, la technologie de cryptographie par courbe elliptique a fait l’objet du dépôt de nombreux brevets à travers le monde. Cela pourrait rendre son utilisation coûteuse !