Chiffre de Hill

Le chiffre de Hill a été proposé par le mathématicien américain Lester S. Hill en 1929 dans The American Mathematical Monthly. C’est le premier chiffrement à utiliser explicitement l’algèbre linéaire — un pont historique entre la cryptographie classique et les chiffres modernes par blocs (DES, AES).

Principe

Hill travaille sur des blocs de n lettres au lieu de lettres individuelles. Chaque bloc est vu comme un vecteur de n entiers (rang alphabétique : A = 0, …, Z = 25). La clé est une matrice carrée n × n inversible modulo 26.

Le chiffrement :

C = K · P mod 26

Le déchiffrement utilise l’inverse modulaire de K :

P = K⁻¹ · C mod 26

Pour que K soit inversible modulo 26, son déterminant doit être premier avec 26 (c’est-à-dire impair et non divisible par 13).

Exemple (matrice 2×2)

Clair CIPHERCHRONICLEX (complété à 16 lettres pour rentrer dans les blocs de 2), clé :

      | 3  2 |
  K = | 5  7 |   (det = 21 − 10 = 11, premier avec 26 ✓)

Chiffrement du bloc CI = [2, 8] :

  | 3·2 + 2·8 |   | 22 |   |  W |
  | 5·2 + 7·8 | = | 66 | = | 14 |  →  WO
                       mod 26

En continuant sur tous les blocs de CIPHERCHRONICLEX, on obtient :

CI → WO     PH → HU     ER → UJ     CH → UH
RO → BB     NI → DR     CL → CJ     EX → GZ

Ciphertext : WOHUUJUHBBDRCJGZ.

Variantes

• Hill 3×3 — matrices 3×3, chiffrage par triplets. Espace de clés plus grand.
• Hill-like modernes — DES, AES et tous les chiffrements par blocs symétriques descendent de l’idée hilliaire, adaptée à des matrices non-linéaires sur GF(2ⁿ).
• Cramer-Shoup, LWE — les chiffrements post-quantiques modernes restent, eux aussi, de l’algèbre linéaire sur des corps finis.

Faiblesses

• Attaque à clair connu : si l’attaquant connaît n paires (P, C), il obtient un système de n équations à n inconnues et en déduit la matrice K par algèbre linéaire. C’est instantané avec un ordinateur.
• Pas de sécurité sémantique : deux blocs clairs identiques produisent deux blocs chiffrés identiques — la structure du texte reste visible.
• Pour des petits n (2 ou 3), l’espace de matrices inversibles reste dans les dizaines de milliers ; brute-forçable.

C’est pourquoi, bien que mathématiquement élégant, Hill n’est jamais utilisé seul en pratique moderne. Ses descendants (DES, AES) ajoutent de la non-linéarité (les S-boxes) pour résister à l’analyse linéaire.

Dans CipherChronicle

Hill est une passerelle vers les chiffrements modernes. Les grilles associées peuvent inviter le joueur à manipuler directement des matrices, ce qui donne un aspect plus mathématique et technique — un contraste avec le pur décalage de César.