{"cells":[{"metadata":{},"cell_type":"markdown","source":"\n\n\n© Copyright Franck CHEVRIER 2019-2022 https://www.python-lycee.com.
\nLes activités partagées sur Capytale sont sous licence Creative Commons.\n\n Pour exécuter une saisie Python, sélectionner la cellule et valider avec SHIFT+Entrée.\n"},{"metadata":{},"cell_type":"markdown","source":"# Chiffrement matriciel de Hill (corrigé)\n\n### Activité sur le chiffrement n°2\n##### (prérecquis: calcul matriciel, déterminant, inverse d'une matrice, congruences, théorème de Bézout)\n\n"},{"metadata":{},"cell_type":"markdown","source":"### Sommaire\n\n0. Notation : matrices congruentes
\n1. Chiffrement de Hill dans un cas particulier
\n2. Généralisation
\n"},{"metadata":{},"cell_type":"markdown","source":"## 0. Notation : matrices congruentes"},{"metadata":{},"cell_type":"markdown","source":"Dans cette activité, on étend la notion de congruence modulo $n$ ( $n \\geqslant 2$ ) à des matrices à coefficients entiers.
\nOn dira que deux matrices $A$ et $B$ à coefficients entiers sont congrues modulo $n$ si leurs coefficients correspondants sont deux à deux congrus modulo $n$.
On notera alors $A \\equiv B \\;[n]$.\n
\n\n\nAinsi, pour des matrices de dimension $2 \\times 2$ à coefficients entiers, on a :
\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]$.__
\n$\\;\\;\\;\\;\\;\\;$__Démontrer que $CA \\equiv CB \\;[n]$.__\n\n\n\nPosons $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}$.
\nOn a alors:
\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}$
\nVérifions que les premiers coefficients de chaque matrice sont congrus modulo $n$ :
\n$a \\equiv a'[n]$ donc $ea \\equiv ea'[n]$
\n$c \\equiv c'[n]$ donc $fc \\equiv fc'[n]$
\ndonc $ea+fc \\equiv ea'+fc'[n]$
\nDes 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\n\n"},{"metadata":{},"cell_type":"markdown","source":"## 1. Chiffrement de Hill dans un cas particulier"},{"metadata":{},"cell_type":"markdown","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.
\n
\nIls décident de coder leurs messages avec un chiffrement matriciel de Hill, à l'aide d'une matrice de chiffrement $ H= \\begin{pmatrix} 9 & 4 \\\\ 5 & 7 \\end{pmatrix} $.
\n
\nPour cela, ils commencent par remplacer chaque lettre du message à coder par son rang dans l'alphabet, comme l'indique le tableau ci-dessous:
\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
\nLes 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).
\nA 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$.
\nOn peut alors, en considérant les rangs dans l'alphabet, associer un couple de lettres au couple de lettres initial.
\n\nPar exemple:
\nArchibald 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\".
\n"},{"metadata":{},"cell_type":"markdown","source":"__1.1. Coder complètement le mot \"EUREKA\".__\n\n\n\nLe mot \"EUREKA\" est codé en \"MENJMY\".\n"},{"metadata":{},"cell_type":"markdown","source":"__1.2. On donne la fonction Python codage_Hill ci-dessous, qui permet de coder un message à l'aide d'une matrice de chiffrement H.__
\n$\\;\\;\\;\\;\\;\\;$__Exécuter les deux cellules pour vérifier le résultat de la question 1.1.__"},{"metadata":{"trusted":false},"cell_type":"code","source":"import numpy as np\n\n#Mise en mémoire de l'alphabet\nAlphabet=\"ABCDEFGHIJKLMNOPQRSTUVWXYZ\"\n\ndef 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","execution_count":null,"outputs":[]},{"metadata":{"trusted":false},"cell_type":"code","source":"#définition de la matrice de chiffrement H\nH = np.array([ [ 9 , 4 ],\n [ 5 , 7 ] ])\n\n#Appel à la fonction codage_Hill pour la construction du message codé\ncode = codage_Hill(\"EUREKA\",H)\ncode","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","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}$.__
\n$\\;\\;\\;\\;\\;$__Pourquoi la matrice $H^{-1}$ ne peut-elle pas être la matrice $D$ cherchée ?__\n\n\n\nLe déterminant de $H$ vaut $det(H)=9 \\times 7 - 5 \\times 4 = 43$.
\nComme $det(H) \\ne 0$, on en déduit que $H$ est inversible et :
\n$H^{-1}= \\frac{1}{43} \\begin{pmatrix} 7 & -4 \\\\ -5 & 9 \\end{pmatrix} $
\nLa matrice $H^{-1}$ ne convient pas pour être la matrice de décodage car elle n'est pas à coefficients entiers.\n\n"},{"metadata":{},"cell_type":"markdown","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]$.__
\n$\\;\\;\\;\\;\\;\\;\\;\\;\\;$__On dit que $m$ est l'inverse de $43$ modulo $26$__
\n$\\;\\;\\;\\;\\;\\;\\;\\;\\;$(pour démontrer l'existence, on pourra appliquer le théorème de Bézout)
\n\n\nExistence:
\n43 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]$).
\n
\nUnicité:
\nSupposons 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)$.
\nOr $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\n
\n\n$\\;\\;\\;\\;\\;$__b. Ecrire une fonction Python inv qui renvoie une valeur $m$ qui convient.__
\n$\\;\\;\\;\\;\\;\\;\\;\\;$(on pourra écrire une boucle qui teste un à un les candidats pour la valeur de $m$ à partir de $1$)
\n"},{"metadata":{"trusted":false},"cell_type":"code","source":"#Ecrire ici la fonction inv\n\ndef 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","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"$\\;\\;\\;\\;\\;$__c. A l'aide d'un appel à la fonction Python inv, déterminer une valeur de $m$ qui convient.__
\n\n"},{"metadata":{"trusted":false},"cell_type":"code","source":"#Effectuer ici l'appel à la fonction inv\ninv()","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"__1.5. a. Vérifier que la matrice $D_0=43H^{-1}$ est à coefficients entiers.__
\n\n\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\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]$.__
\n\n\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\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
\nLa matrice $D$ ainsi construite est donc la matrice de déchiffrement cherchée.
\n
\n\nSupposons que $Y \\equiv HX [26]$. Alors en multipliant par $D$, en utilisant le résultat de la question 0.0, il vient:
\n$DY \\equiv DHX \\;[26]$
\n$DY \\equiv 23D_0HX \\;[26]$ car $D=23D_0$
\n$DY \\equiv 23 \\times 43 H^{-1}HX \\;[26]$ car $D_0=43H^{-1}$
\n$DY \\equiv X [26]$ car $23 \\times 43 \\equiv 1 \\;[26]$ et $H^{-1}H=I_2$
\n
\nRéciproquement, supposons que $X \\equiv DY \\;[26]$. Alors en multipliant par $H$, en utilisant le résultat de la question 0.0, il vient:
\n$HX \\equiv HDY \\;[26]$
\n$HX \\equiv 23HD_0Y \\;[26]$
\n$HX \\equiv 23 \\times 43 HH^{-1}Y \\;[26]$
\n$HX \\equiv Y \\;[26]$
\n\n\n"},{"metadata":{},"cell_type":"markdown","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).__"},{"metadata":{"trusted":false},"cell_type":"code","source":"# définir ici la matrice de déchiffrement D\nD = np.array([ [ 5 , 12 ],\n [ 15 , 25 ] ])\nD","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"__1.7. Effectuer un appel à la fonction Python codage_Hill pour décoder le message qui a été codé à la question 1.2.__
\n$\\;\\;\\;\\;\\;$__Vérifier qu'on retrouve bien le mot \"EUREKA\".__"},{"metadata":{"trusted":false},"cell_type":"code","source":"# Effectuer ici l'appel à la fonction codage_Hill\ndecode = codage_Hill(\"MENJMY\",D)\ndecode","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"__1.8. Balthazar a reçu de la part d'Archibald le message suivant: \"IWVZHSGENJSSMQMVSIINAJ\". Décoder ce message.__"},{"metadata":{"trusted":false},"cell_type":"code","source":"# Utiliser cette zone de saisie pour décoder le message\ndecode = codage_Hill(\"IWVZHSGENJSSMQMVSIINAJ\",D)\ndecode","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"## 2. Généralisation"},{"metadata":{},"cell_type":"markdown","source":"On considère une matrice $H$ de dimension $2 \\times 2$ à coefficients entiers, de déterminant $d=det(H)$.
\nOn suppose que $d$ est non nul et premier avec $26$.\n"},{"metadata":{},"cell_type":"markdown","source":"__2.1. Justifier qu'il existe un entier $m$ tel que $dm \\equiv 1[26]$ ($m$ est inverse de $d$ modulo $26$)__
\n$\\;\\;\\;\\;\\;\\;$(on pourra utiliser le théorème de Bézout)\n\n\nComme $d$ et $26$ sont premiers entre eux, il existe un couple d'entiers $(m;v)$ tel que $md+26v=1$.
\nOn en déduit que $md \\equiv 1 [26]$.\n\n\n__2.2. Adapter la fonction inv de la question 1.4 pour qu'elle reçoive en argument une valeur d et renvoie son inverse m modulo $26$.__"},{"metadata":{"trusted":false},"cell_type":"code","source":"#Ecrire ici la fonction inv modifiée\n\ndef 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","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"__2.3. a. Justifier que la matrice $D_0=dH^{-1}$ est à coefficients entiers.__
\n\n\nComme $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}$.
\nOn en déduit que $D_0=dH^{-1}=\\begin{pmatrix} h & -f \\\\ -g & e \\end{pmatrix}$ est à coefficients entiers.\n\n\n$\\;\\;\\;\\;\\;$__b. On considère une matrice $D$ à coefficients entiers telle que $D \\equiv mD_0 [26]$.__
\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.__
\n$\\;\\;\\;\\;\\;\\;\\;\\;$__Démontrer que $Y \\equiv HX [26]$ est équivalent à $X \\equiv DY [26]$.__\n
\n\n(démonstration similaire à celle de la question 1.5.c)
\n
\nSupposons que $Y \\equiv HX [26]$. Alors en multipliant par $D$, en utilisant le résultat de la question 0.0, il vient:
\n$DY \\equiv DHX [26]$
\n$DY \\equiv mD_0HX [26]$ car $D=mD_0$
\n$DY \\equiv m \\times d H^{-1}HX [26]$ car $D_0=dH^{-1}$
\n$DY \\equiv X [26]$ car $m \\times d \\equiv 1 [26]$ et $H^{-1}H=I_2$
\n
\nRéciproquement, supposons que $X \\equiv DY [26]$. Alors en multipliant par $H$, en utilisant le résultat de la question 0.0, il vient:
\n$HX \\equiv HDY [26]$
\n$HX \\equiv mHD_0Y [26]$
\n$HX \\equiv m \\times d HH^{-1}Y [26]$
\n$HX \\equiv Y [26]$
\n\n\n\n\n"},{"metadata":{},"cell_type":"markdown","source":"__2.4. Convenir avec une autre personne d'une matrice de chiffrement $H$ (dont le déterminant est premier avec $26$).__
\n$\\;\\;\\;\\;\\;$__Chacun code alors un message à l'aide de la fonction Python codage_Hill en utilisant cette matrice, et le donne à l'autre.__
\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 codage_Hill.__"},{"metadata":{"trusted":false},"cell_type":"code","source":"#Utiliser les zones de saisie ci-dessous\n\n#définition de la matrice de chiffrement H\nH = np.array([ [ 7 , 15 ],[ 13 , 4 ] ])\nH","execution_count":null,"outputs":[]},{"metadata":{"trusted":false},"cell_type":"code","source":"#Codage d'un message\n\ncode = codage_Hill(\"ONARRIVEAUBOUTDELACTIVITE\",H)\ncode","execution_count":null,"outputs":[]},{"metadata":{"trusted":false},"cell_type":"code","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)\nd = H[0][0]*H[1][1]-H[0][1]*H[1][0]\nd","execution_count":null,"outputs":[]},{"metadata":{"trusted":false},"cell_type":"code","source":"#calcul de m (inverse de d)\nm = inv(d)\nm","execution_count":null,"outputs":[]},{"metadata":{"trusted":false},"cell_type":"code","source":"#calcul des matrices D0 et D\n#(attention, le calcul ne donne pas des valeurs int)\nD0 = d*np.linalg.inv(H)\nD0 = D0.astype(int)\nD = m*D0\nD","execution_count":null,"outputs":[]},{"metadata":{"trusted":false},"cell_type":"code","source":"decodage = codage_Hill(code,D)\ndecodage","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"\n\nLester S. Hill (1891-1961)"},{"metadata":{},"cell_type":"markdown","source":"© Copyright Franck CHEVRIER 2019-2022 https://www.python-lycee.com.
\nLes activités partagées sur Capytale sont sous licence Creative Commons.\n
\nDernière modification de l'activité : Juillet 2022"}],"metadata":{"celltoolbar":"Raw Cell Format","kernelspec":{"display_name":"Python 3","language":"python","name":"python3"}},"nbformat":4,"nbformat_minor":2}