Télécharger cet IPython-Notebook : Courbe_Elliptique.ipynb

Courbe elliptique

https://www.bibmath.net/forums/viewtopic.php?id=14524

On considère la courbe elliptique $\mathcal{C}$ d'équation de Weierstrass $y^2 = x^3+ax+b$ dans $\mathbb{Z}/p\mathbb{Z}$, $p$ premier.

On considère l'ensemble $\mathcal{E}$ des points de la courbe : $$ \mathcal{E} = \left\{ [x, y] \in \mathbb{Z}/p\mathbb{Z}\times\mathbb{Z}/p\mathbb{Z} ~~|~~ y^2 = x^3+ax+b\right\} \cup \{0\}$$ où $0$ est le point à l'infini de $\mathcal{C}$.

On définit une addition sur $\mathcal{E}$ qui fait de $\mathcal{E}$ un groupe abélien, d'élément neutre $0$.

Addition des points

D'après le petit théorème de Fermat $n^{p-1}\equiv 1 \mod{p}$ si $p$ est premier.
Donc $n^{p-2}\equiv n^{-1} \mod{p}$. On suppose naturellement $n\neq 0$
La fonction Python de calcul de la puissance modulaire pow est très rapide.

In [1]:
def inverse_mod_p(n, p):
    """Retourne l'inverse de n modulo p premier.
    """
    return pow(n,p-2,p)

On encapsule les paramètres de la courbe elliptique dans un objet. On définit trois méthodes :

  • has_point qui teste si un point est sur la courbe,
  • opp qui renvoie l'opposé d'un point (c'est le symétrique par rapport à l'axe des abscisses),
  • addP qui renvoie le point correspondant à la somme de deux points.
In [2]:
class EllipticCurve(object):
    """Objet représentant la courbe elliptique d'équation y**2 = x**3 + a*x + b
       sur le corps Z/pZ (p premier).
    """
    def __init__(self, a, b, p):  
        delta = (4*a**3 + 27*b**2)%p  # discriminant
        if delta == 0:
            raise Exception ("Discriminant nul : courbe elliptique singulière.")
        self.a = a%p
        self.b = b%p
        self.p = p
        
    def __str__(self):
        return 'y^2 = x^3 + {}x + {} modulo {}'.format(self.a, self.b, self.p)
    
    def has_point(self, p1):
        if p1 == 0:
            return True
        return (p1[1] ** 2) % self.p == (p1[0] ** 3 + self.a * p1[0] + self.b) % self.p
    
    def opp(self, p1):
        if p1 == 0:
            return 0
        return [p1[0], -p1[1]%self.p]
    
    def addP(self, p1, p2):
        if p1 != 0 and self.has_point(p1) == False:
            raise Exception ("Le point {} n'est pas sur la courbe.".format(p1))
        if p2 != 0 and self.has_point(p2) == False:
            raise Exception ("Le point {} n'est pas sur la courbe.".format(p2))
        if p1 == 0:
            return p2       # 0 + p2 = p2
        if p2 == 0:
            return p1       # p1 + 0 = p1
        if (p1[0] - p2[0])%self.p == 0 and (p1[1] + p2[1])%self.p == 0 : # si p1 == -p2 mod p
            return 0
        if (p1[0] - p2[0])%self.p == 0 and (p1[1] - p2[1])%self.p == 0:  # si p1 == p2 mod p
            m = (3*p1[0]*p1[0] + self.a)*inverse_mod_p(2*p1[1], self.p) # pente tangente
        else:
            m = (p2[1] - p1[1])*inverse_mod_p(p2[0] - p1[0], self.p)    # pente sécante
        x = (m*m - p1[0] - p2[0])%self.p
        return [x, (m*(p1[0] - x) - p1[1])%self.p ]

Application

In [3]:
ec = EllipticCurve(100, 100, 1009)
In [4]:
print(ec)

y^2 = x^3 + 100x + 100 modulo 1009
In [5]:
p = [12, 1]
In [6]:
ec.has_point(p)
Out[6]:
True

Donc le point p est sur la courbe.
On demande de calculer 17p (17 est la clé privée de Bob).

In [7]:
p2 = ec.addP(p, p)      # p2 = 2p
p2
Out[7]:
[102, 275]
In [8]:
p4 = ec.addP(p2, p2)    # p4 = 4p
p4
Out[8]:
[401, 373]
In [9]:
p8 = ec.addP(p4, p4)    # p8 = 8p
p8
Out[9]:
[227, 480]
In [10]:
p16 =ec.addP(p8, p8)    # p16 = 16p
p16
Out[10]:
[308, 156]
In [11]:
p17 = ec.addP(p16, p)   # p17 = 17p
p17
Out[11]:
[237, 355]

17p est la clé publique que Bob envoie à Alice.

Tables d'addition

Si le module est petit, le nombre de points de la courbe est petit aussi et on peut dresser la table d'addition des points de la courbe elliptique. On n'affiche pas les marges, car la marge gauche est identique à la première colonne et la marge supérieure est identique à la première ligne.

In [12]:
ec = EllipticCurve(3, 8, 13)
print(ec)

y^2 = x^3 + 3x + 8 modulo 13

Ensemble des points de la courbe :

In [13]:
e = []
for a in range(13):
    for b in range(13):
        if ec.has_point([a, b]):
            if [a, b] not in e:
                e.append([a, b])
e = [0] + e
print(e)

[0, [1, 5], [1, 8], [2, 3], [2, 10], [9, 6], [9, 7], [12, 2], [12, 11]]

Table d'addition (sans les marges) :

In [14]:
for x in e:
    for y in e:
        z = ec.addP(x, y)
        if z == 0:
            print('{:>8}'.format('0   '), end=' ' )
        else:
            print('{:>8}'.format(str(z)), end=' ' )
    print()

    0      [1, 5]   [1, 8]   [2, 3]  [2, 10]   [9, 6]   [9, 7]  [12, 2] [12, 11] 
  [1, 5]  [2, 10]     0      [1, 8]   [9, 7]   [2, 3]  [12, 2] [12, 11]   [9, 6] 
  [1, 8]     0      [2, 3]   [9, 6]   [1, 5] [12, 11]  [2, 10]   [9, 7]  [12, 2] 
  [2, 3]   [1, 8]   [9, 6] [12, 11]     0     [12, 2]   [1, 5]  [2, 10]   [9, 7] 
 [2, 10]   [9, 7]   [1, 5]     0     [12, 2]   [1, 8] [12, 11]   [9, 6]   [2, 3] 
  [9, 6]   [2, 3] [12, 11]  [12, 2]   [1, 8]   [9, 7]     0      [1, 5]  [2, 10] 
  [9, 7]  [12, 2]  [2, 10]   [1, 5] [12, 11]     0      [9, 6]   [2, 3]   [1, 8] 
 [12, 2] [12, 11]   [9, 7]  [2, 10]   [9, 6]   [1, 5]   [2, 3]   [1, 8]     0    
[12, 11]   [9, 6]  [12, 2]   [9, 7]   [2, 3]  [2, 10]   [1, 8]     0      [1, 5]

Autre courbe elliptique :

In [15]:
ec = EllipticCurve(-1, 0, 13)
print(ec)

y^2 = x^3 + 12x + 0 modulo 13

Ensemble des points :

In [16]:
e = []
for a in range(13):
    for b in range(13):
        if ec.has_point([a, b]):
            if [a, b] not in e:
                e.append([a, b])
e = [0] + e
print(e)

[0, [0, 0], [1, 0], [5, 4], [5, 9], [8, 6], [8, 7], [12, 0]]

Table d'addition (sans les marges) :

In [17]:
for x in e:
    for y in e:
        z = ec.addP(x, y)
        if z == 0:
            print('{:>8}'.format('0   '), end=' ' )
        else:
            print('{:>8}'.format(str(z)), end=' ' )
    print()

    0      [0, 0]   [1, 0]   [5, 4]   [5, 9]   [8, 6]   [8, 7]  [12, 0] 
  [0, 0]     0     [12, 0]   [5, 9]   [5, 4]   [8, 7]   [8, 6]   [1, 0] 
  [1, 0]  [12, 0]     0      [8, 6]   [8, 7]   [5, 4]   [5, 9]   [0, 0] 
  [5, 4]   [5, 9]   [8, 6]   [0, 0]     0     [12, 0]   [1, 0]   [8, 7] 
  [5, 9]   [5, 4]   [8, 7]     0      [0, 0]   [1, 0]  [12, 0]   [8, 6] 
  [8, 6]   [8, 7]   [5, 4]  [12, 0]   [1, 0]   [0, 0]     0      [5, 9] 
  [8, 7]   [8, 6]   [5, 9]   [1, 0]  [12, 0]     0      [0, 0]   [5, 4] 
 [12, 0]   [1, 0]   [0, 0]   [8, 7]   [8, 6]   [5, 9]   [5, 4]     0

On remarque les trois points [0, 0], [1,0] et [12, 0] sont "à tangentes verticales" (si on peut dire !)

Le 5/12/2021 - Contact : Rossignol@bribes.org