{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "4b6ddcad",
   "metadata": {
    "deletable": false,
    "editable": false,
    "run_control": {
     "frozen": true
    }
   },
   "source": [
    "# RSA et logarithme discret"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6a93a596",
   "metadata": {
    "deletable": false,
    "editable": false,
    "run_control": {
     "frozen": true
    }
   },
   "source": [
    "## 0. Utilitaire\n",
    "\n",
    "Écrire une fonction `randprime(b)` qui renvoie un nombre premier d'exactement $b$ bits, tiré uniformément, en se basant sur la fonction `random_prime` de SageMath."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "id": "2562a2a0",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "666533d3",
   "metadata": {
    "deletable": false,
    "editable": false,
    "run_control": {
     "frozen": true
    }
   },
   "source": [
    "## 1. RSA simplifié\n",
    "\n",
    "*Exercice tiré du TP noté 2022.*\n",
    "\n",
    "Le but de cet exercice est d'implanter, à l'aide des fonctions et classes de SageMath, les algorithmes nécessaires pour une version simplifiée du cryptosystème RSA."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "371e731c",
   "metadata": {
    "deletable": false,
    "editable": false,
    "run_control": {
     "frozen": true
    }
   },
   "source": [
    "1. Écrire une fonction `RSA_KeyGen(b)` qui prend en entrée un entier $b$ et génère un couple de clefs *publique* et *privée* $(pk,sk)$ selon l'algorithme suivant :\n",
    "    1. tirer aléatoirement deux nombres premiers $p$ et $q$ de $b$ bits ;\n",
    "    2. calculer $N = p×q$ et $φ(N) = (p-1)×(q-1)$ ;\n",
    "    3. tirer aléatoirement un entier $e$ premier avec $φ(N)$ ;\n",
    "    4. calculer l'inverse $d$ de $e$ modulo $φ(N)$ ;\n",
    "    5. renvoyer $pk = (N, e)$ et $sk = d$.\n",
    "    \n",
    "    Utiliser la fonction pour générer un couple de clefs de $100$ bits.\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "id": "1330d99b",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "7229d59b",
   "metadata": {
    "deletable": false,
    "editable": false,
    "run_control": {
     "frozen": true
    }
   },
   "source": [
    "2. Écrire une fonction `RSA_Encrypt(m, pk)` qui prend en entrée un entier $m∈ℤ$ et une clef publique $pk = (N,e)$, et renvoie le *chiffré* $c∈ℤ/Nℤ×ℤ/Nℤ$ de $m∈ℤ$ avec la clef $pk$, selon l'algorithme suivant :\n",
    "    1. construire l'anneau $ℤ/Nℤ$ ;\n",
    "    1. tirer aléatoirement un élément $r$ *inversible* dans $ℤ/Nℤ$ ;\n",
    "    1. calculer l'élément $s = (m×r)^e∈ℤ/Nℤ$ ;\n",
    "    1. renvoyer $c = (s,r)$.\n",
    "  \n",
    "   *Remarque : la fonction prend en entrée un élément de $ℤ$ et renvoie un couple d'éléments de $ℤ/Nℤ$.*\n",
    "   \n",
    "   Utiliser la fonction pour chiffrer un message $m$ de votre choix avec la clef publique de la question précédente."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "id": "901b78f7",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "c8fe03e0",
   "metadata": {
    "deletable": false,
    "editable": false,
    "run_control": {
     "frozen": true
    }
   },
   "source": [
    "3. Écrire une fonction `RSA_Decrypt(c, sk)` qui prend en entrée $c = (s,r)∈ℤ/Nℤ×ℤ/Nℤ$ et la clef privée $sk = d$, et renvoie le message $m∈ℤ$ avec l'algorithme suivant :\n",
    "    1. calculer $t= s^d×r^{-1}∈ℤ/Nℤ$ ;\n",
    "    1. renvoyer $m∈ℤ$, conversion de $t$ vers les entiers.\n",
    "    \n",
    "    Utiliser la fonction pour déchiffrer le chiffré de la question précédente (et vérifier qu'on retrouve bien le message d'origine)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "id": "bf11facd",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "c9cb51ac",
   "metadata": {
    "deletable": false,
    "editable": false,
    "run_control": {
     "frozen": true
    }
   },
   "source": [
    "5. Écrire une fonction de test `RSA_test(b)` qui génére un couple de clefs de $b$ bits, tire aléatoirement un message $m∈ℤ$, calcule son chiffré, puis déchiffre le chiffré et vérifie si on retrouve bien le message de départ.\n",
    "\n",
    "    Utiliser la fonction dans une boucle pour vérifier vos algorithmes, avec valeurs de $b$ jusqu'à 1000 bits."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "id": "c2747729",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "7c9f9e2d",
   "metadata": {
    "deletable": false,
    "editable": false,
    "run_control": {
     "frozen": true
    }
   },
   "source": [
    "## 2. Logarithme discret\n",
    "\n",
    "Soit $p$ un nombre premier. Étant donné un générateur $g$ de $ℤ/pℤ^×$ et un élément $h\\in ℤ/pℤ^×$, le *logarithme discret de $h$ en base $g$* est l'unique entier $n\\in\\{0,…,p-2\\}$ tel que $g^n = h$."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d5c26036",
   "metadata": {
    "deletable": false,
    "editable": false,
    "run_control": {
     "frozen": true
    }
   },
   "source": [
    "0. Écrire une fonction `randgen(b)` qui prend en entrée un entier $b$ et renvoie un couple $(p,g)$ où $p$ est un nombre premier de $b$ bits et $g$ est un générateur de $ℤ/pℤ^×$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "id": "028ec387",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "03fb7cbc",
   "metadata": {
    "deletable": false,
    "editable": false,
    "run_control": {
     "frozen": true
    }
   },
   "source": [
    "1.  1.  Écrire une fonction `log_naif(h,g,p)` qui prend en entrée un élément $h\\in ℤ/pℤ^×$ et un générateur $g\\in ℤ/pℤ^×$, et calcule l'unique entier $n\\in\\{0,…,p-2\\}$ tel que $g^n = h$. \n",
    "    \n",
    "    1. Jusqu'à quelle taille (environ) la fonction s'exécute en moins de 10 secondes ?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "id": "954c6df0",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "id": "4153db68",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "b11d6d72",
   "metadata": {
    "deletable": false,
    "editable": false,
    "run_control": {
     "frozen": true
    }
   },
   "source": [
    "2.  On s'intéresse à la stratégie « pas de bébés – pas de géants ». On définit $m = ⌊\\sqrt{p-1}⌋$. Si $h = g^n$, on écrit la division euclidienne $n = qm + r$. On a donc $h =g^{qm}g^r$, autrement dit $g^{qm} = h⋅g^{-r}$. L'idée est de précalculer tous les $g^{qm}$ pour $0 ≤ q ≤ n/m$ (*pas de géants*). Ensuite, on calcule les $h⋅g^{-r}$ pour $r = 0$, $1$, … jusqu'à trouver une égalité $h⋅g^{-r}=g^{qm}$ (*pas de bébés*). On en déduit que $n = qm+r$.\n",
    "\n",
    "    1.  Écrire une fonction `pas_de_geants(g, p)` qui renvoie un dictionnaire $G$ tel que $G[g^{qm}] = q$ pour $0 ≤ q ≤ (p-1)/m$. *On peut utiliser la fonction `isqrt` (lire la doc !).*\n",
    "    \n",
    "    1.  Écrire une fonction `log_discret(h, g, p)` qui calcule le logarithme discret de $h\\in ℤ/pℤ^×$ en base $g$, avec l'algorithme décrit.\n",
    "    \n",
    "    1.  Jusqu'à quelle taille de $p$ peut-on calculer le logarithme discret en moins de 10 secondes ? *Comparer avec la version naïve, et avec l'algorithme fourni par Sagemath : `h.log(g)`. Expliquer, par une analyse de coût, la différence observée `log_naif` et `log_discret`.*"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "id": "343a9306",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "id": "304761a9",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "id": "72acc8ba",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "dbee6907",
   "metadata": {
    "deletable": false,
    "editable": false,
    "run_control": {
     "frozen": true
    }
   },
   "source": [
    "3. L'algorithme précédent peut se généraliser. Supposons qu'on sache à l'avance que $h = g^n$ avec $a≤n≤b$. Alors on peut écrire $n = a + qm+r$ où $m = ⌊\\sqrt{b-a}⌋$, et trouver $q$ et $r$ comme précédemment. Les *pas de géants* sont les éléments de la forme $g^{a+qm}$ et les *pas de bébés* commencent à $g^a$.\n",
    "\n",
    "    1.  Écrire une fonction `log_discret_intervalle(h,g,p,a,b)` qui implante l'algorithme décrit.\n",
    "    1.  Vérifier que le temps de calcul ne dépend que très peu de $p$, mais essentiellement de la longueur $b-a$ de l'intervalle, et que votre algorithme, pour des intervalles de taille raisonnable, est plus efficace qu'un appel générique à `h.log(g)`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "id": "75700076",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "id": "4255a4ad",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "SageMath 9.5",
   "language": "sage",
   "name": "sagemath"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.10.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}