Courbes elliptiques

De quoi sont les courbes elliptiques ?

Pour faire court, ce sont, du troisième degré, les courbes planes non singulières, autrement dit, les courbes définies par une équation $P(x,y)=0$, où $P$ est un polynôme de degré 3 en au moins une des variables, et qui admettent en chaque point une tangente unique (ce qui exclut par exemple le folium de Descartes $x^3+y^3=3axy$ (un point double : cubique nodale) ou la parabole semi-cubique $y^2−x^3=0$ (une tangente double au point anguleux), ainsi que toutes le courbes qui se décomposent en une droite et une conique.

On peut faire quelques dessins avec jupyter, sympy et matplotlib.

In [1]:
from sympy import *
from sympy.plotting import plot, plot_parametric
import math
import numpy as np
import matplotlib.pyplot as plt
In [2]:
%matplotlib inline 
In [3]:
var('x y')
Out[3]:
(x, y)
In [8]:
# Une courbe elliptique
p1 = plot_implicit(Eq(y**2,x**3-3*x))
In [9]:
# Folium de Descartes
p2 = plot_implicit(Eq(x**3+y**3,6*x*y))
In [10]:
# Parabole semi-cubique
p3 = plot_implicit(Eq(y**2-x**3,0))
In [11]:
# Autre courbe elliptique
p4 = plot_implicit(Eq(y**2,x**3-x+1))

La classification des courbes planes du troisième degré est très compliquée.

Pour simplifier les choses, les mathématiciens leur rajoutent deux sortes de points : les points imaginaires et les points à l'infini. La définition des points imaginaires est naturelle : on autorise les variables $x,y$ à prendre des valeurs complexes, et on voit donc la courbe comme un sous-ensemble de ${\mathbb C}^2$.

La définition des points à l'infini est un peu plus subtile : on imagine notre plan comme étant le plan $z=1$ dans l'espace à 3 dimensions, on remplace l'équation de la courbe par celle du cône d'origine O qui s'appuie sur elle, un polynôme homogène du troisième degré $\hat P(x,y,z)=0$, tel que $\hat P(x,y,1)=P(x,y)$.

Par exemple, pour la courbe elliptique $y^2+x^3+x=0$, on a l'équation (dite projective) $y^2z+x^3+xz^2=0$. On identifie deux triplets $(x,y,z)$ et $(x′,y′,z′)$ s'il sont proportionnels : $(x′,y′,z′)=(ax,ay,az)$. L'ensemble des classes de triplets non nuls de nombres complexes est appelé plan projectif complexe. Ceux pour lesquels $z\not=0$ correspondent aux points ordinaires de notre courbe. Ceux pour lesquels $z=0$ sont nouveaux, ce sont les points à l'infini.

Pourquoi cette construction ? L'introduction des points imaginaires permet d'éliminer les discussions sur le nombre de racines des équations. Celle des points à l'infini élimine la question des asymptotes. Par exemple, la classification projective des courbes du second degré ne contient plus que trois cas. En effet, un polynôme homogène de degré 2 peut soit ne pas se factoriser (une conique), soit être un produit de deux polynômes du premier degré distincts (deux droites sécantes), soit enfin être le carré d'un polynôme du premier degré (une droite double). Au niveau projectif, il n'y a plus de distinction entre les trois types de coniques. Si on choisit une projection (par exemple le plan $z=1$) pour regarder la courbe, alors, elle pourra ne pas avoir de point à l'infini réel (ellipse), en avoir un (parabole) ou deux (hyperbole). On ne distingue pas non plus les droites sécantes ou parallèles (les parallèles se coupent à l'infini), etc. Donc, en géométrie projective, c'est beaucoup plus simple.

Pourquoi elliptiques ?

C'est parce qu'elles sont paramétrables par des fonctions spéciales appelées fonctions elliptiques (il restera à expliquer le nom de ces fonctions).

Dans un sens, les fonctions elliptiques généralisent les fonctions circulaires. Les coniques sont paramétrables par des fonctions circulaires (ou hyperboliques), par exemple une ellipse sera $x=a\cos\theta, y=b\sin\theta$. On ne les appelle pas pour autant courbes circulaires, car elles sont en fait paramétrables par des fonctions rationnelles : si $t=\tan\frac{\theta}{2}$, on a $\cos\theta=\frac{1-t^2}{1+t^2}$ et $\sin\theta=\frac{2t}{1+t^2}$ . On les appelle donc courbes rationnelles.

Il n'y a pas que les coniques qui soient rationnelles. Certaines cubiques le sont aussi. Par exemple, en posant $y=tx$ dans l'équation du folium de Descartes, on trouve $(t^3+1)x^3 = 3atx^2$ et on a donc le paramètrage donc $x = \frac{3at}{t^3+1}$, $y=\frac{3at^2}{t^3+1}$. De même, la parabole semi-cubique se paramètre par $x=t^2$, $y=t^3$.

Et les fonctions elliptiques, alors ?

Leur nom vient du fait qu'elles peuvent être définies comme les fonctions réciproques des intégrales elliptiques, qui ont enfin quelque chose à voir avec les ellipses : si on essaie de calculer la longueur d'un arc d'ellipse, on tombe sur une intégrale elliptique.

Il y a plusieurs versions de la théorie des fonctions elliptiques. La plus utilisée en physique ou en ingénierie est celle de Jacobi.

Elle permet d'exprimer les solutions de nombreuses équations différentielles, comme celle des grandes oscillations du pendule, par exemple (et la période est alors donnée par une intégrale elliptique).

Mais la version qui nous intéresse pour la cryptographie est celle de Weierstrass.

Sachant, par les travaux précédents, que les extensions au plan complexe des fonctions elliptiques sont doublement périodiques (elles vérifient $(z+n\omega_1+m\omega_2)=f(z)$ pour tous $(m,n\in{\mathbb Z}$ et tout $z\in{\mathbb C}$ pour lequel $f(z)$ est défini, $\omega_1,\omega_2$ sont deux nombres complexes dont le rapport n'est pas réel), Weierstrass s'est demandé s'il existait un moyen simple de construire directement de telles fonctions doublement périodiques. Son raisonnement est bien expliqué dans l'article de Wikipédia. L'idée est de partir d'une fonction quelconque $f$ et de former la somme infinie $$F(z)=\sum_{m,n\in{\mathbb Z}} f(z+n\omega_1+m\omega_2)$$

Si la série converge, $F$ sera doublement périodique. Il faut donc que $f$ tende assez vite vers 0 à l'infini. La construction marche avec $f(z)=z^{-3}$, mais on peut faire mieux en bricolant un peu la série associée à $f(z)=z^{-2}$. Telle quelle, elle ne converge pas, mais en retranchant à chaque terme son équivalent asymptotique, on peut montrer que ça marche encore. Le résultat est la fameuse fonction $$\wp(z) = {1\over z^2} + {\sum_{(n_1,n_2)\not = (0,0)}}\left[ {1\over (z+n_1\omega_1+n_2\omega_2)^2} - {1\over (n_1\omega_1+n_2\omega_2)^2}\right]$$

(le caractère $\wp$ n'appartient à aucune police connue, il a été réalisé spécialement pour Weierstrass)

On peut maintenant rentrer dans le vif du sujet. En développant chaque terme de la série en série de puissances de $z$, on peut montrer que la fonction $\wp$ vérifie l'équation différentielle

$$\wp'(z)^2=4\wp(z)^3-g_2\wp(z)-g_3$$

où $g_2=60G_4$ et $g_3=140G_6$, avec

$$G_k={\sum_{(m,n)\not=(0,0)}}{1\over (m\omega_1+n\omega_2)^k}$$

et

$$\wp(z)={1\over z^2}+\sum_{k\ge 2}(2k-1)G_{2k}(\tau)z^{2k-2}$$

Donc, $x=\wp(t), y=\wp'(t)$ fournit directement un paramétrage de la courbe elliptique $$y^2=4x^3-g_2x-g_3$$. Un peu de géométrie projective élémentaire permet de montrer que toute courbe elliptique admet une équation de cette forme dans un repère approprié. La fonction de Weierstrass fournit donc une méthode simple et élégante pour paramétrer les courbes elliptiques par des fonctions elliptiques.

Elle montre en particulier qu'on peut additionner les points d'une courbe elliptique ! Si $P_1 = (\wp(t_1),\wp'(t_1))$ et $P_2=(\wp(t_2),\wp'(t_2))$, on peut poser

$$P_1\oplus P_2 = (\wp(t_1+t_2),\wp'(t_1+t_2))$$

Cette opération définit une structure de groupe commutatif sur la courbe.

On peut vérifier que géométriquement, la somme est le symétrique par rapport à l'axe horizontal du troisième point d'intersection de la droite passant par $P_1,P_2$ avec la courbe (c'est souvent présenté comme la définition de l'addition sur la courbe, ce qui n'est pas franchement naturel...), et que l'élément neutre est son point à l'infini.

Il reste à la calculer (c'est le théorème d'addition pour la fonction $\wp$). Ce n'est pas évident, mais on aboutit à un résultat intéressant : les coordonnées de $P_1\oplus P_2$ sont des fonctions rationnelles à coefficients entiers des coordonnées de $P_1$ et $P_2$ :

On trouvera le calcul ici.

En fait, le théorème d'addition pour la fonction $\wp$ s'obtient en remarquant que si $t_3$ est le paramètre du troisème point d'intersection $P_3$ de la droite $(P_1P_2)$ avec la courbe, alors $t_1+t_2+t_3\in{\mathbb Z}\omega_1\oplus{\mathbb Z}\omega_2$. C'est une conséquence simple de résultats généraux sur les zéros et les pôles d'une fonction elliptique.

Courbes elliptiques sur les corps finis

On peut donc appliquer les formules d'addition à la courbe modulo un nombre premier $p$, c'est à dire à l'ensemble des solutions de l'équation projective dans $({\mathbb Z}/p{\mathbb Z})^3$. Dans les bons cas, on obtiendra un très grand groupe dans lequel le problème du logarithme discret est encore beaucoup plus difficile que dans un corps fini (à cause de la non-linéarité des fomules d'addition).

Le système proposé (indépendamment par Koblitz et Miller) est donc essentiellement un ElGamal dans le groupe d'une courbe elliptique modulo un grand nombre premier. Par rapport au RSA, il permet d'avoir des clés plus courtes à sécurité équivalente.

On notera que, si la description du RSA est relativement simple, le choix des clés n'est pas trivial. Pour les courbes elliptiques, c'est encore plus complexe. Il est donc recommandé d'utiliser les courbes proposées dans divers standards.

In [12]:
from ent import *

Le code pour manipuler les courbes elliptiques n'est pas compliqué. Voici la formule d'addition :

In [13]:
def ellcurve_add(E, P1, P2):
    """
    Returns the sum of P1 and P2 on the elliptic 
    curve E.
    Input:
         E -- an elliptic curve over Z/pZ, given by a 
              triple of integers (a, b, p), with p odd.
         P1 --a pair of integers (x, y) or the 
              string "Identity".
         P2 -- same type as P1
    Output:
         R -- same type as P1
    Examples:
    >>> E = (1, 0, 7)   # y**2 = x**3 + x over Z/7Z
    >>> P1 = (1, 3); P2 = (3, 3)
    >>> ellcurve_add(E, P1, P2)
    (3, 4)
    >>> ellcurve_add(E, P1, (1, 4))
    'Identity'
    >>> ellcurve_add(E, "Identity", P2)
    (3, 3)
    """ 
    a, b, p = E
    assert p > 2, "p must be odd."
    if P1 == "Identity": return P2
    if P2 == "Identity": return P1
    x1, y1 = P1; x2, y2 = P2
    x1 %= p; y1 %= p; x2 %= p; y2 %= p
    if x1 == x2 and y1 == p-y2: return "Identity"
    if P1 == P2:
        if y1 == 0: return "Identity"
        lam = (3*x1**2+a) * inversemod(2*y1,p)
    else:
        lam = (y1 - y2) * inversemod(x1 - x2, p)
    x3 = lam**2 - x1 - x2
    y3 = -lam*x3 - y1 + lam*x1
    return (x3%p, y3%p)

Testons sur la courbe P-256 du NIST :

In [14]:
a = 115792089210356248762697446949407573530086143415290314195533631308867097853948
b = 41058363725152142129326129780047268409114441015993725554835256314039467401291
p = 2**256-2**224+2**192+2**96-1

Son équation est $$y^2=x^3+ax+b \mod p$$

Voici un point de la courbe :

In [15]:
xP=48439561293906451759052585252797914202762949526041747995844080717082404635286
yP=36134250956749795798585127919587881956611106672985015071877198253568414405109
In [16]:
pow(yP,2,p) == (pow(xP,3,p) + a*xP + b) % p
Out[16]:
True

Et un autre :

In [17]:
xQ=91120319633256209954638481795610364441930342474826146651283703640232629993874
yQ=80764272623998874743522585409326200078679332703816718187804498579075161456710

pow(yQ,2,p) == (pow(xQ,3,p) + a*xQ + b) % p
Out[17]:
True
In [18]:
E = (a,b,p)
P = (xP,yP)
Q = (xQ,yQ)
ellcurve_add(E,P,Q)
Out[18]:
(90311347416124380843053629782909799863811022113695181534556410735564918416699L,
 4439786493922664689351604000024584586041837813305394846042624716681282749942L)

Il faut aussi définir la multiplication $P\rightarrow nP$ par un entier :

In [19]:
def ellcurve_mul(E, m, P):
    """
    Returns the multiple m*P of the point P on 
    the elliptic curve E.
    Input:
        E -- an elliptic curve over Z/pZ, given by a 
             triple (a, b, p).
        m -- an integer
        P -- a pair of integers (x, y) or the 
             string "Identity"
    Output:
        A pair of integers or the string "Identity".
    Examples:
    >>> E = (1, 0, 7)
    >>> P = (1, 3)
    >>> ellcurve_mul(E, 5, P)
    (1, 3)
    >>> ellcurve_mul(E, 9999, P)
    (1, 4)
    """   
    assert m >= 0, "m must be nonnegative."
    power = P
    mP = "Identity"
    while m != 0:
        if m%2 != 0: mP = ellcurve_add(E, mP, power)
        power = ellcurve_add(E, power, power)
        m /= 2
    return mP
In [20]:
ellcurve_mul(E,2,P)
Out[20]:
(56515219790691171413109057904011688695424810155802929973526481321309856242040L,
 3377031843712258259223711451491452598088675519751548567112458094635497583569L)

Il n'est pas évident de calculer le nombre de points de cette courbe. Le système sage connaît des algorithmes sophistiqués :

sage: E = EllipticCurve([GF(p)(0),0,0,a,b])
sage: E.abelian_group()
Additive abelian group isomorphic to Z/115792089210356248762697446949407573529996955224135760342422259061068512044369 embedded in Abelian group of points on Elliptic Curve defined by y^2 = x^3 + 115792089210356248762697446949407573530086143415290314195533631308867097853948*x + 41058363725152142129326129780047268409114441015993725554835256314039467401291 over Finite Field of size 115792089210356248762697446949407573530086143415290314195533631308867097853951

Ainsi cette courbe est d'ordre $$q = 115792089210356248762697446949407573529996955224135760342422259061068512044369 $$

C'est un nombre premier. Donc, le groupe de la courbe est cyclique, et il existe un entier $m$ tel que $Q=mP$.

Il est en pratique impossible de le calculer, mais la question de savoir si $m$ n'avait pas été choisi par la NSA a fait beaucoup jaser il y a quelques années.

Ce sera l'objet du dernier TD.

Paramètres de domaine

Les paramètres à fourinir sont les suivants. Le nombre premier $p$ qui définit le corps de base, les coefficients $a$ et $b$ de l'équation $y^2=x^3+ax+b$, un point $G$ générateur d'un grand sous-groupe, et son ordre $n$, en général premier. Le théorème de Lagrange entraîne que le nombre $h={\frac {1}{n}}|E(\mathbb {F} _{p})| $ est un entier. On demande que ce nombre, appelé le cofacteur, soit petit $h\leq 4$) et de préférence $h=1$.

Les paramètres de domaine sont donc $( p , a , b , G , n , h )$.

Il n'est pas facile de calculer le nombre de points de la courbe, ni de vérifier l'abscence de faiblesses éventuelles. On utilise donc en général des courbes standardisées.

ECDH

Dans la version courbes elliptiques de Diffie-Hellman, les deux parties s'entendent sur des paramètres de domaine $( p , a , b , G , n , h )$.

Chacun choisit un entier $d<n$ et calcule le point $Q=dG$. La clef publique est $Q$, la clef secrète est $d$.

Si A et B veulent communiquer, A calcule $(x_k,y_k)=d_AQ_B$, B calcule $d_BQ_A=(x_k,y_k)$, et la clé de session est $x_k$ (en général un hachage $h(x_k)$).

ECDSA, ElGamal

Ils s'adaptent directement aux groupes des courbes elliptiques.

On trouvera ici une liste d'applications des courbes elliptiques.

In []: