Chiffre de Hill

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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[1], utilise les propriétés de l'arithmétique modulaire et des matrices.

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[2].

Principe[modifier | modifier le code]

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 \Z/n\Z et X est alors un élément de (\Z/n\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 A~^{\operatorname t}\!{\rm com}A={^{\operatorname t}\!{\rm com}A}~A =\det A~I_p (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 \pmod n

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

AB\equiv BA\equiv I_p\pmod n,

soit encore

Y=AX \Leftrightarrow X=BY.

Illustration sur un exemple simple[modifier | modifier le code]

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

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.

Chiffrement[modifier | modifier le code]

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= \begin{pmatrix} 3 & 5 \\ 6 & 17\end{pmatrix}\begin{pmatrix}19\\4\end{pmatrix} = \begin{pmatrix}25\\0\end{pmatrix} 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[modifier | modifier le code]

Il faut inverser la matrice A. Il suffit de prendre la transposée de sa comatrice, c'est-à-dire

^{\operatorname t}\!{\rm com}A=\begin{pmatrix} 17 & -5\\ -6 & 3\end{pmatrix}

et la multiplier (modulo 26) par l'inverse du déterminant de A c'est-à-dire par 5 :

 B = \begin{pmatrix} 7 & 1\\ 22 & 15\end{pmatrix}.

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[modifier | modifier le code]

Le cassage par force brute nécessiterait de tester toutes les matrices carrés inversible soit (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 (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 :

\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 x_1x_4-x_2x_3 est premier avec 26, alors on peut déterminer A par

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.

Sources[modifier | modifier le code]

Notes et références[modifier | modifier le code]

  1. (en) Lester S. Hill, « Concerning certain linear transformation apparatus of cryptography », American Mathematical Monthly, vol. 38, 1931, p. 135-154.
  2. (en) Copie du dépôt de brevet.
  3. Ou plus généralement : de choisir a et b tels que PGCD(a, b, 26) = 1, puis u, v tels que au – bv ≡ 1 (mod 26), et de poser d = mu, c = mv pour un entier m premier avec 26.
  4. Selon cet exposé d'introduction à la cryptographie, université Lyon 1.