=Paper=
{{Paper
|id=Vol-547/paper-50
|storemode=property
|title=Sécurité des Données en se basant sur le Chiffre de Hill
|pdfUrl=https://ceur-ws.org/Vol-547/18.pdf
|volume=Vol-547
|dblpUrl=https://dblp.org/rec/conf/ciia/Hadj-SaidAMB09
}}
==Sécurité des Données en se basant sur le Chiffre de Hill==
https://ceur-ws.org/Vol-547/18.pdf
Sécurité des Données en se basant sur le Chiffre de Hill
Naima HADJ-SAID1–A. ALI-PACHA1 – A. M’HAMED2–A. BELGORAF1
1
Université des Sciences et de la Technologie d’Oran –USTO, BP 1505 El M’Naouer Oran 31036 ALGERIE
2
Institut National des Télécommunications Evry- Paris
Tél. /Fax : 213 – 041 / 46 26 85
E.Mail : nim_hadj@yahoo.fr
Résume : petite entreprise qui veux se doter d’un moyen
La cryptologie, véritable science régissant le codage de software sécurisant ses données et qui n’est pas
l'information, a connu une réelle explosion avec le cher.
développement des systèmes informatiques, passant
2. Notion sur les Matrices
d'une ère artisanale et confidentielle à des systèmes de
très hautes technologies nécessitant une importante En mathématiques, les matrices servent à
puissance de calcul. Elle a connu un plus large essor interpréter en termes calculatoires et donc
encore avec l'arrivée des systèmes de communications opérationnels les résultats théoriques de
modernes (Internet, etc...) où il y a une nécessité l'algèbre linéaire et même de l'algèbre
absolue de protéger les données échangées bilinéaire. Toutes les disciplines étudiant des
des individus. phénomènes linéaires utilisent les matrices.
Quant aux phénomènes non linéaires, on en
Dans cette communication on essaye d’étudier Le
donne souvent des approximations linéaires
chiffre Lester S. Hill, ce chiffre regroupe deux thèmes
comme c'est le cas en optique géométrique
principaux : le calcul matriciel et le calcul modulo 26.
avec les approximations de Gauss.
Le contexte est celui des messages secrets. C'est un
sujet qui est très riche en applications mathématiques et 2.1 Matrice :
qui intéresse beaucoup les communications et le
Soient A un ensemble et (m,n) un couple
commerce électroniques.
d'entiers positifs. On appelle matrice à
Mots Clés : Cryptographie, Hill, Matrices, coefficients dans A, corps commutatif
Polygraphiques. quelconque, de dimension (ou taille) (m,n) ie à
m lignes et n colonnes, une famille (ai,j)
1. Introduction :
d'éléments de A indexée par le produit
Dans un contexte où les échanges d'information cartésien des ensembles de nombres entiers
dématérialisées se développent, il est indispensable de [1,m] et [1,n]. La matrice M pourra être notée
pouvoir bénéficier de systèmes sécurisés pour protéger par :
les données a caractère personnel ou confidentiel. Il est
donc, nécessaire d'avoir accès à des outils permettant
une meilleure protection contre les intrusions arbitraires
de la confidentialité des données. Le chiffrement est On représente généralement une matrice sous la
souvent le seul moyen efficace pour répondre à ces forme d'un tableau rectangulaire. Par exemple,
exigences. est représentée ci-dessous une matrice M, à
La cryptographie est l’ensemble des processus de coefficients entiers, et de dimension (3,4) :
verrouillage visant à protéger l’accès à certaines
données afin de les rendre incompréhensible aux
personnes non autorisées. Les technologies
cryptographiques sont ainsi reconnues comme étant des
outils essentiels de sécurité des données et de la Dans cette représentation, le premier
confiance dans les communications et le commerce coefficient de la dimension est le nombre de
électroniques. lignes, et le deuxième, le nombre de colonnes
Le chiffre de Hill que nous allons étudier afin de du tableau. Une matrice pour laquelle le
l’implémenter pour sécuriser les données a été publié nombre m de lignes est égal au nombre n de
par Lester S. Hill en 1929. C'est un chiffre colonnes sera dite matrice carrée de taille n.
polygraphique, c'est-à-dire qu'on ne (dé) chiffre pas les Une matrice ne comportant qu'une seule ligne
lettres les unes après les autres, mais par paquets. Nous et n colonnes est appelée matrice ligne de taille
étudierons la version bigraphique, c'est-à-dire que nous n. Une matrice ne comportant m lignes et une
grouperons les lettres deux par deux, mais on peut seule colonne est appelée matrice colonne de
imaginer des paquets plus grands. C'est une méthode de taille m.
chiffrement qui utilise des matrices carrées. Cet Pour repérer un coefficient d'une matrice, on
algorithme est, plus au moins, performant pour une indique son indice de ligne puis son indice de
colonne, les lignes se comptant du haut vers le bas et les
colonnes de la gauche vers la droite. Par exemple, on
notera ai,j, les coefficients de la matrice M, pour 1≤ i≤ 3
désignant le numéro de la ligne sur laquelle figure le
coefficient envisagé, et 1≤ j ≤ 4 désignant son numéro
de colonne ; ainsi a2,4=7. La disposition générale des Où detA est le déterminant de A, comA est la
coefficients d'une matrice M de taille (m,n) est donc la comatrice de A et tA est la matrice transposée
suivante : de A. Cette écriture permet un calcul aisé de
l'inverse d'une matrice de petite dimension.
Pour des matrices de plus grandes dimensions,
cette méthode essentiellement récursive devient
inefficace.
Pour effectuer certaines opérations, il peut être utile de
travailler sur le système des lignes ou des colonnes 2.2.3 Inversion des matrices 2 x 2
d'une matrice. On pourra alors l'écrire sous une des L'équation des cofacteurs ci-dessus permet de
formes suivantes : calculer l'inverse des matrices de dimensions
2x2 :
ou .
L'ensemble des matrices à coefficients dans A possédant
m lignes et n colonnes est noté Mm,n(A). Lorsque m=n det A = ad-bc ≠ 0
on note plus simplement Mn(A).Soit :
3. Chiffre de Hill
Lester Hill, mathématicien cryptographe (1891-
1961) publie en 1929 dans la revue American
On appelle transposée de A la matrice : Mathematical Monthly un article intitulé
Cryptography in an algebraic alphabet, où il
. détaille un nouveau type d'algorithme de
Remarquons que : chiffrement. Son idée n'est plus de coder lettres
par lettres, mais de coder simultanément des
. groupes de m lettres! Bien sûr, plus m est
Par exemple, avec la matrice M des exemples grand, plus les analyses statistiques deviennent
précédents, on a : difficiles!. Le chiffre de Hill est une méthode de
chiffrement qui utilise des matrices carrées. On
désigne par 2-chiffre de Hill, le chiffre obtenu
en codant les lettres par blocs de deux, par 3-
chiffre de Hill celui obtenu en codant les lettres
par blocs de trois, et ainsi de suite.
L'opération de transposition est involutive, c'est-à-dire
3.1 Chiffrement
que Dans une première phase, chaque lettre du texte à
2.2 Matrice inverse : chiffrer est remplacée par une valeur numérique,
celle de son rang dans l’alphabet, c'est-à-dire,
2.2.1 Méthodes d'inversion nous remplaçons chaque lettre par son ordre dans
Avant de décrire les méthodes usuelles d'inversion, l'alphabet : A devient 1, B devient 2,..., Z devient
notons qu'en pratique, il n'est pas nécessaire de calculer 26. On groupe les nombres ainsi obtenus par m
l'inverse d'une matrice pour résoudre un système (prenons par exemple m=2).
d'équations linéaires. Il est toutefois nécessaire que la Les lettres Pk et Pk+1 du texte clair seront chiffrés
matrice considérée soit inversible. Des méthodes de Ck et Ck+1 avec la formule ci-dessous:
décomposition comme la décomposition LU sont
beaucoup plus rapide que l'inversion.
2.2.2 Méthode des cofacteurs
L'inverse d'une matrice A s'écrit sous une forme très Ce qui signifie, pour fixer les idées, que les
simple à l'aide de la matrice complémentaire tcomA deux premières lettres du message clair (P1 et
P2) seront chiffrées (C1 et C2) selon les deux
équations suivantes:
a,b,c,d sont des entiers, C1 et C2 seront aussi des entiers.
Cette matrice doit être l'inverse de matrice de
Le choix de la clé correspond ici au choix d'un nombre
chiffrement (modulo 26). Ordinairement
m, et au choix des combinaisons linéaires à effectuer (ce
sont toujours les mêmes de blocs en blocs).
l'inverse de la matrice est:
Remarque
a b c d e f g
1 2 3 4 5 6 7
h i j k l m n Mais que cela signifie-t-il dans le contexte Z26?
8 9 10 11 12 13 14 Reprenons notre exemple.
o p q r s t u
15 16 17 18 19 20 21 3.4 Exemple de déchiffrement
v w x y z Pour déchiffrer le message qu’on a envoyé par
22 23 24 25 0 la clef P1 doit calculer :
La valeur 0 est attribuée à la lettre Z afin de travailler
modulo 26. Cependant, d'autres auteurs posent "A"=0,
"B"=1, ..., "Z"=25. Les deux conventions se défendent.
L'essentiel est que les protagonistes se mettent d'accord
Comme pgdc(43,26)=1, (43)-1 existe dans Z26 et
avant d'échanger des messages. On pourrait même
(43)-1 égale 23. Le récepteur a donc maintenant la
imaginer de prendre un alphabet désordonné, par
matrice de déchiffrement:
exemple "A"=15, "B"=6, etc., ce qui constituerait un
surchiffrement.
3.2 Exemples de chiffrement
1) On souhaite coder le message "je vous aime" en
Il prend donc la matrice pour déchiffrer
prenant comme clef de cryptage la matrice P1= . le message "FGXGE DSPGV". Après avoir
Après avoir remplacé les lettres par leur rang dans remplacé les lettres par leur rang dans l'alphabet
l'alphabet (a=1, b=2, etc.), elle obtiendra: (A=1, B=2, etc.), il obtiendra:
Elle fera de même avec les 3e et 4e lettres, 5e et 6e, etc. Il fera de même avec les 3e et 4e lettres, 5e et 6e,
Elle obtiendra finalement: etc. Il obtiendra finalement:
Lettres j e v o u s a i m e Lettres
F G X G E D S P G V
chiffrées
Rangs (Pk) 10 5 22 15 21 19 1 9 13 5
Rangs
Rangs
6 7 24 7 5 4 19 16 7 22 chiffrés 6 7 24 7 5 4 19 16 7 22
chiffrés (Ck)
(Ck)
Lettres
F G X G E D S P G V Rangs
chiffrées 10 5 22 15 21 19 1 9 13 5
(Pk)
Lettres j e v o u s a i m e
2) Soit la matriceP2= , si on veut crypter le 3.5 Chiffre de Hill avec des mathématiques
message "Rendez-vous ce soir", on obtient le
cryptogramme : "UDZBI WLOSR VSSAY STAIE Le chiffre de Hill est à l'intersection de
AM" l'arithmétique et de l'algèbre linéaire. En
remplaçant les lettres par des nombres (A--
3.3 Déchiffrement : >0,...), on ne traite plus que des entiers compris
Pour déchiffrer, le principe est le même que pour le entre 0 et 25. En outre, un nombre n est identifié
chiffrement: on prend les lettres deux par deux, puis on avec tous les nombres n+26k, où k est un entier
les multiplie par une matrice. (en clair, si 1 représente B, 27,53,-25... aussi!).
Quand les calculs faits par les combinaisons linéaires être des nombres entiers positifs. Il faut aussi
sortent des entiers de 0 à 25, on s'y ramène en prenant le qu'elle ait une matrice inverse dans Z26.
reste dans la division par 26. On dit que l'on travaille dans
Z|26Z.
existe si (ad-bc)-1 (mod
Chaque groupe de 2 lettres, ou par identification de 2 26) existe. Or (ad-bc)-1 (mod 26) existe si (ad-
nombres x1-x2, est représenté par un vecteur bc) et 26 sont premiers entre eux. Il faut donc
contrôler que (ad-bc) est impair et n'est pas
colonne . Les relations de dépendance linéaire multiple de 13 (voir à ce sujet le chiffre
sont, comme souvent, représentés par une affine).
Exemple : Soit k=43. Trouvons k-1 (mod 26).
matrice . On a, dans Z|26Z, la relation 43·1 (mod 26) = 43 (mod 26) Donc 1 n'est pas le nombre
= 17 (mod 26). cherché.
43·3 (mod 26) = 129 (mod 26) Donc 3 n'est pas le nombre
= 25 (mod 26). cherché.
43·5 (mod 26) = 215 (mod 26) Donc 5 n'est pas le nombre
= 7 (mod 26). cherché.
43·7 (mod 26) = 301 (mod 26) Donc 7 n'est pas le nombre
= 15 (mod 26). cherché.
où est le bloc codé, et est le bloc clair.
43·9 (mod 26) = 387 (mod 26) Donc 9 n'est pas le nombre
3.6 Réversibilité : = 23 (mod 26). cherché.
43·11 (mod 26) = 473 (mod Donc 11 n'est pas le
Toute matrice de chiffrement ne convient pas! Par 26) = 5 (mod 26). nombre cherché.
exemple, si on prend la matrice A suivante: 43·15 (mod 26) = 645 (mod Donc 15 n'est pas le
26) = 21 (mod 26). nombre cherché.
43·17 (mod 26) = 731 (mod Donc 17 n'est pas le
26) = 3 (mod 26). nombre cherché.
43·19 (mod 26) = 817 (mod Donc 19 n'est pas le
26) = 11 (mod 26). nombre cherché.
Elle n'est pas une bonne matrice de chiffrement, car par 43·21 (mod 26) = 903 (mod Donc 21 n'est pas le
exemple, 26) = 19 (mod 26). nombre cherché.
43·23 (mod 26) = 989 (mod Donc 23 est le nombre
26) = 1 (mod 26). cherché. STOP.
La table suivante donne les inverse modulo 26:
(Où on a ramené les calculs dans Z|26Z). Ainsi, deux 1 3 5 7 9 11 15 17 19 21 23 25
vecteurs (ou encore deux couples de deux lettres) 1 9 21 15 3 19 7 23 11 5 17 25
différents sont codés de la même façon. Il est donc
3.7 Cas d’image
impossible, même en connaissant la clé, de décrypter.
Nous avons pris comme exemple une image
Pour que le processus soit inversible, il est nécessaire et
paysage bitmap [256*256] pixels et nous avons
suffisant que A soit inversible, mais attention, inversible
crypté cette image par les deux clés de
dans Z|26Z. On montre que cela est vérifié si, et
chiffrement P1 et P2, voici les résultats
seulement si, det A=ad-bc est inversible dans Z|26Z
obtenus :
(c'est-à-dire qu'il existe k un entier tel que k×det
A=1+26n, où n est un entier - cela est équivalent à dire
que det A est premier avec 26). Dans ce cas, l'inverse
est donné par :
On décrypte en utilisant le même procédé, mais en
utilisant A-1.
Il est facile de montrer que A est régulière dans Z26 si
son déterminant D est inversible modulo 26 (i.e. D et Image originale
26 sont premiers entre eux). Le calcul de A–1 s’effectue
selon les règles usuelles en travaillant dans Z26 .
On ne peut pas prendre n'importe quoi comme matrice
de chiffrement. Ses composantes doivent tout d'abord
droite A=BC-1. On s'empresse de calculer le
déterminant de C : il vaut -110, qui n'est pas
premier avec 26. C n'est pas inversible dans
Z|26Z. C'est raté! On recommence avec les
deuxième et troisième paires :
qu'on écrit en D=AE. Le déterminant de E vaut
Image cryptée par le P1
145, il est premier avec 26, et E est inversible
dans Z|26Z. On obtient alors :
On peut vérifier la matrice de chiffrement sur
les autres paires.
3.9 Autre exemple : décryptement d'un
chiffre de Hill (2x2)
Image cryptée par P2 Le chiffre de Hill est sensible aux attaques de
type texte clair connu. Nous allons décrypter le
Les images cryptées ont la même taille que l’image message ci-dessous, sachant qu'il contient le
claire. nom GEORGE PAPANDREOU:
3.8. Attaque à texte clair connu : chiffrement de Hill CMYPZ GTAYO EQBYQ JLAOW INELN
NECNN UESZT YTFRU OWYXH KYADM
Lorsque l'on cherche à déterminer la clé de chiffrement NJRUK CUFZP YPNNM XWSQQ OJMGO
d'un adversaire, on peut se situer à plusieurs niveaux JZQZQ FLVAY XGIPR OPUFJ WTSVA ATQU
d'information. On peut n'avoir à sa disposition que le
message chiffré. Parfois, et cela apporte beaucoup Remarquons tout d'abord que "GEORGE
d'informations, on dispose à la fois du message chiffré PAPANDREOU" contient des répétitions de
et de sa traduction en clair, ou au moins une partie de bigrammes à des intervalles pairs:
celle-ci. Cela n'est pas si saugrenu : bien des messages 1. GEORGE PAPANDREOU
protocolaires (et dans l'armée, les protocoles...) 2. GEORGE PAPANDREOU
comportent le même début ou la même fin, et c'est ainsi
par exemple que Türing a procédé pour la machine On retrouvera ces répétitions de bigrammes
Enigma. C'est ce que l'on appelle l'attaque à texte clair dans le texte chiffré si le rang de la première
connu! lettre du bigramme est impair. Avec GEORGE
PAPANDREOU, on est sûr de retrouver soit
Voyons un exemple à partir du chiffrement de Hill GE...GE et PAPA, soit EO...EO, car soit c'est
(cette méthode s'applique à tout algorithme fonctionnant G qui est de rang impair soit c'est E.
à partir de combinaisons linéaires). On suppose qu'on a
le texte codé suivant : COR ZZETMDW...., qui On remarque dans le cryptogramme le segment
correspond au début de MON GENERAL... Un espion ZQZQ qui pourrait correspondre à PAPA; le
dans les bases ennemies nous a permis de savoir que premier Z de ce bigramme est la 77ème lettre
nos adversaires utilisent le chiffre de Hill, avec une du cryptogramme. Essayons cette
longueur de clé égale à 2. On note A la matrice 2×2 de correspondance (tableau de correspondance) :
chiffrement à coefficients dans Z|26Z. La première Cela semble coïncider parfaitement. Si notre
paire CO s'obtient en appliquant la matrice A à partir de hypothèse est exacte, alors, après avoir
la paire MO, la seconde paire RZ s'obtient en appliquant remplacé les lettres par leur rang dans
la matrice A à partir de la paire NG. Cela se traduit l'alphabet (a=1, b=2, ..., y=25, z=0), le couple
matriciellement par la relation : chiffré (15;10) a été obtenu à partir du couple
clair (7;5), (13;7) à partir de (15;18), (0;17) à
partir de (16;1), etc. Il s'agit maintenant de
trouver la matrice de déchiffrement (D) à partir
de ces couples.
que nous écrivons sous la forme B=AC. Si la matrice C
est inversible dans Z|26Z, on obtient en multipliant à
Chiffré OJ MG OJ ZQ ZQ FL VA YX chiffrage d’information de type synchrone
Couples
(parole, images animées, …). Le chiffre de Hill
(15;10) (13;7) (15;10) (0;17) (0;17) (6;12) (22;1) (25;24) fait partie de cette catégorie d’algorithme en
chiffrés
Couples
bloc.
(7;5) (15;18) (7;5) (16;1) (16;1) (14;4) (18;5) (15;21)
clairs
Pour rendre le chiffre de Hill plus difficile à
Clair GE OR GE PA PA ND RE OU casser, on peut penser aux améliorations
suivantes:
Tableau de correspondance)
Transposer les lettres avant de les
Dans notre tableau, prenons les premiers et les
chiffrer.
quatrièmes couples chiffrés et formons une matrice (A)
en disposant verticalement ces valeurs. Prenons les Modifier les nombres associés aux
premiers et les quatrièmes couples clairs de notre lettres. Par exemple, au lieu de dire "A"=1,
tableau pour former une matrice (B). On aurait pu "B"=2, etc., on pourrait dire "A"=12, "B"=5,
choisir n'importe quel couple de colonnes du tableau etc. Cela revient en fait à surchiffrer le chiffre
pourvu que la matrice A formée soit inversible modulo de Hill avec un alphabet désordonné.
26.
Agrandir la taille de la matrice de
On obtient l'équation matricielle: chiffrement. On peut utiliser des matrices 3x3,
4x4, 5x5, etc. La seule limitation est d'ordre
DA=B
pratique: plus les matrices sont grandes, plus le
Dans notre exemple, on a:
temps de calcul est élevé, et plus le risque
d'erreur augmente.
5. Bibliographies
-1
Pour trouver D, il faut calculer A , puis multiplier à [1] Bruce Schneir, "Applied Cryptography,
droite les deux termes de l'équation avec A-1 (tant que A Protocols, Algorithms, and source Code in C" ,
n'est pas inversible modulo 26, il faut essayer d'autres edition John Wiley & Sons Inc., 1994.
matrices A et B):
[2] Beckett Brian :’’ Introduction aux méthodes
D A A-1 = B A-1, d'où D = B A-1 de la cryptologie’’, Editions Masson, 1990.
A est inversible modulo 26: [3] Gilles Zémor, «Cours de Cryptographie»,
CASSINI, 2000.
[4] Didier Müller, « Une application
d’où intéressante des matrices : le chiffre de Hill « ,
Article paru dans le bulletin No 90 de la
SSPMP (www.vsmp.ch), octobre 2002.
[5] http://www.apprendre-en-ligne.net/crypto/
rabin/euclide.html
On obtient alors facilement le message [6] Eastaway R. et Wyndham J., Pourquoi les
décrypté: bus arrivent-il toujours par trois ? Flammarion,
IT IS BELIEVED BY MANY GREEKS THAT THE HEAD 2001, pp. 95-107
OF THE GROUP CALLED THE SHIELD IS THE SON OF
[7] Hill Lester S., « Cryptography in an
GEORGE PAPANDREOU EX PREMIER OF GREECE (T).
Algebraic Alphabet », American Mathematical
4. Conclusion Monthly, 36, 1929, pp. 306-312
On peut classer les algorithmes cryptographiques en [8] Lewand Robert Edward, Cryptological
deux grandes familles. Certains opèrent sur le message Mathematics, published by The Mathematical
en clairs par groupes de bits (blocs). Et d’autres opèrent Association of America, 2000, pp. 124-140
sur le message en clair un bit à la fois (continue).
[9] Stinson Douglas, Cryptographie, Théorie et
Les algorithmes de bloc sont souvent coûteux en termes pratique, Vuibert, 2001, pp. 12-16
de temps de calcul, et ne permettent que malaisément le