Dans cet article, nous allons vous présenter le chiffrement de Hill, une méthode de chiffrement un peu plus évoluée que le chiffrement affine.
Prérequis
Le chiffrement de Hill
Bien sûr, comme pour tout chiffrement, on va faire une correspondance entre chiffres et lettres (cf notre article sur le chiffrement affine)
On dispose d’un alphabet à n caractères, qu’on va donc encoder entre 0 et n-1 (donc 0 et 25 pour notre alphabet si on ne prend pas en compte les accents et autres caractères spéciaux). Ensuite, on prend un entier p et on dispose d’une matrice carrée de taille p inversible dans \mathbb{Z}/n\mathbb{Z}.
Inversibilité d’une matrice dans Z/nZ
Une matrice dans \mathbb{Z}/n\mathbb{Z} est inversible si et seulement si son déterminant est inversible dans \mathbb{Z}/n\mathbb{Z}.
En effet, dans le sens direct, si une matrice A est inversible alors il existe B tel que AB = I_p . Donc pour le déterminant, on a \det(A)\det(B) = 1. Ainsi, on a montré qu’il existe k \in \mathbb{Z} tel que k \times \det(A) = 1, ce qui signifie que le déterminant de A est inversible dans \mathbb{Z}/n\mathbb{Z}
Pour le sens retour, on utilise la formule A {}^t com(A) = det(A) \times I_p . En multipliant par k, l’inverse dans \mathbb{Z}/n\mathbb{Z} du déterminant de A, on obtient k {}^t com(A) A= I_p . On a donc comme inverse A^{-1} = k {}^t com(A).
Cette démonstration est d’ailleurs une bonne méthode pour calculer concrètement l’inverse d’une telle matrice.
Le principe du chiffrement de Hill
Soit A une matrice carrée de taille p inversible dans \mathbb{Z}/n\mathbb{Z}. On va découper notre chaîne de caractères à chiffre en blocs de longueur p X = (x_1, \ldots, x_p).
Pour chiffrer, on fait le produit matriciel Y = AX
Exemple de chiffrement de Hill
Prenons la matrice
A = \begin{pmatrix} 1 & 2 \\ 3 & 4 \end{pmatrix} On va chiffrer le mot “lettre”. On va donc le découper en par groupe de 2 : “le”, “tt”, “re”. Traduisons maintenant en nombres : “11;4” , “19;19”, “17;4”.
On fait ensuite les produits matriciels :
\begin{array}{lll}
\begin{pmatrix} 1 & 2 \\ 3 & 4 \end{pmatrix} \begin{pmatrix} 11 \\ 4 \end{pmatrix} & = \begin{pmatrix} 19 \\ 49 \end{pmatrix} &= \begin{pmatrix} 19 \\ 23 \end{pmatrix} \\
\begin{pmatrix} 1 & 2 \\ 3 & 4 \end{pmatrix} \begin{pmatrix} 19 \\ 19 \end{pmatrix} & = \begin{pmatrix} 57 \\ 133 \end{pmatrix} &= \begin{pmatrix} 5 \\ 3 \end{pmatrix} \\
\begin{pmatrix} 1 & 2 \\ 3 & 4 \end{pmatrix} \begin{pmatrix} 17 \\ 4 \end{pmatrix} & = \begin{pmatrix} 25 \\ 67 \end{pmatrix} &= \begin{pmatrix} 25 \\ 15 \end{pmatrix}
\end{array}On obtient donc la suite de chiffres “19; 23; 5; 3; 25; 15” ce qui en termes de caractères s’écrit txfdzp.
Déchiffrement
Si on connaît la matrice de chiffrement. On calcule l’inverse du déterminant. De plus, on calcule la transposée de la comatrice et on a l’inverse. On fait ensuite le même calcul par blocs que pour chiffrer et on obtient le mot déchiffré.
Pour déchiffrer lorsque p = 2, on a 157248 matrices possibles, nombre qui augmente très fortement au fur et à mesure que p grandit ce qui peut rendre le déchiffrement par force brute rapidement compliqué (et c’est intéressant !)
Une autre méthode consiste à regarder les fréquences par blocs, chaque suite de caractères ayant une certaine probabilité. Par exemple, lorsque p = 2, les suites de caractères les plus fréquentes sont ES, DE, LE, EN, RE, NT, ON et TE.
En conclusion, si vous voulez utiliser ce chiffrement de manière robuste, il vaut mieux prendre un p plus grand que 2.
Exercice corrigé
Le chiffrement de Hill est tombé au baccalauréat en 2016 (pour les centres étrangers). Il s’agit de l’exercice 4
Voici le sujet entier
Et son corrigé :
