Séance 9 : logarithme discret et courbes elliptiques

Séance 9 : logarithme discret et courbes elliptiques#

Exercice 1 : arithmétique d’une courbe elliptique#

Dans cet exercice, on propose d’implémenter simplement les opérations élémentaires du groupe des points d’une courbe elliptique. Pour cela, on doit fixer certaines conventions. D’abord, pour simplier l’implémentation en python, on se place dans le contexte d’un corps fini premier \(\mathbb{F}_p\), avec \(p \equiv 3 \mod 4\). Ainsi, les racines carrées de \(x\) modulo \(p\) sont \(\pm x^{(p+1)/4}\).

Ensuite, on considère le modèle de Weierstrass pour réprésenter une courbe elliptique :

\[ \mathcal{E} : \quad y^2 = x^3 + a x + b \]

où \(a\) et \(b\) sont deux élements de \(\mathbb{F}_p\) tels que \(4a^3 + 27b^2 \ne 0\).

Une courbe elliptique sera donc vue comme un triplet formé de \(3\) éléments : (p, a, b). On représentera ensuite :

  • le point à l’infini de la courbe par l’objet python None ;

  • les autres points de la courbe de coordonnées affines \((x, y)\) par le tuple (x, y).

Question 1. Écrire une fonction ec_opp(EC, P) qui prend en entrée un triplet EC = (p, a, b) représentant une courbe elliptique, et un point P, et qui retourne l’opposé du point P pour la loi de groupe de la courbe.

# à compléter

Rappelons que si \(P = (x, y)\) est un point de la courbe d’ordonnée non-nulle, alors \(2P\) est un point affine de la courbe de coordonnées \((x', y')\), où

\[\begin{split} \left\{ \begin{array}{ll} x' &= u^2 - 2x \mod p\\ y' &= -y + u(x - x') \mod p \end{array} \right. \quad\quad \text{ avec } u = (3x^2 + a) \cdot (2y)^{-1} \mod p \end{split}\]

Si \(P\) est le point à l’infini, ou est un point affine d’ordonnée nulle, alors \(2P\) est le point à l’infini.

Question 2. Écrire une fonction ec_double(EC, P) qui prend entrée un triplet EC représentant une courbe elliptique, et un point P, et qui retourne le double de P pour la loi de groupe de la courbe.

# à compléter

Si \(P, Q\) sont deux points de la courbe, leur somme \(P \oplus Q\) vaut :

  • le point à l’infini si \(P\) et \(Q\) ont la même abscisse,

  • \(P\) si \(Q\) est le point à l’infini, et \(Q\) si \(P\) est le point à l’infini,

  • le point de cooordonnées \((x, y)\) où :

\[\begin{split} \left\{ \begin{array}{ll} x &= u^2 - x_P - x_Q \mod p\\ y &= -y_P + u(x_P - x) \mod p \end{array} \right. \quad\quad \text{ avec } u = (y_Q - y_P) \cdot (x_Q - x_P)^{-1} \mod p \end{split}\]

Question 3. Écrire une fonction ec_add(EC, P, Q) qui prend entrée un triplet EC représentant une courbe elliptique, et deux points P et Q, et qui retourne la somme de P et Q pour la loi de groupe de la courbe.

# à compléter

Pour calculer efficacement \(mP\) avec \(m\) un entier et \(P\) un point de la courbe, on peut adapter la méthode d’exponentiation rapide ( »square-and-multiply ») dans le contexte d’un groupe abélien noté additivement. On obtient une méthode dite « double-and-add », dont voici un pseudo-code

resultat = point à l'infini
base = P
tant que m > 0, faire :
    si m est impair, faire :
        resulltat = resultat + base   (opération de groupe)
    base = 2 * base                   (opération de groupe)
    diviser m par 2
retourner resultat

Question 4. Écrire une fonction ec_mult(EC, P, m) qui prend entrée un triplet EC représentant une courbe elliptique, un point P et un entier naturel m, et qui retourne le point \(m P\).

# à compléter

Pour calculer l’ensemble des points d’une courbe elliptique (ce dont on n’a pas vraiment besoin en cryptographie), une méthode naïve consiste à parcourir tous les éléments \((x, y) \in \mathbb{F}_p^2\), et de ne garder que ceux qui satisfont l’équation de la courbe. Cette méthode a une complexité approximative en \(\tilde{O}(p^2)\), tandis que la taille de la sortie est en \(O(p)\), on peut donc faire mieux.

Une méthode plus efficace consiste à liste toutes les abscisses \(x \in \mathbb{F}_p\), puis à calculer (si elles existent) les racines carrées de \(x^3 + ax + b\). Le calcul d’une racine carrée dans un corps fini est efficace en général (algorithme de Cipolla, par exemple), et d’autant plus dans \(\mathbb{F}_p\) avec \(p \equiv 3 \mod 4\), voir introduction.

Question 5. Écrire une fonction ec_list_points(EC) qui retourne la liste des points de la courbe EC. Attention, cette fonction n’est à utiliser que pour de « petites » valeurs de \(p\).

# à compléter

Question 6. Pour la courbe \(y^2 = x^3 + x + 1\) définie sur \(\mathbb{F}_{19}\) :

  1. Calculer la liste des points de la courbe, et en déduire l’ordre \(r\) de la courbe.

  2. Vérifier que \(G = (16, 16)\) est un point d’ordre exactement \(r\), et donc que l’ensemble des points de la courbe forme un groupe cyclique engendré par \(G\).

# à compléter

Exercice 2 : baby-step giant-step#

Pour cet exercice, on souhaite implémenter l’algorithme « pas de bébé, pas de géant » sur le groupe de points d’une courbe elliptique.

Question 1. Implémenter l’algorithme « pas de bébé, pas de géant » tel que vu en cours.

# à compléter

L’ensemble des points de la courbe \(y^2 = x^3 + x + 1\) définie sur \(\mathbb{F}_{p}\) avec \(p = 1\,000\,003\), forme un groupe cyclique d’ordre \(r = 1000727\). Un de ses générateurs est \(G = (445619, 638237)\).

Question 2. Avec la fonction qui vient d’être implémentée, calculer le logarithme discret de \(P = (165283, 514138)\) en base \(G\).

# à compléter
Contenu