Chiffrement_Hill_correction.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![En tête general](img/En_tete_general.png)\n",
    "\n",
    "\n",
    "*(C) Copyright Franck CHEVRIER 2019-2020 http://www.python-lycee.com/*\n",
    "\n",
    "<span style=\"color: #9317B4\"> Pour exécuter une saisie Python, sélectionner la cellule et valider avec </span><span style=\"color: #B317B4\"><strong>SHIFT+Entrée</strong></span>.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# <span style=\"color:#6C3483\">Chiffrement matriciel de Hill </span> <span style=\"color:red\">(corrigé)</span>\n",
    "\n",
    "### <span style=\"color:#6C3483\">Activité sur le chiffrement n°2</span>\n",
    "##### <span style=\"color:#C18FDE\">(prérecquis: calcul matriciel, déterminant, inverse d'une matrice, congruences, théorème de Bézout)</span>\n",
    "\n",
    "![Illustration_detectives](img/Chiffrement_Hill.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <span style=\"color:#8E44AD\">Sommaire</span>\n",
    "\n",
    "<span style=\"color:#8E44AD\">0.</span> <a href=\"#0\">Notation : matrices congruentes</a><br>\n",
    "<span style=\"color:#8E44AD\">1.</span> <a href=\"#1\">Chiffrement de Hill dans un cas particulier</a><br>\n",
    "<span style=\"color:#8E44AD\">2.</span> <a href=\"#2\">Généralisation</a><br>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## <span style=\"color:#8E44AD\" id=\"0\">0. Notation : matrices congruentes</span>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Dans cette activité, on étend la notion de congruence modulo $n$ ( $n \\geqslant 2$ ) à des matrices à coefficients entiers.<br>\n",
    "On dira que deux matrices $A$ et $B$ à coefficients entiers sont congrues modulo $n$ si leurs coefficients correspondants sont deux à deux congrus modulo $n$.<br> On notera alors $A \\equiv B \\;[n]$.\n",
    "<br><br>\n",
    "\n",
    "\n",
    "Ainsi, pour des matrices de dimension $2 \\times 2$ à coefficients entiers, on a :<br>\n",
    "$ \\begin{pmatrix} a & b \\\\ c & d \\end{pmatrix} \\equiv \\begin{pmatrix} a' & b' \\\\ c' & d' \\end{pmatrix} [n]$ si et seulement si $\\begin{Bmatrix} a \\equiv a' [n] \\\\ b \\equiv b' [n] \\\\ c \\equiv c' [n] \\\\ d \\equiv d' [n] \\end{Bmatrix}$\n",
    "\n",
    "\n",
    "__0.0. On considère des matrices $A$; $B$ et $C$ de dimension $2 \\times 2$ à coefficients entiers, telles que $A \\equiv B \\;[n]$.__<br>\n",
    "$\\;\\;\\;\\;\\;\\;$__Démontrer que $CA \\equiv CB \\;[n]$.__\n",
    "\n",
    "\n",
    "<span style=\"color:red\">\n",
    "Posons $A=\\begin{pmatrix} a & b \\\\ c & d \\end{pmatrix}$ ; $B=\\begin{pmatrix} a' & b' \\\\ c' & d' \\end{pmatrix}$ et $C=\\begin{pmatrix} e & f \\\\ g & h \\end{pmatrix}$.<br>\n",
    "On a alors:<br>\n",
    "$CA=\\begin{pmatrix} ea+fc & eb+fd \\\\ ga+hc & gb+hd \\end{pmatrix}$ et $CB=\\begin{pmatrix} ea'+fc' & eb'+fd' \\\\ ga'+hc' & gb'+hd' \\end{pmatrix}$<br>\n",
    "Vérifions que les premiers coefficients de chaque matrice sont congrus modulo $n$ :<br>\n",
    "$a \\equiv a'[n]$ donc $ea \\equiv ea'[n]$<br>\n",
    "$c \\equiv c'[n]$ donc $fc \\equiv fc'[n]$<br>\n",
    "donc $ea+fc \\equiv ea'+fc'[n]$<br>\n",
    "Des raisonnements similaires permettent de démontrer que tous les coefficients de $CA$ et $CB$ sont deux à deux congrus modulo $n$, et on en déduit bien que $CA \\equiv CB \\;[n]$.\n",
    "</span>\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## <span style=\"color:#8E44AD\" id=\"1\">1. Chiffrement de Hill dans un cas particulier</span>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Deux détectives, Archibald et Balthazar, souhaitent échanger des messages secrets, de telle sorte qu'ils soient difficilement déchiffrables s'ils tombaient en de mauvaises mains. Pour simplifier, on supposera que les messages à coder sont écrits en majuscules, sans accents, et ne comportent pas d'espaces.<br>\n",
    "<br>\n",
    "Ils décident de coder leurs messages avec un <strong>chiffrement matriciel de Hill</strong>, à l'aide d'une <strong>matrice de chiffrement</strong> $ H= \\begin{pmatrix} 9 & 4 \\\\ 5 & 7 \\end{pmatrix} $.<br>\n",
    "<br>\n",
    "Pour cela, ils commencent par remplacer chaque lettre du message à coder par son rang dans l'alphabet, comme l'indique le tableau ci-dessous:<br>\n",
    "\n",
    "| A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z |  \n",
    "|:--|:--|:--|:--|:--|:--|:--|:--|:--|:--|:--|:--|:--|:--|:--|:--|:--|:--|:--|:--|:--|:--|:--|:--|:--|:--|\n",
    "| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10| 11| 12| 13| 14| 15| 16| 17| 18| 19| 20| 21| 22| 23| 24| 25|\n",
    "\n",
    "<br>\n",
    "Les valeurs sont ensuite regroupées par deux dans des matrices colonnes (S'il manque une valeur, on complète arbitrairement le texte avec une lettre).<br>\n",
    "A chaque matrice colonne $ X= \\begin{pmatrix} x_1 \\\\ x_2 \\end{pmatrix} $ ainsi construite, on associe la matrice colonne $HX$, définie modulo $26$, ce qui permet d'obtenir une matrice colonne $Y= \\begin{pmatrix} y_1 \\\\ y_2 \\end{pmatrix}$ de coefficients compris entre $0$ et $25$.<br>\n",
    "On peut alors, en considérant les rangs dans l'alphabet, associer un couple de lettres au couple de lettres initial.<br><br>\n",
    "\n",
    "<strong>Par exemple:</strong><br>\n",
    "Archibald souhaite coder le mot \"EUREKA\". Les premières lettres \"EU\" correspondent à la matrice $ X=\\begin{pmatrix} 4 \\\\ 20 \\end{pmatrix} $ qui donne la matrice codée $ HX= \\begin{pmatrix} 9 & 4 \\\\ 5 & 7 \\end{pmatrix} \\begin{pmatrix} 4 \\\\ 20 \\end{pmatrix}=\\begin{pmatrix} 116 \\\\ 160 \\end{pmatrix} \\equiv \\begin{pmatrix} 12 \\\\ 4 \\end{pmatrix} [26]$. On obtient donc les lettres codées \"ME\".<br>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__1.1. Coder complètement le mot \"EUREKA\".__\n",
    "\n",
    "\n",
    "<span style=\"color:red\">\n",
    "Le mot \"EUREKA\" est codé en \"MENJMY\".\n",
    "</span>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__1.2. On donne la fonction Python <mark>codage_Hill</mark> ci-dessous, qui permet de coder un message à l'aide d'une matrice de chiffrement H.__<br>\n",
    "$\\;\\;\\;\\;\\;\\;$__Exécuter les deux cellules pour vérifier le résultat de la question 1.1.__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "\n",
    "#Mise en mémoire de l'alphabet\n",
    "Alphabet=\"ABCDEFGHIJKLMNOPQRSTUVWXYZ\"\n",
    "\n",
    "def codage_Hill(message,H):\n",
    "    \"\"\"\n",
    "    fonction réalisant le codage du message\n",
    "    à l'aide de la matrice de chiffrement H\n",
    "    \"\"\"\n",
    "    code=\"\"\n",
    "    if len(message)%2 !=0: message += \"A\" # s'il n'y a pas un nombre pair de lettres, on complète le message avec un A\n",
    "        \n",
    "    for k in range(len(message)//2):                       # pour chaque couple de lettres:\n",
    "        X = np.array([[ Alphabet.index(message[2*k])],     #     on crée la matrice X\n",
    "                      [ Alphabet.index(message[2*k+1])]]) \n",
    "        Y = np.dot( H , X ) %26                            #     on calcule la matrice Y\n",
    "        code += Alphabet[Y[0][0]]+Alphabet[Y[1][0]]        #     on complète le code avec les deux lettres obtenues\n",
    "    \n",
    "    return code\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'MENJMY'"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#définition de la matrice de chiffrement H\n",
    "H = np.array([ [ 9 , 4 ],\n",
    "               [ 5 , 7 ] ])\n",
    "\n",
    "#Appel à la fonction codage_Hill pour la construction du message codé\n",
    "code = codage_Hill(\"EUREKA\",H)\n",
    "code"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Archibald et Balthazar ont convenu d'une matrice $H$ pour coder leurs messages, mais il leur faut maintenant aussi une méthode pour déchiffrer les messages. On cherche à déterminer une matrice $D$ qui, utilisée comme précédemment, permette ce décodage.\n",
    "\n",
    "\n",
    "__1.3. Vérifier que la matrice $H$ a pour déterminant $43$. En déduire que $H$ est une matrice inversible et calculer $H^{-1}$.__<br>\n",
    "$\\;\\;\\;\\;\\;$__Pourquoi la matrice $H^{-1}$ ne peut-elle pas être la matrice $D$ cherchée ?__\n",
    "\n",
    "\n",
    "<span style=\"color:red\">\n",
    "Le déterminant de $H$ vaut $det(H)=9 \\times 7 - 5 \\times 4 = 43$.<br>\n",
    "Comme $det(H) \\ne 0$, on en déduit que $H$ est inversible et :<br>\n",
    "$H^{-1}= \\frac{1}{43} \\begin{pmatrix} 7 & -4 \\\\ -5 & 9 \\end{pmatrix} $<br>\n",
    "La matrice $H^{-1}$ ne convient pas pour être la matrice de décodage car elle n'est pas à coefficients entiers.\n",
    "</span>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__1.4. a. Sans chercher à déterminer sa valeur, justifier qu'il existe un unique $m$ tel que $1 \\leqslant m \\leqslant 25$ et $43m \\equiv 1 [26]$.__<br>\n",
    "$\\;\\;\\;\\;\\;\\;\\;\\;\\;$__On dit que $m$ est l'inverse de $43$ modulo $26$__<br>\n",
    "$\\;\\;\\;\\;\\;\\;\\;\\;\\;$(pour démontrer l'existence, on pourra appliquer le théorème de Bézout)<br>\n",
    "\n",
    "<span style=\"color:red\">\n",
    "Existence:<br>\n",
    "43 et 26 étant premiers entre eux, il existe un couple d'entiers $(u;v)$ tel que $43u+26v=1$, ce qui donne $43u \\equiv 1[26]$. En posant $m$ le reste de la division euclidienne de $u$ par $26$, on a alors $1 \\leqslant m \\leqslant 25$ et $43m \\equiv 1[26]$ ($m$ ne peut pas être nul car sinon $u$ serait divisible par $26$, ce qui serait en contradiction avec $43u \\equiv 1[26]$).<br>\n",
    "<br>\n",
    "Unicité:<br>\n",
    "Supposons que $m_1$ et $m_2$ conviennent. On a alors $43m_1 \\equiv 1 [26]$ et $43m_2 \\equiv 1 [26]$ donc $43(m_1-m_2) \\equiv 0[26]$. Comme $26$ divise $43(m_1-m_2)$ et que $26$ et $43$ sont premiers entre eux, le théorème de Gauss permet de déduire que $26$ divise $(m1-m2)$.<br>\n",
    "Or $1 \\leqslant m_1 \\leqslant 25$ et $1 \\leqslant m_2 \\leqslant 25$ donnent $-24 \\leqslant m_1-m_2 \\leqslant 24$ et le seul multiple de $26$ compris dans cet intervalle est $0$. On en déduit que $m_1-m_2=0$ c'est à dire $m_1=m_2$.\n",
    "</span>\n",
    "<br>\n",
    "\n",
    "$\\;\\;\\;\\;\\;$__b. Ecrire une fonction Python <mark>inv</mark> qui renvoie une valeur $m$ qui convient.__<br>\n",
    "$\\;\\;\\;\\;\\;\\;\\;\\;$(on pourra écrire une boucle qui teste un à un les candidats pour la valeur de $m$ à partir de $1$)<br>\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "#Ecrire ici la fonction inv\n",
    "\n",
    "def inv():\n",
    "    \"\"\"\n",
    "    renvoie l'inverse de 43 modulo 26\n",
    "    \"\"\"\n",
    "    for m in range(1,26):\n",
    "        if 43*m %26 == 1:\n",
    "            return m\n",
    "    return None\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$\\;\\;\\;\\;\\;$__c. A l'aide d'un appel à la fonction Python <mark>inv</mark>, déterminer une valeur de $m$ qui convient.__<br>\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "23"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#Effectuer ici l'appel à la fonction inv\n",
    "inv()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__1.5. a. Vérifier que la matrice $D_0=43H^{-1}$ est à coefficients entiers.__<br>\n",
    "\n",
    "<span style=\"color:red\">\n",
    "$D_0=43H^{-1}=43 \\times \\frac{1}{43} \\begin{pmatrix} 7 & -4 \\\\ -5 & 9 \\end{pmatrix} =\\begin{pmatrix} 7 & -4 \\\\ -5 & 9 \\end{pmatrix}$ est bien à coefficients entiers.\n",
    "</span>\n",
    "\n",
    "$\\;\\;\\;\\;\\;$__b. Déterminer une matrice $D$, dont les coefficients sont entiers compris entre $0$ et $25$, telle que $D \\equiv m D_0[26]$.__<br>\n",
    "\n",
    "<span style=\"color:red\">\n",
    "$mD_0=23 \\begin{pmatrix} 7 & -4 \\\\ -5 & 9 \\end{pmatrix} = \\begin{pmatrix} 161 & -92 \\\\ -115 & 207 \\end{pmatrix} \\equiv \\begin{pmatrix} 5 & 12 \\\\ 15 & 25 \\end{pmatrix} [26]$ donc $D = \\begin{pmatrix} 5 & 12 \\\\ 15 & 25 \\end{pmatrix}$ convient.\n",
    "</span>\n",
    "\n",
    "$\\;\\;\\;\\;\\;$__c. On considère deux matrices colonnes $X=\\begin{pmatrix} x_1 \\\\ x_2 \\end{pmatrix}$ et $Y=\\begin{pmatrix} y_1 \\\\ y_2 \\end{pmatrix}$. Démontrer que $Y \\equiv HX [26]$ est équivalent à $X \\equiv DY [26]$.__\n",
    "<br><br>\n",
    "La matrice $D$ ainsi construite est donc la matrice de déchiffrement cherchée.<br>\n",
    "<br>\n",
    "<span style=\"color:red\">\n",
    "Supposons que $Y \\equiv HX [26]$. Alors en multipliant par $D$, en utilisant le résultat de la question <strong>0.0</strong>, il vient:<br>\n",
    "$DY \\equiv DHX \\;[26]$<br>\n",
    "$DY \\equiv 23D_0HX \\;[26]$ car $D=23D_0$<br>\n",
    "$DY \\equiv 23 \\times 43 H^{-1}HX \\;[26]$ car $D_0=43H^{-1}$<br>\n",
    "$DY \\equiv X [26]$ car $23 \\times 43 \\equiv 1 \\;[26]$ et $H^{-1}H=I_2$<br>\n",
    "<br>\n",
    "Réciproquement, supposons que $X \\equiv DY \\;[26]$. Alors en multipliant par $H$, en utilisant le résultat de la question <strong>0.0</strong>, il vient:<br>\n",
    "$HX \\equiv HDY \\;[26]$<br>\n",
    "$HX \\equiv 23HD_0Y \\;[26]$<br>\n",
    "$HX \\equiv 23 \\times 43 HH^{-1}Y \\;[26]$<br>\n",
    "$HX \\equiv Y \\;[26]$<br>\n",
    "</span>\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__1.6. Définir ci-dessous la matrice $D$ en langage Python (s'inspirer de la syntaxe utilisée pour $H$ dans la question 1.2).__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[ 5, 12],\n",
       "       [15, 25]])"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# définir ici la matrice de déchiffrement D\n",
    "D = np.array([ [ 5 , 12 ],\n",
    "               [ 15 , 25 ] ])\n",
    "D"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__1.7. Effectuer un appel à la fonction Python <mark>codage_Hill</mark> pour décoder le message qui a été codé à la question 1.2.__<br>\n",
    "$\\;\\;\\;\\;\\;$__Vérifier qu'on retrouve bien le mot \"EUREKA\".__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'EUREKA'"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Effectuer ici l'appel à la fonction codage_Hill\n",
    "decode = codage_Hill(\"MENJMY\",D)\n",
    "decode"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__1.8. Balthazar a reçu de la part d'Archibald le message suivant: \"IWVZHSGENJSSMQMVSIINAJ\". Décoder ce message.__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'SUPERJAIREUSSIADECODER'"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Utiliser cette zone de saisie pour décoder le message\n",
    "decode = codage_Hill(\"IWVZHSGENJSSMQMVSIINAJ\",D)\n",
    "decode"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## <span style=\"color:#8E44AD\" id=\"2\">2. Généralisation</span>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On considère une matrice $H$ de dimension $2 \\times 2$ à coefficients entiers, de déterminant $d=det(H)$.<br>\n",
    "On suppose que $d$ est non nul et premier avec $26$.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__2.1. Justifier qu'il existe un entier $m$ tel que $dm \\equiv 1[26]$ ($m$ est inverse de $d$ modulo $26$)__<br>\n",
    "$\\;\\;\\;\\;\\;\\;$(on pourra utiliser le théorème de Bézout)\n",
    "\n",
    "<span style=\"color:red\">\n",
    "Comme $d$ et $26$ sont premiers entre eux, il existe un couple d'entiers $(m;v)$ tel que $md+26v=1$.<br>\n",
    "On en déduit que $md \\equiv 1 [26]$.\n",
    "</span>\n",
    "\n",
    "__2.2. Adapter la fonction <mark>inv</mark> de la question 1.4 pour qu'elle reçoive en argument une valeur <mark>d</mark> et renvoie son inverse <mark>m</mark> modulo $26$.__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "#Ecrire ici la fonction inv modifiée\n",
    "\n",
    "def inv(d):\n",
    "    \"\"\"\n",
    "    renvoie l'inverse de d modulo 26\n",
    "    \"\"\"\n",
    "    for m in range(1,26):\n",
    "        if d*m %26 == 1:\n",
    "            return m\n",
    "    return None\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__2.3. a. Justifier que la matrice $D_0=dH^{-1}$ est à coefficients entiers.__<br>\n",
    "\n",
    "<span style=\"color:red\">\n",
    "Comme $d$ est non nul, $H=\\begin{pmatrix} e & f \\\\ g & h \\end{pmatrix}$ est inversible et $H^{-1}=\\frac{1}{d}\\begin{pmatrix} h & -f \\\\ -g & e \\end{pmatrix}$.<br>\n",
    "On en déduit que $D_0=dH^{-1}=\\begin{pmatrix} h & -f \\\\ -g & e \\end{pmatrix}$ est à coefficients entiers.\n",
    "</span>\n",
    "\n",
    "$\\;\\;\\;\\;\\;$__b. On considère une matrice $D$ à coefficients entiers telle que $D \\equiv mD_0 [26]$.__<br>\n",
    "$\\;\\;\\;\\;\\;\\;\\;\\;$__On considère deux matrices colonnes $X=\\begin{pmatrix} x_1 \\\\ x_2 \\end{pmatrix}$ et $Y=\\begin{pmatrix} y_1 \\\\ y_2 \\end{pmatrix}$ à coefficients entiers.__<br>\n",
    "$\\;\\;\\;\\;\\;\\;\\;\\;$__Démontrer que $Y \\equiv HX [26]$ est équivalent à $X \\equiv DY [26]$.__\n",
    "<br><br>\n",
    "<span style=\"color:red\">\n",
    "(démonstration similaire à celle de la question 1.5.c)<br>\n",
    "<br>\n",
    "Supposons que $Y \\equiv HX [26]$. Alors en multipliant par $D$, en utilisant le résultat de la question <strong>0.0</strong>, il vient:<br>\n",
    "$DY \\equiv DHX [26]$<br>\n",
    "$DY \\equiv mD_0HX [26]$ car $D=mD_0$<br>\n",
    "$DY \\equiv m \\times d H^{-1}HX [26]$ car $D_0=dH^{-1}$<br>\n",
    "$DY \\equiv X [26]$ car $m \\times d \\equiv 1 [26]$ et $H^{-1}H=I_2$<br>\n",
    "<br>\n",
    "Réciproquement, supposons que $X \\equiv DY [26]$. Alors en multipliant par $H$, en utilisant le résultat de la question <strong>0.0</strong>, il vient:<br>\n",
    "$HX \\equiv HDY [26]$<br>\n",
    "$HX \\equiv mHD_0Y [26]$<br>\n",
    "$HX \\equiv m \\times d HH^{-1}Y [26]$<br>\n",
    "$HX \\equiv Y [26]$<br>\n",
    "</span>\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__2.4. Convenir avec une autre personne d'une matrice de chiffrement $H$ (dont le déterminant est premier avec $26$).__<br>\n",
    "$\\;\\;\\;\\;\\;$__Chacun code alors un message à l'aide de la fonction Python <mark>codage_Hill</mark> en utilisant cette matrice, et le donne à l'autre.__<br>\n",
    "$\\;\\;\\;\\;\\;$__Enfin, après avoir déterminé la matrice de décodage $D$, chacun décode le message reçu à l'aide de la fonction Python <mark>codage_Hill</mark>.__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[ 7, 15],\n",
       "       [13,  4]])"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#Utiliser les zones de saisie ci-dessous\n",
    "\n",
    "#définition de la matrice de chiffrement H\n",
    "H = np.array([ [ 7 , 15 ],[ 13 , 4 ] ])\n",
    "H"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'HAVQFTZDOCJRJYDDZNNYHGDYCA'"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#Codage d'un message\n",
    "\n",
    "code = codage_Hill(\"ONARRIVEAUBOUTDELACTIVITE\",H)\n",
    "code"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "-167"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# LES CALCULS SUIVANTS PEUVENT ETRE FAIT A PART, SANS PYTHON\n",
    "# LES SYNTAXES D'UTILISATION DES MATRICES SONT EXPERTES\n",
    "# ET IL Y A DES PRECAUTIONS A PRENDRE SUR LE TYPE DES VARIABLES (int)\n",
    "\n",
    "#calcul du déterminant de H\n",
    "#(attention, l'utilisation de la fonction np.linalg.det de numpy ne renvoie pas un int)\n",
    "d = H[0][0]*H[1][1]-H[0][1]*H[1][0]\n",
    "d"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "7"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#calcul de m (inverse de d)\n",
    "m = inv(d)\n",
    "m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[  28, -105],\n",
       "       [ -91,   49]])"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#calcul des matrices D0 et D\n",
    "#(attention, le calcul ne donne pas des valeurs int)\n",
    "D0 = d*np.linalg.inv(H)\n",
    "D0 = D0.astype(int)\n",
    "D = m*D0\n",
    "D"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'ONARRIVEAUBOUTDELACTIVITEA'"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "decodage = codage_Hill(code,D)\n",
    "decodage"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![Hill](img/Hill.png)\n",
    "\n",
    "<center><a href=\"https://fr.wikipedia.org/wiki/Lester_S._Hill\">Lester S. Hill</a> (1891-1961)</center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*(C) Copyright Franck CHEVRIER 2019-2020 http://www.python-lycee.com/*\n"
   ]
  }
 ],
 "metadata": {
  "celltoolbar": "Raw Cell Format",
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "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.7.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}