[PDF] Chapitre 7 : Cryptographie classique

View - Download Chapitre 7 : Cryptographie classique

Previous PDF

Next PDF

Chapitre 7 : Cryptographie classique

SÉcurité et Cryptographie

2013-2014

Sup Galilée INFO3

1/61

Introduction

L"objectif fondamental de la cryptographie est de permettre à deux personnes, traditionnellement appelées Alice et Bob, de communiquer au travers d"un canal peu sûr de telle sorte qu"un opposant, Oscar, ne puisse

comprendre ce qui est échangé.Le canal peut être par exemple une ligne de téléphone, Internet, ou autre.

L"information qu"Alice souhaite transmettre à Bob, que l"on appelle texte (ou message clair , peut être un texte écrit en français ou encore des

données numériques.Alice transforme le texte clair par un procédé de chiffrement, en utilisant

une clef prédéterminée, et envoie le texte (ou message chiffré (ou enco re cryptogramme ) au travers du canal.Oscar, qui espionne éventuellement le canal, ne peut retrouver le texte clair, mais Bob, qui connaît la clef pour déchiffrer, peut récupére le message clair à partir du cryptogramme. 2/61

Définition formelle

Un p rocédé (ou système ou algo rithme de chiffrement (ou cryptosystème

est un quintupletA= (P;C;K;E;D)oùPest un ensemble fini de blocs de textes clairs possibles,Cest un ensemble fini de blocs de textes chiffrés possibles,Kest un ensemble fini declefs p ossibles,Eest unefonction de chiffrement ,E:P K ! C,Dest unefonction de déchiffrement D:C K ! P,Pour chaque clefK, il existe au moins une clefK0telle que pour tout

x2 P,

D(E(x;K);K0) =x:

3/61

Définition formelle

La dernière propriété est fondamentale.Elle précise que si un texte clairx est chiffré en un cryptogrammeyavecK, alors il existe une clefK0telle

queydéchiffré avecK0redonnex.En termes mathématiques, cela signifie que pour toutK, l"application

E(;K):P ! Cest injective, et queD(;K0):C ! Pest surjective.Remarquons que les ensemblesPetCsont supposésfinis donc, dans le cas

oùjPj=jCj, les fonctionsE(;K)etD(;K0)sont en faitbijectives ,et inverses l"une de l"autre p ourtoute clef K.4/61 Supposons qu"Alice souhaite transmettre un message à Bob, ce message

étant une suite

x=x1x2xn où chaquexiest un élément deP, en utilisant une clefK.Alors chaquexi est chiffré avecK.Ainsi Alice calculeyi=E(xi;K),i=1;;n,et transmet à Bob la suite y=y1yn:Si Bob connaîtK0, alors il peut déchiffrer le message.Pour ce faire, il calcule pour chaquei=1;;n,D(yi;K0)=D(E(xi;K);K0)=xiet récupère doncx.5/61 Le chiffrement par décalage : arithmétique modulaire Avant d"introduire ce cryptosystème, commençons par la description de l" arithmétique modulaire .Définition Sia;betmsont des entiers, avecm>0, on écritab(modm), et on dit queaest congru àbmodulom, simdiviseab.L"entiermest parfois appelé le mo dulus .Remarquons immédiatement que sim=1, alors pour tousa;b,ab modm.Supposons que l"on diviseaetbparm(division entière).On obtient alors a=q1m+r1etb=q2m+r2(avec les restesr1;r2satisfaisant

0r1;r2m1).Il est alors facile de voir queab(modm)si, et

seulement si ,r1=r2.Dans la suite, le reste d"un entieramodulomsera notéamodm(sans les parenthèses).Il en résulte que l"on aab (modm)si, et seulement si,amodm=bmodm.Si on remplaceapar amodm, on dit que l"onréduit amodulom.6/61 On est maintenant en mesure de définir l"arithmétique modulom:Z=mZ

désigne l"ensemblef0;;mgmuni de deux opérations+et.L"addition et la multiplication dansZ=mZfonctionnent comme l"addition

et la multiplication usuelles, excepté le fait que tous les résultats sont

réduits modulom.Supposons par exemple que l"on veuille calculer 1113 dansZ=16Z.Comme entiers ordinaires, on a 1113=143.Pour réduire 143 modulo

16, on effectue une division euclidienne (ou entière) : 143=816+15,et donc 143 mod 16=15,de sorte que 1113=15 dansZ=16Z.7/61

Propriétés de+

Avec ces définitions, l"addition et de la multiplication dansZ=mZsatisfont la plupart des règles familières en arithmétique.On rappelle la liste de ces

propriétés sans les démontrer :L"addition estinterne : sia;b2Z=mZ, alorsa+b2Z=mZ.L"addition estcommutative : sia;b2Z=mZ, alorsa+b=b+a.L"addition estasso ciative: sia;b;c2Z=mZ, alors

(a+b) +c=a+ (b+c).0 estneutre p ourl"addition : sia2Z=mZ, alors 0+a=a=a+0.Chaque élémenta2Z=mZadmet unopp oséc"est-à-dire un élément

a(unique) tel que(a) +a=0=a+ (a).Notons que pour touta2Z=mZ,a6=0,a=ma.(En effet, a+ (ma) =0.)Évidemment,0=0.8/61

Propriétés deLa multiplication estinterne : sia;b2Z=mZ, alorsab2Z=mZ.La multiplication estcommutative : sia;b2Z=mZ, alors

ab=ba.La multiplication estasso ciative: sia;b;c2Z=mZ, alors (ab)c=a(bc).1 estneutre p ourLa multiplication : sia2Z=mZ, alors

1a=a=a1.La multiplication estdistributive sur l"addition : sia;b;c2Z=mZ,

alorsa(b+c) =ab+ac.Les propriétés de+font deZ=mZungroup eab élien,celles defont de Z=mZunmonoïde commutatif ,et la totalité de ces propriétés en fait un anneau commutatif 9/61 Puisque les opposés existent dansZ=mZ, on peut également réaliser des soustractions

.Poura;b2Z=mZ,ab=a+ (b).On obtientabcomme suit :On calculeabcomme des entiers usuels,puis on réduit modulom.Exemple : Calculer 1118 dansZ=31Z(de deux façons différentes).On

peut calculer18 dansZ=31Z, soit18=13,puis calculer 11+13 modm,soit 24.On peut aussi calculer directement 1118=7,puis réduire7 modulo 31,soit 317=24.10/61

Chiffrement par décalage

Il est défini par les données suivantes :P=C=K=Z=26Z.Pour 0K25 et 0x25, on définitE(x;K) =x+Kmod 26

et

D(x;K) =yKmod 26:Remarque

LorsqueK=3, le système par décalage s"appelle lechiffrement de Césa r car il était utilisé par un certain Caius Iulius Caesar IV (-100 à -44). 11/61 On peut utiliser le chiffrement par décalage pour chiffrer un texte ordinaire en décidant d"une correspondance entre les caractères alphabétiques et les résidus modulo 26 comme donné dans la table suivante : A B C D E F G H I J K L M0 1 2 3 4 5 6 7 8 9 10 11 12 N O P Q R S T U V W X Y Z13 14 15 16 17 18 19 20 21 22 23 24 25 12/61

Exercice

Déchiffrer le message suivant en utilisant la clefK=11.

HPHTWWXPPELEXTOYTRSE

13/61 Pour qu"un système de chiffrement soit utilisable en pratique, il doit

satisfaire certaines propriétés :La fonction de chiffrementEet la fonction de déchiffrementD

doivent être calculables efficacement .Un opposant observant le texte chiffréydoit être incapable de

déterminer ni la clefKutilisée, ni le texte clairx.La seconde propriété définit de manière informelle la notion de "sécurité".

L"opération consistant à rechercher la clefKà partir du texte chiffréyest appelée cryptanalyse .On observe que si Oscar peut retrouverK, alors il peut retrouverxcomme le fait Bob en utilisantD.Donc retrouver la clef

Kest au moins aussi difficile que de retrouver le texte clair.On remarque que le chiffrement par décalage n"est pas sûr, car il peut être

cryptanalysé pa rla métho dede recherche exhaustive ou fo rceb rute .Comme il n"y a que 26 clefs possibles, essayer le déchiffrement avec toutes les clefs jusqu"à trouver un texte clair compréhensible est aisé. 14/61

Exercice

Déchiffrer le message (chiffré avec le système par décalage) par force brute. JBCRCLQRWCRVNBJENBWRWN.Solution :clef=9 et message="A stitch in time saves nine" ("Un point à temps en vaut cent" autrement dit l"entretien consciencieux permet d"éviter le gaspillage). 15/61

Chiffrement par substitution

Un autre procédé de chiffrement bien connu est le chiffrement pa r substitution .Il est défini comme suit :P=C=A, oùAdésigne l"alphabet des 26 lettres usuelles.L"ensemble des clefsKest l"ensembleSAdes permutations de A.Rappelons ici qu"une permutation sur un ensembleX est une bijection deXsur lui-même.Pour chaque permutation2SA, on définit

E(;) =()et

D(;) =1()

pour2A.16/61

Exercice

Soit la clef suivante :

A B C D E F G H I J K L MX N Y A H P O G Z Q W B T N O P Q R S T U V W X Y ZS F L R C V M U E K J D I Chiffrer le message suivant "On ne peut rien apprendre aux gens. On peut seulement les aider à découvrir qu"ils possèdent déjà en eux tout ce qui est à apprendre" (Galilée).Déchiffrer le message suivant

"MGZVYZLGHCMHJMYXSSFMNHAHYCDLMHA".Quel est le nombre total de clefs possibles dans le chiffrement par

substitution ?(26!) 17/61

Chiffrement affine

Le chiffrement par décalage est un cas particulier du chiffrement par substitution (qui n"utilise que 26 des 26! clefs possibles) dans la mesure où l"on peut voir le premier comme un système de chiffrement sur l"alphabetA (des 26 lettres usuelles, par un codage des lettres en des nombres) et que

chaque fonction de chiffrement/déchiffrement est une permutation.Un autre cas particulier du chiffrement par substitution est lechiffrement

affine .Dans ce procédé, on limite les fonctions de chiffrement à celles de la forme

E(x;K) =ax+bmod 26

oùa;b2Z=26ZetK= (a;b).Les fonctions de la formeE(;K)sont appelées desfonctions affines (pa r analogie avec les droites affines de la géométrie du plan réel).Observons que l"on retrouve le chiffrement par décalage poura=1.18/61 Pour que l"opération de chiffrement soit possible, il est nécessaire que la fonction affine soit injective donc bijective.Autrement dit, pour chaque y2Z=26Z, l"équation ax+by(mod 26) doit avoir une unique solutionx(poura;bfixés).Cette équation est équivalente àaxyb(mod 26).Lorsqueyparcourt l"ensembleZ=26Z, ybparcourt égalementZ=26Z(puisquey7!ybest une bijection).Il suffit donc d"étudier l"équationaxy(mod 26)pour chaquey2Z=26Z.19/61 Solutions de l"équationaxy(mod 26)Théorème Pour chaquey2Z=26Z, l"équationaxy(mod 26)admet une unique solution si, et seulement si,pgcd(a;26) =1.Preuve :Supposons pour commencer quepgcd(a;26) =d>1.Alors l"équationax0(mod 26)admet au moins deux solutions distinctes dans Z=26Z,à savoirx=0 etx=26=d.La fonctionE(;(a;0)):x7!ax mod 26 n"est donc pas injective.Supposons maintenant quepgcd(a;26) =1. Soientx1;x2tels que ax

1ax2(mod 26).Alorsa(x1x2)0(mod 26)et donc 26 divise

a(x1x2).On utilise une propriété de la division : sipgcd(a;b) =1 et sia divisebc, alorsadivisec.Comme 26 divisea(x1x2)etpgcd(a;26) =1, il en résulte que 26 divisex1x2,de sorte quex1x2(mod 26).On vient de montrer que sipgcd(a;26) =1, alors l"équationaxy(mod 26) admet au plus une solution dansZ=26Z.Donc quand on fait varierxdans Z=26Z,ax(mod 26)ne peut pas prendre deux fois la même valeurs, et donc parcourt égalementZ=26Z.Donc, pour chaquey2Z=26Z, l"équationaxy(mod 26)admet une solution unique.20/61

Remarque

Le résultat précédent reste vrai si 26 est remplacé par un entierm>0 quelconque.Soita2Z=mZ.Sipgcd(a;m) =1, alors il existe en particulier une unique solution à l"équationax1(modm).Dans ce cas on dit queaest inversible modulom.21/61

Exercice

Calculerpgcd(4;26).(=2).Trouver un entiern2Z=26Ztel queE(x;(4;0)) =E(x+n;(4;0)) pour toutx2Z=26Z.(n=13).Donner la liste des élémentsxdeZ=26Ztels que pgcd(x;26) =1.(Puisque 26=213, les élémentsxtels que

pgcd(x;26) =1 sont 1;3;5;9;11;15;17;19;21;23;25.)Soientmun entier>0 eta2Z=mZ. Montrer que siaest inversible

modulom, alorspgcd(a;m) =1.(L"équationaxy(mod 26) admet une unique solution !)En déduire queaest inversible modulo

msi, et seulement si,pgcd(a;m) =1.Expliquer pourquoi tout élémentx2Z=mZ, qui est un entier premier,

est nécessairement inversible modulom.22/61 Comme 26=213, les valeursadeZ=26Ztelles quepgcd(x;26) =1 sont 1;3;5;9;11;15;17;19;21;23;25.Le paramètre peut quant à lui être quelconque dansZ=26Z.Le chiffrement affine admet donc 1226=312

clefs possibles, ce qui est évidemment trop petit pour être sûr.Considérons maintenant le cas général où le modulus estm>0.On

utiliser une définition issue de la théorie des nombres.Définition Soient des entiersa1 etm2.Sipgcd(a;m) =1, on dit queaetm sont p remiersentre eux .Le nombre d"entiers deZ=mZqui sont premiers avecmest noté(m),etest appelé lafonction indicatrice d"Euler .23/61 Un résultat bien connu de la théorie des nombres donne la valeur de(m)

à partir de sa décomposition en puissances de facteurs premiers.(Rappelons ici qu"un entierp>0 est ditp remiers"il est distinct de 1, et

n"est divisible que 1 et par lui-même.Tout entierm>1 sefacto riseen produit de puissances de nombres premiers de manière unique, à l"ordre

près des facteurs.Par exemple, 60=2235 et 98=272.)On rappelle la formule de(m)dans le théorème suivant (non démontré

ici).Définition

Supposons quem=Qn

i=1peiioù lespisont des nombres premiers deux-à-deux distincts, et lesei>0 pour 1im. On a (m) =Qn i=1(peiipei1 i).24/61 Si on considère le chiffrement affine surZ=mZ(le même que celui que l"on a vu en remplaçant 26 parm), alors le nombre de clefs estm(m).(Dans la fonction de chiffrementE(;(a;b)),mcompte le nombre deb possibles, et(m)le nombre deapossibles.)Par exemple, si m=60=2235,(60) = (222)(31)(51) =224=16, et

le nombre total des clefs est 1660=960.Considérons maintenant la fonction de déchiffrement dans le chiffrement

affine avecm=26.Supposons quepgcd(a;26) =1.Pour déchiffrer on a besoin de résoudreyax+b(mod 26)pour chaquex.Le raisonnement précédent donne l"existence d"une unique solution (carpgcd(a;b) =1) mais ne nous donne pas de moyen de la calculer (et encore moins pour la calculer de façon efficace).On utilise maintenant la notion d"inverse.

Définition

Soita2Z=mZ. L"inversede aest un élémenta12Z=mZtel que aa

11(modm).25/61

Par des arguments semblables à ceux déjà utilisés, on peut montrer quea

admet un inverse modulomsi, et seulement si,pgcd(a;m) =1.Si un inverse existe, alors il est unique.(Supposons queaadmette deux

inversesxety, alorsy(xa)y=xay=x(ay)x(modm).)Et si a=b1, alorsb=a1.(On aba=bb1=1, doncb=a1par unicité de l"inverse dea.)On remarque que simest un entierp remierp, alors tous les élémentsnon nuls de Z=pZadmettent un inverse.On dit dans ce cas queZ=pZest un corps .Nous ne connaissons pas (encore) d"algorithme efficace pour le calcul des inverses.Par exemple, pour trouver l"inverse de 7 modulo 26 il faut résoudre 7x1(mod 26),soit trouver deux entiersxetq, 1x25, tels que 7x=q26+1.Dans ce casx=71.En testant on trouve

715=1051(mod 26), de sorte que 15=71.Il en résulte

immédiatement que 15

1=7.26/61

L"équationax+by(mod 26)est équivalente àaxyb(mod 26).Commepgcd(a;26) =1,aadmet un inverse modulo 26.En multipliant les

deux membres de l"équation para1, on obtienta1(ax)a1(yb) (mod 26).Par associativité de la multiplication dansZ=26Z, le membre de gauche devienta1(ax)(a1a)x1xx(mod 26).En conséquence de quoi,xa1(yb) (mod 26).Le procédé de chiffrement affine est donc défini comme suit : P=C=Z=26Z, etK=f(a;b)2Z=26ZZ=26Z:pgcd(a;26) =1g.PourK= (a;b)2 K, on définit :

E(x;(a;b)) =ax+bmod 26

et

D(y;(a;b)) =a1(yb)mod 26

pourx;y2Z=26Z.27/61

Exemple d"utilisation

Supposons queK= (7;3).Rappelons que 7

1mod 26=15.La fonction

de chiffrement est

E(x;K) =7x+3

et celle de déchiffrement estD(y;K) =15(y3) =15y19.Vérifions queD(E(x;K);K) =xpour toutx2Z=26Z.On a

D(E(x;K);K) =D(7x+3;K)

=15(7x+3)19 =x+4519 =x:(1)Chiffrer le motaffineavec la même clefK= (7;3)(le résultat doit être donné sous la forme d"un message formé avec des lettres).On convertit tout d"abord les lettres en nombres (0$a, 1$b, ...),puis on calcule E(x;(7;3))pour chacun des nombresxobtenus.Cela donne une suite de 6 nombres que l"on re-transforme en lettre (en utilisant le même codage en sens inverse). 28/61

Chiffrement de Vigenère

Dans le cas du chiffrement par décalage ou par substitution, dès qu"une clef est fixée, chaque caractère alphabétique, partout où il apparaît dans le texte, est transformé en un même caractère.Autrement dit, pour toute lettre, chaque occurrence dedans le texte clair est transformée en E(;K)(pour être précis il faudrait remplacerdans le chiffrement par son codage en un nombre...).Pour cette raison, le procédé est dit monoalphabétique .On présente maintenant un chiffrement qui n"est pas monoalphabétique : le chiffrement de Vigenère .Soitmun entier strictement positif.SoitP=C=K= (Z=26Z)m.Pour toute clefK= (k1;;km)(oùki2Z=26Zpour chaquei=1;;m),on définit

E(x1;x2;;xm;K) = (x1+k1;x2+k2;;xm+km)

et

D(y1;y2;;ym;K) = (y1k1;y2k2;;ymkm)

où les opérations sont effectuées dansZ=26Z.29/61 En utilisant la correspondance 0$a, 1$b, ..., 25$z, on décrit chaque clefKdu chiffrement de Vigenère par une chaîne de caractères de longueur

mappeléemot-clef .Le chiffrement de Vigenère traitemcaractères alphabétiques à la fois:

chaque bloc du texte clair est équivalent àmcaractères alphabétiques.30/61

Exercice

Déchiffrer le texte suivant (chiffré avec la méthode de Vigenère et le mot-clef "CIPHER") : VPXZGIAXIVWPUBTTMJPWIZITWZT.Solution :La clef correspondant au mot-clef est(2;8;15;7;4;17). Et le texte déchiffré est

THISCRYPTOSYSTEMISNOTSECURE.

31/61
Quel est le nombre de clefs possibles dans le chiffrement de Vigenère ? 26
m.Déjà pourm=5, cela représente plus de dix millions de possibilités (11 881 673). C"est donc assez grand pour exclure une recherche

exhaustive "à la main" (mais pas avec un ordinateur).Dans le chiffrement de Vigenère avec un mot-clef de longueurm, un

caractère alphabétique peut être transformé enmcaractères différents (au plus), si on suppose que le mot-clef contientmcaractères deux-à-deux distincts.Un tel procédé est ditp olyalphabétique.En général, la cryptanalyse est plus difficile dans de tels systèmes. 32/61

Chiffrement de Hill

On décrit maintenant un autre système cryptographique polyalphabétique appelé chiffrement de Hill .Soitmun entier strictement positif, et soit P=C= (Z=26Z)m.L"idée consiste à transformermcaractères d"un bloc de texte clair enmcaractères d"un bloc de texte chiffré par des combinaisons linéaires .Sim=2, alors pour un bloc de texte clairx= (x1;x2), on obtient un bloc de texte chiffréy= (y1;y2)oùy1ety2sont obtenus comme combinaisons linéaires dex1etx2.Par exemple,y1=11x1+3x2,y2=8x1+7x2.

(L"addition et la multiplication sont réalisées dansZ=26Z.)On peut bien entend écrire cela en sous la forme d"un produit matriciel :

(y1;y2) = (x1;x2)11 8 3 7 33/61
En général, on prend une matrice carrée de taillemmpour clefK.Si le coefficient(i;j)de la matrice estki;j, on écritK= (ki;j).Pour x= (x1;;xm)2 P, etK2 K, on calculey=E(x;K) = (y1;;ym) ainsi(y1;;ym) = (x1;;xm)0 B @k

1;1k1;m

k m;1km;m1 C

A:C"est-à-dire que l"on calculey=xK.On dit que le texte chiffré est obtenu par unetransfo rmationlinéaire .Pour

voir comment le procédé de chiffrement fonctionne, on doit trouver comment calculerxà partir dey.Si vous vous souvenez de vos cours

d"algèbres linéaires, alors vous savez que l"on utilise la matrice inverseK1.En effet, le texte clair est calculé par la formulex=yK1.34/61

Un bref rappel d"algèbre linéaire élémentaire SiA= (ai;k)est une matrice de taillem`etB= (bk;j)est une matrice de taille`n, alors on définit lep roduitmatriciel AB= (ci;j)par la formule c i;j=`X k=1a i;kbk;j

pour 1im, 1jn.AinsiABest une matrice de taillemn.Ce produit matriciel est associatif (c"est-à-dire(AB)C=A(BC), avecAde

taillem`,Bde taille`netCde taillenp; le résultat étant de taille mp), mais n"est pas commutatif en général (on a rarementAB=BA).35/61 Lamatrice identité Im= (ai;j)de taillemmest constituée de uns sur sa

diagonale (ai;i=1) et de zéros partout ailleurs (ai;j=1 pour tousi6=j).Par exemple pourm=3, on aI3=0

@1 0 0 0 1 0

0 0 11

A :Cette matriceIms"appelle matrice identité car elle satisfaitAIm=Aet I mB=Bpour toutes matricesAde taille`m,`quelconque, etBde taillemk,kquelconque.Lamatrice inverse d"une matrice Acarrée de taillemmest (lorsqu"elle existe) une matrice notéeA1telle queAA1=Im=A1A.Certaines

matrices ne possèdent pas d"inverse, mais si l"inverse existe, il est unique.L"inverse deImestIm.SiA=B1, alorsB=A1.36/61

Retour un instant au chiffrement de Hill

Si la clefKchoisie est une matrice inversible, alors il est facile de trouver laquotesdbs_dbs31.pdfusesText_37

[PDF] FORMULAIRE D ATTRIBUTION DU SUPPLEMENT FAMILIAL DE TRAITEMENT 2014-2015 (annexe 1) DECLARATION SUR L HONNEUR

[PDF] BOURSE DE RECHERCHE TRANSLATIONNELLE ème Edition

[PDF] THÈME : la géométrie dans l espace

[PDF] Tenir la comptabilité d une PME/PMI sur Ciel comptabilité en toute autonomie

[PDF] Totems (5ème HarmoS) :

[PDF] Modalités d examen Session 2016

[PDF] DOSSIER'D'INSCRIPTION' '' A'L'ORDRE'DES'VETERINAIRES'' ' DE'LA'REGION'ALSACE'

[PDF] Décision n 11-DCC-186 du 14 décembre 2011 relative à l affiliation de la Mutuelle Civile de la Défense à l union mutualiste de groupe Istya

[PDF] Mener à bien son projet de rénovation thermique en copropriété

[PDF] Enrichir les pratiques enrichir le développement de l enfantl

[PDF] Le Traitement des Données Personnelles au sein d une Association

[PDF] BAREME DES TRAITEMENTS AU 1 ER JUILLET 2016

[PDF] Résoudre des problèmes mathématiques à l'ecole Maternelle

[PDF] Engagement actif, défense moderne Concept stratégique

[PDF] Comment les copropriétés peuvent-elles se mobiliser pour répondre aux enjeux énergétiques?