{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "7898bcdc",
   "metadata": {},
   "source": [
    "# Séance 2 : RSA\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "## Exercice 1 : RSA \"brut\"\n",
    "\n",
    "Le but de cet exercice est **d'implémenter le chiffrement RSA brut** avec des paramètres réels. En particulier :\n",
    "- on choisira l'exposant public $e$ égal à $2^{16}+1 = 65537$, quitte à regénérer des nombres premiers\n",
    "- le chiffrement et déchiffrement seront déterministes (pour la conversion sémantiquement sûre, voir exercice suivant)\n",
    "\n",
    "\n",
    "**Question 1.** Écrire une fonction `rsa_keygen(t)` qui retourne une paire de clés publique/privée du chiffrement RSA. Cette fonction prend en entrée un paramètre `t`, la taille en bits du module RSA (l'entier $n = pq$) qui sera construit. On peut supposer `t` pair pour simplifier."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e862e15c",
   "metadata": {},
   "outputs": [],
   "source": [
    "from Crypto.Util.number import getPrime, isPrime\n",
    "from math import gcd\n",
    "\n",
    "def rsa_keygen(t):\n",
    "    assert(t >= 10)\n",
    "    p = getPrime(t//2)\n",
    "    q = getPrime(t//2)\n",
    "    while p == q:\n",
    "        q = getPrime(t)\n",
    "    n = p*q\n",
    "    phi = (p-1)*(q-1)\n",
    "    e = 2**16 + 1\n",
    "    if gcd(e, phi) != 1:\n",
    "        return rsa_keygen(t)\n",
    "    d = pow(e, -1, phi)\n",
    "    return ((n, e), d)\n",
    "    \n",
    "print(rsa_keygen(24))\n",
    "print(rsa_keygen(256))\n",
    "print(rsa_keygen(2048))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "59395123",
   "metadata": {},
   "source": [
    "**Question 2.** Écrire une fonction `rsa_encrypt(m, pk)`, qui prend en entrée un message `m` sous forme d'entier, et qui retourne un chiffré de RSA par la clé publique `pk`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "33d57354",
   "metadata": {},
   "outputs": [],
   "source": [
    "def rsa_encrypt(m, pk):\n",
    "    return pow(m, pk[1], pk[0])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6a64387e",
   "metadata": {},
   "source": [
    "**Question 3.** Écrire une fonction `rsa_decrypt(c, pk, sk)`, qui prend en entrée un chiffré RSA `c` sous forme d'entier, et qui retourne le déchiffré de `c` par la paire de clés `pk`/`sk`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e60ca11f",
   "metadata": {},
   "outputs": [],
   "source": [
    "def rsa_decrypt(c, pk, sk):\n",
    "    return pow(c, sk, pk[0])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7033c4ff",
   "metadata": {},
   "source": [
    "**Question 4.** Test.\n",
    "1. Créer une paire de clés publique/privée pour $t = 2048$.\n",
    "1. Calculer le chiffré de $n+1$, puis le déchiffrer. Que remarquez-vous ? Modifier la fonction de chiffrement en fonction.\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": "1df258b4",
   "metadata": {},
   "outputs": [],
   "source": [
    "pk, sk = rsa_keygen(2048)\n",
    "print(\"Clé publique :\", pk)\n",
    "print(\"Clé privée   :\", sk)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d30f2f5c",
   "metadata": {},
   "outputs": [],
   "source": [
    "m = pk[0]+1\n",
    "c = rsa_encrypt(m, pk)\n",
    "res = rsa_decrypt(c, pk, sk)\n",
    "print(m == res, res)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "34483176",
   "metadata": {},
   "source": [
    "On remarque que le déchiffré du chiffré de $n+1$ vaut $1$, et ne correspond donc pas au message initial. En effet, RSA n'est valide que si le message est strictement inférieur au module."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "854b2b4b",
   "metadata": {},
   "outputs": [],
   "source": [
    "def rsa_encrypt(m, pk):\n",
    "    assert (0 <= m < pk[0]) \n",
    "    return pow(m, pk[1], pk[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "45734f14",
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "\n",
    "for _ in range(100):\n",
    "    m = random.randint(0, pk[0]-1)\n",
    "    if (m != rsa_decrypt(rsa_encrypt(m, pk), pk, sk)):\n",
    "        print(\"Erreur\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d0e7a098",
   "metadata": {},
   "source": [
    "## Exercice 2 : déchiffrement accéléré pour RSA\n",
    "\n",
    "Nous avons vu en cours qu'il est possible d'accélérer la procédure de déchiffrement, en effectuant les calculs sur des entiers de taille plus petite.\n",
    "\n",
    "Rappelons la méthode (voir le cours si nécessaire) :\n",
    "\n",
    "1. Dans la **génération des clefs**, les données suivantes sont calculées :\n",
    "   - l'entier $d_p = d \\mod (p-1)$\n",
    "   - l'entier $d_q = d \\mod (q-1)$\n",
    "   - l'entier $i_q = q^{-1} \\mod p$ \n",
    "1. La **clé privée** $d$ est remplacée par les cinq entiers $(d_p, d_q, i_q, p, q)$\n",
    "1. Lors du **déchiffrement**, au lieu de calculer $c^d \\mod n$, on calcule successivement :\n",
    "   - l'entier $m_p = c^{d_p} \\mod p$\n",
    "   - l'entier $m_q = c^{d_q} \\mod q$\n",
    "   - la combinaison linéaire entière (sans réduction $\\mod n$) : $m = m_q + q \\cdot (i_q \\cdot (m_p - m_q) \\mod p)$\n",
    "\n",
    "\n",
    "**Question 1.** Dans le même contexte que pour l'exercice 1, écrire une fonction `rsa_keygen_fast(t)` qui effectue la génération de ces nouvelles clefs RSA."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d43800d8",
   "metadata": {},
   "outputs": [],
   "source": [
    "def rsa_keygen_fast(t):\n",
    "    assert(t >= 10)\n",
    "    p = getPrime(t//2)\n",
    "    q = getPrime(t//2)\n",
    "    while p == q:\n",
    "        q = getPrime(t)\n",
    "    n = p*q\n",
    "    phi = (p-1)*(q-1)\n",
    "    e = 2**16 + 1\n",
    "    if gcd(e, phi) != 1:\n",
    "        return rsa_keygen_fast(t)\n",
    "    d = pow(e, -1, phi)\n",
    "    dp = d % (p-1)\n",
    "    dq = d % (q-1)\n",
    "    iq = pow(q, -1, p)\n",
    "    \n",
    "    return ((n, e), (dp, dq, iq, p, q))\n",
    "    \n",
    "# vérification partielle\n",
    "pk, sk = rsa_keygen_fast(1024)\n",
    "n, e = pk\n",
    "dp, dq, iq, p, q = sk\n",
    "print(1 == (e * dp) % (p-1) and 1 == (e * dq) % (q-1))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7e16eb3a",
   "metadata": {},
   "source": [
    "**Question 2.** Écrire une fonction `rsa_decrypt_fast(c, sk)`, qui prend en entrée un chiffré RSA `c` sous forme d'entier, et qui retourne le déchiffré de `c` par la nouvelle clé privée `sk`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "239e9d8d",
   "metadata": {},
   "outputs": [],
   "source": [
    "def rsa_decrypt_fast(c, sk):\n",
    "    dp, dq, iq, p, q = sk\n",
    "    mp = pow(c, dp, p)\n",
    "    mq = pow(c, dq, q)\n",
    "    m = mq + q * ( (iq * (mp - mq)) % p )\n",
    "    return m"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ee73322c",
   "metadata": {},
   "source": [
    "**Question 3.** Vérifier sur des exemples que le déchiffrement est correct. On pourra utiliser la fonction de chiffrement de l'exercice 1."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f3748053",
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "pk, sk = rsa_keygen_fast(2048)\n",
    "\n",
    "for _ in range(100):\n",
    "    m = random.randint(0, pk[0]-1)\n",
    "    if (m != rsa_decrypt_fast(rsa_encrypt(m, pk), sk)):\n",
    "        print(\"Erreur\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ef932b96",
   "metadata": {},
   "source": [
    "**Question 4.** En faisant la moyenne des temps d'exécution sur des centaines de déchiffrement, donner une valeur expériementale du **facteur** de réduction de temps de calcul obtenu par cette accélération. On donnera la valeur obtenue pour $t = 1024$, et on pourra également tracer les temps de calculs en fonction $t$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "97bc6d03",
   "metadata": {
    "tags": [
     "remove-input"
    ]
   },
   "outputs": [],
   "source": [
    "random.seed(10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "211632bf",
   "metadata": {},
   "outputs": [],
   "source": [
    "import time\n",
    "import matplotlib.pyplot as plt\n",
    "\n",
    "\n",
    "T = [ 50 * i for i in range(1,40) ]\n",
    "times_classic = []\n",
    "times_fast    = []\n",
    "N = 100\n",
    "\n",
    "for t in T:\n",
    "    \n",
    "    pk, sk = rsa_keygen(t)\n",
    "    total_time = 0\n",
    "    for _ in range(N):\n",
    "        m = random.randint(0, pk[0]-1)\n",
    "        c = rsa_encrypt(m, pk)\n",
    "        start = time.time()\n",
    "        mm = rsa_decrypt(m, pk, sk)\n",
    "        total_time += (time.time() - start)\n",
    "    times_classic.append(total_time/N)\n",
    "\n",
    "    pk, sk = rsa_keygen_fast(t)\n",
    "    total_time = 0\n",
    "    for _ in range(N):\n",
    "        m = random.randint(0, pk[0]-1)\n",
    "        c = rsa_encrypt(m, pk)\n",
    "        start = time.time()\n",
    "        mm = rsa_decrypt_fast(m, sk)\n",
    "        total_time += (time.time() - start)\n",
    "    times_fast.append(total_time/N)\n",
    "\n",
    "plt.plot(T, times_classic, color='blue')\n",
    "plt.plot(T, times_fast, color='red')\n",
    "plt.show()\n",
    "print(f\"Pour t = {T[-1]}, le facteur de gain est de {times_classic[-1] / times_fast[-1]}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "eef67309",
   "metadata": {},
   "source": [
    "Ci-dessus, on a tracé en fonction de $t$ :\n",
    "- en bleu le temps moyen (sur $N = 100$ échantillons) de déchiffrement \"classique\" d'un chiffré RSA ;\n",
    "- en rouge le temps moyen (sur $N = 100$ échantillons) de déchiffrement \"accéléré\" d'un chiffré RSA.\n",
    "\n",
    "Puis, on donne affiche le facteur de gain pour la plus grande valeur de $t$.\n",
    "\n",
    "\n",
    "\n",
    "<!-- ## Exercice 2 : RSA et OAEP -->\n",
    "\n",
    "<!-- Le but de cet exercice est **d'implémenter une version sémantiquement sûre** du chiffrement RSA. Pour cela, on utilisera le système de remplissage OAEP vu en cours, qu'on peut également retrouver [ici](https://fr.wikipedia.org/wiki/Optimal_Asymmetric_Encryption_Padding). -->\n",
    "\n",
    "<!-- Nous aurons donc besoin de deux fonctions de hachage $G$ et $H$. Ici, pour l'exemple, nous utiliserons pour $G$ et pour $H$ la même fonction de hachage `SHA3-256`, implémentée par exemple dans la bibliothèque cryptodome : [pycryptodome.readthedocs.io/en/latest/src/hash/sha3_256.html](https://pycryptodome.readthedocs.io/en/latest/src/hash/sha3_256.html). Cette fonction prend en entrée un tableau d'octets de taille quelconque, et retourne le haché de cette suite d'octets sous la forme d'une chaine de caractères en hexadécimal. -->\n",
    "\n",
    "<!-- **Exemple** d'utilisation sur du **texte** : -->\n",
    "\n",
    "<!-- ```{code-cell} -->\n",
    "<!-- from Crypto.Hash import SHA3_256 -->\n",
    "\n",
    "<!-- H = SHA3_256.new()         # on initialise la fonction de hachage -->\n",
    "<!-- H.update(b'Some data')     # on lui passe le message à hacher en paramètre, sous forme de tableau d'octets -->\n",
    "<!-- print(H.hexdigest())        # on récupère le haché correspondant -->\n",
    "<!-- ``` -->\n",
    "\n",
    "<!-- **Exemple** d'utilisation sur un **entier** :  -->\n",
    "\n",
    "<!-- ```{code-cell} -->\n",
    "<!-- k = 1234567 ** 89 -->\n",
    "\n",
    "<!-- # on calcule la taille (en octets) du tableau à construire -->\n",
    "<!-- size = (k.bit_length() - 1) // 8 + 1 -->\n",
    "\n",
    "<!-- # on effectue la conversion en octets ('little' précise l'endianness,  -->\n",
    "<!-- # c'est-à-dire l'ordre de lecture des octets) -->\n",
    "<!-- k_bytes = k.to_bytes(size, 'little') -->\n",
    "\n",
    "<!-- H = SHA3_256.new() -->\n",
    "<!-- H.update(k_bytes) -->\n",
    "<!-- print(H.hexdigest()) -->\n",
    "<!-- ``` -->\n",
    "\n",
    "\n",
    "<!-- **Question 1.** -->\n",
    "\n",
    "<!-- <only student> -->\n",
    "<!-- ```{code-cell} -->\n",
    "<!-- # À compléter -->\n",
    "<!-- ``` -->\n",
    "<!-- <endonly> -->\n",
    "<!-- <only teacher> -->\n",
    "<!-- ```{code-cell} -->\n",
    "<!-- def rsa_encrypt_oaep(m, pk, sizes): -->\n",
    "<!--     k0, k1 = sizes -->\n",
    "<!--     c = rsa_encrypt(m, pk) -->\n",
    "<!--     r = random.randint(0, 2**k0-1) -->\n",
    "<!--     c *= 2**k1 -->\n",
    "<!--     pass -->\n",
    "<!-- ``` -->"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "python",
   "language": "python",
   "name": "python"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}