La géométrie des courbes elliptiques

La courbe et l'addition de points

Après RSA, une seconde grande famille de cryptographie à clé publique s'est imposée : celle des courbes elliptiques, qui offre la même sécurité avec des clés bien plus petites. Mais il faut d'abord comprendre l'objet géométrique sur lequel elle est bâtie.

Une courbe, une équation

Une courbe elliptique est l'ensemble des points (x, y) vérifiant une équation de la forme :

y^2 = x^3 + a*x + b

où a et b sont des constantes fixées. En les faisant varier, on obtient toute une famille de courbes. La seule condition est que la courbe soit « lisse », sans point anguleux ni croisement — techniquement, 4*a^3 + 27*b^2 != 0.

Voici l'allure d'une telle courbe :

            y
            |     .-'''-.
            |    /       \
     -------+---+---------+------ x
            |    \       /
            |     '-...-'

Remarquez la symétrie par rapport à l'axe des x : si (x, y) est sur la courbe, alors (x, -y) l'est aussi, puisque y^2 et (-y)^2 sont égaux. Cette symétrie est le cœur de tout ce qui suit.

Additionner deux points

Le miracle des courbes elliptiques, c'est qu'on peut définir une addition entre deux points de la courbe, dont le résultat est encore un point de la courbe. Cette addition n'a rien à voir avec l'addition ordinaire des coordonnées : elle est géométrique.

Pour additionner deux points P et Q :

On trace la droite qui passe par P et Q.
Cette droite recoupe la courbe en un troisième point (une cubique est coupée en trois points par une droite).
On réfléchit ce troisième point par rapport à l'axe des x. Le point obtenu est P + Q.

            y
            |        R'  (troisième intersection)
            |       *
            |   Q  /
            |  * '/
            | ' /
     -------+--/------------------- x
            | /
            |*  P
            |
            |          * P+Q  (réflexion de R')

La réflexion finale n'est pas un détail : sans elle, l'opération ne serait pas associative et ne formerait pas une structure algébrique propre.

Le cas P + P : la tangente

Comment additionner un point à lui-même ? Si P et Q sont confondus, la « droite passant par les deux » devient la tangente à la courbe en P. On prend son second point d'intersection avec la courbe, puis on le réfléchit, exactement comme avant. Le résultat est noté 2P.

Le point à l'infini

Que se passe-t-il si la droite (PQ) est verticale ? Elle relie alors P et son symétrique -P, et ne recoupe pas la courbe ailleurs. On invente pour ce cas un point spécial, le point à l'infini, noté O.

Ce point joue le rôle d'élément neutre : pour tout point P, on a P + O = P. Il est l'équivalent du zéro pour l'addition ordinaire. Le symétrique -P d'un point P est simplement son reflet (x, -y), et P + (-P) = O.

Avec cette addition, les points de la courbe forment une structure mathématique complète (un groupe commutatif), sur laquelle on va pouvoir bâtir toute une cryptographie.

En résumé