Plan du site  
français  English
pixel
pixel

Articles - Étudiants SUPINFO

Chapitre 05 - Chiffre affine et chiffre de Hill

Chiffre affine

Cette première partie sera consacrée à l'étude d'une généralisation du célèbre chiffre de César. On se placera du point de vue des correspondants, avec l'étude des opérations de chiffrement et déchiffrement, mais également de celui de l'ennemi, puisque l'on verra aussi comment décrypter ce chiffre.

Objectif

Rappelons pour commencer qu’un chiffre de substitution monoalphabétique est un algorithme de chiffrement où chaque lettre du message d’origine est remplacée par une autre lettre (ou un autre symbole). Il est important de noter que dans un tel système de chiffrement, une même lettre est toujours remplacée par une même autre lettre.

[Note]

Cette définition et plus généralement toutes celles de cryptologie figurent dans le premier chapitre de ce cours.

Le nombre de façons de chiffrer un texte par une telle méthode est assez impressionnant :

  • On a en effet 26 choix pour la lettre a.

  • Une fois ce choix fait, il nous reste 25 choix pour la lettre b.

  • On aura de même 24 choix pour la lettre c et ainsi de suite…

  • On a donc 26 × 25 × 24 × . . . × 1 = 26 ! algorithmes de substitutions monoalphabétiques. Ce qui fait environ 4 × 10 26 possibilités.

[Note]

On verra bientôt que même si ce nombre de possibilités peut paraître astronomique, et il l'est d'ailleurs, un message chiffré par ce type de procédé est relativement facile à décrypter.

Rappelons également qu'un système de chiffrement est dit symétrique si la clé utilisée lors du chiffrement est aussi celle utilisée lors du déchiffrement. Un tel système est aussi qualifié de système de chiffrement à clé secrète.

On va donc dans cette partie généraliser le chiffre de César en un chiffre dit affine, qui sera lui aussi un algorithme de chiffrement symétrique et de substitution monoalphabétique.

Pour mémoire, voici le tableau de chiffrement du chiffre de César, où l'on décale de 3 rangs vers la droite les lettres de l'alphabet :

clair a b c d e f g h i j k l m n o p q r s t u v w x y z
chiffré X Y Z A B C D E F G H I J K L M N O P Q R S T U V W

Moralement, on ajoute donc 3 à la valeur de chaque lettre, et quand on arrive à la fin de l'alphabet on revient au début. Le lecteur reconnaîtra sans peine une congruence modulo 26, qui sera constamment utilisée dans l'algorithme que nous allons étudier.

Chiffrement

Pour pouvoir effectuer des calculs arithmétiques sur les lettres, et donc définir nos algorithmes, nous devons associer préalablement un entier à chaque lettre.

Convention de représentation des lettres

a b c d e f g h i j k l m n o p q r s t u v w x y z
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

Dans toute la suite, on confondra donc une lettre et le nombre la représentant.

Nous sommes maintenant en mesure de présenter la formule du chiffrement affine. Puisque la substitution va être monoalphabétique, cette formule va porter sur une seule lettre à la fois.

Formule du chiffrement affine

Soient a et b des éléments de .

Une lettre x du message d'origine sera chiffrée par la lettre y vérifiant

y a x + b [ 26 ] et 0 y 25

Commençons par donner deux petits exemples afin de bien fixer les idées.

Example 1.1. Un premier chiffrement affine

Si a = 1 et b = 3 , on retrouve le chiffre de César. En effet, on a alors y x + 3 [ 26 ] , ce qui donne :

clair a b c d e f g h i j k l m
x 0 1 2 3 4 5 6 7 8 9 10 11 12
y 3 4 5 6 7 8 9 10 11 12 13 14 15
chiffré X Y Z A B C D E F G H I J
clair n o p q r s t u v w x y z
x 13 14 15 16 17 18 19 20 21 22 23 24 25
y 16 17 18 19 20 21 22 23 24 25 0 1 2
chiffré K L M N O P Q R S T U V W

Le mot "supinfo" est alors chiffré en "VXSLQIR".


[Note]

L'exemple précédent montre bien que le chiffre affine est une généralisation du chiffre de César.

Example 1.2. Un second chiffrement affine

Si a = 3 et b = 5 , on a alors y 3 x + 5 [ 26 ] , ce qui donne :

clair a b c d e f g h i j k l m
x 0 1 2 3 4 5 6 7 8 9 10 11 12
y 5 8 11 14 17 20 23 0 3 6 9 12 15
chiffré F I L O R U X A D G J M P
clair n o p q r s t u v w x y z
x 13 14 15 16 17 18 19 20 21 22 23 24 25
y 18 21 24 1 4 7 10 13 16 19 22 25 2
chiffré S V Y B E H K N Q T W Z C

Le mot "supinfo" est alors chiffré en "HNYDSUV".


[Note]

Pour remplir les tableaux précédents, on peut bien sûr calculer la valeur de y pour chacune des valeurs de x en appliquant la formule y a x + b [ 26 ] .

On peut cependant gagner un peu de temps en calculant tout d'abord la valeur de y pour x = 0 , ce qui donne évidemment b. On passe ensuite d'une case à la suivante en ajoutant a.

Nous allons maintenant nous intéresser à la clé de cet algorithme. Rappelons que la clé est le paramètre qui précise le fonctionnement d'un algorithme de chiffrement.

Clé du chiffrement affine

Avec les notations précédentes, la clé du chiffrement affine est le couple ( a , b ) .

Puisque la transformation précédente est définie modulo 26, on peut se contenter de choisir les entiers a et b entre 0 et 25. Cependant toutes ces valeurs ne vont pas convenir. Il paraît en effet naturel d’exiger que deux lettres distinctes soient chiffrées par deux lettres distinctes. Dans le cas contraitre le déchiffrement serait impossible. Et si l’on ne choisit pas correctement a et b ce n’est pas nécessairement le cas, comme nous allons le voir tout de suite sur un exemple.

Example 1.3. Une clé non valide

Si a = 2 et b = 5 , c'est-à-dire pour la transformation y 2 x + 5 [ 26 ] , les valeurs 0 et 13 sont toutes deux transformées en 5 (car 31 5 [ 26 ] ). Les lettres "a" et "n" sont donc toutes les deux chiffrées par "F".


Le résultat suivant nous donne une condition pour qu'une clé soit valide.

Validité de la clé

Un couple ( a , b ) convient (au sens précédent) pour un algorithme de chiffrement affine si et seulement si a et 26 sont premiers entre eux, i.e. PGCD ( a , 26 ) = 1 . Il n’y a pas de conditions sur b.

Avant de nous intéresser à la preuve de ce résultat, constatons que cela donne comme valeurs possibles pour a les entiers 1,3,5,7,9,11,15,17,19,21,23,25. Il y a donc 12 possibilités pour a, et comme il y en a 26 pour b, cela donne 12 × 26 = 312 clés possibles.

[Note]

Il y a en fait 311 clés car on peut exclure la transformation identité qui correspond à a = 1 et b = 0 . Cette dernière ne modifiant en effet aucune des lettres de l'alphabet, tout message demeurerait inchangé.

Démonstration de la condition sur la clé

Supposons dans un premier temps que a soit premier avec 26. Il suffit de montrer que si deux lettres chiffrées sont égales, alors elles proviennent de la même lettre du message d'origine. On considère donc y et y de la forme y a x + b [ 26 ] et y a x + b [ 26 ] tels que y y [ 26 ] . Cela donne évidemment a x + b a x + b [ m ] , et donc après factorisation a ( x - x ) 0 [ 26 ] . Ce qui signifie que 26 | a ( x - x ) . Or PGCD ( a , 26 ) = 1 , donc d'après le théorème de Gauss 26 | ( x - x ) . Cependant 0 x 25 et 0 x 25 donc - 25 x - x 25 . La seule possibilité est donc que x - x = 0 , i.e. x = x , ce que l'on souhaitait obtenir.

Réciproquement, supposons que a ne soit pas premier avec 26. Soit d = PGCD ( a , 26 ) et k, k les entiers tel que 26 = k d et a = k d . On a bien sûr 0 < k < 26 (car d > 1 par hypothèse) et on peut donc considérer la lettre de l’alphabet représentée par k. Notons $ cette lettre. Montrons que les lettres "A" et $, qui sont distinctes puisque représentées respectivement par 0 et k, sont alors chiffrées de la même façon. On a a k + b k d k + b 26 k + b b [ 26 ] . Or il est clair que a 0 + b b [ 26 ] . On en conclut que la clé n'est pas valide.

[Note]

Le lecteur aura sans doute remarqué qu'exiger que deux lettres distinctes soient chiffrées par deux lettres distinctes revient à demander que l'application

0 ; 25 0 ; 25 x a x + b [ 26 ]

soit injective.

Elle sera alors même bijective, car l'ensemble 0 ; 25 est de cardinal fini.

Déchiffrement

L'objectif de cette sous-partie sera de comprendre comme le destinataire d'un message chiffré de façon affine peut reconstituer le message d'origine à l'aide de la clé.

Formule du déchiffrement affine

Soient a et b des éléments de tels que PGCD ( a , 26 ) = 1 .

Soit a l'inverse multiplicatif de a modulo 26. On pose b - a b [ 26 ] .

Une lettre y du message chiffré correspondra à la lettre x du message d'origine vérifiant

x a y + b [ 26 ] et 0 x 25

Démonstration de la formule de déchiffrement

Constatons tout d'abord que a existe bien. Cela provient du fait que PGCD ( a , 26 ) = 1 et du critère du troisième chapitre sur l'existence d'un inverse multiplicatif.

Il suffit ensuite de démontrer que si l'on applique la formule de déchiffrement à un y de la forme y a x + b [ 26 ] , alors le résultat est x.

On a a y + b a ( a x + b ) + b a a x + a b + b [ 26 ] . Or a a 1 [ 26 ] et b - a b [ 26 ] donc on a bien a y + b x [ 26 ] . Q.E.D.

[Note]

Rappelons que l’inverse multiplicatif modulo 26 d’un nombre a premier avec 26 s’obtient en déterminant les coefficients de Bézout de a et 26. Voir troisième chapitre de ce cours.

Voyons à présent sur un exemple comment cette formule se manipule.

Example 1.4. Un déchiffrement affine

Reprenons la clé a = 3 et b = 5 , qui correspondait au chiffrement y 3 x + 5 [ 26 ] . On va chercher à déchiffrer "HNYDSUV".

On commence par déterminer la relation de Bézout de 3 et 26 : 3 × 9 + 26 × ( - 1 ) = 1 . L'inverse multiplicatif modulo 26 de 3 est donc a = 9 .

D'autre part, b - a b - 9 × 5 - 45 7 [ 26 ] .

La relation de déchiffrement est donc x 9 y + 7 [ 26 ] . Cela donne :

chiffré A B C D E F G H I J K L M
x 0 1 2 3 4 5 6 7 8 9 10 11 12
y 7 16 25 8 17 0 9 18 1 10 19 2 11
clair h q z i r a j s b k t c l
chiffré N O P Q R S T U V W X Y Z
x 13 14 15 16 17 18 19 20 21 22 23 24 25
y 20 3 12 21 4 13 22 5 14 23 6 15 24
clair u d m v e n w f o x p p y

Le mot "HNYDSUV" se déchiffre alors en "supinfo".


Décryptement

On se place ici du point de vue d’un ennemi interceptant un message dont il sait qu’il a été chiffré avec un algorithme de chiffrement affine, mais qui ignore avec quelle clé.

Sa première option est d’essayer toutes les clés jusqu’à obtenir un texte intelligible. C’est long mais tout à fait faisable, surtout avec un ordinateur. On a vu en effet qu’il n’existait que 311 clés.

[Note]

Cette méthode consistant à tester toutes les possibilités pour trouver la bonne s'appelle une attaque par force brute.

La seconde option est beaucoup plus générale, car elle permet en effet de décrypter tout message chiffré avec un algorithme de substitution monoalphabétique. Cette technique s’appelle analyse des fréquences. Elle repose sur une constatation très simple : dans une langue donnée, chaque lettre n’a pas la même fréquence d’utilisation. Comme chaque lettre du message d’origine est remplacée par une même autre lettre, on va pouvoir en analysant les fréquences des lettres dans le message chiffré, retrouver la clé de chiffrement.

[Note]

Cette technique date du 9e siècle, voir historique du premier chapitre.

Il faut pour ce faire connaître les fréquences théoriques d’utilisation des différentes lettres en français. On peut par exemple effectuer des relevés sur des grands échantillons de lettres provenant de divers textes.

Les fréquences suivantes (exprimées en pourcentages) ont été calculées par Didier Muller, et figurent dans son excellent livre "Les codes secrets décryptés", City Editions.

lettre A B C D E F G H I J K L M
fréquence 8,40 1,06 3,03 4,18 17,26 1,12 1,27 0,92 7,34 0,31 0,05 6,01 2,96
lettre N O P Q R S T U V W X Y Z
fréquence 7,13 5,26 3,01 0,99 6,55 8,08 7,07 5,74 1,32 0,04 0,45 0,30 0,12

Voici ces mêmes fréquences représentées cette fois sous la forme d'un histogramme :

Cette fois-ci en classant les fréquences par ordre décroissant :

[Note]

Pour que les lettres d'un texte donné aient approximativement ces fréquences, il faut que ce texte soit assez long. Sur un texte court, par exemple "RV au pub", ça ne sera pas le cas. En statistiques on appelle ce phénomène la loi des grands nombres.

Il faut de plus que ce texte ne possède pas de particularités bizarres. Oublions donc des ouvrages comme celui de Georges Pérec "La Disparition", roman ne comportant pas la lettre "e".

En pratique on complètera cette étude des fréquences des lettres par celle des doublets. En français les plus fréquents sont dans l'ordre : "ss", "ll", "mm", "rr", "tt", "nn", "pp", "ee", "cc", "ff".

Si l'on connaît le sujet du message, on pourra également tenter une attaque par mot probable, c’est-à-dire que l'on supposera qu’un mot donné fait partie du message et on essaiera de l’identifier dans le texte. Cela permet alors de décrypter plusieurs lettres d'un seul coup.

Example 1.5. Application de la technique d'analyse des fréquences

Essayons de décrypter le message : "GMKAM PPMKK MJCSM BNPMJ VMSGG MQKMK KSNQF DQVCS KNDPO MJTCB KGMQJ KOJCK KCBKN DPOMJ MBNJM GMQJK PCSBK".

La lettre ayant la plus forte fréquence est le "M". On peut donc penser qu’elle représente le "e".

Si l'on effectue ce remplacement, le texte devient : "GeKAe PPeKK eJCSe BNPeJ VeSGG eQKeK KSNQF DQVCS KNDPO eJTCB KGeQJ KOJCK KCBKN DPOeJ eBNJe GeQJK PCSBK".

Ensuite la lettre la plus fréquente est le "K". Elle représente sans doute le "a" ou le "s". Etant plusieurs fois accolée au ‘e’ on va plutôt opter pour le ‘s’. Essayons : "GesAe PPess eJCSe BNPeJ VeSGG eQses sSNQF DQVCS sNDPO eJTCB sGeQJ sOJCs sCBsN DPOeJ eBNJe GeQJs PCSBs".

La lettre la plus fréquente est alors le "J". Étant elle aussi accolée plusieurs fois au "e" c’est sans doute une consonne. De même pour le "P".

Le "a" sera donc sans doute chiffrée par le "C", lettre la plus fréquente non collée au "e".

Cela donne : "GesAe PPess eJaSe BNPeJ VeSGG eQses sSNQF DQVaS sNDPO eJTaB sGeQJ sOJas saBsN DPOeJ eBNJe GeQJs PaSBs".

etc.


Exercice corrigé

1.1.

Terminer le décryptement commencé lors de l'exemple précédent.

"Les femmes seraient merveilleuses si tu pouvais tomber dans leurs bras sans tomber entre leurs mains".

[Note]

La citation précédente est extraite de la bande dessinée de Hugo Pratt, "Sous le signe du Capricorne".

Extensions possibles

La technique d'analyse des fréquences a donc mis en évidence toute la faiblesse d’un chiffre de substitution monoalphabétique.

Pour pallier à ce problème, plusieurs solutions sont envisageables :

  • Utiliser un chiffre de substitution polyalphabétique, comme par exemple le chiffre de Vigenère présenté dans le premier chapitre de ce cours.

  • Utiliser un chiffre de substitution polygrammique, comme par exemple le chiffre de Hill, que l’on étudiera dans la partie suivante.

  • Utiliser un algorithme de cryptographie asymétrique, tel le R.S.A., que l’on décrira dans le prochain et dernier chapitre.

Chiffre de Hill

Nous allons dans cette partie remédier à certaines faiblesses du chiffre affine en présentant une version polygrammique de celui-ci.

Objectif

Tout d'abord, rappelons qu’avec un chiffre de substitution polygrammique les lettres ne sont pas chiffrées une par une mais par blocs de plusieurs (deux ou trois généralement). On parle également de chiffrement par blocs.

Dans un premier temps on ne considèrera que des blocs de deux lettres, i.e. des bigrammes. Cela permet déjà d'obtenir un très grand nombre de possibilités pour chiffrer un texte :

  • Constatons déjà que l'on dispose de 26 2 = 676 bigrammes (26 choix pour la première lettre et autant pour la seconde).

  • Pour chiffrer le premier de ces bigrammes on a donc 676 choix.

  • Une fois ce choix effectué, il restera 675 choix pour le second bigramme.

  • On aura de même 674 choix pour le troisième bigramme et ainsi de suite…

  • On a donc 676 × 675 × 674 × . . . × 1 = 676 ! algorithmes de substitutions polygrammiques avec des blocs de deux lettres.

[Note]

Ce nombre de 676! est gigantesque, une simple calculatrice ne peut l'exprimer.

Dans la suite de cette partie, nous allons donc présenter un chiffre symétrique de substitution polygrammique. Cet algorithme apparaîtra également comme une version à deux dimensions du chiffre affine, puisque nous effectuerons les mêmes types de calculs que lors de celui-ci.

Ce chiffre est dû à l'américain Lester Hill (1891-1961).

Chiffrement

Il faut bien sûr commencer par découper le message à chiffrer en blocs de deux lettres. Dans le cas où le nombre de lettres du message est impair, on rajoute arbitrairement un "x" à la fin pour le rendre pair.

Nous adopterons la même convention de représentation des lettres en nombres que pour le chiffre affine. Un bigramme sera donc un couple de deux entiers ( x 1 , x 2 ) compris entre 0 et 25. Voici la formule de chiffrement :

Formule du chiffrement de Hill

Soient a, b, c et d des éléments de .

Un bigramme ( x 1 , x 2 ) du message d'origine sera chiffré par le bigramme ( y 1 , y 2 ) vérifiant

{ y 1 a x 1 + b x 2 [ 26 ] et 0 y 1 25 y 2 c x 1 + d x 2 [ 26 ] et 0 y 2 25

Présentons de suite un exemple.

Example 1.6. Un chiffrement de Hill

Si a = 5 , b = 17 , c = 4 , et d = 15 , on a

{ y 1 5 x 1 + 17 x 2 [ 26 ] et 0 y 1 25 y 2 4 x 1 + 15 x 2 [ 26 ] et 0 y 2 25

Cherchons à chiffrer le mot "supinfo". Le nombre de lettres étant impair, on lui adjoint arbitrairement un "x". On découpe alors ce mot en blocs de deux lettres "su pi nf ox".

L'équivalent en nombres du premier bigramme est donc ( x 1 , x 2 ) = ( 18 , 20 ) . Il sera donc chiffré en

{ y 1 5 × 18 + 17 × 20 430 14 [ 26 ] y 2 4 × 18 + 15 × 20 372 8 [ 26 ]

Ce qui donne en lettres "OI".

On procède de même pour les trois autres blocs, et l'on obtient finalement "OIDYUXTL".


Il est temps de nous intéresser à la clé de cet algorithme.

Clé du chiffrement de Hill

Avec les notations précédentes, la clé du chiffrement de Hill est le quadruplet ( a , b , c , d ) .

Comme pour le chiffre affine, puisque l'on travaille modulo 26, on pourra se contenter de prendre les entiers a, b, c et d entre 0 et 25. Et pour les mêmes raisons qu'avec le chiffre affine toutes ces valeurs ne vont cependant pas convenir. On va en effet logiquement exiger que deux bigrammes distincts soient chiffrés par deux bigrammes distincts.

Voici le résultat nous permettant de savoir si une clé est valide ou non.

Validité de la clé

Un quadruplet ( a , b , c , d ) convient (au sens précédent) pour un algorithme de chiffrement de Hill si et seulement si a d - b c et 26 sont premiers entre eux, i.e. PGCD ( a d - b c , 26 ) = 1 .

Démonstration de la condition sur la clé

La preuve de ce résultat sera effectuée dans un cadre plus général lors de la sous-partie 2.5.

Déchiffrement

Le destinataire d'un message chiffré avec l'algorithme de Hill reconstituera le message d'origine à l'aide de la clé et de la formule suivante :

Formule du déchiffrement de Hill

Soient a, b, c et d des éléments de tels que PGCD ( a d - b c , 26 ) = 1 .

Soit i l'inverse multiplicatif de a d - b c modulo 26.

Un bigramme ( y 1 , y 2 ) du message chiffré correspondra au bigramme ( x 1 , x 2 ) du message d'origine vérifiant

{ x 1 i ( d y 1 b y 2 ) [ 26 ] x 2 i ( c y 1 + a y 2 ) [ 26 ]

Démonstration de la formule de déchiffrement

Constatons tout d'abord que i existe bien. Cela provient du fait que PGCD ( a d - b c , 26 ) = 1 et du critère du troisième chapitre sur l'existence d'un inverse multiplicatif.

Vérifions ensuite que si l'on applique la première des deux égalités de la formule à un couple ( y 1 , y 2 ) de la forme

{ y 1 a x 1 + b x 2 [ 26 ] y 2 c x 1 + d x 2 [ 26 ]

alors le résultat est x 1 .

On a i ( d y 1 b y 2 ) = i ( d ( a x 1 + b x 2 ) b ( c x 1 + d x 2 ) ) = i ( a d b c ) x 1 x 1 [ 26 ] . La dernière simplification découlant du fait que i ( a d b c ) 1 [ 26 ] .

La formule donnant x 2 se démontre évidemment de la même façon. Q.E.D.

Continuons maintenant l'exemple de la sous-partie précédente pour bien saisir comment s'applique cette formule.

Example 1.7. Un déchiffrement de Hill

Reprenons la clé a = 5 , b = 17 , c = 4 , et d = 15 qui correspondait au chiffrement

{ y 1 5 x 1 + 17 x 2 [ 26 ] y 2 4 x 1 + 15 x 2 [ 26 ]

On va chercher à déchiffrer "OIDYUXTL". On a a d - b c = 7 , qui est bien premier avec 26. On détermine alors la relation de Bézout de a d - b c et 26 : 7 × 15 + 26 × ( - 4 ) = 1 . L'inverse multiplicatif modulo 26 de 7 est donc i = 15 .

La relation de déchiffrement est donc

{ x 1 15 × ( 15 y 1 17 y 2 ) [ 26 ] x 2 15 × ( 4 y 1 + 5 y 2 ) [ 26 ]

Considérons le premier bigramme "OI" dont l'équivalent numérique est ( y 1 , y 2 ) = ( 14 , 8 ) . Il sera donc déchiffré en

{ x 1 15 × ( 15 × 14 17 × 8 ) 1110 18 [ 26 ] x 2 15 × ( 4 × 14 + 5 × 8 ) 240 20 [ 26 ]

ce qui donne en lettres "su".

On procède de même pour les trois autres blocs, et l'on obtient finalement "supinfo".


Décryptement

Bien qu’il soit plus dur à casser qu’un chiffre affine, le chiffre de Hill est loin de garantir une sécurité totale.

On peut lui aussi l’attaquer en faisant une analyse de fréquences, mais cette fois sur les bigrammes. Les plus fréquents de la langue française sont : "es", "en", "ou", "de", "nt", "te", "on". En relevant les bigrammes apparaissant le plus dans un texte chiffré, on pourra supposer qu’ils représentent un de ceux-là.

On pourra ensuite compléter cette démarche par une attaque avec mot probable.

Nous ne rentrerons pas plus dans les détails.

Définition matricielle du chiffre de Hill

[Note]

Cette sous-partie n'est pas au programme d'évaluation des étudiants de SUPINFO International University.

Nous allons dans cette dernière sous-partie reformuler les formules de chiffrement et déchiffrement à l'aide de matrices. Cela nous permettra également de les généraliser à des blocs de plus de deux lettres.

[Note]

Le lecteur pourra consulter le cours 1LAL pour toutes généralités sur le calcul matriciel.

Pour x 1 , x 2 , y 1 et y 2 des éléments de , posons

X = ( x 1 x 2 ) et Y = ( y 1 y 2 )

Pour a, b, c et d des éléments de , on définit la matrice A comme

A = ( a b c d )

Il est alors facile de voir que la formule du chiffrement de Hill telle que nous l'avons présentée dans la sous partie 2.2, i.e.

{ y 1 a x 1 + b x 2 [ 26 ] y 2 c x 1 + d x 2 [ 26 ]

est équivalente à celle-ci

Y = A X [ 26 ]

Ici AX désigne le produit des matrices A et X, et le modulo 26 est appliqué à chacun des coefficients de Y.

Sur le modèle de cette dernière formule, on peut alors présenter le chiffre de Hill avec des blocs de n lettres.

Formule du chiffrement de Hill avec des blocs de taille quelconque

Soit n élément de * .

Soit A élément de M n ( ) , i.e. une matrice carrée d'ordre n à coefficients entiers.

Un bloc de n lettres X= ( x 1 x n ) du message d'origine sera chiffré par le bloc Y= ( y 1 y n ) vérifiant Y A X [ 26 ] .

Clé du chiffrement de Hill

Avec les notations précédentes, la clé du chiffrement de Hill est la matrice A.

On va évidemment conserver l'exigence que deux blocs de lettres distincts soient chiffrés par deux blocs de lettres distincts. Rappelons que pour n = 2 , la condition pour cela est que a d - b c et 26 soient premiers entre eux. Le lecteur reconnaîtra bien sûr en a d - b c l'expression du déterminant de la matrice A. La restriction sur la clé se généralisera donc naturellement de la façon suivante pour des blocs de n lettres, avec n > 2 .

Validité de la clé

Une matrice A convient (au sens précédent) pour un algorithme de chiffrement de Hill si et seulement si det ( A ) et 26 sont premiers entre eux, i.e. PGCD ( det ( A ) , 26 ) = 1 .

Nous démontrerons le résultat précédent en même temps que la formule de déchiffrement.

Formule du déchiffrement de Hill avec des blocs de taille quelconque

Soit n élément de * .

Soit A élément de M n ( ) tel que PGCD ( det ( A ) , 26 ) = 1 .

Soit i l'inverse multiplicatif de det ( A ) modulo 26, et soit B i × c t o m ( A ) [ 26 ] .

Un bloc de n lettres Y= ( y 1 y n ) du message chiffré correspondra au bloc X= ( x 1 x n ) du message d'origine vérifiant X B Y [ 26 ] .

Démonstration de la validité de la clé et de la formule de déchiffrement

Pour que la clé soit valide et donc que l'on puisse déchiffrer un message, il convient connaissant A et Y tel que Y A X [ 26 ] de pouvoir calculer la valeur de X. Cela est faisable si et seulement si la matrice A est inversible et que son inverse est à coefficients entiers. On aura alors tout simplement X A - 1 Y [ 26 ] .

Pour démontrer cela on considère l'égalité algébrique classique

c t o m ( A ) × A = A × c t o m ( A ) = det ( A ) × I n

Ainsi, pour que A soit inversible et que son inverse soit à coefficients entiers il faut et il suffit que det ( A ) soit inversible modulo 26. Si i est cet inverse, on a alors A 1 i × c t o m ( A ) [ 26 ] . Q.E.D.

A propos de SUPINFO | Contacts & adresses | Enseigner à SUPINFO | Presse | Conditions d'utilisation & Copyright | Respect de la vie privée | Investir
Logo de la société Cisco, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société IBM, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Sun-Oracle, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Apple, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Sybase, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Novell, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Intel, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Accenture, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société SAP, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Prometric, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo du IT Academy Program par Microsoft, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management

SUPINFO International University
Ecole d'Informatique - IT School
École Supérieure d'Informatique de Paris, leader en France
La Grande Ecole de l'informatique, du numérique et du management
Fondée en 1965, reconnue par l'État. Titre Bac+5 certifié au niveau I.
SUPINFO International University is globally operated by EDUCINVEST Belgium - Avenue Louise, 534 - 1050 Brussels