{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "fb185538",
   "metadata": {},
   "source": [
    "# Séance 1 : autour de l'échange de clefs de Diffie--Hellman\n",
    "\n",
    "\n",
    "\n",
    "## Pré-requis : installation de la bibliothèque `pycryptodome`\n",
    "\n",
    "Les TPs de ce cours de Cryptographie à clef publique nécessitent l'utilisation d'objets et de fonctions **non-natifs de python**, c'est-à-dire qui n'existent pas dans la version standard du langage. C'est le cas par exemple de certaines fonctions arithmétiques, ou de fonctions de nature cryptographique que nous n'aurons pas le temps d'implémenter par nous-mêmes.\n",
    "\n",
    "La bibliothèque `pycryptodome` contient l'ensemble de ces fonctions. Vous pouvez retrouver la documentation à [l'adresse suivante](https://pycryptodome.readthedocs.io/en/latest/index.html).\n",
    "\n",
    "**Pour l'installer** sur votre machine (Linux), ouvrez un terminal et entrez la commande suivante\n",
    "```\n",
    "pip install pycryptodomex\n",
    "```\n",
    "Suivant votre configuration, il se peut que vous deviez remplacer `pip` ci-dessus par `pip3` ou par `python -m pip`. Appelez l'enseignant si nécessaire. Pour les autres distributions, voir la [documentation](https://pycryptodome.readthedocs.io/en/latest/src/installation.html).\n",
    "\n",
    "\n",
    "Une fois l'installation réussie, vous pouvez essayer de faire fonctionner cette nouvelle bibliothèque. Pour cela, exécutez le contenu de la cellule suivante :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "8be3cbed",
   "metadata": {},
   "outputs": [],
   "source": [
    "from Crypto.Util.number import getPrime\n",
    "print(getPrime(10))\n",
    "print(getPrime(100))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ad84a4d2",
   "metadata": {},
   "source": [
    "Vous devriez voir apparaître **deux nombres premiers aléatoires** de taille $10$ bits et $100$ bits (mais pas nécessairement les mêmes que ceux affichés sur la page web du cours). En effet, **à retenir** : la fonction `getPrime(t)` du module `Crypto.Util.number` retourne un nombre premier aléatoire de taille `t` bits. Il existe aussi une fonction `isPrime(x)`, du même module, qui permet de tester si un entier $x$ est premier.\n",
    "\n",
    "\n",
    "\n",
    "## Exercice 1 : protocole de Diffie-Hellman dans les résidus quadratiques\n",
    "\n",
    "Le but de cet exercice est **d'implémenter le protocole d'échange de clés de Diffie-Hellman** dans le groupe $\\mathrm{QR}_p^\\times$ des résidus quadratiques modulo $p$, dans le cas favorable où $p$ est un nombre premier **sûr**. \n",
    "\n",
    "On rappelle que $p$ est un nombre premier **sûr** si $(p-1)/2$ est un nombre premier. Par conséquent, pour un nombre premier sûr, l'ordre du groupe des résidus quadratiques est premier, et tous les éléments différents de $1$ **de ce groupe** en sont donc des générateurs.\n",
    "\n",
    "On rappelle aussi que $x \\in \\mathbb{F}_p^\\times$ est un résidu quadratique (non-nul) si $x^{(p-1)/2} = 1$.\n",
    "\n",
    "\n",
    "**Question 1.** Écrire une fonction `set_global_parameters(t)` qui prend en entrée un paramètre de sécurité $t$ (la taille en bits du module $p$), et qui retourne deux entiers : un nombre premier sûr $p$ aléatoire et de taille $t$ bits, ainsi qu'un générateur $g$ du groupe $\\mathrm{QR}_p^\\times$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b0622834",
   "metadata": {},
   "outputs": [],
   "source": [
    "from Crypto.Util.number import getPrime, isPrime\n",
    "\n",
    "# def set_global_parameters(t):"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d67fd878",
   "metadata": {},
   "source": [
    "**Question 2.** Écrire une fonction `init_exchange(params)` qui prend en entrée une liste de paramètres (les entiers $p$ et $g$ de la question ci-dessus), et qui exécute la première étape du protocole de Diffie-Hellman :\n",
    "+ génération aléatoire d'un entier secret $a$ compris entre $1$ et $r-1$, où $r$ est l'ordre du groupe ;\n",
    "+ calcul de $\\alpha = g^a$, où $g$ est le générateur du groupe.\n",
    "\n",
    "Votre fonction retournera les entiers $a$ et $\\alpha$. Il faut penser que $a$ est l'entier gardé secrètement, tandis que $\\alpha$ est transmis à l'autre participant du protocole."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d79bda4f",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Votre réponse ici"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9d5d4dfd",
   "metadata": {},
   "source": [
    "**Question 3.** Écrire une fonction `compute_common_values(params, secret, received)` qui prend en entrée :\n",
    "+ `params` la liste des paramètres du protocole de Diffie-Hellman ;\n",
    "+ `secret` la valeur gardée secrètement par un des participants ;\n",
    "+ `received` la valeur transmise par l'autre participant ;\n",
    "\n",
    "et qui retourne la valeur commune calculée dans le protocole de Diffie-Hellman."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "5f05f831",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Votre réponse ici"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7554f055",
   "metadata": {},
   "source": [
    "**Question 4.** Grâce aux fonctions qui ont été implémentées, simuler un échange de clés de Diffie-Hellman entre deux personnes, dans le groupe $\\mathrm{QR}_p^\\times$, pour une taille $t = 256$. Vérifier que la valeur commune est identique."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "8f588a72",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Votre réponse ici"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c9a8c3d5",
   "metadata": {},
   "source": [
    "## Exercice 2 : calcul d'ordre et de générateur dans $\\mathbb{F}_p^\\times$\n",
    "\n",
    "L'objectif final de cet exercice est de **calculer un générateur** de $\\mathbb{F}_p^\\times$ dans un cadre \"assez\" général, en supposant uniquement connus les diviseurs premiers de $p-1$.\n",
    "\n",
    "\n",
    "On rappelle que, dans un groupe cyclique $\\mathbb{G}$ d'ordre $r$ dont on connaît la factorisation $r = \\prod_{i=1}^k p_i^{e_i}$, on peut calculer l'ordre d'un élément $x \\in \\mathbb{G}$ en calculant successivement certaines puissances de $x$. En effet, si $x$ a pour ordre $s$ dans $\\mathbb{G}$, alors $x^s = 1$ et pour tout $s'$ diviseur propre de $s$, on a $x^{s'} \\ne 1$ dans $\\mathbb{G}$.\n",
    "\n",
    "Ainsi, l'ordre de $x$ est le produit des $p_i^{d_i}$, où $d_i$ est le plus petit entier compris entre $0$ et $e_i$ tel que $x^{r/(p_i^{e_i-d_i})} = 1$. \n",
    "\n",
    "Pour calculer l'ordre d'un élément, on a donc l'algorithme suivant :\n",
    "1. Initialiser $s = r$\n",
    "1. **Pour tout** $i = 1, ..., k$:\n",
    "   1. **Tant que** $x^s = 1$ dans $\\mathbb{G}$, et si $p_i$ divise $s$, alors **faire** :\n",
    "      1. $s = s/p_i$\n",
    "   1. **Si** $x^s = 1$  dans $\\mathbb{G}$, alors **faire** :\n",
    "      1. $s = s \\times p_i$\n",
    "1. **Retourner** $s$\n",
    "\n",
    "\n",
    "\n",
    "**Question 1.** On suppose que pour un nombre premier $p$, les diviseurs premiers de $p-1$ sont connus et stockés dans une liste `factors`. Implémenter une fonction `multiplicative_order(x, p, factors)` qui prend en entrée ces valeurs, ainsi qu'un élément $x$ entre $1$ et $p-1$, et qui retourne l'ordre de $x$ dans $\\mathbb{F}_p^\\times$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "8a23535d",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Votre réponse ici"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "df523eec",
   "metadata": {},
   "source": [
    "**Question 2.** On donne dans le tableau suivant une liste de nombres premiers $p$, et la liste correspondante de diviseurs premiers de $p-1$. Calculer l'ordre de $x = 10$ pour chacun de ces cas.\n",
    "\n",
    "\n",
    "| nombre premier $p$ | diviseurs premiers de $p-1$ |\n",
    "| :---: | :---: | \n",
    "| 547 | [2, 3, 7, 13] |\n",
    "| 829 | [2, 3, 23] |\n",
    "| 577 | [2, 3] |\n",
    "| 735821558575852047177156941659 | [2, 3, 29, 31, 136414823614358926061764357] |\n",
    "| 1137117441125669215421702626619 | [2, 53, 16312391, 657630327122948771183] |\n",
    "| 1070938697827903187221632294947 | [2, 535469348913951593610816147473] |"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "7400cdb4",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Votre réponse ici"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "090009ea",
   "metadata": {},
   "source": [
    "Déterminer si $x \\in \\mathbb{G}$ est un générateur du groupe est plus simple que de calculer son ordre. En effet, il suffit de savoir si $\\mathrm{ord}(x) = r$ ou non. On a donc :\n",
    "$$\n",
    "x \\text{ générateur de } \\mathbb{G} \\; \\iff \\; x^{r/p_i} \\ne 1 \\forall i \\in \\{1, \\dots, k\\}\n",
    "$$\n",
    "\n",
    "\n",
    "**Question 3.** Écrire une fonction `is_generator(x, p, factors)` qui teste si $x$ est un générateur du groupe multiplicatif $\\mathbb{F}_p^\\times$. Parmi les nombres premiers $p$ listés plus haut, lequels admettent l'entier $x = 7$ comme générateur de $\\mathbb{F}_p^\\times$ ?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f4138608",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Votre réponse ici"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fe1ac664",
   "metadata": {},
   "source": [
    "**Question 4.** Écrire une fonction `smallest_generator(p, factors)` qui retourne le plus petit générateur du groupe multiplicatif $\\mathbb{F}_p^\\times$. Déterminer les plus petits générateurs des groupes  $\\mathbb{F}_p^\\times$ correspondant aux nombres premiers $p$ listés plus hauts."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d9642bfa",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Votre réponse ici"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "python",
   "language": "python",
   "name": "python"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}