Le chiffrement de Hill : Cours et exercice corrigé

Qu’est-ce que le chiffrement de Hill ? Découvrez-le dans cet article !
Chiffrement

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é :

Total
0
Shares

Laisser un commentaire

Articles similaires