Chiffre de Hill

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 ${\displaystyle X=(x_{1},x_{2},\cdots ,x_{p})}$. Les nombres ${\displaystyle x_{i}}$ étant compris entre 0 et n – 1, on peut les considérer comme des éléments de ${\displaystyle \mathbb {Z} /n\mathbb {Z} }$ et X est alors un élément de ${\displaystyle (\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 ${\displaystyle A~^{\operatorname {t} }\!{\rm {com}}A={^{\operatorname {t} }\!{\rm {com}}A}~A=\det A~I_{p}}$ (où ${\displaystyle I_{p}}$ désigne la matrice identité de taille p) donc s'il existe un entier k tel que

${\displaystyle k\times \det(A)\equiv 1{\pmod {n}}}$

alors, en notant B n'importe quelle matrice congrue modulo n à k ^tcom(A), on aura

${\displaystyle AB\equiv BA\equiv I_{p}{\pmod {n}},}$

soit encore

${\displaystyle Y=AX\Leftrightarrow X=BY.}$

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[3]. Pour la suite on prendra

${\displaystyle 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.

Le cassage par force brute nécessiterait de tester toutes les matrices carrées inversibles soit ${\displaystyle (2^{2}-1)(2^{2}-2)(13^{2}-1)(13^{2}-13)=157248}$ matrices[4] 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 ${\displaystyle (x_{1};x_{2})}$ est codé par ${\displaystyle (y_{1};y_{2})}$ et ${\displaystyle (x_{3};x_{4})}$ est codé par ${\displaystyle (y_{3};y_{4})}$ alors on peut écrire l'égalité matricielle suivante :

${\displaystyle {\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 ${\displaystyle x_{1}x_{4}-x_{2}x_{3}}$ est premier avec 26, alors on peut déterminer A par

${\displaystyle 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.

• 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.