{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "4b6ddcad",
   "metadata": {
    "deletable": false,
    "editable": false,
    "run_control": {
     "frozen": true
    }
   },
   "source": [
    "# TP noté\n",
    "\n",
    "Ce TP est constitué de deux exercices indépendants. Une case de réponse est prévue pour chaque question."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "347d8a13",
   "metadata": {
    "deletable": false,
    "editable": false,
    "run_control": {
     "frozen": true
    }
   },
   "source": [
    "*Par sécurité, merci d'indiquer votre nom :*"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "666533d3",
   "metadata": {
    "deletable": false,
    "editable": false,
    "run_control": {
     "frozen": true
    }
   },
   "source": [
    "## Exercice 1 : RSA\n",
    "\n",
    "Le but de cet exercice est d'implanter, à l'aide des fonctions et classes de SageMath, les algorithmes nécessaires pour le 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": [
    "## Exercice 2 : codes linéaires\n",
    "\n",
    "Soit $𝔽_q = ℤ/qℤ$ où $q$ est un nombre premier. Un *code linéaire sur $𝔽_q$* associe à un *message* $m∈𝔽_q^k$ un *mot de code* $c∈𝔽_q^n$, $n>k$, grâce à une *matrice génératrice* $G∈𝔽_q^{k×n}$ :\n",
    "$$c = G^⊤⋅m$$\n",
    "où $G^⊤$ est la transposée de $G$. On impose que $G$ soit de rang maximal $k$."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bb5d3c1e",
   "metadata": {
    "deletable": false,
    "editable": false,
    "run_control": {
     "frozen": true
    }
   },
   "source": [
    "1.  Écrire une fonction `Encode(G,m)` qui prend en entrée une matrice $G∈𝔽_q^{k×n}$ et un vecteur $m∈𝔽_q^k$ et renvoie le mot de code $c = G^⊤⋅m$.\n",
    "\n",
    "    Calculer l'encodage du mot $m = (4, 6, 2, 7)∈𝔽_{11}$ avec la matrice \n",
    "    $$G = \\begin{pmatrix}\n",
    "    1 & 2 & 9 & 5 & 5 & 9 & 10 \\\\\n",
    "    8 & 1 & 9 & 4 & 1 & 10 & 9 \\\\\n",
    "    3 & 10 & 4 & 8 & 9 & 4 & 1 \\\\\n",
    "    2 & 0 & 5 & 10 & 9 & 9 & 5\n",
    "    \\end{pmatrix}$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "id": "1b16f338",
   "metadata": {
    "tags": [
     "sujet"
    ]
   },
   "outputs": [],
   "source": [
    "m = vector(Zmod(11), [4,6,2,7])\n",
    "G = matrix(Zmod(11), [[1,2,9,5,5,9,10],[8,1,9,4,1,10,9],\n",
    "                      [3,10,4,8,9,4,1],[2,0,5,10,9,9,5]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "id": "6d6e32a2",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "4502ff1b",
   "metadata": {
    "deletable": false,
    "editable": false,
    "run_control": {
     "frozen": true
    }
   },
   "source": [
    "2. Écrire une fonction `Decode(G, c)` qui prend en entrée une matrice $G∈𝔽_q^{k×n}$ et un vecteur $c∈𝔽_q^n$ et renvoie le message $m∈𝔽_q^k$ tel que `Encode(G, m)` soit `c`.\n",
    "\n",
    "    Vérifier que le décodage du vecteur $c$ calculé à la question précédente est bien le message d'origine $m = (4,6,2,7)$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "id": "86af31a7",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "9a4ee878",
   "metadata": {
    "deletable": false,
    "editable": false,
    "run_control": {
     "frozen": true
    }
   },
   "source": [
    "3. L'objectif d'un code linéaire est de pouvoir *décoder* un message codé $c$, même si certaines valeurs de $c$ ont été perdues. Par exemple, on peut avoir un vecteur $c = (10, 2, 3, ?, ?, ?, 7)$ où les $?$ représentent des valeurs perdues. Un message $m∈𝔽_q^k$ est *compatible* avec $c$ si l'encodage $c'$ de $m$ vérifie $c_i = c'_i$ dès que $c_i ≠ \\ ?$.\n",
    "\n",
    "   Étant donné un vecteur $c$ avec des $?$, on veut déterminer dans quelle situation on est : soit il n'existe aucun message compatible avec $c$, soit il en existe un unique, soit il en existe plusieurs.\n",
    "   \n",
    "   En utilisant des calculs, pour chacun des trois vecteurs $c$ suivants, déterminer dans quelle situation on se trouve, et calculer le vecteur $m$ compatible avec $c$ dans le cas où il est unique.\n",
    "   \n",
    "   - $c = (10, 2, 3, ?, ?, ?, 7)$\n",
    "   - $c = (?, 6, ?, 5, 2, ?, 0)$\n",
    "   - $c = (2, ?, 1, ?, 0, 6, 4)$\n",
    "  \n",
    "   \n",
    "   *Indication : la méthode `G.matrix_from_columns(L)` permet de construire la matrice constituée des colonnes de $G$ dont les indices sont dans la liste $L$. N'hésitez pas à consulter la documentation via `G.matrix_from_columns?`*"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "id": "57954ed6",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "id": "858d223d",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "id": "0f0ff2ed",
   "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.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}