Chiffre de Hill

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 ${\displaystyle X=(x_{1},x_{2},\cdots ,x_{p})}$. Les nombres ${\displaystyle x_{i}}$ étant compris entre 0 et n – 1, on peut les considérer comme des éléments de ${\displaystyle \mathbb {Z} /n\mathbb {Z} }$ et X est alors un élément de ${\displaystyle (\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 ${\displaystyle A~^{\operatorname {t} }\!{\rm {com}}A={^{\operatorname {t} }\!{\rm {com}}A}~A=\det A~I_{p}}$ (où ${\displaystyle I_{p}}$ désigne la matrice identité de taille p) donc s'il existe un entier k tel que

${\displaystyle k\times \det(A)\equiv 1{\pmod {n}}}$

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

${\displaystyle AB\equiv BA\equiv I_{p}{\pmod {n}},}$

soit encore

${\displaystyle Y=AX\Leftrightarrow X=BY.}$

Summarize Timeline Top Qs Fact Check

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

${\displaystyle 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.

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 :

${\displaystyle 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 :

${\displaystyle 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.

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

${\displaystyle ^{\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) :

${\displaystyle 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.