Chiffrement de Hill : les matrices modulo 26

Le chiffrement de Hill code un message par blocs de lettres : chaque paire de lettres devient une matrice colonne de deux nombres, que l'on multiplie par une matrice clé K, puis on réduit le résultat modulo 26. Pour déchiffrer, on multiplie par une matrice K' telle que K' × K ≡ I modulo 26. Publié par le mathématicien américain Lester Hill en 1929, il combine les deux modules de l'E3 que sont le calcul matriciel et l'arithmétique modulaire. Ce chapitre le déroule pas à pas, explique pourquoi certaines clés ne marchent pas et pourquoi ce chiffrement n'est plus utilisé.

Les ingrédients

Le chiffrement de Hill réutilise deux outils que tu connais :

• la numérotation des lettres de 0 (A) à 25 (Z), et le calcul modulo 26, vus avec le chiffrement affine :

• le produit d'une matrice par une colonne (chapitre 3).

Rappel sur les congruences : y ≡ r [26] signifie que y et r ont le même reste dans la division par 26. Réduire un nombre modulo 26, c'est le remplacer par ce reste, entre 0 et 25 : 59 = 2 × 26 + 7, donc 59 ≡ 7 [26]. Le détail est dans le cours d'arithmétique : congruences modulo n.

Chiffrer un message, pas à pas

La clé est une matrice carrée d'ordre 2 à coefficients entiers. Prenons :

K = [ 3  2 ]
    [ 5  7 ]

Pour chiffrer le mot RESEAU :

1. On découpe en paires : RE, SE, AU. Si le nombre de lettres est impair, on complète la dernière paire par une lettre convenue, souvent X.
2. On remplace chaque lettre par son rang : RE devient la colonne X = (17 ; 4).
3. On calcule Y = K × X : (3 × 17 + 2 × 4 ; 5 × 17 + 7 × 4) = (59 ; 113).
4. On réduit modulo 26 : 59 = 2 × 26 + 7 et 113 = 4 × 26 + 9, donc Y ≡ (7 ; 9) [26].
5. On repasse en lettres : 7 est H, 9 est J. La paire RE devient HJ.

On fait de même pour les autres paires :

RESEAU se chiffre HJKOOK.

Regarde le résultat : la lettre E de RE est devenue J, celle de SE est devenue O, alors que le O de HJKOOK vient tantôt d'un E, tantôt d'un A. Contrairement au chiffrement de César ou au chiffrement affine, une même lettre ne se chiffre pas toujours de la même façon : chaque lettre chiffrée dépend des deux lettres de sa paire. C'est ce qui rendait le chiffrement de Hill bien plus résistant à l'analyse des fréquences de lettres.

Déchiffrer avec la matrice inverse modulo 26

Pour revenir de Y à X, il faut « défaire » la multiplication par K. On cherche une matrice K' à coefficients entiers entre 0 et 25 telle que K' × K ≡ I₂ [26] : alors K' × Y ≡ K' × K × X ≡ X [26]. Pour notre clé, on donne :

K' = [ 3  14 ]
     [ 9   5 ]

Montrons que K' convient. On calcule le produit ordinaire, puis on réduit modulo 26 :

K' × K = [ 3×3 + 14×5    3×2 + 14×7 ]  =  [ 79  104 ]
         [ 9×3 +  5×5    9×2 +  5×7 ]     [ 52   53 ]

79 = 3 × 26 + 1 ≡ 1, 104 = 4 × 26 ≡ 0, 52 = 2 × 26 ≡ 0, 53 = 2 × 26 + 1 ≡ 1. Donc K' × K ≡ I₂ [26]. Le produit dans l'autre sens, K × K' = [ 27 52 ; 78 105 ], est lui aussi congru à I₂ modulo 26. K' est la matrice inverse de K modulo 26. C'est la même démarche qu'au chapitre 5, avec des égalités modulo 26 à la place d'égalités exactes.

Déchiffrons HJ : Y = (7 ; 9), K' × Y = (3 × 7 + 14 × 9 ; 9 × 7 + 5 × 9) = (147 ; 108). Or 147 = 5 × 26 + 17 ≡ 17 et 108 = 4 × 26 + 4 ≡ 4 : on retrouve (17 ; 4), soit RE.

Pourquoi certaines clés ne marchent pas

Une matrice K ne peut servir de clé que si elle a une inverse modulo 26 : sinon, deux paires différentes peuvent donner la même paire chiffrée, et le destinataire ne sait plus laquelle était envoyée. Prenons la matrice [ 2 4 ; 1 3 ] et chiffrons deux mots :

Deux mots différents donnent le même message chiffré : le chiffrement n'est pas réversible, la matrice n'est pas une clé valable. La raison tient à son nombre ad − bc = 2 × 3 − 4 × 1 = 2, qui n'est pas premier avec 26 : 2 n'a pas d'inverse modulo 26, exactement comme le coefficient a d'un chiffrement affine doit être premier avec 26 (pourquoi a doit être premier avec 26). Une clé de Hill d'ordre 2 est valable si et seulement si ad − bc est premier avec 26, c'est-à-dire impair et non multiple de 13. Sur les 26⁴ = 456 976 matrices 2 × 2 à coefficients entre 0 et 25, 157 248 sont des clés valables.

Pourquoi on n'utilise plus le chiffrement de Hill

Le chiffrement de Hill a marqué l'histoire, parce qu'il a été l'un des premiers à chiffrer des blocs de lettres par une opération algébrique, une idée qu'on retrouve dans les chiffrements modernes. Mais il est cassé depuis longtemps :

• il est linéaire : la paire AA (0 ; 0) donne toujours AA, et le chiffré de la somme de deux colonnes est la somme des chiffrés. Si un attaquant connaît quelques paires du message en clair et les paires chiffrées correspondantes (une formule de politesse, un en-tête), il retrouve la clé par un simple calcul matriciel modulo 26 : c'est une attaque à texte clair connu ;
• les fréquences des paires de lettres restent exploitables sur un long texte.

Les chiffrements actuels, comme AES, enchaînent de nombreux tours d'opérations non linéaires pour qu'aucun calcul algébrique simple ne relie le clair, le chiffré et la clé. Le principe de Kerckhoffs reste le même : la méthode est publique, seule la clé est secrète. Le cours de cryptographie raconte cette histoire, de César à AES : chiffrements historiques et chiffrement symétrique.

En Python

ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"


def hill(message, K):
    """Chiffre (ou déchiffre, avec la matrice inverse) un message par paires."""
    if len(message) % 2 == 1:
        message = message + "X"          # on complète la dernière paire
    resultat = ""
    for i in range(0, len(message), 2):
        x1 = ALPHABET.index(message[i])
        x2 = ALPHABET.index(message[i + 1])
        y1 = (K[0][0] * x1 + K[0][1] * x2) % 26
        y2 = (K[1][0] * x1 + K[1][1] * x2) % 26
        resultat = resultat + ALPHABET[y1] + ALPHABET[y2]
    return resultat


K = [[3, 2], [5, 7]]
K_inv = [[3, 14], [9, 5]]
chiffre = hill("RESEAU", K)
print(chiffre)
print(hill(chiffre, K_inv))

HJKOOK
RESEAU

La même fonction sert à chiffrer (avec K) et à déchiffrer (avec K'), puisque les deux opérations sont des produits par une matrice suivis d'une réduction modulo 26. L'opérateur % de Python donne le reste de la division euclidienne, toujours entre 0 et 25 ici.

Exercices