Chiffre de Hill

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

Il s'agit de chiffrer le message en substituant les lettres du message, non plus lettre à lettre, mais groupe de lettres 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]

Sommaire

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 xi é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 construit alors une matrice p × p d'éléments de \Z/n\Z : 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. Cela peut se faire si le déterminant de cette matrice est premier avec n. En effet, si Det(A) est premier avec n, il existe un élément k de \Z/n\Z tel que k\times Det(A) \equiv 1 \pmod n Ceci est une conséquence directe du théorème de Bachet-Bézout

Le produit de A et de sa comatrice transposée tCom(A) donne Det(A)Ip. Si l'on appelle B la matrice ktcom(A). On aura AB = BA = Ip. Soit encore

Y=AX \Leftrightarrow 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 bloc de 2 lettres. Ici n= 26 et p = 2.

Et l'on cherche à crypter le message suivant : TEXTEACRYPTER en utilisant une matrice A dont le déterminant est premier avec 26.

Pour construire cette matrice, il suffit de choisir trois entiers (a, b, c ) au hasard mais tel que a soit premier avec 26, le dernier terme d doit être choisi tel que ad - bc soit premier avec 26. Pour la suite on prendra

A=\begin{pmatrix} 3 & 5 \\ 6 & 17\end{pmatrix}

dont le déterminant est 21. Comme 21 est premier avec 26, il possède un inverse dans \Z/26\Z qui est 5 car 5 \times 21 = 105 \equiv 1 \mod {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 est complétée arbitrairement

X1 = (19;4);X2 = (23;19);X3 = (4;0);X4 = (2;17);X5 = (24;15);X6 = (19;4);X7 = (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

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

^tCom(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

Le cassage par force brute nécessiterait de tester toutes les matrices carrés inversible soit (22 − 1)(22 − 2)(132 − 1)(132 − 13) = 157248 matrices[3] dans les cas de matrices d'ordre 2 modulo 26. Ce nombre augmente considérablement si 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 on suppose connu le fait que (x1;x2) est codé par (y1;y2) et (x3;x4) est codé par (y3;y4) 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 x1x4x2x3 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 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

Notes et références

  1. Lester S. Hill, Concerning certain linear transformation apparatus of cryptography, in American mathematical monthly, vol 38, (1931), p135 - 154
  2. voir un copie du dépôt de brevet ici
  3. selon cet exposé d'introduction à la cryptographie, université de Lyon 1

Voir aussi



Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Chiffre de Hill de Wikipédia en français (auteurs)

Игры ⚽ Нужен реферат?

Regardez d'autres dictionnaires:

  • Chiffre de substitution — Chiffrement par substitution Le chiffrement par substitution est une technique de cryptage utilisée depuis fort longtemps puisque le chiffre de César en est un cas particulier. Sans autre précision, elle désigne en général un chiffrement par… …   Wikipédia en Français

  • Chiffre affine — Le chiffre affine est une méthode de cryptographie basée sur un chiffrement par substitution. Il s agit d un code simple à appréhender mais aussi un des plus faciles à casser. Sommaire 1 Principe 1.1 Chiffrement 1.1.1 Note …   Wikipédia en Français

  • Chiffre De Beale — Le Chiffre de Beale est le nom donné au chiffre de Thomas J. Beale, chiffre qui reste en partie encore mystérieux. Il faut également noter que cette histoire est soumise à caution, de nombreux éléments laissant planer un doute sur sa véracité.… …   Wikipédia en Français

  • Chiffre de beale — Le Chiffre de Beale est le nom donné au chiffre de Thomas J. Beale, chiffre qui reste en partie encore mystérieux. Il faut également noter que cette histoire est soumise à caution, de nombreux éléments laissant planer un doute sur sa véracité.… …   Wikipédia en Français

  • Chiffre De Vigenère — Le chiffre de Vigenère est un système de chiffrement, élaboré par Blaise de Vigenère (1523 1596), diplomate français du XVIe siècle. C est un système de substitution poly alphabétique ou de chiffrement polyalphabétique. Cela signifie qu il… …   Wikipédia en Français

  • Chiffre de Vigenere — Chiffre de Vigenère Le chiffre de Vigenère est un système de chiffrement, élaboré par Blaise de Vigenère (1523 1596), diplomate français du XVIe siècle. C est un système de substitution poly alphabétique ou de chiffrement polyalphabétique.… …   Wikipédia en Français

  • Chiffre de vigenère — Le chiffre de Vigenère est un système de chiffrement, élaboré par Blaise de Vigenère (1523 1596), diplomate français du XVIe siècle. C est un système de substitution poly alphabétique ou de chiffrement polyalphabétique. Cela signifie qu il… …   Wikipédia en Français

  • Chiffre Des Francs-maçons — Le chiffre des Francs maçons, encore appelé alphabet du parc à cochons ou Pigpen, est un chiffre de substitution associant à chaque lettre un symbole. Ce chiffre est facilement attaquable par analyse fréquentielle. Sommaire 1 Historique 2… …   Wikipédia en Français

  • Chiffre des Francs-macons — Chiffre des Francs maçons Le chiffre des Francs maçons, encore appelé alphabet du parc à cochons ou Pigpen, est un chiffre de substitution associant à chaque lettre un symbole. Ce chiffre est facilement attaquable par analyse fréquentielle.… …   Wikipédia en Français

  • Chiffre des francs-maçons — Le chiffre des Francs maçons, encore appelé alphabet du parc à cochons ou Pigpen, est un chiffre de substitution associant à chaque lettre un symbole. Ce chiffre est facilement attaquable par analyse fréquentielle. Sommaire 1 Historique 2… …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”