On connaît des techniques cryptographique exploitant les propriétés des nombres entiers, comme RSA ou encore ElGamal. Avec les courbes elliptiques on reprend des idées semblables à ceci près que l'on fait les calculs sur les points d'une courbe.

On définit ce que cela signifie que de calculer $P + Q$. On obtient des tables de calcul plus compliquées que celles des nombres entiers d'autant que ces tables vont dépendre de la courbe choisie.

Les courbes elliptiques sont des courbes du plan définies dans un repère $(O;x,y)$ par une équation de forme $$(E): y^2 = x^3 + a\cdot x + b$$

Quand on fait de la cryptographie, choisir les valeurs de a et b fait partie du choix de clé. La seule contrainte est qu'il faut $4\cdot a^3 + 27\cdot b^2 \neq 0$ pour que la courbe soit suffisamment régulière.

Dans le cadre de ce TD, on choisira $a = -1$ et $b = 1$, donc : $$(E) : y^2 = x^3 - x + 1$$

Pour deux points $P$ et $Q$ de la courbe, on définit l'opération $P + Q$ :

• tracer la droite $(PQ)$,
• relever la 3e intersection de cette droite avec la courbe,
• prendre le symétrique de ce point sur la courbe. On le nomme $R$.
• On définit : $R = P + Q$

Cela peut sembler une façon étrange de concevoir l'addition et pourtant, cette addition a de bonnes propriétés :

• Elle est associative : $(P + Q) + R = P + (Q + R)$ – autrement dit, on peut enlever les parenthèses.
• Elle est commutative : $P + Q = Q + P$

Supposons que l'on prenne $P$ et $Q$ symétriques sur la courbe.

La droite $(PQ)$ est verticale et n'a pas d'autre intersection avec la courbe. On définit alors un point $P_0$ qui est en quelque sorte à l'infini. On dit que dans ce cas là, $(PQ)$ coupe la courbe en l'infini, donc en $P_0$ et alors $P + Q = P_0$ – on appelle cela de la géométrie projective.

On définit aussi que $P_0$ est l'élément neutre de notre addition, c'est à dire le $0$. Autrement dit, on a toujours $P + P_0 = P$ tout comme on dirait $x + 0 = x$.

Ainsi notre addition a deux nouvelles propriétés essentielles :

• $P_0$ est l'élément neutre tel que pour tout $P$, $P + P_0 = P$.
• Soit $P$ un point de la courbe, son symétrique par rapport à $(Ox)$ est $Q$ et on a a $P + Q = P_0$. On note donc $Q = - P$ ce qui signifie que tout $P$ a un opposé $-P$ qui est son symétrique.

Notre addition $P + Q$ suppose de tracer $(PQ)$ ce qui sera impossible si $P = Q$. Dans ce cas particulier, au lieu de tracer $(PQ)$, on utilise la tangente à la courbe en $P$.

Ainsi, nous pouvons obtenir $P + P = 2P$ et son opposé $-2P$. Partant de là on pourra calculer $P + 2P = 3P$ et déduire $-3P$. Etc.

Ainsi, on a donné un sens à $n\cdot P, n\in\mathbb{Z}$.

Prenons deux calculs :

1. D'abord $2\cdot(3P + Q)$
   cela veut dire que l'on calcule $2P = P + P$ puis $3P = 2P + P$, puis $Z = 3P + Q$ et enfin le résultat $2Z = Z + Z$.
2. Ensuite $6P + 2Q$
   on calcule $2P = P + P$, $4P = 2P + 2P$, $6P = 4P + 2P$, $2Q = Q + Q$ et enfin le résultat $6P + 2Q$

Les deux constructions / calculs produisent le même résultat. C'est pour cette raison que l'on peut écrire $2(3P + Q) = 6P + 2Q$. Nos constructions respectent les règles de calculs habituelles comme le fait de développer une multiplication sur une addition.

L'addition définie par la courbe elliptique a toute les propriétés d'une bonne addition.

Pour le calcul de $P + Q$ On peut trouver toutes les formules utiles sur cette page Wikipedia. Je les reprends ici, avec $P(x_P;y_P)$ et $Q(x_Q;y_Q)$.

L'équation de $(PQ)$ est de la forme $y=m\cdot x + p$ avec $m = \frac{y_P - y_Q}{x_P - x_Q}$ et $p = \frac{x_P\cdot y_Q - x_Q\cdot y_P}{x_P - x_Q}$. On peut calculer ensuite : $$x_{P+Q} = m^2 - x_P - x_Q \quad ; \quad y_{P+Q} = - m\cdot x_{P+Q} - p$$

Il s'agit de deux points opposés. Dans ce cas, $P + Q = P_0$.

La seule possibilité est que $P = Q$ et dans ce cas on cherche $2P$ en utilisant la tangente.

La tangente a pour équation $y = m\cdot x + p$ avec $m = \frac{3\cdot x_P^2 + a}{2y_P}$ et $p = y_P - m\cdot x_P$. On peut calculer ensuite : $$x_{2P} = m^2 - 2\cdot x_P \quad ; \quad y_{2P} = -m\cdot x_{2P} - p$$

Dans le cadre du TD, on a $a = -1$.

Comme avec les nombres entiers, il est plus intéressant de travailler avec modulo :

• Les calculs seront exclusivement sur des nombres entiers ce qui facilitera les choses,
• comme avec les nombres entiers, les modulos « embrouillent » un peu les calculs ce qui est idéal pour la cryptographie.

On modifie un peut la définition :

• On choisit un premier $p$, en situation réelle on le prend assez grand.
  on note $a \overset{p}{\equiv} b$ pour $a = b \mod p$.
• Les points considérés ont des coordonnées $(x ; y)$ entières.
• On considère que deux points $P_1(x_1;y_1)$ et $P_2(x_2;y_2)$ sont identiques si $x_1 \overset{p}{\equiv} x_2$ et $y_1 \overset{p}{\equiv} y_2$
• L'équation de la courbe est maintenant $(E): y^2 \overset{p}{\equiv} x^3 + a\cdot x + b$
• La contrainte devient $4\cdot a^3 + 27 \cdot b^2 \overset{p}{\not\equiv} 0$

Dans le cadre de ce TD, on prendra $p = 13$ et toujours $a=-1$ et $b=1$.

Tenant compte de ces nouvelles définition, notre addition fonctionne toujours et a toujours les bonnes propriété !

Les formules présentées plus haut sont toujours valides à ceci près que toutes les quantités sont calculées modulo $p$. De plus, vous pouvez voir des divisions. On n'utilisera pas l'opérateur de division, mais on utilisera l'inverse modulaire.

Puisque toute la technique consiste à inventer une addition sur des objets qui normalement ne s'additionnent pas, il me parait pertinent d'utiliser des classes et d'utiliser des méthodes magiques qui vont nous permettre de définir ce que sera l'addition.

L'algorithme de chiffrement que l'on envisagera ensuite repose sur le fait qu'il peut être très rapide de calculer $n \cdot P = \overbrace{P + P + \cdots + P}^{n\times}$ mais très long de trouver le $n$ vérifiant $n\cdot P = Q$. Il est donc très important de disposer d'un algorithme rapide pour calculer $n\cdot P$.

On retrouve exactement le même principe que l'exponentiation rapide.

Entrée : n un entier positif, P un point
Sortie : n*P
    Q = P0 (point nul)
    RÉPÉTER n FOIS
        Q = Q + P
    FIN
    RENVOYER Q

La boucle se répète $n$ fois, mais dans le cas cryptographique, $n$ est un très grand nombre.

Entrée : n un entier positif, P un point
Sortie : n*P
    Q = P0 (point nul)
    S = P
    TANT QUE n > 0:
        SI n % 2 = 1 ALORS
            Q = Q + S
        FIN
        S = S + S
        n = n // 2    
    FIN
    RENVOYER Q

Il n'est pas forcément évident de trouver au moins un point sur la courbe. Une possibilité est de tirer au hasard des paires $(x;y)$ telles que $0 \leq x < p$ et $0 \leq y < p$ jusqu'à trouver une paire sur la courbe.

J'ai fait le test avec $a=-1$, $b = 1$ et $p = 502181$. J'obtiens rapidement des points. Par exemple $(224426 ; 32906)$.

Je vous propose la structure suivante.

# module ecc.py

class Point:
    P = 13  # premier choisi pour le modulo
    A = -1  # coefficient a
    B = 1   # coefficient b
    @absrtactmethod
    def test(x,y):
        """
        Teste si des coordonnées (x,y) sont bien sur la courbe
        Par exemple ici : Point.test(1,1) renvoie True
        """
        return (x**3 + Point.A * x + Point.B - y**2) % Point.P == 0
        
    def __init__(self, x, y):
        """
        x, y: coordonnées du point
        si x = None ou y = None, c'est le point P0
        """
        if x == None or y == None:
            self.nul = True
            return
        self.nul = False
        self.x = x % self.P
        self.y = y % self.P
        # vérification que (x,y) est bien sur la courbe choisie
        assert Point.test(x,y)
    
    def __add__(P, Q):
        """
        renvoie le point résultat de P + Q
          Sera automatiquement utilisé quand on écrira P + Q
          dans une calcul avec P et Q deux objets Point
        """
        
        # à vous

    def opposite(self):
       """
       renvoie l'opposé d'un point, c'est à dire
       son symétrique par rapport à (Ox)
       """
       if self.nul:
          # si P0, -P0 = P0
          return self
       return Point(self.x, -self.y)

    def __mul__(P,n):
        """
        P: un point
        n: un entier
          Sera automatiquement appelé quand on fera un calcul P*n
          avec P un Point et n un int
        Renvoie n.P
        Utilisez une méthode rapide de préférence.
        """
        assert type(n) == int
        
        # à vous
    
    def __eq__(P, Q):
       """
       Fonction automatiquement appelée quand on testera P == Q
       On veut comparer les coordonnées
       """
       if P.nul or Q.nul:
           # au moins l'un des deux est nul, égaux si les deux nuls
           return P.nul == Q.nul
       # sinon égaux si coordonnées égales
       return P.x == Q.x and P.y == Q.y
    
    def __str__(self):
        """
        Pour affichage en mode texte
        """
        if self.nul:
            return "P0"
        return "({} ; {})".format(self.x, self.y)
    
    def __repr__(self):
        """
        Pour affichage dans la console
        """
        if self.nul:
            return "<P0>"
        return "<{} ; {}>".format(self.x, self.y)
        
if __name__ == "__main__"
    # petit test
    # définition de points se trouvant sur la courbe (avec modulo)
    P = Point(3,8)
    Q = Point(5,2)
    R = Point(6,4)
    
    # exemple de calculs :
    Z = P + Q
    assert Z == Point(1, 12)
    print("P + Q -> {}".format(Z))
    
    W = R*2
    assert W == Point(5,11)
    print("2R -> {}".format(W))
    # remarque : pour l'utilisation de __mul__, il faut écrire R*2 et pas 2*R
    
    # vérification des propriétés
    assert (P + Q) + R == P + (Q + R)
    assert P + Q == Q + P
    

Si vous voulez tenter le point aléatoire, en utilisant sqrtmod.py, on peut ajouter une méthode :

# module ecc.py
import sqrtmod
from random import randrange

class Point:
    ...

    @absrtactmethod
    def alea_point():
        """
        renvoie un point aléatoire sur la courbe
        """
        x = randrange(Point.P) # il faut P impair
        y2 = x**3 + Point.A * x + Point.B
        while not sqrtmod.is_quadratic(y2, self.P):
            x = randrange(Point.P)
            y2 = x**3 + self.A * x + self.B
        y = sqrtmod.sqrt(y2, Point.P)
        return Point(x, y)

Reprenons le chiffrement de ElGamal – on pourrait faire autrement, nos points ont les mêmes capacités que les entiers.

Bob choisit $p$, $d$ et $s$ avec $p$ premier, $1 < d < p$ et $s > 1$ puis il calculait $h = d^s \mod p$.

• $K_{PU} = (p, d, h)$
• $K_{PR} = (p, d, s)$

Alice chiffre un message $m$ (un entier).

• Elle choisit un $z > 1$ aléatoire, et calcule
• $r = m\cdot h^z \mod p$
• $t = d^z \mod p$.

et elle envoie $(r, t)$

Pour déchiffrer, Bob dispose de sa clé $(p, d, s)$ et du message $(r, t)$. Il calcule

• $t^s$,
• il cherche $u$ l'inverse de $t^s$
• $m = r\cdot u$

Il a retrouvé $m$

Bob choisit sa courbe (c'est à dire $a$ et $b$), le nombre premier $p$, un point $D$ de la courbe et un entier $s > 1$. Il calcule $H = s\cdot D$.

• $K_{PU} = (a, b, p, D, H)$
• $K_{PR} = (a, b, p, D, s)$

Alice chiffre un message $M$ (un point de la courbe)

• Elle choisit $z > 1$ au hasard et calcule
• $R = M + z\cdot H$,
• $T = z\cdot D$.

Elle envoie $(R, T)$

Pour déchiffrer, Bob connaît $s$. Il calcule

• $M = R - s\cdot T$

c'est fini, Bob a $M$.

$T = z\cdot D$ donc $$s\cdot T = s\cdot z \cdot D = z \cdot (s \cdot D) = z \cdot H$$ $$R - s \cdot T = M + z \cdot H - z \cdot H = M$$

Le calcul est même plus simple qu'avec ElGamal, dès lors que l'on ne pense pas trop au fait que l'on calcule avec des points !

Écrire de plus les fonctions suivantes :

• calculer_cle_publique(D, s) qui renvoie (D, H)
• chiffrer(M, D, H) qui renvoie la paire (R, T) du message chiffré
• dechiffrer(R, T, D, s) qui renvoie M.

La connaissance du nombre premier $p$ et de la courbe choisie sont important mais ces éléments sont déjà contenus dans notre classe Point. On pourra donc supposer que Alice et Bob ont déjà ces informations en main.

Faire le test en choisissant p = 17, d = 5, s = 12 et M = Point(5,11).