La cryptographie de l’Antiquité à l’Internet

Description

La cryptographie est l’´etude des messages secrets. Le terme cryptographie vient en effet des mots grecs anciens : kruptos (κρυπτoσ) qu’on peut traduire comme secret ou caché; et graphein (γραϕην) pour écriture.

Informations

• Publié par: Force_IT
• Nombre de lectures: 103
• Licence : En savoir +
  Paternité, pas d'utilisation commerciale, partage des conditions initiales à l'identique
• Langue: Français
• Poids de l'ouvrage: 4 Mo

Extrait

Lacryptographiedel’Antiquite´a`
l’Internet

Fran¸coisBergeronetAlainGoupil

22 juillet 2006

Université du Québec à Montréal
Département de mathématiques
Case postale 8888, Succursale Centre-Ville
Montréal (Québec) H3C 3P8

2

Tabledesmatie`res

Pr´efaceiii
1 Introduction1
1.1 Unpeu d’histoire. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1
1.2 Lejargon de la cryptographie. . . . . . . . . . . . . . . . . . . . . . .. . .6
1.3Lacryptographie,lesmath´ematiquesetl’informatique............7
1.4 Utilisationcourantes de la cryptographie .. . . . . . . . . . . . . . . . . . .8
2Quelquescryptosyst`emessimples11
2.1 Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .11
2.2Chiffrementparde´calage.............................11
2.3 Chiffrementpar substitution .. . . . . . . . . . . . . . . . . . . . . .. . . .12
2.4LecodedeVigene`re...............................13
2.5 Chiffrementpar permutation de blocs dem15. . . . . . . . . . . . .lettres .
2.6 Chiffrementde Hill. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .15
2.7 Chiffrementde Playfair. . . . . . . . . . . . . . . . . . . . . . . . . . . .. 18
2.8Lesyste`meADFGVX20. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.9 Lechiffre de Vernam. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .22
2.10Quelquesnotionsmath´ematiques........................25
2.11 Chiffrementaffine .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .32
2.12 Exercices. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .32
3Cryptanalysedessyste`mesclassiques37
3.1 Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .37
3.2Cryptanalysedessyst`emesmonoalphab´etiques................38
3.3L’e´critureautomatique..............................43
3.4CassageduchiffredeVigene`re.........................45
3.5 L’indicede co¨ıncidence .. . . . . . . . . . . . . . . . . . . . . . . . .. . . .47
3.6 Briserun codage de Hill. . . . . . . . . . . . . . . . . . . . . . . . . . . .. 49
3.7 Exercices .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .50
i

`
iiTABLE DES MATIERES
3.8Appendice:Fre´quencesden51. . . . . . . . . . . . . . . . . . . .grammes .
4Probabilit´es55
4.1Laroulettedesprobabilite´............................55
4.2Exemplesautourdulance´dedeuxd´es.....................56
4.3Lejargondesprobabilit´es............................59
4.4 Lejeu de craps. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .66
4.5Probabilite´totale.................................69
4.6Explicationdel’indicedecoı¨ncidence......................70
4.7 Exercices .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .71
5Lathe´oriedel’information73
5.1 Entropieet incertitude. . . . . . . . . . . . . . . . . . . . . . . . . . .. . .73
5.2Propri´ete´sdel’entropie.............................78
5.3Quantite´d’informationetentropieconditionnelle...............79
5.4Syste`mescryptographiquesetthe´oriedel’information............83
5.5Syst`emesparsubstitutionmonoalphabe´tique.................85
5.6 Exercices .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .86
6 Cryptographiemoderne 89
6.1 Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .89
´
6.2El´ementsdeth´eoriedesnombres........................90
6.3 L’algorithmed’Euclide . . . . . . . . . . . . . . . . . . . . . . . . . . .. . .93
6.4Algorithmed’Euclidee´tendu..........................95
6.5 Exponentiationmodulon97. . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.6Lesyst`emeRSA.................................102
6.7Se´curit´edusyst`emeRSA............................103
6.8 Recherchede grands nombres premiers. . . . . . . . . . . . . . . . . . . . .104
6.9 Logarithmediscret .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 105
7 Pourles mordus109
7.1 Courbeselliptiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. .109
7.2Cryptosyste`meselliptiques............................113
7.3 Chaˆınesd’additions .. . . . . . . . . . . . . . . . . . . . . . . . . . . .. . .116

Bibliographie

Index

119

121

Pre´face

1
Cesnotesaccompagnentlecoursdumeˆmenom,offertparlaFacult´edesSciencesde
l’Universite´duQue´beca`Montr´eal.Ilestengrandepartiebase´suruncoursmisaupoint
parAdrianoGarsia,duDe´partementdeMathe´matiquesdel’University of California San
Diegoraoueg´edresuoniovacnerde´etrend’c,onsdicremerelrap,uejc¸nommnesuoc.oN
dans ce projet.

Notrebutestdepr´esenter,defac¸ontoutesimple,leside´esdebasesdelacryptographie
pourunlargeauditoire.Dansuncontextemoderne,ou`degrandesquantite´sd’informations
sonttransmisesouenregistre´esdefa¸concod´ee,notreobjectifestd’expliquercommentilse
faitquecescodagespeuventeˆtrefacilementvulne´rablesauxattaquesparordinateur.C’est
la`unobjetd’´etudeplussp´ecifiquea`lacryptanalyse,dontl’apprentissaged´epasselargement
leniveaudepr´esentationdecetexte.Cependant,nousavonsl’intentiondebienillustrer
legenredetechniquesquirendentpossiblecettecryptanalyse.Dansundeuxie`metemps,
nousallonspr´esenterdestechniquesmodernesdecryptographie,vialesquelleslase´curit´e
desdonne´esencrypte´esestbeaucoupmieuxassure´e.

Ayantdonne´cecoursenCalifornie,lepremierauteurae´t´ea`meˆmedeconstaterl’en
gouementquelacryptographiesoul`evechezunpublicprovenantdedisciplinestre`svarie´es,
surtoutsil’approchechoisieprivile´giel’accessibilit´e.Entransposantcecoursaucontextede
l’UQAM,nousavonsdonctente´deconserveruntonquipermeta`tousdebiencomprendre
lessujetsaborde´s.Enparticulier,touteslesnotionsmathe´matiquesne´cessairessontintro
duitesdefa¸coninformelle,aufuret`amesurequ’ellesdeviennentne´cessaires.L’emphaseest
donctoujoursplussurl’accessibilit´eetlaclart´e,quesurl’exactitudeetlarigueur.Celan’a
pastoujours´et´efacile,e´tantdonne´notrebiaisnaturel(demath´ematiciens)quinousporte
`a´ecrireensaupoudrantlestextesdesmots✭th´emeseor`✮,✭propositions✮,✭lemmes✮et (bien
entendu)✭preuves✮.Qu’onsearssru,eonsuvanorespuesqujtorsouue´r`isse´ratsisetteca`re
tentationparticulie`re.

1
Mis au point par les auteurs.

iii

iv

´
PREFACE

Chapitre 1

Introduction

1.1 Unpeu d’histoire

Lacryptographieestl’e´tudedesmessagessecrets.Leterme✭cryptographie✮vient en
effet des mots grecs anciens :kruptos(κρυπτ oσ) qu’on peut traduire comme✭secret✮
ou✭eca´hc✮; etgraphein(γραϕηνeetssulPe´rp´sicnemelat,ypcrgrtohiap.erutirce´ruop)
l’e´tudedescodes secretsmoemsec(ed’lvaceeencr,etnoedellecnegassemsemplimssl´oitven
invisible,parexemple).Lesoriginesdelacryptographiesemblentremontera`plusde4000
ans.Onatrouv´e,surunetombee´gyptiennedecette´epoque,desinscriptionscontenantdes
hi´eroglyphesmodifie´s,etilsembleraitqu’onaitcherche´parcesmodifications`aobscurcir
lesensdesinscriptions.Quoiqu’ilensoit,plusieursindicationsarche´ologiquestendenta`
montrer que les✭rce`etsituresse´ecr✮isrcneo´e’tlfeneruttnevdnoieuqsni’lcianneentaaisius
ellemˆeme.
e
Lepremierexempleinde´niabledecryptographieremonteaumoinsauVsie`cleavantnotre
e`re.Eneffet,lesSpartiates(Gr`ece)dutempsavaientde´veloppe´unem´ethodeoriginale
pourl’e´changedemessagessecrets.Celleciestbas´eesurlefaitquedeuxcopiesidentiques
d’unbaˆtonnet,appel´escytaleuryeduetl’devoensessnoistiosopne,age.emssruudpeet´rce
Pourpr´eparerunmessage,onenrouleenspiraleautourdelascytaleunebandelettede
parchemin(oudecuir),pourensuitee´crirelemessagelelongdelascytale(voircicontre).
Unefoisde´roule´elabandelettenecontientplusqu’unesuiteapparemmentincompr´ehensible
delettres.Cependant,pourd´ecoderlemessageilsuffitsimplementd’enroulerlabandelette
surlascytalejumelle.Commelam´ethodeestassezsimple,illeurfallaitbienentendula
conserversecr`ete.Scytale
Lepremiertexteconnu,traitantexplicitementdecryptographie,sembleˆetreletrait´ede
1

Carre´dePolybius

2CHAPITRE 1.INTRODUCTION
Aeneas Tacticus (circa 400 AD), sur la✭ioatfictinssedesforD´efen✮. On sait aussi qu&#