title: Chiffre de Hill
text: # Chiffre de Hill
  
  En cryptographie symétrique, le chiffre de Hill est un modèle simple d'extension du chiffrement affine à un bloc. Ce système étudié par Lester S. Hill, utilise les propriétés de l'arithmétique modulaire et des matrices.
  
  Il consiste à chiffrer le message en substituant les lettres du message, non plus lettre à lettre, mais par groupe de lettres. Il permet ainsi de rendre plus difficile le cassage du code par observation des fréquences.
  
  Lester S. Hill a aussi conçu une machine capable de réaliser mécaniquement un tel codage.
  
  ## Principe
  
  Chaque caractère est d'abord codé par un nombre compris entre 0 et n – 1 (son rang dans l'alphabet diminué de 1 ou son code ASCII diminué de 32). Les caractères sont alors regroupés par blocs de p caractères formant un certain nombre de vecteurs $X=(x_{1},x_{2},\cdots ,x_{p})$. Les nombres $x_{i}$ étant compris entre 0 et n – 1, on peut les considérer comme des éléments de Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « http://localhost:6011/fr.wikipedia.org/v1/ » :): \Z/n\Z et X est alors un élément de $(\mathbb {Z} /n\mathbb {Z} )^{p}$.
  
  On a construit au préalable une matrice p × p d'entiers : A. Le bloc X est alors chiffré par le bloc Y = AX, le produit s'effectuant modulo n.
  
  Pour déchiffrer le message, il s'agit d'inverser la matrice A modulo n. Cela peut se faire si le déterminant de cette matrice possède un inverse modulo n (c'est-à-dire, d'après le théorème de Bachet-Bézout, si det(A) est premier avec n).
  
  En effet, le produit de A et de la transposée de sa comatrice donne $A~^{\operatorname {t} }\!{\rm {com}}A={^{\operatorname {t} }\!{\rm {com}}A}~A=\det A~I_{p}$ (où $I_{p}$ désigne la matrice identité de taille p) donc s'il existe un entier k tel que
  
      $k\times \det(A)\equiv 1{\pmod {n}}$
  
  alors, en notant B n'importe quelle matrice congrue modulo n à k $^tcom(A),$ on aura
  
      $AB\equiv BA\equiv I_{p}{\pmod {n}},$
  
  soit encore
  
      $Y=AX\Leftrightarrow X=BY.$
  
  ## Illustration sur un exemple simple
  
  On imagine dans cette section que chaque lettre est codée par son rang dans l'alphabet diminué de 1 et que le chiffrement s'effectue par blocs de 2 lettres. Ici n = 26 et p = 2.
  
  Et l'on cherche à chiffrer le message suivant : TEXTEACRYPTER en utilisant une matrice A dont le déterminant est premier avec 26.
  
  Pour construire une telle matrice, il suffit de choisir trois entiers a, b, c au hasard mais tels que a soit premier avec 26, ce qui permet de choisir le dernier terme d tel que ad – bc soit inversible modulo 26. Pour la suite on prendra
  
      $A={\begin{pmatrix}3&5\\6&17\end{pmatrix}}$
  
  dont le déterminant est 21. Comme 5 × 21 = 105 ≡ 1 (mod 26), 5 est un inverse de det(A) modulo 26.
  
  ### Chiffrement
  
  On remplace chaque lettre par son rang à l'aide du tableau suivant :
  
  | 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 |
  | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - |
  | 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 |
  
  Puis on code le message
  
      TEXTEACRYPTER→ 19 ; 4 ; 23 ; 19 ; 4 ; 0 ; 2 ; 17 ; 24 ; 15 ; 19 ; 4 ; 17
  
  On regroupe les lettres par paires créant ainsi 7 vecteurs de dimension deux, la dernière paire étant complétée arbitrairement :
  
      $X_{1}=(19;4);X_{2}=(23;19);X_{3}=(4;0);X_{4}=(2;17);X_{5}=(24;15);X_{6}=(19;4);X_{7}=(17;6).$
  
  On multiplie ensuite ces vecteurs par la matrice A en travaillant sur des congruences modulo 26 :
  
      $Y_{1}={\begin{pmatrix}3&5\\6&17\end{pmatrix}}{\begin{pmatrix}19\\4\end{pmatrix}}={\begin{pmatrix}25\\0\end{pmatrix}}$ etc.
  
  On obtient alors 7 vecteurs, soit 14 lettres :
  
      (25 ; 0) ; (8;19) ; (12 ; 24) ; (13 ; 15) ; (17 ; 9) ; (25 ; 0) ; (3 ; 22)
      ZAITMYNPRJZADW.
  
  ### Déchiffrement
  
  Il faut inverser la matrice A. Il suffit de prendre la transposée de sa comatrice, c'est-à-dire
  
      $^{\operatorname {t} }\!{\rm {com}}A={\begin{pmatrix}17&-5\\-6&3\end{pmatrix}}$
  
  et la multiplier (modulo 26) par un inverse modulaire du déterminant de A c'est-à-dire par 5 (cf. ci-dessus) :
  
      $B={\begin{pmatrix}7&1\\22&15\end{pmatrix}}.$
  
  Connaissant les couples Y, il suffit de les multiplier (modulo 26) par la matrice B pour retrouver les couples X et réussir à déchiffrer le message.
  
  ## Cryptanalyse
  
  Le cassage par force brute nécessiterait de tester toutes les matrices carrées inversibles soit $(2^{2}-1)(2^{2}-2)(13^{2}-1)(13^{2}-13)=157248$ matrices dans les cas de matrices d'ordre 2 modulo 26. Ce nombre augmente considérablement si l'on décide de travailler avec des matrices 3 × 3 ou 4 × 4.
  
  L'autre système consiste à travailler sur les fréquences d'apparition de blocs de lettres.
  
  Dans l'exemple précédent, la paire ZA apparait 2 fois ce qui la classe parmi les paires les plus fréquentes qui sont ES, DE, LE, EN, RE, NT, ON, TE. Si l'on arrive à déterminer le chiffrement de 2 paires de lettres, on peut sous certaines conditions retrouver la matrice de codage A.
  
  En effet, si l'on suppose connu le fait que $(x_{1};x_{2})$ est codé par $(y_{1};y_{2})$ et $(x_{3};x_{4})$ est codé par $(y_{3};y_{4})$ alors on peut écrire l'égalité matricielle suivante :
  
      ${\begin{pmatrix}y_{1}&y_{3}\\y_{2}&y_{4}\end{pmatrix}}=A{\begin{pmatrix}x_{1}&x_{3}\\x_{2}&x_{4}\end{pmatrix}}.$
  
  Si la seconde matrice est inversible, c'est-à-dire si $x_{1}x_{4}-x_{2}x_{3}$ est premier avec 26, alors on peut déterminer A par
  
      $A={\begin{pmatrix}y_{1}&y_{3}\\y_{2}&y_{4}\end{pmatrix}}{\begin{pmatrix}x_{1}&x_{3}\\x_{2}&x_{4}\end{pmatrix}}^{-1}.$
  
  Si l'on travaille avec des blocs de taille p, il faut connaitre le chiffrement de p blocs pour arriver à déterminer la matrice. Encore faut-il que ces blocs constituent une matrice inversible.
  
  ## Sources
  
  * Robert Noirfalise, Arithmétique et cryptographie, IREM de Clermont-Ferrand ;
  * Introduction à la cryptographie, université Lyon 1 ;
  * Didier Müller, Une application intéressante des matrices ; le chiffre de Hill
  * Frédéric Bayart, « Méthodes anciennes de cryptographie », sur bibmath.net ;
  * (en) Murray Eisenberg, Hill Ciphers and Modular Linear Algebra.
  