1. Introduction

Lester Hill, mathématicien cryptographe (1891-1961), publie en 1929, dans la revue American Mathematical Monthly, un article intitulé "Cryptography in an algebraic alphabet", dans lequel il détaille un nouveau type d'algorithme de chiffrement [1]. Son idée est de continuer à utiliser des décalages du même type que celui du chiffre de César, mais en effectuant ces décalages simultanément sur des groupes de m lettres. Bien sûr, plus m est grand, plus les analyses statistiques deviennent difficiles!

Dans ce paragraphe, nous allons présenter le chiffrement de Hill. C'est une méthode de chiffrement qui utilise les matrices carrées, la calcul du modulo n et la notion d'algorithme. Le chiffre de Hill est un chiffre polygraphique, c'est-à-dire que nous ne (dé)chiffrons pas les lettres les unes après les autres, mais par paquets. Nous étudierons la version bigraphique, c'est-à-dire que nous grouperons les lettres deux par deux. Cependant, nous pouvons imaginer des paquets beaucoup plus grands.

2. Chiffrement de Hill

Les lettres sont d'abord remplacées par leur rang dans l'alphabet :

\begin{matrix} A & B&C&D&E&F&G&H&I&J&K&L&M&N \\ 1&2&3&4&5&6&7&8&9&10&11&12&13&14 \\ O&P&Q&R&S&T&U&V&W&X&Y&Z \\
15 &16&17&18&19&20&21&22&23&24&25&26
\end{matrix}

Les lettres P_k et P_k+1 du texte en clair seront chiffrées C_k et C_k+1 avec le système matriciel suivant :


\begin{pmatrix}
C_k\\
C_{k+1}
\end{pmatrix} = \begin{pmatrix}
a & b\\
c & d
\end{pmatrix} \begin{pmatrix}
P_k\\
P_{k+1}
\end{pmatrix} \text{ (mod 26) }


La formule 2 signifie, afin de fixer les idées, que les deux premières lettres du message clair (P₁, P₂) seront chiffrées (C₁, C₂) selon le système (S) d'équations suivant :
(S) = \begin{cases} C_1 = a\cdot P_1 + b\cdot P_2 \text{ (mod 26) } \\ C_2 = c\cdot P_1 + d\cdot P_2 \text{ (mod 26) }
\end{cases}

3. Exemple de chiffrement

Alice prend comme clés de chiffrement la matrice A suivante afin de chiffrer le message "je vous aime" :
A = \begin{pmatrix}
9 & 4\\
5 & 7
\end{pmatrix}
D'après le tableau 1, P₁ = "j" = 10 et P₂ = "e" = 5. Les deux premières lettres du message seront donc chiffrées selon :

(S) = \begin{cases} C_1 = 9\cdot 10 + 4\cdot 5 \text{ (mod 26) } = 110 \text{ (mod 26) } = 6 \\ C_2 = 5\cdot 10 + 7\cdot 5 \text{ (mod 26) } = 85 \text{ (mod 26) } = 7
\end{cases}

En procédant de même avec les paires de lettres suivantes, Alice obtiendra finalement le chiffrement suivant :

\begin{matrix} \text{Lettres} & j & e & v & o & u & s & a & i & m & e\\ \text{Rang }(P_k) & 10 & 5 & 22 & 15 & 21 & 19 & 1 & 9 & 13 & 5\\ \text{Rang }(C_k) & 6 & 7 & 24 & 7 & 5 & 4 & 19 & 16 & 7 & 22\\ \text{Lettres chiffrées} &F & G & X & G & E & D & S & P & G & V
\end{matrix}

Le message chiffré sera donc "FGXGE DSPGV". L'écriture en lettres majuscules regroupées par 5 est une convention.

A noter que si le nombre de lettres du message en clair est impair, il est nécessaire d'ajouter une lettre arbitraire à la fin du message original.

4. Matrice de déchiffrement

Il paraît d'emblée évident que la matrice de déchiffrement ne peut pas être quelconque. Tout d'abord, ses éléments doivent être des nombres entiers positifs afin d'être en accord avec le tableau 1. De plus, l'expression 2 repose sur un système matriciel de type Ax = b. Ainsi, pour trouver les solutions x de Ax = b, il est nécessaire que A soit inversible et donc que son déterminant soit non nul. Alors, nous aurons les solutions via x = A^{-1} b et le message pourra être déchiffré.

Ordinairement, si A est inversible, nous pouvons calculer son inverse selon :


A^{-1} = \frac{1}{ad - bc}\begin{pmatrix}
d & -b\\
-c & a
\end{pmatrix}

Cependant, nous travaillons ici en modulo 26. Qu'en est-il dans ce cas de la matrice inverse ? En reprenant notre exemple précédent, nous devons calculer :

\begin{pmatrix}
9 & 4\\
5 & 7
\end{pmatrix}^{-1} \text{ (mod 26) } = \frac{1}{9\cdot 7 - 5\cdot 5}\begin{pmatrix}
7 & -4\\
-5 & 9
\end{pmatrix} \text{ (mod 26) }

soit

\begin{pmatrix}
9 & 4\\
5 & 7
\end{pmatrix}^{-1} \text{ (mod 26) } = \frac{1}{43}\begin{pmatrix}
7 & -4\\
-5 & 9
\end{pmatrix} \text{ (mod 26) } = ?


Le problème est de calculer l'inverse de 43 modulo 26. Il existe des algorithmes efficaces pour déterminer l'inverse de k (mod n)}, par exemple en utilisant l'agorithme d'Euclide étendu. Cependant, quand n=26, la méthode dite "force brute" est sans doute plus efficace :

Algorithme "force brute" pour 1/k modulo 26

1. Multiplier successivement k par les entiers m de l'ensemble des nombres premiers suivants (1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25),


2. Stopper lorsque le produit k*m est égal à 1 (mod 26) .

L'utilisation de l'algorithme précédent pour notre exemple nous donne :

43^{-1} \text{ (mod 26) } = 23

Nous pouvons à présent terminer le calcul de la matrice de chiffrement inverse :


\begin{pmatrix}
9 & 4\\
5 & 7
\end{pmatrix}^{-1} \text{ (mod 26) } = 23 \begin{pmatrix}
7 & -4\\
-5 & 9
\end{pmatrix} \text{ (mod 26) }

soit :

\begin{pmatrix}
9 & 4\\
5 & 7
\end{pmatrix}^{-1} \text{ (mod 26) } = \begin{pmatrix}
161 & -92\\
-115 & 207
\end{pmatrix} \text{ (mod 26) } = \begin{pmatrix}
5 & 12\\
15 & 25
\end{pmatrix}


Nous devons par conséquent utiliser la matrice :


\begin{pmatrix}
5 & 12\\
15 & 25
\end{pmatrix}
afin de déchiffrer le message "FGXGE DSPGV". Après avoir remplacé les lettres par leur rang respectif, nous calculons, pour l'exemple, les deux premières lettres :

\begin{cases} P_1 = 5\cdot 6 + 12\cdot 7 \text{ (mod 26) } = 114 \text{ (mod 26) } = 10 \\ P_2 = 15\cdot 6 + 25\cdot 7 \text{ (mod 26) } = 265 \text{ (mod 26) } = 5
\end{cases}

En procédant de même avec les autres paires de lettres, nous obtenons le résultat complet suivant :

\begin{matrix} \text{Lettres chiffrées} & F & G & X & G & E & D & S & P & G & V\\ \text{Rang }(P_k) & 6 & 7 & 24 & 7 & 5 & 4 & 19 & 16 & 7 & 22\\ \text{Rang }(C_k) & 10 & 5 & 22 & 15 & 21 & 19 & 1 & 9 & 13 & 5\\ \text{Lettres} & j & e & v & o & u & s & a & i & m & e
\end{matrix}

Le message déchiffré est donc bien "je vous aime".

5. Pour aller plus loin

Nous venons de voir la méthode de chiffrement de Hill à partir d'une matrice d'ordre 2. Cependant, il est possible d'augmenter l'ordre de la matrice et prendre, par exemple, une matrice d'ordre 3. Nous parlerons dans ce cas de chiffrement trigraphique. Le raisonnement est alors exactement le même mais les calculs sont plus lourds. D'autre part, nous avons choisi un alphabet à 26 lettres. Il est possible d'accroître la taille de cet alphabet en y insérant notamment les accents ou même un espace pour séparer les mots entre eux. Si nous choisissons un alphabet à n lettres, il nous faudra donc travailler en modulo n. Enfin, il est possible de déchiffrer un message chiffré avec la méthode de Hill sans connaître la matrice de chiffrement. Pour ce faire, il est nécessaire de tester un ensemble de combinaisons possibles d'alphabet et de matrice de chiffrement. Cela peut parfois prendre beaucoup de temps de calculs et décourager les plus ambitieux.