Cryptographie!
Le plan de la partie : méthodes historiques de cryptographie >

Le chiffre de Hill (sans mathématiques)

Principe

  Lester Hill, mathématicien cryptographe (1891-1961) publie en 1929 dans la revue American Mathematical Monthly un article intitulé Cryptography in an algebraic alphabet, où il détaille un nouveau type d'algorithme de chiffrement. Son idée est de continuer à utiliser des décalages du même type que celui du chiffre de César, mais en effectuant ces décalages simultanément sur des groupes de m lettres! Bien sûr, plus m est grand, plus les analyses statistiques deviennent difficiles!

  D'abord, nous remplaçons chaque lettre par son ordre dans l'alphabet-1 : A devient 0, B devient 1,..., Z devient 25. On groupe les nombres ainsi obtenus par m (prenons par exemple m=2). Pour chaque bloc de m nombres à coder x1x2...xm, on calcule le texte codé en effectuant des combinaisons linéaires (ici m=2) :
y1=ax1+bx2
y2=cx1+dx2
Si a,b,c,d sont des entiers, y1 et y2 seront aussi des entiers. Pourtant, si l'on souhaite les reconvertir en lettres, il faudrait qu'ils soient compris entre 0 et 25 ce dont on ne peut s'assurer. On les y ramène en prenant leur reste dans la division par 26. Si z1 et z2 sont les restes respectifs de y1 et y2 dans la division par 26, on peut retransformer z1 et z2 en lettres, et obtenir le message codé.

  Le choix de la clé correspond ici au choix d'un nombre m, et au choix des combinaisons linéaires à effectuer (ce sont toujours les mêmes de blocs en blocs), c'est-à-dire des entiers a,b,c,d.

Exemple

  On souhaite coder le mot ELECTION avec le chiffre de Hill, pour m=2, a=3, b=5, c=1 et d=2.
Etape 1 : On partage en blocs de 2 : EL EC TI ON.
Etape 2 : On remplace les lettres par leur nombre associé : 4-11 | 4-2 | 19-8 | 14-13.
Etape 3 : On effectue les combinaisons linéaires pour chaque bloc. Par exemple, pour le premier bloc, où x1=4 et x2=11, on a :
y1=3×4+5×11=67.
y2=1×4+2×11=26.
De même, y3=22, y4=8, y5=97, y6=35, y7=107, y8=40.
Etape 4 : On prend les restes modulo 26, et on trouve : z1=15, z2=0, z3=22, z4=8, z5=19, z6=9, z7=3, z8=14.
Etape 5 : On reconvertit en lettres, pour trouver PAWITJDO.
On peut remarquer que le premier E de ELECTION est transformé en P, tandis que le second est transformé en W. Le critère des chiffrements polyalphabétiques est bien respecté : les analyses statistiques directes sur la fréquence des lettres sont impossibles.


Déchiffrement
  Pour déchiffrer un message codé connaissant la clé, on procède exactement de la même façon. On découpe donc en blocs de m lettres, mais cette fois il faut inverser les relations données par les combinaisons linéaires : si un système donne y1 et y2 en fonction de x1 et x2, il faut pouvoir l'inverser et exprimer y1 et y2 en fonction de x1 et x2. Ce n'est pas toujours possible, et il existe des critères mathématiques pour tester cela. Très concrètement, la condition est que l'entier $ad-bc$ ne soit ni divisible par 2, ni divisible par 13.

En pratique

  Codons donc nos messages par le chiffre de Hill :

Message clair
Clé a= b=
c= d=
     
Message codé

Consulter aussi