{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "1463092c",
   "metadata": {},
   "source": [
    "# Séance 9 : logarithme discret et courbes elliptiques\n",
    "\n",
    "\n",
    "## Exercice 1 : arithmétique d'une courbe elliptique\n",
    "\n",
    "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}$. \n",
    "\n",
    "Ensuite, on considère le modèle de Weierstrass pour réprésenter une courbe elliptique :\n",
    "\n",
    "$$\n",
    "  \\mathcal{E} : \\quad y^2 = x^3 + a x + b\n",
    "$$\n",
    "\n",
    "où $a$ et $b$ sont deux élements de $\\mathbb{F}_p$ tels que $4a^3 + 27b^2 \\ne 0$.\n",
    "\n",
    "Une courbe elliptique sera donc vue comme un triplet formé de $3$ éléments : `(p, a, b)`. On représentera ensuite :\n",
    " - le point à l'infini de la courbe par l'objet python `None` ;\n",
    " - les autres points de la courbe de coordonnées affines $(x, y)$ par le tuple `(x, y)`. \n",
    "\n",
    "\n",
    "\n",
    "**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."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "1dfcfa07",
   "metadata": {},
   "outputs": [],
   "source": [
    "def ec_opp(EC, P):\n",
    "    p, _, _ = EC\n",
    "    if P == None:\n",
    "        return None\n",
    "    return (P[0], -P[1] % p)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ea5ecb80",
   "metadata": {},
   "source": [
    "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ù \n",
    "\n",
    "$$\n",
    "\\left\\{\n",
    "\\begin{array}{ll}\n",
    "x' &= u^2 - 2x \\mod p\\\\\n",
    "y' &= -y + u(x - x') \\mod p\n",
    "\\end{array}\n",
    "\\right. \\quad\\quad \\text{ avec } u = (3x^2 + a) \\cdot (2y)^{-1} \\mod p\n",
    "$$\n",
    "\n",
    "Si $P$ est le point à l'infini, ou est un point affine d'ordonnée nulle, alors $2P$ est le point à l'infini.\n",
    "\n",
    "**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."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "71568810",
   "metadata": {},
   "outputs": [],
   "source": [
    "def ec_double(EC, P):\n",
    "    if P == None:\n",
    "        return None\n",
    "    x, y = P\n",
    "    if y == 0:\n",
    "        return None\n",
    "    p, a, _ = EC\n",
    "    inv_y = pow(2*y, -1, p)\n",
    "    u = ((3*x**2 + a) * inv_y) % p\n",
    "    res_x = (u**2 - 2*x) % p\n",
    "    res_y = (-y + u*(x - res_x)) % p\n",
    "    return (res_x, res_y)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "280573b1",
   "metadata": {},
   "source": [
    "Si $P, Q$ sont deux points de la courbe, leur somme $P \\oplus Q$ vaut :\n",
    "- le point à l'infini si $P$ et $Q$ ont la même abscisse,\n",
    "- $P$ si $Q$ est le point à l'infini, et $Q$ si $P$ est le point à l'infini,\n",
    "- le point de cooordonnées $(x, y)$ où :\n",
    "\n",
    "$$\n",
    "\\left\\{\n",
    "\\begin{array}{ll}\n",
    "x &= u^2 - x_P - x_Q \\mod p\\\\\n",
    "y &= -y_P + u(x_P - x) \\mod p\n",
    "\\end{array}\n",
    "\\right. \\quad\\quad \\text{ avec } u = (y_Q - y_P) \\cdot (x_Q - x_P)^{-1} \\mod p\n",
    "$$\n",
    "\n",
    "\n",
    "**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."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "2cde6760",
   "metadata": {},
   "outputs": [],
   "source": [
    "def ec_add(EC, P, Q):\n",
    "    if P == Q:\n",
    "        return ec_double(EC, P)\n",
    "    if P == None:\n",
    "        return Q\n",
    "    if Q == None:\n",
    "        return P\n",
    "    xP, yP = P\n",
    "    xQ, yQ = Q\n",
    "    if xP == xQ:\n",
    "        return None\n",
    "    p, _, _ = EC\n",
    "    inv = pow(xQ - xP, -1, p)\n",
    "    u = (inv * (yQ - yP)) % p\n",
    "    res_x = (u**2 - xP - xQ) % p\n",
    "    res_y = (-yP + u * (xP - res_x)) % p\n",
    "    return (res_x, res_y)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0c0b7e6d",
   "metadata": {},
   "source": [
    "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\n",
    "\n",
    "```\n",
    "resultat = point à l'infini\n",
    "base = P\n",
    "tant que m > 0, faire :\n",
    "    si m est impair, faire :\n",
    "        resulltat = resultat + base   (opération de groupe)\n",
    "    base = 2 * base                   (opération de groupe)\n",
    "    diviser m par 2\n",
    "retourner resultat\n",
    "```\n",
    "\n",
    "**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$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "1145a306",
   "metadata": {},
   "outputs": [],
   "source": [
    "def ec_mult(EC, P, m):\n",
    "    res = None\n",
    "    e = m\n",
    "    B = P\n",
    "    while e > 0:\n",
    "        if (e % 2) == 1:\n",
    "            res = ec_add(EC, res, B)\n",
    "        B = ec_double(EC, B)\n",
    "        e = e//2\n",
    "    return res"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "16f7382a",
   "metadata": {},
   "source": [
    "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.\n",
    "\n",
    "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.\n",
    "\n",
    "\n",
    "**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$.*"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e03ec371",
   "metadata": {},
   "outputs": [],
   "source": [
    "def ec_list_points(EC):\n",
    "    p, a, b = EC\n",
    "    res = [ None ]\n",
    "    for x in range(p):\n",
    "        s = (x**3 + a*x + b) % p\n",
    "        if s == 0:\n",
    "            res.append((x, 0))\n",
    "        if pow(s, (p-1)//2, p) == 1:\n",
    "            y = pow(s, (p+1)//4, p)\n",
    "            res.append((x,y))\n",
    "            res.append((x,p-y))\n",
    "    return res"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0e006972",
   "metadata": {},
   "source": [
    "**Question 6.** Pour la courbe $y^2 = x^3 + x + 1$ définie sur $\\mathbb{F}_{19}$ :\n",
    "1. Calculer la liste des points de la courbe, et en déduire l'ordre $r$ de la courbe. \n",
    "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$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "98825987",
   "metadata": {},
   "outputs": [],
   "source": [
    "EC_19 = [19, 1, 1]\n",
    "points = ec_list_points(EC_19)\n",
    "print(points)\n",
    "r = len(points)\n",
    "print(r)\n",
    "G = (16, 16)\n",
    "print(ec_mult(EC_19, G, r) == None)\n",
    "print(all(ec_mult(EC_19, G, i) != None for i in range(1, r)))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f764ca2d",
   "metadata": {},
   "source": [
    "## Exercice 2 : baby-step giant-step\n",
    "\n",
    "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.\n",
    "\n",
    "**Question 1.** Implémenter l'algorithme \"pas de bébé, pas de géant\" tel que vu en cours."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "7d30b9a9",
   "metadata": {},
   "outputs": [],
   "source": [
    "import math\n",
    "\n",
    "def BSGS(EC, G, P):\n",
    "    p, _, _ = EC\n",
    "    m = math.isqrt(p)\n",
    "    dictionnaire = dict()\n",
    "    Q = None\n",
    "    \n",
    "    for i in range(m):\n",
    "        dictionnaire[Q] = i\n",
    "        Q = ec_add(EC, Q, G)\n",
    "\n",
    "    oppG = ec_opp(EC, G)\n",
    "    big_step = ec_mult(EC, oppG, m)\n",
    "    Q = P\n",
    "    j = 0\n",
    "    while not(Q in dictionnaire):\n",
    "        j += 1\n",
    "        Q = ec_add(EC, Q, big_step)\n",
    "    return dictionnaire[Q] + j*m"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ea332bf4",
   "metadata": {},
   "source": [
    "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)$.\n",
    "\n",
    "**Question 2.** Avec la fonction qui vient d'être implémentée, calculer le logarithme discret de $P = (165283, 514138)$ en base $G$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c2236b71",
   "metadata": {},
   "outputs": [],
   "source": [
    "EC = [1000003, 1, 1]\n",
    "G = (445619, 638237)\n",
    "P = (165283, 514138)\n",
    "ell = BSGS(EC, G, P)\n",
    "print(ell)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "66561f46",
   "metadata": {},
   "source": [
    "<!-- ## Exercice 3 : ECDSA -->"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "python",
   "language": "python",
   "name": "python"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}