Diapositive 1

Le chiffrement de Lester Hill est un crypto systme conu en 1929 pour rsister aux analyses de frquences.PrincipeSoit n et m deux entiers naturels suprieurs ou gaux 2, et K une matrice carre inversible de format (n, n) coefficients dans Zm ( = Z/mZ).Lapplication qui, toute matrice colonne X de format (n,1) et coefficients dans Zm, associe la matrice Y = KX, dfinit un systme de chiffrement symtrique (i.e. la mme cl est utilise pour crypter et dcrypter l'information) ou clef secrte.Chiffrement de Lester HillPropritSoit K une matrice appartenant Mn(Zm).K est inversible dans Mn(Zm) si, et seulement si, det(K) est inversible modulo m. En effet : Si K est inversible dans Mn(Zm), il existe L Mn(Zm) telle que KL = LK = In (modulo m).Alors det(KL)=det(LK) =1 (mod m) do det(K) det(L) =1 (mod m), ce qui prouve que det(K) est inversible modulo m. Rciproquement : Supposons det(K) inversible modulo m.Il existe donc , entier naturel infrieur ou gal m 1, tel que det(K) =1 (mod m). Alors la matrice L = t(com K) vrifie KL = LK = In (mod m), ce qui prouve que K est inversible dans Mn(Zm) .Proprit 1Card (Mn (Z26))* = Card (Mn (Z2))* Card (Mn (Z13))*Proprit 2Si p est un nombre premier, alors :

DmonstrationDmonstrationLe nombre de cls (nombre de matrices inversibles dans Mn (Z26) ) est :

Pour le dmontrer, on utilise les deux proprits suivantes :On note (Zm)* lensemble des lments inversibles de Zm et (m) son cardinal. ( est lindicatrice dEuler)

alors :Si (dcomposition de m en produit de facteurs premiers),

4Proprit 2Soit p un nombre premier.Pour tout entier naturel non nul : (p) = p p 1. Il y a en effet p 1 entiers compris entre 0 et p 1, non premiers avec p. Ce sont les nombres kp o k {0, 1,2,, (p 1 1)} (multiples de p strictement infrieurs p ).Proprit 1Si m et n sont premiers entre eux : (mn) = (m)(n).En effet, Zmn Zm Zn , et donc (Zmn)* (Zm)* (Zn)*. Pour le dmontrer, on utilise les deux proprits suivantes :Pour le professeurtude de quelques exemples1. Chiffrement dun texte laide de 26 caractresLes 26 lettres de lalphabet sont codes de 0 25 (0 pour A et 25 pour Z)On enlve les caractres non alphabtiques (espaces, ponctuation, chiffres) ; on ne distingue pas les majuscules des minuscules. On dcoupe le texte par blocs de n lettres. La cl est une matrice K de Mn(Z26)., alors det(K ) = 1 et .

Si n = 2 etLe texte crypt est donc : ATVZ.Inversement le texte FX se dcrypte en calculant .Le texte clair OTTO, dfini par les matrices colonnes , est crypt en calculant

et donne les codes suivants : .

Le texte clair est donc PI.Exemple

Ressources sur eulerChiffre de HillOutil : 4045 (Codage dun texte laide du chiffre de Hill)Apprentissage 4046/4046 (Coder/dcoder un mot ) Inverse dune matrice modulo un entierOutil : 4043Apprentissage, gnrateur, QCM : 4055, 4058, 4056, 4057

Dans le cas dun chiffrement de Hill avec n = 2 et 26 caractres, Card (M2(Z26))* = (22 1)(22 2)(132 1)(132 13), soit 157 248 cls possibles.La probabilit quune matrice de M2(Z26) choisie au hasard puisse tre une matrice de chiffrement est gale Card (M2(Z26))* / Card M2(Z26) soit 0,34 (arrondi au centime). 1. On peut dnombrer directement les matrices de (M2(Z26))*.

K est inversible ssi ad bc est premier avec 26, cest--diressi ad bc est impair et non divisible par 13.2. Si lon utilise 37 caractres (les 26 lettres de lalphabet, les 10 chiffres et lespace) : Card (M2(Z37))* = (372 1)(372 37) soit 1 822 176 cls possibles et la probabilit quune matrice de M2(Z37) choisie au hasard puisse tre une matrice de chiffrement est gale Card (M2(Z37))* / Card M2(Z37) , soit 0,97 (arrondi au centime).RemarquesUne premire approche avec un tableur consiste crer une image trs simple (comme une spirale) et visualiser directement cette image en associant la couleur darrire-plan de la cellule la valeur de la cellule elle-mme.On peut ensuite crypter limage en la dcoupant en blocs de n pixels (dans lexemple de la spirale, n = 2) et en la chiffrant avec une cl K de Mn (Z256) spirale2. Chiffrement dune image en niveaux de grisDun point de vue informatique, les niveaux de gris sont cods sous forme de nombres entiers compris entre 0 et 255 (avec huit bits, un maximum de 256 = 28 valeurs distinctes de lintensit lumineuse peut tre atteint). La valeur 0 reprsente alors la couleur noire, et la valeur 255 la couleur blanche.Une image numrique matricielle est essentiellement un ensemble de pixels,organiss en un rectangle, chacun de ces pixels tant pourvu dune couleur qui peut tre un niveau de gris, une combinaison dintensits lumineuses en rouge, vert et bleu ou simplement du noir ou blanc.

11DmonstrationsDmontrons que Card (Mn (Z26))* = Card (Mn (Z2))* Card (Mn (Z13))*.Considrons la relation :

dfinit une fonction car si aij aij (mod 26) alors aij aij (mod 2) et aij aij (mod 13).On vrifie que est un morphisme danneaux unitaires, injectif (Ker = {(aij )i,j (mod 26) tel que (i,j),aij 0 (mod 2) et aij 0 (mod 13)} ; do aij 0 (mod 26) car 2 et 13 sont premiers entre eux).Comme Card Mn (Z26) = Card ((Mn (Z2) Mn (Z13)), est un isomorphisme danneaux : Mn (Z26) Mn (Z2) Mn (Z13).On en dduit que : (Mn (Z26))* (Mn (Z2))* (Mn (Z13))*.Soit K Mn (Z26). K est inversible dans Mn(Z26) si, et seulement si K est inversible dans Mn (Z2) et dans Mn (Z13) (en effet K est inversible dans Mn (Z26) si et seulement si det(K) nest divisible ni par 2 ni par 13).