{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "c417fd15",
   "metadata": {},
   "source": [
    "# Séance 3 : Chiffrement ElGamal\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "## Exercice 1 : ElGamal dans $\\mathrm{QR}_p^\\times$\n",
    "\n",
    "Le but de cet exercice est **d'implémenter le chiffrement ElGamal**, sur le groupe des résidus quadratiques $\\mathrm{QR}_p^\\times$, avec $p$ un nombre premier sûr, c'est-à-dire tel que $(p-1)/2$ est également premier.\n",
    "\n",
    "\n",
    "**Question 1.** Reprendre la question de la séance 1 qui permet d'engendrer les paramètres globaux du chiffrement ElGamal dans le contexte de l'exercice, à savoir un nombre premier sûr $p$ de taille $t$ bits et un générateur $g$ du groupe des résidus quadratiques $\\mathrm{QR}_p^\\times$. On appellera une nouvelle fois `set_global_parameters(t)` la fonction qui retourne ces paramètres."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "db82df18",
   "metadata": {},
   "outputs": [],
   "source": [
    "from Crypto.Util.number import getPrime, isPrime\n",
    "\n",
    "def set_global_parameters(t):\n",
    "    p = getPrime(t)\n",
    "    while not(isPrime((p-1)//2)):\n",
    "        p = getPrime(t)\n",
    "    g = 2\n",
    "    while pow(g, (p-1)//2, p) != 1:\n",
    "        g += 1\n",
    "    return [p, g]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "db3cf3e2",
   "metadata": {},
   "source": [
    "**Question 2.** Écrire une fonction `elgamal_keygen(params)`, qui prend en entrée les paramètres globaux du système, et qui retourne une paire de clés publique/privée pour le chiffrement ElGamal."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "5f661368",
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "\n",
    "def elgamal_keygen(params):\n",
    "    p, g = params\n",
    "    sk = random.randint(1, (p-1)//2 - 1)\n",
    "    pk = pow(g, sk, p)\n",
    "    return pk, sk"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5f54b915",
   "metadata": {},
   "source": [
    "**Question 2.** Écrire une fonction `elgamal_encrypt(params, m, pk)`, qui prend en entrée `params` les paramètres globaux du système, `m` un message à chiffrer (que l'on supposera élément du groupe $\\mathrm{QR}_p^\\times$) et `pk` une clé publique ElGamal, et qui retourne le chiffré correspondant sous forme de couple."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "bb20e3b6",
   "metadata": {},
   "outputs": [],
   "source": [
    "def elgamal_encrypt(params, m, pk):\n",
    "    p, g = params\n",
    "    k = random.randint(1, (p-1)//2 - 1)\n",
    "    c1 = pow(g, k, p)\n",
    "    c2 = (pow(pk, k, p) * m) % p\n",
    "    return (c1, c2)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "80345663",
   "metadata": {},
   "source": [
    "**Question 3.** Écrire une fonction `elgamal_decrypt(params, c, sk)`, qui prend en entrée `params` les paramètres globaux du système, `c` un chiffré ElGamal sous forme de couple d'entiers, et `sk` une clé privée ElGamal, et qui retourne le déchiffré de `c` par la clé `sk`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "758e5258",
   "metadata": {},
   "outputs": [],
   "source": [
    "def elgamal_decrypt(params, c, sk):\n",
    "    p, g = params\n",
    "    c1, c2 = c\n",
    "    return (c2 * pow(c1, -sk, p) % p)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "041660aa",
   "metadata": {},
   "source": [
    "**Question 4.** Test.\n",
    "1. Créer une paire de clés publique/privée pour $t = 256$ (pour que cela ne prenne pas trop de temps).\n",
    "1. Vérifier que deux chiffrés du même message sont distincts.\n",
    "1. Vérifier, sur une centaine de tests, que le déchiffrement du chiffré d'un message aléatoire se déroule correctement."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a34a6c2d",
   "metadata": {},
   "outputs": [],
   "source": [
    "params = set_global_parameters(256)\n",
    "print(\"(p, g) =\", params)\n",
    "pk, sk = elgamal_keygen(params)\n",
    "print(\"Clé publique :\", pk)\n",
    "print(\"Clé privée   :\", sk)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d586060d",
   "metadata": {},
   "outputs": [],
   "source": [
    "p, g = params\n",
    "m = pow(g, 18031871, p)\n",
    "enc_1 = elgamal_encrypt(params, m, pk)\n",
    "enc_2 = elgamal_encrypt(params, m, pk)\n",
    "print(enc_1 != enc_2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "405b7c5f",
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "\n",
    "for _ in range(100):\n",
    "    m = random.randint(1, (p-1)//2-1)\n",
    "    c = elgamal_encrypt(params, m, pk)\n",
    "    if (m != elgamal_decrypt(params, c, sk)):\n",
    "        print(\"Erreur\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "114de0c8",
   "metadata": {},
   "source": [
    "## Exercice 2 : logarithme discret par *baby-step giant-step*\n",
    "\n",
    "Le but de cet exercice est d'implanter l'algorithme *baby-step giant-step* de calcul de logarithme discret. Nous allons l'implanter dans le contexte de l'exercice précédent, à savoir le groupe des résidus quadratiques $\\mathrm{QR}_p^\\times$, avec $p$ un nombre premier sûr.\n",
    "\n",
    "Rappel de l'algorithme :\n",
    "\n",
    "**Entrée :** les paramètres du groupe $\\mathrm{QR}_p^\\times$ (nombre premier $p$ et générateur $g$), et un élément $y \\in \\mathrm{QR}_p^\\times$.\n",
    "\n",
    "**Sortie :** le logarithme discret de $y$ en base $g$.\n",
    "\n",
    "1. Calculer $m = \\lceil \\sqrt{n} \\rceil$.\n",
    "1. Calculer $x = g^{-m} \\!\\!\\mod p$.\n",
    "1. (Précalcul) Construire un dictionnaire `D` dont les clés sont les $g^i \\!\\! \\mod p$, pour $0 \\le i < m$, et la valeur associée à $g^i$ est $i$.\n",
    "1. Initialiser $j = 0$\n",
    "1. **Tant que** $y$ n'est pas une clé du dictionnaire :\n",
    "   1. Mettre à jour $y$ en $y \\cdot x \\!\\!\\mod p$.\n",
    "   1. Incrémenter $j$.\n",
    "1. **Retourner** $i + jm$, où $i$ est la valeur associée à $y$ dans le dictionnaire `D`.\n",
    "\n",
    "\n",
    "\n",
    "**Question 1.** Implanter l'algorithme *baby-step giant-step* dans une fonction `baby_step_giant_step(params, y)`, où `params` désigne le couple de paramètres (module $p$, générateur $g$) du groupe $\\mathrm{QR}_p^\\times$, et où `y` est l'élément du groupe dont on cherche le logarithme en base $g$. Puis, tester votre fonction avec un module $p$ de taille $t = 32$ bits."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "5f88289c",
   "metadata": {},
   "outputs": [],
   "source": [
    "import math\n",
    "\n",
    "def baby_step_giant_step(params, y):\n",
    "    p, g = params\n",
    "    m = math.ceil(math.sqrt((p-1)//2))\n",
    "    x = pow(g, -m, p)\n",
    "    D = dict()\n",
    "    z = 1\n",
    "    for i in range(m):\n",
    "        D[z] = i\n",
    "        z = z*g % p\n",
    "    j = 0\n",
    "    while not(y in D):\n",
    "        y = y*x % p\n",
    "        j += 1\n",
    "    return D[y] + j*m\n",
    "    \n",
    "params = set_global_parameters(32)\n",
    "p, g = params\n",
    "a = random.randint(0, (p-1)//2-1)\n",
    "y = pow(g, a, p)\n",
    "print(a)\n",
    "print(baby_step_giant_step(params, y))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7eba78ac",
   "metadata": {},
   "source": [
    "**Question 2.** Tracer l'évolution du temps de calcul d'un logarithme discret en fonction de l'ordre du groupe (ou de $t$). Commenter."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e5a64d5d",
   "metadata": {},
   "outputs": [],
   "source": [
    "import time\n",
    "import matplotlib.pyplot as plt\n",
    "\n",
    "\n",
    "T = [ t for t in range(10, 32) ]\n",
    "TIMES = []\n",
    "N = 200\n",
    "\n",
    "for t in T:\n",
    "    params = set_global_parameters(t)\n",
    "    p, g = params\n",
    "    total_time = 0\n",
    "    for _ in range(N):\n",
    "        a = random.randint(0, (p-1)//2-1)\n",
    "        y = pow(g, a, p)\n",
    "        start = time.time()\n",
    "        baby_step_giant_step(params, y)\n",
    "        total_time += (time.time() - start)\n",
    "    TIMES.append(total_time/N)\n",
    "    \n",
    "\n",
    "plt.plot(T, [ math.log(x, 2) for x in TIMES ], ls='', marker='o', color='red')\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2d432f19",
   "metadata": {},
   "source": [
    "Le graphique ci-dessus trace le logarithme (en base $2$) du temps de calcul moyen de $N = 200$ logarithmes discrets en fonction de $t$. On oberve des points alignés sur une droite de pente $\\simeq 0.5$. Comme $p \\simeq 2^t$, cela signifie que le temps de calcul se comporte bien en $O(\\sqrt{p})$."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "python",
   "language": "python",
   "name": "python"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}