{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "d35b022f",
   "metadata": {},
   "source": [
    "# Séance 10 : ECDSA\n",
    "\n",
    "\n",
    "Dans ce TP, nous allons explorer l'utilisation de l'algorithme de signature ECDSA. Les objectifs sont les suivants :\n",
    "1. Implémenter la signature ECDSA grâce à l'implémentation de l'arithmétique des courbes elliptiques réalisée à la séance précédente.\n",
    "2. Comprendre l'utilisation de la bibliothèque de cryptographie `openssl`, libre et multi-plateforme, ainsi que des modules de la bibliothèque python `pycryptodome`\n",
    "3. Faire interagir notre implémentation avec ces bibliothèques, et ainsi vérifier sa validité.\n",
    "\n",
    "\n",
    "## Exercice 1 : utilisation de `openssl` \n",
    "\n",
    "Dans cet exercice, nous allons manipuler la bibliothèque `openssl` afin de signer le contenu d'un fichier avec la signature ECDSA. Pour cela, notons :\n",
    " - `{type_de_courbe}` une chaîne de caractères représentant une courbe elliptique utilisée dans ECDSA (ici, nous utiliserons la courbe NIST P-256 nommée `prime256v1` dans openssl) ;\n",
    " - `{public_key}` un préfixe de fichier pour la clé publique ;\n",
    " - `{private_key}` un préfixe de fichier pour la clé privée ;\n",
    " - `{fichier}` le nom d'un fichier à signer ;\n",
    " - `{signature}` le nom de fichier dans lequel stocker la signature (en binaire).\n",
    "\n",
    "Le contenu du fichier sera haché avec la fonction de hachage SHA-256. Les commandes listées ci-dessous permettent alors respectivement de :\n",
    "- créer les paramètres de la courbe elliptique à utiliser, et les stocker dans le fichier `{type_de_courbe}.pem` ;\n",
    "- créer une paire de clés, et stocker la clé privée dans `{private_key}.pem` ;\n",
    "- dériver la clé publique, et la stocker dans `{public_key}.pem` ;\n",
    "- afficher la paire de clés et les paramètres de la courbe ;\n",
    "- signer le fichier ;\n",
    "- vérifier la signature obtenue.\n",
    "\n",
    "\n",
    "```\n",
    "openssl ecparam -name {type_de_courbe} -out {type_de_courbe}.pem\n",
    "openssl ecparam -in {type_de_courbe}.pem -genkey -noout -out {private_key}.pem\n",
    "openssl ec -in {private_key}.pem -pubout > {public_key}.pem\n",
    "openssl ec -in {private_key}.pem -text -param_enc explicit -noout\n",
    "openssl dgst -sha256 -sign {private_key}.pem -out {signature} {fichier}\n",
    "openssl dgst -sha256 -verify {public_key}.pem -signature {signature} {fichier}\n",
    "```\n",
    "\n",
    "**Question 1.** Dans un terminal, effectuer ces opérations, en choisissant des noms de fichiers appropriés. Observer les résultats (création de fichiers, affichage des paramètres, etc.).\n",
    "\n",
    "Si l'on passe par python (sera utile plus tard), on pourra exécuter les commandes :\n",
    "```\n",
    "type_de_courbe = \"prime256v1\"\n",
    "public_key = type_de_courbe + \"-pubkey\"\n",
    "private_key = type_de_courbe + \"-privkey\"\n",
    "fichier = \"fichier.txt\"\n",
    "signature = \"sign.bin\"\n",
    "\n",
    "commands = [\n",
    "    f\"openssl ecparam -name {type_de_courbe} -out {type_de_courbe}.pem\",\n",
    "    f\"openssl ecparam -in {type_de_courbe}.pem -genkey -noout -out {private_key}.pem\",\n",
    "    f\"openssl ec -in {private_key}.pem -pubout > {public_key}.pem\",\n",
    "    f\"openssl ec -in {private_key}.pem -text -param_enc explicit -noout\",\n",
    "    f\"openssl dgst -sha256 -sign {private_key}.pem -out {signature} {fichier}\",\n",
    "    f\"openssl dgst -sha256 -verify {public_key}.pem -signature {signature} {fichier}\",\n",
    "    ]\n",
    "\n",
    "for cmd in commands:\n",
    "    print(cmd)\n",
    "    os.system(cmd)\n",
    "```\n",
    "\n",
    "\n",
    "## Exercice 2 : implémentation personnelle de ECDSA\n",
    "\n",
    "Dans le but d'implémenter une version d'ECDSA, nous avons de fixer certains paramètres du sytème.\n",
    "\n",
    "D'abord, nous utiliserons la **courbe elliptique NIST P-256**, d'équation $y^2 = x^3 + ax + b$ sur $\\mathbb{F}_p$, qui admet un groupe de points cyclique, d'ordre premier $q$, et engendré par un point $G$, avec les valeurs suivantes :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f597be39",
   "metadata": {},
   "outputs": [],
   "source": [
    "p  = 0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff\n",
    "a  = 0xffffffff00000001000000000000000000000000fffffffffffffffffffffffc\n",
    "b  = 0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b\n",
    "Gx = 0x6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296\n",
    "Gy = 0x4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5\n",
    "G = (Gx, Gy)\n",
    "q = 0xffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "83ccd84b",
   "metadata": {},
   "source": [
    "Ensuite, nous utiliserons la fonction de hachage SHA-256. Pour l'utiliser facilement avec `pycryptodome`, on pourra utilisera la fonction suivante :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "0ee0cfd4",
   "metadata": {},
   "outputs": [],
   "source": [
    "from Crypto.Hash import SHA256\n",
    "\n",
    "def HASH(text):\n",
    "    aux = SHA256.new(bytes(text, \"utf-8\")).hexdigest()\n",
    "    return int(aux, 16)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4717a16b",
   "metadata": {},
   "source": [
    "Cette fonction prend en entrée une chaîne de caractères `text` au format `utf-8`, et retourne l'entier associé au haché de la chaîne par la fonction SHA-256.\n",
    "\n",
    "Enfin, on utilisera les fonctions d'arithémtique de courbe elliptique qu'on a développées à la séance précédente. Elles sont regroupées dans [ce fichier](https://lvzl.fr/teaching/2025-26/docs/cp/dev/ec.py). \n",
    "\n",
    "\n",
    "**Question 1.** Implémenter une fonction de génération de clé ECDSA `keygen(EC_group)`, qui prend en entrée une liste de $5$ éléments `EC_group = (p, a, b, G, q)` correspondant aux paramètres du système, et qui retourne une paire de clés publique/privée."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "6af39d35",
   "metadata": {
    "tags": [
     "remove-input"
    ]
   },
   "outputs": [],
   "source": [
    "import sys\n",
    "sys.path.insert(0, '../dev/')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "bd2bcb0f",
   "metadata": {},
   "outputs": [],
   "source": [
    "from ec import *\n",
    "\n",
    "def keygen(EC_group):\n",
    "    G, q = EC_group[3:]\n",
    "    a = random.randint(1, q-1)\n",
    "    A = ec_mult(EC_group[:3], G, a)\n",
    "    return (A, a)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9e029796",
   "metadata": {},
   "source": [
    "**Question 2.** Implémenter une fonction de signature ECDSA nommée `sign(EC_group, message, sk)`, qui prend en entrée les paramètres systèmes `EC_group`, le message (au format chaîne de caractères) `message` et la clé privée `sk`, et qui retourne la signature associée."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c04e5c7f",
   "metadata": {},
   "outputs": [],
   "source": [
    "def sign(EC_group, message, sk, to_bytes=False):\n",
    "    G, q = EC_group[3:]\n",
    "    h = HASH(message)\n",
    "    ok = False\n",
    "    while not(ok):\n",
    "        k = random.randint(1, q-1)\n",
    "        inv_k = pow(k, -1, q)\n",
    "        M = ec_mult(EC_group[:3], G, k)\n",
    "        b = M[0] % q\n",
    "        c = ((h + sk * b) * inv_k) % q\n",
    "        ok = (b != 0 and c != 0)\n",
    "    return (b, c)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1d130f3e",
   "metadata": {},
   "source": [
    "**Question 3.** Implémenter une fonction de vérification ECDSA `verif(EC_group, message, signature, pk)`, qui prend en entrée les paramètres systèmes `EC_group`, le message (au format chaîne de caractères) `message`, la signature `signature` (un couple d'entiers) et la clé publique `pk`, et qui teste si la signature donnée est valide."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "7e9fbb55",
   "metadata": {},
   "outputs": [],
   "source": [
    "def verif(EC_group, message, signature, pk):\n",
    "    G, q = EC_group[3:]\n",
    "    h = HASH(message)\n",
    "    b, c = signature\n",
    "    inv_c = pow(c, -1, q)\n",
    "    Q1 = ec_mult(EC_group[:3], G, (h * inv_c) % q)\n",
    "    Q2 = ec_mult(EC_group[:3], pk, (b * inv_c) % q)\n",
    "    Q = ec_add(EC_group[:3], Q1, Q2)\n",
    "    return (Q[0] % q) == b"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7049d11d",
   "metadata": {},
   "source": [
    "**Question 4.** Créer un message, des clés, signer et vérifier avec vos fonctions."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "1c2c363f",
   "metadata": {},
   "outputs": [],
   "source": [
    "P256_group = (p, a, b, G, q)\n",
    "message = \"Bonjour !\"\n",
    "pk, sk = keygen(P256_group)\n",
    "s = sign(P256_group, message, sk)\n",
    "v = verif(P256_group, message, s, pk)\n",
    "print(\"Véritable signature =>\", v)\n",
    "\n",
    "v2 = verif(P256_group, message, (1234, 5678), pk)\n",
    "print(\"Signature modifiée  =>\", v2)\n",
    "v3 = verif(P256_group, message, s, (1234, 5678))\n",
    "print(\"Message modifiée    =>\", v3)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d9940958",
   "metadata": {},
   "source": [
    "Le module `pycryptodome` permet aussi de signer et de vérifier des signatures ECDSA. Nous allons voir si le module peut vérifier nos signatures. \n",
    "\n",
    "**Attention !** La fonction `verify` de vérification de signature de `pycryptodome` utilise les conventions suivantes :\n",
    "  - elle prend en entrée le haché du message (et non le message brut) ;\n",
    "  - la signature doit être fournie sous un format binaire (et non un couple d'entiers), pour lequel sont concaténés les $32$ octets  de chacun des entiers ; \n",
    "  - si la signature est n'est pas valide, `verify` retourne une erreur (qu'il faut traiter) ; \n",
    "  - si la signature est valide, `verify` retourne `False`. Elle ne renvoie donc **jamais** `True`.\n",
    "\n",
    "\n",
    "Pour résumer, voici une manière d'utiliser les fonctions du module `pycryptodome` :\n",
    "\n",
    "```\n",
    "from Crypto.Signature import DSS\n",
    "from Crypto.PublicKey import ECC\n",
    "\n",
    "def pair_to_bytes(b, c):\n",
    "    return b\"\".join([b.to_bytes(32, 'big'), c.to_bytes(32, 'big')])\n",
    "    \n",
    "def bytes_to_pair(signature):\n",
    "    b = int.from_bytes(signature[:32], 'big')\n",
    "    c = int.from_bytes(signature[32:], 'big')\n",
    "    return b, c\n",
    "\n",
    "key_cryptodome = ECC.construct(curve='p256', d=sk, point_x=pk[0], point_y=pk[1])\n",
    "signer = DSS.new(key_cryptodome, 'deterministic-rfc6979')\n",
    "\n",
    "h = SHA256.new(message.encode(\"utf-8\"))\n",
    "s = pair_to_bytes(b, c)\n",
    "\n",
    "try:\n",
    "    signer.verify(h, s)\n",
    "    print(\"La signature est valide\")\n",
    "except:\n",
    "    print(\"La signature n'est pas valide\")\n",
    "```\n",
    "\n",
    "**Question 5.** Éxécutez les lignes précédentes et vérifiez que la signature construite est valide. Puis, modifiez le message et/ou la signature et observez que la signature n'est plus valide."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c4fb7c9c",
   "metadata": {},
   "outputs": [],
   "source": [
    "from Crypto.Signature import DSS\n",
    "from Crypto.PublicKey import ECC\n",
    "\n",
    "def pair_to_bytes(b, c):\n",
    "    return b\"\".join([b.to_bytes(32, 'big'), c.to_bytes(32, 'big')])\n",
    "    \n",
    "def bytes_to_pair(signature):\n",
    "    b = int.from_bytes(signature[:32], 'big')\n",
    "    c = int.from_bytes(signature[32:], 'big')\n",
    "    return b, c\n",
    "\n",
    "key_cryptodome = ECC.construct(curve='p256', d=sk, point_x=pk[0], point_y=pk[1])\n",
    "signer = DSS.new(key_cryptodome, 'deterministic-rfc6979')\n",
    "\n",
    "h = SHA256.new(message.encode(\"utf-8\"))\n",
    "s = pair_to_bytes(*s)\n",
    "\n",
    "try:\n",
    "    signer.verify(h, s)\n",
    "    print(\"La signature est valide\")\n",
    "except:\n",
    "    print(\"La signature n'est pas valide\")\n",
    "\n",
    "h2 = SHA256.new((message + \" modifié\").encode(\"utf-8\"))\n",
    "try:\n",
    "    signer.verify(h2, s)\n",
    "    print(\"La signature est valide\")\n",
    "except:\n",
    "    print(\"La signature n'est pas valide\")\n",
    "\n",
    "s2 = [ s[0] - 3, s[1] + 2 ]\n",
    "try:\n",
    "    signer.verify(h, s2)\n",
    "    print(\"La signature est valide\")\n",
    "except:\n",
    "    print(\"La signature n'est pas valide\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7b5ad928",
   "metadata": {},
   "source": [
    "## Exercice 3 : interaction avec openssl\n",
    "\n",
    "Dans **l'exercice 1**, nous avons observé que `openssl` produisait des clés et des signatures sous des formats très particuliers. Voici des manières de \"parser\" ces fichiers :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "937f2a58",
   "metadata": {},
   "outputs": [],
   "source": [
    "import os\n",
    "import base64\n",
    "\n",
    "# lit une clé publique au format .pem (pour la courbe considérée ici)\n",
    "# et retourne le point correspondant sous forme de couple d'entiers\n",
    "def read_public_key(filename):\n",
    "    with open(filename, \"r\") as f:\n",
    "        coded_key = f.readlines()[1:-1]\n",
    "        coded_key = [ c[:-1] for c in coded_key ]\n",
    "        key = base64.b64decode(\"\".join(coded_key))\n",
    "        pk_x = int.from_bytes(key[-64:-32], 'big')\n",
    "        pk_y = int.from_bytes(key[-32:], 'big')\n",
    "        return (pk_x, pk_y)\n",
    "\n",
    "# lit une clé privée au format .pem (pour la courbe considérée ici)\n",
    "# et retourne l'entier correspondant\n",
    "def read_private_key(filename):\n",
    "    with open(filename, \"r\") as f:\n",
    "        coded_key = f.readlines()[1:-1]\n",
    "        coded_key = [ c[:-1] for c in coded_key ]\n",
    "        key = base64.b64decode(\"\".join(coded_key))\n",
    "        sk = int.from_bytes(key[7:39], 'big')\n",
    "        return sk\n",
    "\n",
    "\n",
    "# lit une signature au format binaire\n",
    "# et retourne la paire d'entiers correspondant\n",
    "def read_signature(filename):\n",
    "    with open(filename, \"rb\") as f:\n",
    "        b = f.read()\n",
    "        r = int.from_bytes(b[-67:-35], \"big\")   # les octets de r (ou b)\n",
    "        s = int.from_bytes(b[-32:], \"big\")      # les octets de s (ou c)\n",
    "        return (r,s)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "54e58ef8",
   "metadata": {},
   "source": [
    "**Question.** Vérifier la signature générée par `openssl` à l'aide de la fonction de vérification `verif` implémentée plus haut."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "05551f89",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Les noms de fichiers qui seront utiles\n",
    "# Attention à ce que le fichier à signer existe bien (modifier le nom du fichier si besoin)\n",
    "type_de_courbe = \"prime256v1\"\n",
    "public_key = type_de_courbe + \"-pubkey\"\n",
    "private_key = type_de_courbe + \"-privkey\"\n",
    "fichier = \"../dev/fichier.txt\"\n",
    "signature = \"sign.bin\"\n",
    "\n",
    "# Les commandes à effectuer pour générer la signature (et observer les paramètres, cf exo1)\n",
    "commands = [\n",
    "    f\"openssl ecparam -name {type_de_courbe} -out {type_de_courbe}.pem\",\n",
    "    f\"openssl ecparam -in {type_de_courbe}.pem -genkey -noout -out {private_key}.pem\",\n",
    "    f\"openssl ec -in {private_key}.pem -pubout > {public_key}.pem\",\n",
    "    f\"openssl ec -in {private_key}.pem -text -param_enc explicit -noout\",\n",
    "    f\"openssl dgst -sha256 -sign {private_key}.pem -out {signature} {fichier}\",\n",
    "    f\"openssl dgst -sha256 -verify {public_key}.pem -signature {signature} {fichier}\",\n",
    "    ]\n",
    "\n",
    "# On exécute les commandes\n",
    "for cmd in commands[:-1]:\n",
    "    # print(cmd)\n",
    "    os.system(cmd)\n",
    "\n",
    "# On vérifie la signature par openssl\n",
    "print(\"Vérification par openssl de la signature de openssl :\")\n",
    "os.system(commands[-1])\n",
    "\n",
    "\n",
    "# On parse les clés et la signature pour les rentre dans nos formats\n",
    "pk = read_public_key(public_key + \".pem\")\n",
    "sk = read_private_key(private_key + \".pem\")\n",
    "r, s = read_signature(\"sign.bin\")\n",
    "\n",
    "# On lit le fichier et on vérifie la signature\n",
    "mmm = open(fichier, \"r\").read()\n",
    "print(\"Vérification par notre fonction de la signature de openssl :\")\n",
    "print(verif(P256_group, mmm, (r, s), pk))"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "python",
   "language": "python",
   "name": "python"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}