CRYPTOGRAPHIE DE HILL



Chiffrement inventé par Lester Hill (1891-1961) cryptographe et professeur Américain. Il devint célèbre en 1929 lorsqu'il publia son "Cryptography in an Algebraic Alphabet" dans "The American Mathematical Monthly" de Juin. Il n'était alors qu'un simple assistant lorsqu'il proposa une véritable méthode de chiffrement fortement teintée de théorie algébrique.
Le principe consiste encore une fois à chiffrer un bloc de n caractères clairs en un bloc de n caractères cryptés. Par exemple, soient x1, x2 et x3 les 3 caractères à chiffrer. On va obtenir y1, y2 et y3 (les 3 caractères cryptés) par combinaison linéaire de x1, x2 et x3.

y1=a1*x1+b1*x2+c1*x3
y2=a2*x1+b2*x2+c2*x3
y3=a3*x1+b3*x2+c3*x3

ou encore, en notation matricielle:
(y1) (a1 b1 c1) (x1)
(y2)=(a2 b2 c2)*(x2)
(y3) (a3 b3 c3) (x3)
Bien sur nous travaillons toujours modulo 26 (pour l'alphabet). Comme vous le sentez venir pour déchiffrer un bloc il suffit d'appliquer la matrice inverse:
               -1
(x1) (a1 b1 c1)   (y1)
(x2)=(a2 b2 c2) * (y2)
(x3) (a3 b3 c3)   (y3)
C'est là que se pose un petit problème car comme tout le monde le sait, une matrice n'admet pas forcément une inverse surtout si l'on veut travailler avec des entiers. Petit rappel: A*A^-1=Id ou Id est la matrice identité (des 1 sur la diagonale principale, et des 0 partout ailleurs). Dans l'espace des réels, une matrice est inversible si Det A est différent de 0 (déterminant de la matrice non nul), mais dans notre espace, ceci n'est vrai que si pgcd(det A,26)=1.
Pour se représenter un peu plus simplement la manipulation, on peut voir le chiffrement de la manière suivante. On peut considérer le bloc à crypter comme étant un point dans un espace à n dimensions (n étant la taille du bloc). Prenons 3 dimensions pour mettre les idées plus au clair, vu que nous avons bien l'habitude de cet espace. Le chiffrement de Hill est tout simplement une transformation de ce point dans l'espace (par exemple suivant une rotation, ou une translation etc...). On trouve ainsi un autre point dans cet espace qui représente le bloc chiffré. Il faut bien sur que la transformation soit bijective (pour que l'on puisse passer d'un point à son image sans aucune ambiguïté et vis versa). Et il faut rester dans l'espace des Z 26 (entier modulo 26).
C'est une méthode assez amusante car vue de cette façon elle est relativement intuitive et visuelle.

Hill publia en 1931 dans "The American Mathematical Monthly" (je ne sais pas le mois) un autre article sur le chiffrement à plusieurs matrices. PS: si quelqu'un peut me faire parvenir les textes originaux je suis preneur.