”Quand Cesar Fermat et Turing dınent a la meme table” Marc Girault

Alan Turing

Description

Niveau: Secondaire, Lycée
La cryptographie ou ”Quand Cesar, Fermat et Turing dınent a la meme table” Marc Girault France Telecom, Division R&D, Caen Journees APMEP, 20-23 octobre 20051 1. Introduction 1.1 Definition Si l'on en croit Jacques Stern2, la cryptologie (ou cryptographie) est la ”science du secret”, aujourd'hui eten- due a la ”science de la confiance”. Ses missions principales sont de definir des methodes, appelees improprement ”algorithmes” (ou encore ”mecanismes”, ”schemas”, ”systemes” etc.) permettant d'assurer la confidentialite, l'in- tegrite et l'origine des donnees, ainsi que d'en evaluer la securite. Pour cette derniere tache, le savoir-faire des cryptanalystes, qui recherchent les failles des algorithmes proposes, est particulierement apprecie. Afin de dimi- nuer les chances de tomber sous leurs fourches caudines, les cryptographes (qui sont plus ou moins les memes personnes, ce n'est qu'une question de casquette !) ne specifient plus que des algorithmes dotes de preuves, au moins partielles, de securite. 1.2 Un mot d'histoire L'histoire de la cryptographie est pluri-millenaire3, et il ne s'agit pas ici de la retracer. Indiquons simplement qu'on peut facilement distinguer deux periodes : – la periode artisanale, tres longue, qui demarre a la nuit des temps (bien avant les hieroglyphes !) pour expirer en meme temps que la domination qu'Hitler entendait exercer sur le monde, et au service de laquelle la fameuse machine a rotors Enigma, visible

• cle


• ordre dans la discipline en meme temps


• invention du zero-knowledge8


• histoire des codes secrets


• confidentialite des donnees


• algorithme de chiffrement


• message clair

Sujets

• Mercier
• Girault
• Canal+
• Turing (homonymie)
• Discrete
• Lattes
• France Télécom
• Hellman

Informations

• Publié par: apmep
• Nombre de lectures: 52
• Langue: Français

Extrait

La cryptographie ou ”QuandC´esar,FermatetTuringdˆınenta` Marc Girault FranceT´ele´com,DivisionR&D,Caen 1 Journe´esAPMEP,20-23octobre2005

1. Introduction

lameˆmetable”

1.1De´finition 2 Sil’onencroitJacquesStern,lacryptologie(oucryptographie)estla”sciencedusecret”,aujourd’hui´eten- duea`la”sciencedelaconfiance”.Sesmissionsprincipalessontded´efinirdesm´ethodes,appele´esimproprement ”algorithmes”(ouencore”me´canismes”,”sch´emas”,”syste`mes”etc.)permettantd’assurerlaconfidentialite´,l’in- t´egrit´eetl’originedesdonn´ees,ainsiqued’en´evaluerlas´ecurite´.Pourcettederni`eretaˆche,lesavoir-fairedes cryptanalystes,quirecherchentlesfaillesdesalgorithmespropos´es,estparticulie`rementappre´cie´.Afindedimi- nuerleschancesdetombersousleursfourchescaudines,lescryptographes(quisontplusoumoinslesmeˆmes personnes,cen’estqu’unequestiondecasquette!)nespe´cifientplusquedesalgorithmesdote´sdepreuves,au moinspartielles,dese´curit´e.

1.2 Un mot d’histoire 3 L’histoiredelacryptographieestpluri-mill´enaire,etilnes’agitpasicidelaretracer.Indiquonssimplement qu’onpeutfacilementdistinguerdeuxpe´riodes: –lap´eriodeartisanale,tre`slongue,quid´emarre`alanuitdestemps(bienavantleshi´eroglyphes!)pour expirerenmˆemetempsqueladominationqu’Hitlerentendaitexercersurlemonde,etauservicede laquellelafameusemachinea`rotorsEnigma,visibleauMe´morialdeCaen,devaitjouerunroˆle-cl´e. MaisAlanTuringetses´equipesduBletchleyPark,dote´sdespremiersordinateurs,aide´sdesde´couvertes polonaisesetfranc¸aises,mirenttousleurstalents`aenpercerlessecrets,etcontribu`erentainsia`de´jouer les plans du dictateur fou ; –lap´eriodescientifique,encoretr`escourtepuisqu’ellede´buteen1949,dateo`uShannoncommen¸caa`mettre 4 del’ordredansladisciplineenmeˆmetempsqu’ilfondalath´eoriedel’information.Lesautresdates 5 marquantesdecettepe´riodefurent,dansunincroyabletirgroupe´detroisans:1974(inventionduDES 6 ouDataEncryptionStandard),1976(inventiondelacryptographie`acl´epublique)et1977(invention 7 deRSA,pourRivest,ShamiretAdleman,etaccessionduDESautitredenormef´ede´raleam´ericaine). 8 9 Mentionnonse´galement1985(inventionduzero-knowledge) et 1998 (invention de l’AES , Advanced EncryptionStandard,normef´ede´raleame´ricainedepuis2000). Uneautredateimportante,maisd’int´ereˆtessentiellementhexagonal,est1999.Onyassistaaubasculement completdustatutdelacryptologiequi,avantcettedate,relevaitdesmate´rielsdeguerredesecondecat´egorie 10 (telleun...porte-avions),puis,sanstransition,futensuiteenseigne´edansleslyce´es!

1.3 Les missions de la cryptographie (cf. figure 1) Le but de la cryptographie est de fournir des moyens de lutter contre les attaquespassives, consistant a`prendrefrauduleusementconnaissancededonn´eestransmisesoustocke´es,etcontrelesattaquesactives, consistant`amodifierfrauduleusementleurorigineouleurcontenu. 1 LeBulletindel’APMEPad´eja`abord´ecethe`me,notammenta`traversl’articledeDany-JackMercier,Cryptographie classique etcryptographiepublique`acl´er´ev´ele´e, septembre 1996. 2 Jacques Stern,La science du secret, ed. Odile Jacob, 1998. 3 Simon Singh, ”Histoire des codes secrets,”deJ.ae-n91,se`ttaLedualC.99 4 C.E. Shannon,Communication theory of secrecy systems, Bell System Technical Journal, Vol. 28, pages 656-715, 1949. 5 Data Encryption Standard, NBS, Federal Information Processing Standards, Publ. 46, 1977. 6 W. Diffie et M. Hellman,New directions in cryptography, in IEEE Trans. on Inf. Theory, Vol. IT-22, pages 644-654, 1976. 7 R.L. Rivest, A. Shamir et L.A. Adleman,A method for obtaining digital signatures and public-key cryptosystems, CACM, Vol. ◦ 21, n 2, pages 120-126, 1978. 8 S. Goldwasser, S. Micali et C. Rackoff,The knowledge of interactive proof-systems, Proc. of 17th ACM Symposium on Theory of Computing, pages 291-304, 1985. 9 Advanced Encryption Standard, NIST, Federal Information Processing Standards, Publ. 197, 2000. 10 Lesyste`meRSAestparfoisenseign´eensp´ecialite´”mathe´matiques”delaTerminaleS.

1

Pourluttercontrelesattaquespassives,etcefaisantassurerlaconfidentialite´desdonn´ees,onutiliseun m´ecanismedechiffrement:l’e´metteurchiffrelesdonne´esenclairavecunecle´dechiffrement,ler´ecepteur de´chiffrelesdonne´eschiffr´eesavecunecle´ded´echiffrement.Lacl´edede´chiffrementestn´ecessairementsecre`te, fautedequoitoutlemondepourraitr´etablirlaclarte´. Pourlaluttecontrelesattaquesactives,etcefaisantassurerl’authenticite´desdonn´eesoudesentit´es,on distingue deux cas. L’originedesdonn´eesainsiqueleurint´egrit´esontassur´eesparunesignaturenum´erique,produiteavecune cl´edesignature,ve´rifi´eeavecunecle´dev´erification,etdontlavaleurd´ependtout`alafoisdeceluiquisigne etdecequiestsigne´.Cedernierpointladistingued’unesignaturetraditionnelle:unseulbits’inverseettout estchamboul´e!Surlereste,l’analogieestgrande:unesignatureestr´epute´einimitable,satailleestre´duite etinde´pendantedelatailledesdonn´ees.Quanta`lacle´designature,elleestne´cessairementsecre`te,fautede quoitoutlemondepourraitsigner`alaplacedetoutlemonde.Lem´ecanismedesignatureestessentiellement off-lineatgnsine:u.fi´rileeendleaiemluoniomeiusstnavurepeutˆetrecalclue´uejnuoervte´ L’identit´edel’entit´e(eˆtrehumain,ordinateur,cartea`puce,...)aveclaquelleoncommuniquea`l’instant pre´sentestassur´eeparunm´ecanismed’authentification,dontlece´le`bre{login, password}constitue l’exemple lepluspopulaire,`ade´fautd’ˆetreleplussˆur.Lem´ecanismed’authentificationestessentiellementon-line: il met enpre´sencelesdeuxentit´esconcern´ees,etsonverdict(OKouNOK)nevautqu’`al’instanto`uilestprononce´,et ´eventuellementencorequelquesinstantsapre`s,lad´efinitiondel’instantvariantnotablementaveclessituations. Signatureetauthentificationpeuventˆetrecombin´eespourassurerl’origineetl’inte´grite´dedonne´esa`l’instant pre´sent.

Figure 1. Les missions de la cryptographie

2. Cryptographie versus codage

Lesscientifiquesutilisentlemot”codage”a`touteslessauces.D`esquel’onmodifielafac¸ondontunedonn´ee estrepre´sent´ee,elleestd´eclar´ee”cod´ee”.Lamodificationpeuteˆtreplusoumoinslourdeselonquel’onchange lesupportderepre´sentationlui-mˆeme(parexemplelaconversionanalogique–num´erique)ouseulementla repr´esentationsurunsupportdonn´e(parexemplelacompressiondedonn´ees). Afind’´eclaircirunpeulepaysage,nousallonscomparerentreellestroisformesdecodage:lecodagede source,lecodagedecanaletlecodage”secret”.Cesontdanslestroiscasdescodagesdedeuxie`metype:onne faitquemodifierlesmots,maispasl’alphabetdanslequelilss’e´crivent,enl’occurrencel’alphabetbinaire{0,1}. End’autrestermes,cescodagesremplacentdeschaˆınesdebitspard’autreschaıˆnesdebits,plusappropri´ees.

2.1 Codage de source Laquestionestici:commentadapterlasourced’informationau(de´bitdu)canalquilatransporte?Consi- de´ronslecasd’undisquecompact(CD)dontonsouhaitetransmettrelecontenua`unamiparInternet(c’est

2