Utilisateur:Cbyd/Brouillon3

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 (Congruence sur les entiers) et des matrices.

Lester Sanders Hil (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 analyse fréquentielle.

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 $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 : matrice 2x2

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 (digrammes). Ici n = 26 et p = 2.

Et l'on cherche à chiffrer le message suivant : TEXTEACHIFFRER 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 [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.]. 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

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

TEXTEACHIFFRER→ 19 ; 4 ; 23 ; 19 ; 4 ; 0 ; 2 ; 7 ; 8 ; 5 ; 5 ; 17 ; 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;7);X_{5}=(8;5);X_{6}=(5;17);X_{7}=(4;17).$

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) ; (15 ; 1) ; (23 ; 3) ; (22 ; 7) ; (19 ; 2)

ZAITMYPBXDWHTB.

Déchiffrement

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 un inverse modulaire du déterminant de A c'est-à-dire par 5 (cf. ci-dessus) :

$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

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 :

${\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_{1}x_{4}-x_{2}x_{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.

Autre exemple : matrice 3x3

Chiffrement

Toujours avec:

Letter	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
Number	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

Pour coder le message « ACT », avec la matrice ci-dessous (ou GYB / NQK / URP en lettres):

${\begin{pmatrix}6&24&1\\13&16&10\\20&17&15\end{pmatrix}}$

Comme 'A' correspond à 0, 'C' ç 2 et 'T' à 19, le message est le vecteur:

${\begin{pmatrix}0\\2\\19\end{pmatrix}}$

Alors le vecteur crypté est donné par:

${\begin{pmatrix}6&24&1\\13&16&10\\20&17&15\end{pmatrix}}{\begin{pmatrix}0\\2\\19\end{pmatrix}}={\begin{pmatrix}67\\222\\319\end{pmatrix}}\equiv {\begin{pmatrix}15\\14\\7\end{pmatrix}}{\pmod {26}}$

qui correspond en chiffré à « POH ». Si le message était « CAT », soit:

${\begin{pmatrix}2\\0\\19\end{pmatrix}}$

à ce moment, le vecteur crypté serait:

${\begin{pmatrix}6&24&1\\13&16&10\\20&17&15\end{pmatrix}}{\begin{pmatrix}2\\0\\19\end{pmatrix}}={\begin{pmatrix}31\\216\\325\end{pmatrix}}\equiv {\begin{pmatrix}5\\8\\13\end{pmatrix}}{\pmod {26}}$

qui correspond en chiffré à « FIN ». Chaque lettre a changé, ce qui permet au chiffre de Hill d'atteindre la condition de « confusion et diffusion » de Claude Shannon.

Déchiffrement

Pour déchiffrer, on transforme le texte chiffré en vecteur, que l'on multiplie par la matrice inverse de la matrice-clé (IFK / VIV / VMI en lettres). Nous obtenons que, modulo 26, l'inverse de la matrice utilisée dans l'exemple précédent est:

${\begin{pmatrix}6&24&1\\13&16&10\\20&17&15\end{pmatrix}}^{-1}{\pmod {26}}\equiv {\begin{pmatrix}8&5&10\\21&8&21\\21&12&8\end{pmatrix}}$

Pour le texte chiffré « POH », on obtient:

${\begin{pmatrix}8&5&10\\21&8&21\\21&12&8\end{pmatrix}}{\begin{pmatrix}15\\14\\7\end{pmatrix}}={\begin{pmatrix}260\\574\\539\end{pmatrix}}\equiv {\begin{pmatrix}0\\2\\19\end{pmatrix}}{\pmod {26}}$

qui nous amène bien au texte clair « ACT », comme prévu.

Précautions

Le choix de la matrice comporte deux complications :

1. Toutes les matrices n'ont pas d'inverse. Elle n'a une inverse si et seulement si son déterminant n'est pas nul.
2. Le déterminant de la matrice ne doit avoir aucun facteur commun avec la base modulaire.

Ainsi, si on travaille modulo 26 comme ci-dessus, le déterminant doit être non nul, et ne doit être divisible ni par 2 ni par 13. Sinon, la matrice ne peut pas être utilisée pour le chiffrement de Hill, et il faut en changer (sous peine qu'il soit impossible de déchiffrer). Heureusement, des matrices qui satisfont les conditions d'utilisation pour le chiffrement de Hill sont faciles à trouver.

Pour notre exemple de matrice-clé:

${\begin{vmatrix}6&24&1\\13&16&10\\20&17&15\end{vmatrix}}=6(16\cdot 15-10\cdot 17)-24(13\cdot 15-10\cdot 20)+1(13\cdot 17-16\cdot 20)=441\equiv 25{\pmod {26}}$

Le déterminant modulo 26 est 25. Puisque $25=5^{2}$ et $26=2\times 13$, 25 n'a aucun facteur commun avec 26, cette matrice peut donc être utilisée pour le chiffrement de Hill.

Le risque que le déterminant puisse avoir des facteurs communs avec le module peut être éliminé en choisissant un nombre premier. Par conséquent, une variante pratique de Hill utilise 3 symboles supplémentaires (tels qu'une espace, un point et un point d'interrogation) pour travailler modulo 29.

Pour aller plus loin

• 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
• Frédéric Bayart, « Méthodes anciennes de cryptographie », sur bibmath.net ;
• (en) Murray Eisenberg, Hill Ciphers and Modular Linear Algebra ;
• (en) Lester S. Hill, « Concerning certain linear transformation apparatus of cryptography », American Mathematical Monthly, vol. 38, 1931, p. 135-154..