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. vignette|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. vignette|Machine de Hill (1929) 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 . Les nombres étant compris entre 0 et n – 1, on peut les considérer comme des éléments de et X est alors un élément de . 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 (où désigne la matrice identité de taille p) donc s'il existe un entier k tel que alors, en notant B n'importe quelle matrice congrue modulo n à k com(A), on aura soit encore 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.
