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.

Lester Sanders Hill (1891-1961)

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.

Machine de Hill (1929)

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 $\mathbb{Z}/n\mathbb{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 Modèle:Retrait (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(\mathrm{mod}n)$

alors, en notant B n'importe quelle matrice congrue modulo n à k Modèle:Expcom(A), on aura

$AB\equiv BA\equiv I_p(\mathrm{mod}n),$

soit encore

$Y=AX\iff 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=\left(\begin{array}{cc}3& 5\\ 6& 17\end{array}\right)$

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=\left(\begin{array}{cc}3& 5\\ 6& 17\end{array}\right)\left(\begin{array}{c}19\\ 4\end{array}\right)=\left(\begin{array}{c}25\\ 0\end{array}\right)$ 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

${\mathrm{t}}^{}\mathrm{c}\mathrm{o}\mathrm{m}A=\left(\begin{array}{cc}17& -5\\ -6& 3\end{array}\right)$

et la multiplier (modulo 26) par un inverse modulaire du déterminant de A c'est-à-dire par 5 (cf. ci-dessus) :

$B=\left(\begin{array}{cc}7& 1\\ 22& 15\end{array}\right).$

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 :

$\left(\begin{array}{cc}{y}_1& y_3\\ y_2& y_4\end{array}\right)=A\left(\begin{array}{cc}{x}_1& x_3\\ x_2& x_4\end{array}\right).$

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=\left(\begin{array}{cc}{y}_1& y_3\\ y_2& y_4\end{array}\right){\left(\begin{array}{cc}{x}_1& x_3\\ x_2& x_4\end{array}\right)}^{-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
• Modèle:Lien web ;
• Modèle:En Murray Eisenberg, Hill Ciphers and Modular Linear Algebra.