AlgèbreNotion · Glossaire
chiffre de Hill
Le chiffre de Hill est un chiffrement symétrique par blocs : après avoir codé les lettres par des éléments de Z/nZ, il représente chaque bloc de p lettres par un vecteur et le multiplie par une matrice carrée modulo n. Pour que le déchiffrement soit possible, cette matrice doit être inversible, ce qui équivaut à demander que son déterminant soit premier avec n. Sa structure linéaire en fait surtout un outil pédagogique pour relier calcul matriciel et cryptographie, car elle le rend vulnérable aux attaques à clair connu.
Sommaire
Ce que vous allez apprendre
- Coder des lettres en nombres et chiffrer un bloc par multiplication matricielle modulo 26.
- Vérifier l'inversibilité d'une clé avec le déterminant et le plus grand commun diviseur.
- Refaire entièrement le calcul qui transforme HI en TC puis retrouve HI.
- Repérer les conventions incompatibles et la vulnérabilité à une attaque à clair connu.
En clair
Prenons deux lettres à la fois. On remplace chacune par un nombre, puis une grille de quatre nombres mélange la paire par des multiplications et des additions. Avec la grille choisie dans cette fiche, HI devient TC. Une autre grille donnerait généralement un autre résultat.
Le calcul revient toujours dans l'alphabet après Z, comme un compteur circulaire. La grille est la clé secrète. Elle doit posséder une grille inverse : sinon plusieurs paires pourraient aboutir au même message chiffré et le retour au texte initial serait impossible.
Définition
Le chiffre de Hill est un chiffrement symétrique par blocs proposé par Lester S. Hill en 1929. Un même secret sert au chiffrement et au déchiffrement : une matrice carrée K d'ordre p. Chaque lettre est codée par un entier modulo n ; pour l'alphabet latin, la convention courante A = 0, B = 1, …, Z = 25 prend n = 26. Un bloc de p lettres devient alors un vecteur colonne X de p coordonnées.
Le vecteur chiffré Y est obtenu par multiplication matricielle, tous les résultats étant réduits modulo n : . Cette action simultanée sur plusieurs lettres généralise le chiffrement affine, qui agit lettre par lettre. Le choix de vecteurs colonnes est une convention ; avec des vecteurs lignes, la matrice agit de l'autre côté et les formules doivent rester cohérentes.
Le déchiffrement exige l'inverse de K modulo n. Il existe exactement lorsque le déterminant de K est premier avec n, autrement dit lorsque . On récupère alors le bloc initial par . Cette structure linéaire rend cependant le système vulnérable à une attaque à clair connu : assez de blocs clairs et chiffrés indépendants permettent de résoudre des équations linéaires et de retrouver K.
Un exemple, pas à pas
On chiffre le bloc HI avec A = 0, …, Z = 25 et des vecteurs colonnes. Les données sont H = 7, I = 8 et le modulo 26. La matrice clé est :
1. On contrôle la clé. Son déterminant vaut 3 × 5 − 3 × 2 = 9. Comme 9 et 26 sont premiers entre eux, K est inversible modulo 26.
2. On multiplie K par le vecteur de HI, puis on réduit chaque coordonnée modulo 26 :
Les nombres 19 et 2 correspondent à T et C. Le bloc chiffré est donc TC.
3. Pour vérifier, l'inverse de 9 modulo 26 vaut 3, car 9 × 3 = 27 ≡ 1. On obtient :
4. En appliquant cette matrice à (19, 2), on trouve (319, 398), soit (7, 8) modulo 26. Les lettres H et I réapparaissent : ce retour exact contrôle à la fois le calcul et l'inversibilité de la clé.
En pratique
Pour exécuter le chiffre à la main, on fixe d'abord l'alphabet, l'association entre lettres et nombres, la taille des blocs et l'orientation des vecteurs. On complète aussi le dernier bloc si sa longueur est inférieure à p, selon une règle annoncée.
Avant de chiffrer, on calcule le déterminant de la matrice clé. Avec 26 symboles, une matrice dont le déterminant est divisible par 2 ou par 13 doit être remplacée, car elle n'est pas inversible modulo 26.
Le chiffre de Hill convient aujourd'hui surtout pour manipuler concrètement matrices, congruences et inverses modulaires. Pour protéger des données réelles, on choisit un chiffrement moderne conçu et évalué pour résister aux attaques connues, car la linéarité de Hill révèle la clé dès que suffisamment de correspondances clair-chiffré sont disponibles.
À ne pas confondre
Chiffre de Hill et chiffrement affine. Le chiffrement affine transforme chaque lettre séparément par une relation de la forme ax + b modulo n. Hill mélange plusieurs lettres dans un même produit matriciel : modifier le H de HI peut donc changer plusieurs lettres du bloc chiffré.
Chiffrement et codage. Un codage change la représentation selon une règle qui n'est pas secrète. Dans le chiffre de Hill, la matrice K joue le rôle d'une clé secrète ; sans elle, le destinataire ne connaît pas la transformation inverse à appliquer.
Chiffrement et hachage. Le déchiffrement de Hill doit restituer exactement le bloc initial grâce à K−1. Une fonction de hachage vise au contraire une empreinte à sens unique et n'a pas de clé inverse permettant de reconstruire le message.
Limites et pièges
Déterminant non inversible. Avec n = 26, la condition ne se réduit pas à « déterminant non nul ». Si le déterminant est pair ou multiple de 13, son plus grand commun diviseur avec 26 dépasse 1 : la matrice n'a pas d'inverse modulo 26 et certains blocs chiffrés ont plusieurs antécédents. Il faut choisir une autre clé.
Blocs connus insuffisants. Pour une clé d'ordre p, il ne suffit pas de posséder n'importe quels p blocs clairs. Les vecteurs correspondants doivent former une matrice inversible modulo n. Sinon, le système linéaire ne détermine pas une clé unique ; il faut recueillir d'autres paires clair-chiffré indépendantes.
Conventions incompatibles. A = 0 ou A = 1, vecteurs lignes ou colonnes, taille des blocs et règle de remplissage changent les nombres obtenus. Un déchiffrement qui produit des lettres incohérentes peut signaler une convention différente plutôt qu'une erreur d'arithmétique. Il faut reprendre exactement les choix du chiffrement.
Sécurité limitée. Agrandir la matrice ne supprime pas la linéarité. Dès qu'un adversaire réunit assez de blocs clairs et chiffrés exploitables, il peut reconstituer la matrice clé par algèbre linéaire. Le chiffre de Hill ne doit donc pas servir à protéger des informations sensibles.
Pour aller plus loin
chiffrement affine — Pour comparer une transformation lettre par lettre au mélange matriciel de blocs utilisé par Hill.
arithmétique modulaire — Pour approfondir les congruences, les inverses et le calcul dans Z/nZ qui rendent le déchiffrement possible.
cryptographie — Pour replacer le chiffre de Hill parmi les méthodes qui transforment un message et étudient leur résistance aux attaques.
Explorez les mathématiques autrement
Retrouvez nos magazines, podcasts et jeux pour explorer les mathématiques autrement.
Découvrir les offres