30
Dossier > Cryptologie : l'art des codes secrets Futura-Sciences Source : http://www.futura- sciences.com/magazines/mathematiques/infos/dossiers/d/mathematiques-cryptologie-art-codes- Page 1 / 30 Cryptologie : l'art des codes secrets Rendre incassables les codes secrets est un vieux rêve des professionnels de sécurité. Depuis l’Antiquité, les Hommes inventèrent des systèmes manuels puis mécaniques avant la révolution électronique. Découvrez la cryptologie et ses utilisations, du chiffrement traditionnel à l’usage de l’informatique en passant par le chiffrement RSA. Page 1/13 - Cryptologie : l'art des codes secrets Dès que l'écriture a permis aux Hommes de conserver et transmettre les traces de leur savoir, il a fallu trouver des moyens pour que les informations contenues dans les messages écrits puissent être rendues inaccessibles à qui elles n'étaient pas destinées. Depuis l'Antiquité et les substitutions alphabétiques, les techniques de codage ont pris une autre dimension avec la venue des ordinateurs et les clés complexes du chiffrement RSA. Comment le calcul est-il apparu dans ce qu’on appelle aujourd’hui « le chiffre », qui a conduit à imaginer des machines à chiffrer, d’abord mécaniques, puis électromécaniques, enfin électroniques et miniaturisées dans les cartes à puce ? Où intervient l’adversaire, partenaire obligé du jeu cryptologique, sans qui la sécurité ne peut finalement pas être assurée ? Quel a été l’apport de l’informatique, c’est-à-dire de la mécanisation du calcul, et son lien étroit avec la théorie de la calculabilité qui classe les problèmes selon leur difficulté de résolution ? Toutes ces questions sont traitées dans l’ouvrage Cryptologie, l'art des codes secrets de Philippe Guillot, aux éditions EDP Sciences. Ce dossier, qui contient plusieurs extraits du livre, retrace l’histoire de cette technique, en donne quelques exemples d’utilisation et en évoque les potentialités. En somme, des clés pour percer deux ou trois de ses mystères. 23/11/2015 - Par Philippe Guillot, Maître de conférences : cryptologie

Cryptologie Art Codes Secrets

  • Upload
    comanav

  • View
    32

  • Download
    3

Embed Size (px)

DESCRIPTION

cryptologie

Citation preview

Page 1: Cryptologie Art Codes Secrets

Dossier>Cryptologie:l'artdescodessecrets Futura-Sciences

Source:http://www.futura-sciences.com/magazines/mathematiques/infos/dossiers/d/mathematiques-cryptologie-art-codes-

Page1/30

Cryptologie:l'artdescodessecrets

Rendreincassableslescodessecretsestunvieuxrêvedesprofessionnelsdesécurité.Depuisl’Antiquité,les Hommes inventèrent des systèmes manuels puis mécaniques avant la révolution électronique.Découvrez la cryptologie et sesutilisations, du chiffrement traditionnel à l’usagede l’informatiqueenpassantparlechiffrementRSA.

Page1/13-Cryptologie:l'artdescodessecrets

Dèsquel'écritureapermisauxHommesdeconserverettransmettrelestracesdeleursavoir,ilafallutrouverdesmoyenspourquelesinformationscontenuesdanslesmessagesécritspuissentêtrerenduesinaccessiblesàquiellesn'étaientpasdestinées.Depuisl'Antiquitéetlessubstitutionsalphabétiques,lestechniquesdecodageontprisuneautredimensionaveclavenuedesordinateursetlescléscomplexesduchiffrementRSA.

Comment le calcul est-il apparu dans ce qu’on appelle aujourd’hui « le chiffre », qui a conduit à imaginer desmachines à chiffrer, d’abord mécaniques, puis électromécaniques, enfin électroniques et miniaturisées dans lescartes à puce ? Où intervient l’adversaire, partenaire obligé du jeucryptologique, sans qui la sécurité ne peutfinalementpasêtreassurée ?Quel a été l’apport de l’informatique, c’est-à-direde lamécanisationdu calcul, etsonlienétroitaveclathéoriedelacalculabilitéquiclasselesproblèmesselonleurdifficultéderésolution?

Toutes ces questions sont traitées dans l’ouvrageCryptologie, l'art des codes secrets de Philippe Guillot, auxéditionsEDPSciences.Cedossier,quicontientplusieursextraitsdulivre,retracel’histoiredecettetechnique,endonnequelquesexemplesd’utilisationetenévoquelespotentialités.Ensomme,descléspourpercerdeuxoutroisdesesmystères.

23/11/2015-ParPhilippeGuillot,Maîtredeconférences:cryptologie

Page 2: Cryptologie Art Codes Secrets

Dossier>Cryptologie:l'artdescodessecrets Futura-Sciences

Source:http://www.futura-sciences.com/magazines/mathematiques/infos/dossiers/d/mathematiques-cryptologie-art-codes-

Page2/30

Lacryptographieestlaplusancienneformedechiffrement.Ontrouvedestracesdesonutilisationjusqu'en2.000avantJ.-C.Cettetechniqueencoreutiliséeaujourd’hui,notammentsurleWeb,dévoilesesmystèresen

vidéogrâceauprogrammeKézakod'Uniscieletdel'universitéLille1.©Unisciel

Le lecteur découvrira notamment dans ce dossier, à travers un choix de questions relatives à ce passionnantdomainequ'est lacryptologie,quelquesméthodes traditionnelles,utiliséesdans l’histoireou la littérature,quiontde tout temps fait le plaisir des amateurs de puzzle et d’énigmes. Il découvrira aussi un systèmed’une sécuritéabsolue,quidatedudébutduXXesiècle,etconsidéréencoreaujourd’huicommeindécodable.

Onpeutvoirlacryptologiecommel’artdescodessecretsetdelaserrurechiffrée.©ClémentDorando

Quelqueséclaircissementsserontdonnéssurlarévolutionsurvenueaumilieudesannées1970,lorsqueleparadoxedesclés publiques a été inventé. Seront enfin abordés les univers virtuels d’Impagliazzo, chacun doté d’unecryptographie qui lui est propre, et que les progrès scientifiques soit rendront réels, soit feront disparaître,éclairantlesquestionstrèsactuellesdelathéoriecryptographique.

Page2/13-Lechiffrementtraditionnel:grilletournante,radiogrammedelavictoireetcodeSittler

Lepremierprocédéqui vient à l'esprit pour rendreobscurun texteécrit dansune langueàalphabetconsisteàremplacerchaquelettreparuneautreselonunerègleconvenueentrelescorrespondants.LechiffredeCésarapourprincipededécalerl’ordrealphabétique,ilestdécritparleshistoriensSuétone,DionCassiusetAulu-Gelle.

Page 3: Cryptologie Art Codes Secrets

Dossier>Cryptologie:l'artdescodessecrets Futura-Sciences

Source:http://www.futura-sciences.com/magazines/mathematiques/infos/dossiers/d/mathematiques-cryptologie-art-codes-

Page3/30

LedisqueàchiffrerdesConfédérés,utilisépendantlaguerredeSécession.©RadioFan,WikimediaCommons,CCby-sa3.0

Les lettres peuvent aussi être remplacées par des symboles ésotériques, ce qui donne l'illusion d'augmenter lemystèrequientourelecryptogramme.

Enhaut,le«parcàcochons»,procédétrèsanciencitéparBlaisedeVigenèredanssonTraitédeschiffresetdessecrètesmanièresd'écrire,Paris,1586.Enbas,les«hommesdansants»:chaquefigurinereprésente

unelettre.LetalentdeSherlockHolmesetl'analysedesfréquencessontaisémentvenusàboutdecesmystérieuxmessages.©P.Guillot

Unautreprocédéconsisteàchangerl'ordredeslettressanslesaltérer,parexemplelagrilletournante,présentéepar le colonel autrichienÉdouard Fleissner vonWostrowitz (1825-1888) et décrite dans le romande JulesVerneMathiasSandorf.

Page 4: Cryptologie Art Codes Secrets

Dossier>Cryptologie:l'artdescodessecrets Futura-Sciences

Source:http://www.futura-sciences.com/magazines/mathematiques/infos/dossiers/d/mathematiques-cryptologie-art-codes-

Page4/30

La«grilletournante»:lagrilleestplacéesurlecryptogramme,puistournéequatrefoisd'unquartdetourdanslesensdesaiguillesd'unemontre.Lemessageenclairapparaîtdanslescasesajouréesdelagrille.©

P.Guillot

Clédetranspositionetclédesubstitution

Jusqu'à la fin de lapremière guerre mondiale, les chiffres utilisés par les militaires reposaient souvent sur unecombinaison de ces deux procédés : substitution alphabétique et transposition des lettres. Ainsi, les services

d'écoutefrançaisont-ilsinterceptéle1erjuin1918,danslesenvironsdeCompiègne,lemessagesuivant:

FGAXAXAXFFFAFFAAVDFAGAXFXFAAAGDXGGXAGXFDXGAGXGAXGX

AGXVFVXXAGXFDAXGDAAFDGGAFFXGGXXDFAXGXAXVAGXGGDFAGDGXVAXVFXGVFFGGAXDGAXADVGGA

Cemessagefutimmédiatementtransmisàlasectionduchiffrequiréussitàtrouverlaclédetransposition,puislaclé de substitution pour finalement reconstituer lemessage en clair :Munitionierungbeschleunigen Punkt soweitnicht eingesehen auch bei Tag(«hâter l’approvisionnementenmunitions, le fairemêmede jour tantqu’onn’estpasvus»).

Leradiogrammedelavictoire

TransmisaugénéralPétain,puisaugénéralFoch,chefd'état-major interallié,cetexteaconfirméque l'offensiveallemande allait se concentrer à cet endroit. Elle se produisit le 10 juin 1918,mais l'information avait permis deprendretoutesdispositionspour lacontrer.Lefaitdestoppercetteoffensiveaétédécisif.Pourcetteraison, lemessageinterceptéporteaujourd'huilenomde«radiogrammedelavictoire».

Page 5: Cryptologie Art Codes Secrets

Dossier>Cryptologie:l'artdescodessecrets Futura-Sciences

Source:http://www.futura-sciences.com/magazines/mathematiques/infos/dossiers/d/mathematiques-cryptologie-art-codes-

Page5/30

«Radiogrammedelavictoire».Enhaut,applicationdelatransposition.Laclédetranspositionestunenumérotationdescolonnes.Leradiogrammeinterceptéestécritverticalementdanslescolonnesnumérotées1,2…jusqu'à21.Lalecturehorizontaledansletableaudonneraleclairaprèsapplicationdelasubstitution.Enbas,applicationdelasubstitution.Laclédesubstitutionestlafaçonderemplirletableauavecleslettres

etleschiffres.Leslettresordonnéesduradiogrammesontgroupéespardeux.Lapremièreestl'indicedeligne,lasecondeestl'indicedecolonnedutableau.DA=m,GX=u,FA=n,GF=i,XG=t,etc.©P.Guillot

Lafaiblessedessubstitutionsalphabétiquesarapidementétémiseenévidence.Ellesn'apportentqu'unsemblantde sécurité. À la Renaissance, plusieurs acteurs, l'architecte Léon Battista Alberti, l'abbé Jean Trithème, lephysicien Giovanni Battista Porta, le mathématicien Girolamo Cardano et le magistrat Blaise de Vigenèredéveloppent le chiffre polyalphabétique. Il s'agit d'un procédé où l'alphabet de substitution change au cours dumessage, rendant extrêmement difficile le travail de décryptement, au point que cette méthode gardera trèslongtempslaréputationd'êtreindéchiffrable.Ilneseracependantquetrèspeuutilisépourlesdépêchesofficiellesetsonusageresteraconfinéàdeséchangesentreacteursprivés,comme la reineMarie-Antoinetteet lecomteAxeldeFersendanslesannées1791-1792.Laraisonenestl'extrêmedifficultédemiseenœuvreàlamainetlesinévitableserreursquienrésultent.Ilneseraréellementpratiquédansuncadreinstitutionnelqu'aprèsl'inventiondemachinesquienautomatisentl’usage,tellelafameusemachineEnigma.

LecodeSittler

Page 6: Cryptologie Art Codes Secrets

Dossier>Cryptologie:l'artdescodessecrets Futura-Sciences

Source:http://www.futura-sciences.com/magazines/mathematiques/infos/dossiers/d/mathematiques-cryptologie-art-codes-

Page6/30

DeuxpagesdufameuxcodeSittler,oudictionnaireabréviatifchiffrédeSittler.©Fredandre

La cryptologie gouvernementale et diplomatique a longtemps utilisé les nomenclatures qui consistent en unalphabetdesubstitution,avecplusieurschoixpossiblespourleslettreslespluscourantesafindetromperl'analysedes fréquences, associée à un répertoire de codage des mots courants. Ces répertoires ont été populaires audébut du télégraphe tant à des fins deconfidentialité que de compression, les télégrammes étant facturés aunombredecaractères.Lepluscélèbred'entreeuxestsansdouteledictionnaireabréviatifchiffrédeF.-J.Sittler,qui comprend100pagescontenantchacuneune listedecentmotsouportiondephrasecourante.Chaquemotest codépardeuxnombres indiquant lapageet laplacedans lapage.Ces codesperdureront jusqu'auxannées1970,dateàlaquelleledéveloppementducalculélectroniquelesadéfinitivementrendusobsolètes.

Page3/13-LemasquejetableouchiffredeVernam

En 1915, l'ingénieur Gilbert Vernam, alors en charge de la sécurité des téléscripteurs au sein dudépartementrechercheetdéveloppementdel'entrepriseAT&T,déposeunbrevetpourundispositifdecodage.

L'objetdecedispositif,selonsesproprestermes,est«d'assurer lasécuritédestransmissionsdemessages, etparsuite,defournirunsystèmeoùlesmessagespeuventêtretransmisetreçusenclair,oucodésdemanièreconnue, mais où les impulsions du signal sont si altérées avant leur transmission sur la ligne qu'elles sontinintelligiblesàquiconquelesintercepte».

Page 7: Cryptologie Art Codes Secrets

Dossier>Cryptologie:l'artdescodessecrets Futura-Sciences

Source:http://www.futura-sciences.com/magazines/mathematiques/infos/dossiers/d/mathematiques-cryptologie-art-codes-

Page7/30

Lesrubansperforésutilisésauxdébutsdel'informatiquepeuventcontenirdenombreusesinformations.©Wtshymanski,WikimediaCommons,CCby-sa3.0

Lestéléscripteurstransmettentlestextesàl'aided'uncodageinscritsurunrubanperforé.Chaquecaractèreestcodépar cinqunitésqui vont se traduirepar lepassageounondu courantélectrique. L'idéedeVernamestdecombinerlerubanquicontientletexteenclairavecunsecondruban.Larègledecombinaisonestlasuivante:

0+0=0

0+1=1

1+0=1

1+1=0

Codage:lechiffredeVernam

Cecodage,connuaujourd'huisouslenomde«chiffredeVernam»,présentel'avantagederendrel'opérationdedéchiffrement identique à l'opération de chiffrement. Il n'y a donc qu'une seule sorte de réalisationélectromécaniqueàprévoir.Enutilisantunrubanidentique,onretrouveralemessageclair.

Page 8: Cryptologie Art Codes Secrets

Dossier>Cryptologie:l'artdescodessecrets Futura-Sciences

Source:http://www.futura-sciences.com/magazines/mathematiques/infos/dossiers/d/mathematiques-cryptologie-art-codes-

Page8/30

Le«systèmedeVernam»:lapremièrebandeperforéecontientlemessageenclair.Lessignauxsontcombinésavecceuxd'unedeuxièmebandeperforéecontenantdescaractèresaléatoires.Lerésultatdelacombinaisonestunsignalchiffré,illustréiciparunetroisièmebande.Cesignalesttransmisparlesystèmetélégraphique.Àlaréception,unebandeperforéeidentiqueàlabandealéatoireutiliséeàl'émissionpermet

dereconstituerlemessageenclairàpartirdusignalreçu.©P.Guillot

Leprocédédumasquejetable

L'intérêtdecetteinventionestclair:lechiffrementestintégréàlachaînedetransmission.Lesopérateursn'ontpas à s'en préoccuper. La seule contrainte est de placer dans lamachine la bonnebande clé, identiquepour lechiffrementetledéchiffrement.

Il sera très tôtétablique laseuleclésûreestunecléaléatoire, comparableen longueuraumessageetutiliséeuneseulefois(one-timepad).Pourcetteraison,ceprocédéestappelé«masquejetable», lerubanservantdemasque devant être jeté après usage. Cette assertion de sécurité sera prouvée par Claude Shannon dans unarticle publié en 1949, montrant que si le ruban-clé contient une séquence de caractères aléatoires etindépendants, alors le système de Vernam atteint la sécurité inconditionnelle : quels que soient lesmoyens decalculdontildispose,l'adversairen'apasdemeilleurestratégiequed'essayerdedevinerlemessageenclairenletirantauhasardetdecomptersursachance.

Cesystèmeserarapidementadoptépourlescommunicationsdetrèshautniveaudesensibilité.Cequ'onappellele«téléphonerouge»,misenplacele30août1963entrelesprésidencesaméricaineetsoviétiqueàlasuitedelacrise desmissiles de Cuba, était d'abord un téléscripteur, chiffré selon ce procédé avec des bandes aléatoirestransportéesparlavalisediplomatique.

Page4/13-Chiffrementetcalcul,d'IbnDunayniràLesterHill

Lechiffrementestrestélongtempsconfinéàdesproblèmesdetraitementdulangageécrit.Ils'agissaitde remplacer une lettre par une autre, voire un mot par un autre. Il est aujourd’hui devenumajoritairementuncalcul.

Page 9: Cryptologie Art Codes Secrets

Dossier>Cryptologie:l'artdescodessecrets Futura-Sciences

Source:http://www.futura-sciences.com/magazines/mathematiques/infos/dossiers/d/mathematiques-cryptologie-art-codes-

Page9/30

Crypterunmessage,celapeutseréaliserenjouantsurleslettresmaisaussigrâceaucalcul.©Pixabay,DP

LepoèteetcryptologuearabeIbnDunaynir

La première trace d'un procédé dechiffrement faisant explicitement appel à un calcul est due au poète etcryptologue arabe IbnDunaynir (1187-1229) qui décrit ainsi son procédé : « Pour obscurcir un texte, on peutavoirrecoursaunombrecorrespondantàlalettre,puisdedoublerunefois,oudeuxfois,ouplusieursfois,cequidissimuleralesensàlapersonnequilit.Ainsi,onmet"Ba",dontlavaleurnuméraleestdeux,àlaplacedu"Alif",dont lavaleurnuméraleestun.Demême,onmet"Sin",dont lavaleurnuméraleest60,à laplacede"Lam",dontlavaleurnuméraleest30,etainsidesuitepourtoutletexte.Alors,admirecettejolieméthode!»

PremièrepagedutraitédupoètearabeIbnDunaynir.©Kfcris&Kacst

Avantd'adopterlanumérationdeposition,lesArabesattribuaientunevaleurnuméraleauxlettresdel'alphabet,delamêmemanièrequelesRomainsattribuaientlavaleurunàlalettreI,lavaleurcinqàlalettreV,lavaleurdixàlalettreX,etc.ÀladifférencedesRomains,lesArabesattribuaientunevaleurnuméraleàtoutesleslettresdeleuralphabet. À titre d'exemple, en numération romaine, lemot « LIV » se coderait en CIIX aprèsmultiplication par

Page 10: Cryptologie Art Codes Secrets

Dossier>Cryptologie:l'artdescodessecrets Futura-Sciences

Source:http://www.futura-sciences.com/magazines/mathematiques/infos/dossiers/d/mathematiques-cryptologie-art-codes-

Page10/30

deuxetlemot«MIX»secoderaitenDVLaprèsmultiplicationparcinq.

Les connaissances mathématiques de son époque ne permettaient pas à Ibn Dunaynir de proposer des calculsbeaucoup plus élaborés qu'un doublement ou un triplement des valeurs numérales. Le résultat d'opérations pluscomplexes serait vite devenu un nombre trop grand pour pouvoir être transcrit en lettres. Il en a été tout

autrement après que Gauss eut introduit les congruences au début du XIXe siècle. Dans cette arithmétique, lerésultat,lorsqu'ildépasseunecertainelimite,estréduitparsoustraction,cequenousréalisonstoutnaturellementavecleshoraires:cinqheuresaprès22hfont3h.Nouscomptonslesheures«modulo»24.

Lecodagedechaquelettredel'alphabetenunnombreentre0et25etlaréductiondurésultatdèsqu'ildépassela valeur 26 libèrent le concepteur et l'autorisent à imaginer des calculs aussi complexes qu'il le souhaite. Lerésultatseratoujoursunnombrecomprisentre0et25quiseratranscritenunelettredanslecryptogramme.

L'américainLesterHill

L'américain Lester Hill a imaginé utiliser cette arithmétique pour concevoir en 1929 le premier système dechiffrement reposant sur uncalcul algébrique. Son procédé repose sur le calcul matriciel. Chaque lettre del'alphabetestcodéede0à25,commeonl’avu,selonuncodagetenusecretentre lescorrespondants,puis leslettres du message sont regroupées deux par deux. Les couples de lettres sont codés en nombres selon laconventionpourobtenirunvecteurdedimension2.Cevecteurestmultipliéparunematrice2×2pourobtenirunvecteur image qui correspondra au cryptogramme. Toutes les opérations sont réaliséesmodulo26. Pourreconstituer lemessageenclair, il suffirad'effectuer l'opération inverse,enmultipliant lesvecteurs transcritsducryptogrammeparlamatriceinversedecelleutiliséepourlechiffrement.

Ilestpossiblederegrouperleslettrestroispartroisetmultiplierlevecteurrésultatdedimension3parunematrice3x3.

LamachinedechiffrementdueàLesterHill.©Scribner,TheCode-Breakers,DavidKahn

Le calcul à la main étant assez laborieux et sujet à de multiples erreurs, Lester Hill a inventé une machine,constituée d'une chaîne et de roues dentées, permettant de chiffrer jusqu'à des hexagrammes qui sont desgroupementsdesixlettres.Cechiffreaeffectivementétéutiliséparl'arméeaméricainepourcrypter les indicatifsradio.

Page5/13-Lesmachinesàchiffrer:Enigma,wheelcipheretcarteàpuce

Lesopérationsdechiffrementetdedéchiffrementsontconsidéréesàjustetitrecommeparticulièrement

Page 11: Cryptologie Art Codes Secrets

Dossier>Cryptologie:l'artdescodessecrets Futura-Sciences

Source:http://www.futura-sciences.com/magazines/mathematiques/infos/dossiers/d/mathematiques-cryptologie-art-codes-

Page11/30

fastidieuses, cequia conduità concevoirdesmachinesà cryptographierpour rendre l'opérationplusaiséeetexempted'erreur.C'estlecasd'Enigma,ducadrand'Alberti.

Enigmaestpeut-êtrelapluscélèbredesmachinesàchiffrer.©GregGoebel,WikimediaCommons,DP

Lesmachinesmanuelles:lecadrand'Albertietlewheelcipher

Lecadranchiffrantestconstituéd'unboutonmoletéquipermetdefairetournerl'alphabetmobileautourd'unaxe.Larotationrégulièreducadranmobilepermetdefairevarierlacorrespondancedesalphabets.

Lecadrand'Albertiestconstituéd'uncadranfixeetd'uncadranmobile.Leslettresducadranfixesontécritesenmajusculesetreprésententleslettresdutexteclair.Leslettresducadranmobilesontécritesen

minusculesetreprésententleslettresducryptogramme.©DP

LaréglettecoulissantedeSaint-Cyr,dunomdel'académiemilitaire,étaitenusageentre1880etledébutduXX e

siècle.

Page 12: Cryptologie Art Codes Secrets

Dossier>Cryptologie:l'artdescodessecrets Futura-Sciences

Source:http://www.futura-sciences.com/magazines/mathematiques/infos/dossiers/d/mathematiques-cryptologie-art-codes-

Page12/30

LaréglettecoulissantedeSaint-Cyr.©DR

Thomas Jefferson (1743-1826), avant d’être élu président des États-Unis d'Amérique, avait mis au point undispositif appeléwheel cipher, constitué de 26 disques sur la tranche desquels étaient inscrits des alphabetsdésordonnés. Pour chiffrer un message, on fait tourner les roues de manière à faire apparaître le message. Lecryptogramme est constitué de l'une quelconque des séquences des autres lettres. Pour déchiffrer, il suffit dedisposer dumême cylindre constitué desmêmes 26 disques, d'aligner le cryptogramme et de lire ailleurs le seultextequisembleavoirunsens.Onpeutchangerdecléenmodifiantl'ordredescylindres.

LewheelcipherdeThomasJefferson.©Ciphermachines

Lesmachinesélectromécaniques:Enigma

Le chiffrement polyalphabétique ne sera couramment utilisé qu'au début du XXe siècle avec l'apparition desmachines électromécaniques à rotor. Elles ont été présentées presque simultanément par quatre inventeurs depaysdifférents: l'AméricainEdwardHughHebern, leNéerlandaisHugoAlexanderKoch, leSuédoisArvidDammetl'Allemand Arthur Scherbius. Ce dernier est l'inventeur de la fameusemachine Enigma, qui sera adoptée etamélioréeparl'arméeallemandeàpartirde1928.

Page 13: Cryptologie Art Codes Secrets

Dossier>Cryptologie:l'artdescodessecrets Futura-Sciences

Source:http://www.futura-sciences.com/magazines/mathematiques/infos/dossiers/d/mathematiques-cryptologie-art-codes-

Page13/30

LamachineEnigma:cettevueouvertefaitapparaîtrelestroisrotorsainsiqueleslampesquiindiquentlalettrequisesubstitueàcelleactionnéesurleclavier.©DP

Le mode d'emploi de la machine Enigma est très simple : l'opérateur actionne une touche sur un clavieralphabétique et une lampe indique quelle est la lettre à substituer dans le cryptogramme. L'utilisation pour ledéchiffrementestsimilaire.

SoldatsallemandsutilisantunemachineEnigmapendantlasecondeguerremondiale.©DP

Lecœurdecesmachinesestconstituéd'unesériederotorsquisontdescylindresrotatifssurlatranchedesquelssontplacés26contactsreprésentantchacunune lettrede l'alphabet.Unrotorréaliseunepermutationentre lescontacts de chaque bord. Plusieurs rotors sont mis en série pour multiplier les permutations ainsi composées.Chaquelettreprovoquelarotationdesrotors,cequichangelapermutationopérée.

Page 14: Cryptologie Art Codes Secrets

Dossier>Cryptologie:l'artdescodessecrets Futura-Sciences

Source:http://www.futura-sciences.com/magazines/mathematiques/infos/dossiers/d/mathematiques-cryptologie-art-codes-

Page14/30

PrincipedefonctionnementsurunemachineEnigmaàdeuxrotorsportantsurlaséquencealphabétiqueABCDEF.Chaquelettredetexteprovoquelarotationdesrotors,cequichangeàchaquefoislapermutation

opérée.©P.Guillot

Lacarteàpuce

Uneétapetechnologiqueimportantepourlacryptologievaêtrefranchieavecledépôten1974parRolandMorenod'un«objetportableàmémoirerevendiquantdesmoyensinhibiteurs,uncomparateuraveccompteurd'erreursetdesmoyensdecouplageavec lemondeextérieur».Cedispositifdeviendra lacarteàpuceavec l'adjonctiond'unprocesseur de calcul par l'ingénieur en télécommunicationsMichelUgon.Celle-ci contient des clés secrètesqui permettent d'authentifier les données fournies, et ainsi d'ouvrir l'accès à des services de façon confiante etsécurisée.

L'apparitiondecedispositifvaavoirun impactconsidérablesur ledéveloppementde lacryptologiedans legrandpublic,cardemultiplesapplicationsl'utilisentàvasteéchelle:cartebancaire,cartevitale,cartesd'abonnementàlatélévisionàpéage,cartesSimdestéléphonesportables,etc.

Page6/13-ChiffrementRSA:larévolutiondescléspubliques

Notre besoin de communiquer de façon sécurisée se réalise aujourd'hui par ordinateur avec despersonnesquenousn'avons jamais rencontrées,etquenousne rencontreronsprobablement jamais,qu'ils'agissed'unecommandesurunsitedecommerceélectroniqueoudelatransmissiond'unefeuillede soins au centre de Sécurité sociale. Dans ce contexte, l'échange préalable d'une clé, opérationobligatoireencryptographietraditionnelle,n'estpasenvisageable.

Dans le milieu des années 1970, l'invention de lacryptographie à clé publique, liée au développement descommunicationsparordinateur,arésoluleproblème.Sonprincipereposesurunepaireasymétriquedeclés:l'unepourchiffrer,quipeutêtrepublique,etl'autrepourdéchiffrer,quidoitresterprivée.

Pour communiquer secrètement avec un destinataire, je consulte dans un annuaire sa clé publique et je l'utilisepourchiffrerlemessagequiluiestadressé.Lorsqu'ilrecevracecryptogramme,ilutilisera,pourlereconstituerenclair,sapropreclédedéchiffrementqu'ilgardesecrète.

Page 15: Cryptologie Art Codes Secrets

Dossier>Cryptologie:l'artdescodessecrets Futura-Sciences

Source:http://www.futura-sciences.com/magazines/mathematiques/infos/dossiers/d/mathematiques-cryptologie-art-codes-

Page15/30

Illustrationduchiffrementàclépublique:laclépubliqueestuncadenasouvertquetoutexpéditeurpeutfermerpourprotégerunmessageàl'attentiondudestinataire.Lacléprivée,queseulledestinatairedétient,

estcellequipeutouvrirlecadenas.©P.Guillot

Le plus utilisé de ces mécanismes est leRSA, acronyme tiré du nom de ses trois inventeurs Ronald Rivest, AdiShamiretLeonardAdlemanquil'ontpubliéen1978.

Laclépublique

Laclépubliqueest constituéed'unmodulen public, égal auproduitdedeux facteurspremiers inconnus,etd'unexposantpublice,souventégalà3.Ainsi,pourchiffrerunmessagem,codécommeunnombrecomprisentre0etn− 1, on l'élève à la puissanceemodulon. Sie vaut 3, cela revient à l'élever au cubemodulon. L'opérationréciproque,àsavoir l'extractionde la racinecubiquemodulonestréputéeêtreunproblèmedifficileen l'absencedelaconnaissancedelafactorisationden.

Unefonctionàsensuniqueavectrappeestcalculabledansunsenspartous,maisrequiertuneinformationsupplémentairepoureffectuerlecalculinverse.©P.Guillot

Page 16: Cryptologie Art Codes Secrets

Dossier>Cryptologie:l'artdescodessecrets Futura-Sciences

Source:http://www.futura-sciences.com/magazines/mathematiques/infos/dossiers/d/mathematiques-cryptologie-art-codes-

Page16/30

Lacléprivéeestconstituéedesfacteurspetqden.Grâceà laconnaissancedecesfacteurs, ilestpossiblededéterminer un exposant privédquipermettrade retrouver lemessagecorrespondantàuncryptogrammedonné.L'exposantprivédestégalàl'inversedel'exposantpublicemodulolepluspetitmultiplecommunàp−1etq−1.Laconnaissancedesfacteurspetqdumoduleestrequisepourcecalcul.

Lemessageestreconstituéenélevantlecryptogrammeàlapuissanceexposantprivémodulon.

LafonctiondechiffrementRSAestcequ'onappelleunefonctionàsensuniqueavectrappe.Chacunpeutchiffrerun message avec les paramètres publics. Toutefois, pour inverser le processus, c'est-à-dire pour retrouver lemessage à partir du cryptogramme, il faut disposer d'une information additionnelle : la trappe ouclé privée,maintenuesecrète.

L’usaged’entiersdegrandetailleencryptographieafaitdesprogrèssignificatifsenunequinzained’années,avecunquasi-doublementdunombredechiffresdécimaux.©DR

Lasécuritédecemécanismereposedemanièrecrucialesurladifficultéderetrouverlesfacteurspetqduproduitn= p× q. Cela a relancé la recherche pour résoudre ce problème, comme le montre le tableau ci-dessus quiindiquel'annéeoùontpuêtrefactoriséslesentiersdegrandetaille.

Page7/13-Signaturenumériqueetchiffrement

Lesactivitéshumainesreposentpourbeaucoupsur laconfiancedans lesengagementsdesdifférentsacteursentreeux.Cetteconfiancesematérialiseparunesignatureapposéesurundocument.Ilafallutrouverunéquivalentnumériquedelasignature,produiteparunepersonneparticulièreetvérifiablepartous:unesignaturenumérique.

Unmécanismeà clépublique comme leRSAautorise laproductiond'une telle signaturenumérique. Il suffit,pours'engager, d'élever le document que l'on souhaite signer à la puissance exposant privé modulo n. Le résultatconstituera lasignaturedudocument.Quiconquepourravérifier lasignatureen l'élevantà lapuissanceexposantpublicmodulon,maispersonnenepourraproduirelasignaturesanslaconnaissancedel'exposantprivé.

Signatureàclépublique:laproductiondelasignaturenécessiteunecléprivéeetchangeàchaquedocument.Savérificationnerequiertqu'uneclépubliqueaccessibleàtous.©P.Guillot

Cet exemple de la signature RSA qui consiste en un chiffrement avec clé privée a conduit les chercheurs à se

Page 17: Cryptologie Art Codes Secrets

Dossier>Cryptologie:l'artdescodessecrets Futura-Sciences

Source:http://www.futura-sciences.com/magazines/mathematiques/infos/dossiers/d/mathematiques-cryptologie-art-codes-

Page17/30

demander si cette propriété était consubstantielle à la notion de signature. La signature est-elle duale duchiffrementclé publique ? La réponse est négative. Il n'est pas nécessaire de disposer d'une fonction à sensuniqueavectrappepourréalisercemécanisme.Unesimplefonctionàsensuniquesanstrappesuffit.Unefonctionest dite « à sens unique » si elle est facilement calculable, mais étant donné une valeur, il est pratiquementimpossibledetrouverunparamètrequidonneracerésultat.

Parexemple,pourunnombrepremierp,ilestfaciled'élevern'importequelnombreàlapuissancenmodulopavecunesuccessiondemultiplicationsetd'élévationsaucarré.Pourtant,retrouverl'exposantnàpartirdurésultatestunproblèmequ'onnesaitpasrésoudredemanièreefficaceaujourd'hui.C’estleproblèmedulogarithmediscret.

Pour signer un document avec une fonction à sens unique, il suffit de disposer d'une clé secrète constituée dedeuxcouplesdevaleursx1,…xnety1,…yn.Laclépubliquecorrespondanteestconstituéeparlesimagesai =f(xi)

e tbi = f(yi) par une fonction à sens uniquef. Pour signer un messagem = m1,…mn où chaque mi est une

informationbinairevalant0ou1,j'apposeaumessagelarévélationdesdonnéesxisimivaut0etyisimivaut1.

Ledestinatairepourraaisémentvérifier,grâceàlaclépublique,que f(xi)=aisimivaut0etf(yj) =bj simivaut

1. Comme la fonction est à sens unique, il sera difficile à un adversaire de révéler des valeurs convenables enl'absencedelaconnaissancedesparamètresxietyi.

Cettesignaturen'aqu'unintérêtthéoriqueenraisondesatotaleinefficacité.Lasignatured'undocumentestbienplus « lourde » que le document lui-même et laclé privée n'est pas réutilisable pour un autre document.Cependant,l'intérêtthéoriqueestfondamental:lasignaturenumériquepeutseconstruireàpartird'unefonctionàsensunique.Iln'yapasbesoindetrappepoursignerundocument.

Page8/13-Lacryptologiedanslaviequotidienne

Pourillustreràquelpointlacarteàpuceestprésentedansnotreviequotidienne,voiciunpetitcontedelacryptologieordinairequinarrelesaventuresd'Alice,paysagistedemerveilles.

Alice aime son travail de paysagiste dans l'entreprise Thagemoù elle doit aménager l'environnement de travaildes 1.500 employés du site de Palombes-sur-Seine. L'essentiel de son activité se déroule en plein air. C'est leprintemps, les bouleaux lâchent leur pollen, et tout irait pour lemieux sans cemaudit rhume des foins qu'elletraînedepuissonadolescence.

Ce soir en quittant le travail, il faudra qu'elle passe voir son médecin pour se faire prescrire un traitementantiallergique.Endescendantlesescaliersdesonappartementparisien,elleallumesontéléphonemobile.

Page 18: Cryptologie Art Codes Secrets

Dossier>Cryptologie:l'artdescodessecrets Futura-Sciences

Source:http://www.futura-sciences.com/magazines/mathematiques/infos/dossiers/d/mathematiques-cryptologie-art-codes-

Page18/30

Lacarteàpucefaitpartiedenotrequotidien.Elleestnotammentutiliséedanslescartesbancaires.©ThomasKohler,Flickr,CCby2.0

Cartebancaire,carteVitaleetcarteUsim

–Allô,DocteurMaison?Puis-jepasservousvoircetaprès-midivers17h30?

Le rendez-vous est rapidement pris. La journée commence bien. Elle croise sans le remarquer le facteur venudéposerlecourrierdanslehalldel’immeubleets'engouffredanslemétro,passemachinalementsonsacàmainlelongdutourniquetetpensedéjàauxaventuresducommissaireEvenberg,hérosduromanqu'elleacommencéavant-hieretquiluiferapasserplusvitesontempsdetrajet.

Aprèsavoirprésenté sonbadgeauxportesd'accèsdeThagem,sonesprit commutedéjà sur ses tâchesde lajournée. Elle démarre la fourgonnette de service pour aller prendre livraison des nouveaux rosiers destinés àagrémenter les abords du lac artificiel, fierté du directeur, et qui a obtenu le prix dumeilleur environnementd'entreprisedelarégion.

Àmidi,ellevérifielesoldedelacarteMoneixquiluipermetdepayerlerepassansavoiràsepréoccuperdefairel'appointauxcaisses:1,23euro.Elledoitlarecharger.

Fonctionnementdelacartebancaireàpuce:authentificationdynamique.Lacarteàpucesigneelle-mêmelesdonnéesbancairesenfonctiond'unevaleuraléatoirefournieparleterminal.Celaauthentifielapuceelle-

mêmeetempêcheleclonagedescartes.©P.Guillot

Lajournéepassevite.Ellerepasseleportiqueverslasortie.C'estl'heuredesonrendez-vouschezlemédecin.Ilfaitbeau.Elledécidedeprendreunvéloenlibre-serviceavecsonpasseCirculo.

Page 19: Cryptologie Art Codes Secrets

Dossier>Cryptologie:l'artdescodessecrets Futura-Sciences

Source:http://www.futura-sciences.com/magazines/mathematiques/infos/dossiers/d/mathematiques-cryptologie-art-codes-

Page19/30

Elleavaitoublié lechangementd'adressedudocteurMaison!Sanssedémonter,elletélécharge l'application denavigationsursontéléphonequiluiindiqueralanouvelleadresseetl'itinérairepourarriveràl'heure.

LacarteUsimetlecentredediffusionpartagentunecléKipropreàchaqueabonné.Lorsd'unedemandedeconnexionauréseau,lecentred'authentificationtransmetdesdonnéesRAND,SQNetMAQ-Aquelacarte

UsimpeutcontrôleravecKi.Enretour,ellerenvoieuneréponseXRESassurantl'authenticitédel'abonné.CesdonnéespermettentégalementdecalculeruneclédechiffrementCKetunecléd'intégritéIKquiservirontàlaprotectiondesdonnéesémisesetreçuesparvoieradio.CescléssonttransmisesautéléphoneparlacarteUsimafinquecelui-cipuissechiffrerlesignaletl'assortird'unefigurefidecontrôled'intégritéàl'émission,

ainsiquedéchiffrerlesignaletencontrôlerl'intégritéàlaréception.©P.Guillot

–Puis-jeavoirvotrecarteVitalix?

Alice se laisse ausculter, et se réjouit d'avance à l'idée de soulager son nez bouché, ses démangeaisons etl'irritationinsupportabledesesyeux.

–Vousn'avezqu'unesévèreallergieaupollen,jen'airienremarquéd'autre,vousprendrezduRhumactineencasdeproductionnasaleabondante.

Alicesouritintérieurementenpensantauvocabulairemédical.

–Celafera23euros.

–Acceptez-vouslacartebancaire?

–Oui,jepréfère,même!Avoirmoinsd'espècesdansmoncabinetmerassure.Jemesuisdéjàfaitcambrioler.

Page 20: Cryptologie Art Codes Secrets

Dossier>Cryptologie:l'artdescodessecrets Futura-Sciences

Source:http://www.futura-sciences.com/magazines/mathematiques/infos/dossiers/d/mathematiques-cryptologie-art-codes-

Page20/30

Principedudécodeurdesignalaudiovisuel,lequelestcomposédeplusieursinformations:lecontenuchiffréaveclemotdecontrôleCW(ControlWord),lesmessagesdecontrôledestitresd'accèsECMetlesmessagesdegestiondestitresd'accèsEMM.LesmessagesECMetEMMsonttransmisàlacarteàpucequi,enfonctiondestitresd'accès,renvoieounonlemotdecontrôleenclairaudécodeurenvuedudéchiffrementducontenu

parl'algorithmeDVB-CSA.©P.Guillot

Deretourdanssonappartement,ellebranchesonordinateurenserappelantsoudainqu'aujourd'huiest ladatelimitepourvaliderladéclarationderevenusdufoyer.

«Unemiseàjourestdisponiblepourvotreordinateur,télécharger?»

–Encore!

Elle accepte lamise à jour, l'ordinateur redémarre. Enfin, elle valide la déclaration des revenus. Elle en profitepourcommandersurMississipi.frlasuitedesaventuresducommissaireEvenbergquiviennentdeparaître.C'estfinipourlespréoccupationsdelajournée.IlesttempsdesedétendreavecBobenallumantletéléviseur.Ilyaau programme un bon film du cinéma italien des années 1970 sur la chaîne thématique à laquelle ils sontabonnés.

Cette tranche de vie fait intervenir une quinzaine de situations au cours desquelles ont été menées une ouplusieursopérations cryptologiques. Cela montre à quel point la cryptologie a maintenant envahi notre viequotidiennesansquenousenayonsconscience.Citonstroistechniquesquiutilisentunecarteàpuce:

lavoixestchiffréesurletéléphoneportableavantd'êtretransmise;lesdonnéessontauthentifiéesavantdevaliderunetransactionparcartebancaire;leprogrammedetélévisionàpéageestcryptépourn'êtreaccessiblequ'auxabonnés.

Page9/13-Cryptologie:lejeudel'adversaire

Lejeucryptologiquecomprendunadversaireavecquiilfautcompter.Sonbutestledécryptementdesmessages, c'est-à-dire un déchiffrement sans la clé. Ce travail délicat est essentiel pour assurer lasoliditéd'unprocédé.Commel'avaitdéjàfaitremarquerCharlesBabbagedansunéchangeduJournaloftheSocietyofArts,onnepeutproposerunchiffresûrquesil'onasoi-mêmedécryptédeschiffrestrèsdifficiles.

Il est admis aujourd'hui que les substitutions simples tombent rapidement sous les coups de l'analyse desfréquences.LatechniqueutiliséeaétéexposéepourlapremièrefoisparlephilosopheetmathématicienarabeAl-

Kindi dans son traité sur l'extraction de l'obscur dès le IXe siècle. Le travail de décryptement comprend deuxphases:

Page 21: Cryptologie Art Codes Secrets

Dossier>Cryptologie:l'artdescodessecrets Futura-Sciences

Source:http://www.futura-sciences.com/magazines/mathematiques/infos/dossiers/d/mathematiques-cryptologie-art-codes-

Page21/30

l'une,quantitative,consisteàcompterlesoccurrencesdechaquecaractèredansletextedontonveutretrouverlesens;laseconde,qualitative,consisteàutiliserlaconnaissancedelalangueetl'intuition.

PortraitdumathématicienarabeAbuYusufYaqubibnIshaqal-Kindi(801–873).©Dubsahara

Le scarabéed'or, une nouvelle d'Edgar Poe parue en 1843, décrit en détail le patient travail du décrypteur. LaméthodesuitpresquemotpourmotunarticledeDavidA.Conradus,CryptographiaDenudata,paruen1842dansleGentleman'sMagazine.

CharlesBabbage,FriedrichKasiskietleursméthodesdedécryptement

Lessubstitutionspolyalphabétiquesontrésistépluslongtempsàl'analyse.IlafalluattendreleXIXesiècleaveclestravaux de Charles Babbage, puis de Friedrich Kasiski pour voir apparaître une méthode analytique dedécryptement. L'étapecrucialeest ladéterminationde la longueurde la clé.Elleestdéterminéeen repérant les

répétitionsdanslecryptogramme.CetteméthodeaétéaffinéeparWilliamFriedmanaudébutduXXesièclequiautilisé l'index de coïncidence, défini comme la probabilité de collision d'un symbole dans le cryptogramme. Cettegrandeur, significative de l'information portée par les lettres d'un texte, est connue aujourd'hui sous le nom d'«entropie de Rényi ». Elle permet de distinguer les caractères issus d'une langue naturelle d'une suite purementaléatoire.

L'adversaireest supposé toujours connaître ledétail duprocédédechiffrement.Ceprincipeaétéénoncépar lelinguisteAugusteKerckhoffsen1882,quiprônaitdesméthodesnedevantpasreposersur lesecretduprocédé,maisseulementsurceluid'unecléfacilementmodifiable.SathèsereposesurleprincipequeJean-RobertduCarletaapposécommedeviseentêtedesonouvragesur lacryptographie:Ars ipsisecretamagistro,«unartcachéaumaître lui-même», ce qui signifie qu'un chiffre n'est bonpour autant qu'il reste indéchiffrable par sonpropreinventeur.

Page 22: Cryptologie Art Codes Secrets

Dossier>Cryptologie:l'artdescodessecrets Futura-Sciences

Source:http://www.futura-sciences.com/magazines/mathematiques/infos/dossiers/d/mathematiques-cryptologie-art-codes-

Page22/30

Pagedecouverturedel’ArsipsisecretamagistrodeJean-RobertduCarlet,publiéen1644àToulouse.©Tolosana

Outre la connaissance du procédé, le jeu cryptologique fournit aujourd'hui à l'adversaire un dispositif qui réalisel'opération dedéchiffrement. Il peut l’observer, effectuer des mesures physiques, provoquer des erreurs defonctionnement,afind’enextraire lessecrets.Ilseraiteneffet indésirablequ'unlecteurdecartebancairepuisseentirerlessecrets,simplementparl'observationdesaconsommationélectrique,oudutempspasséauxcalculs.

Bancdemesurepouranalyserlaconsommationd'unecarteàpucependantlaréalisationducalculcryptographique:laconsommationdudispositifestmesuréeetmémoriséeenvued'uneanalysestatistique.

Unbancsimilairepermetdemesureravecprécisionletempsd'exécution.©P.Guillot

Par exemple, l'observation de la consommation d'une carte à puce peut révéler l'exposant privé utilisé pour undéchiffrementRSA. Fort heureusement, les fabricants de cartes ont su trouver des parades pour résister à cesattaques.

Page 23: Cryptologie Art Codes Secrets

Dossier>Cryptologie:l'artdescodessecrets Futura-Sciences

Source:http://www.futura-sciences.com/magazines/mathematiques/infos/dossiers/d/mathematiques-cryptologie-art-codes-

Page23/30

AnalysedeconsommationsurundispositifréalisantuncalculRSA.Lacourbedeconsommationpermetdediscernerassezclairementlesmultiplicationsmdesélévationsaucarréc.Celadévoiledirectementles

chiffresbinairesdel'exposantprivé.©P.Guillot

Page10/13-Cryptologieetinformatique,d'EniacàColossus

Lacryptologieet l'informatiqueont connuundéveloppementàpartirde la secondeguerremondiale.Créée par Claude Shannon, la théorie de l'information, qui a conduit à la numérisation de panstechnologiques entiers, est née de la question de savoir ce que pouvait apprendre un adversaire enobservantunecommunicationchiffrée.

LemathématicienbritanniqueAlanTuring,connupouravoirmodélisélanotiondecalculabilitéaveclamachinequiportesonnom,aeuunrôlecrucialauseindel'équipedeBletchleyPark,chargéedudécryptementdesmessagesdel’arméeallemande.

L'intérieurd'unedesmachinesélectromécaniquesEnigma,quiontserviauchiffrementdemessagesparl’arméeallemandedurantlasecondeguerremondiale.AlanTuringagrandementcontribuéàdéchiffrerce

code.©TedColes,WikimediaCommons,DP

La recherchedesclésdevenaitune tâche tropcomplexepourêtre réaliséeà lamain,et ila falluconstruiredesmachinesdeplusenpluspuissantespourtesterlesinnombrablescombinaisonspossibles.Lestechniquesmisesen

Page 24: Cryptologie Art Codes Secrets

Dossier>Cryptologie:l'artdescodessecrets Futura-Sciences

Source:http://www.futura-sciences.com/magazines/mathematiques/infos/dossiers/d/mathematiques-cryptologie-art-codes-

Page24/30

œuvrepourréalisercescalculsontcontribuédemanièrecrucialeaudéveloppementdespremiersordinateurs.

Portraitd’AlanTuringdanslesannées1940.©Criticalgamer

L'ingénieur en téléphone Tommy H. Flowers a eu l'idée d'employer des tubes à vide, récemment utilisés pour lacommutation téléphonique, afin de construire un immense calculateur, le Colossus, destiné au décryptement dutéléscripteurchiffrantallemand.

PortraitdeTommyH.Flowersdanslesannées1940.©KPBS,BBC

LecalculateurColossus

Page 25: Cryptologie Art Codes Secrets

Dossier>Cryptologie:l'artdescodessecrets Futura-Sciences

Source:http://www.futura-sciences.com/magazines/mathematiques/infos/dossiers/d/mathematiques-cryptologie-art-codes-

Page25/30

Lesprogrèsréalisésparlesmoyensdecalculsuiventuneloiempirique,appeléeloideMoore,dunomdudirecteurderecherchedufabricantaméricaindecircuitsintégrésFairchildquil'aénoncéelapremièrefoisen1965.Celle-ciaffirme que la puissance des calculateurs électroniques double tous les 18 mois, ce qui s’est vérifié jusqu'àaujourd'hui.Alorsqu'ilafalluplusde70heuresàl'ordinateurEniacpourcalculer2.000décimalesdunombreπen1949,lemoindrecalculateurembarquédansuntéléphoneportableréaliseaujourd'huicecalculenunefractiondeseconde.En1977, la revueScientificAmericanaprésenté leRSAsous l’appellation«unnouveausystèmequ'onmettraitdesmillionsd'annéesàcasser.»Pourtant, laclépubliquequ'il contenaitaété factoriséeen1994,bienavantlesdélaisannoncés!

LeColossus,premiercalculateurélectronique.©Historyblog

Cet incroyable et constant progrès rend envisageable l'application de la force brutale pour chercher la clé d'unprocédé dans des ensembles de plus en plus grands. Pourtant, c'est au chiffreur et non au décrypteur quebénéficientlesprogrèsdesmoyensdecalcul.Supposonsquel'onutilise,àunmomentdonné,desnombresde200chiffrescommemoduleRSA.Silapuissancedecalculdouble,latailledumodulepourraêtreportéeà250chiffressans que l'utilisateur constate lemoindre changement dans la rapidité du calcul. Le travail de l'adversaire pour

factoriser ce nouveaumodule suit cependant une loi donnée par la formule c(n) = exp(k(ln(n))1/3(ln(ln(n)))2/3)pourunnombredenchiffres.Cetravaildevradoncêtremultipliéparunfacteur36.Avecsapuissancedecalculqui n'aura que doublé, il aura perdu un facteur 18 dans l'affaire. Plus les machines sont puissantes, et plus ladissymétrieentrelechiffrementetl'attaquedonneunavantageauchiffrement.

Page11/13-Lathéoriedelacomplexitéencryptologie

Lacryptographiecontemporaines'appuiesurdesfonctionsàsensunique.Cesfonctionssontfacilementcalculables, mais il est pratiquement impossible, avec une valeur, de retrouver le paramètre qui aconduitàcettevaleur.Parexemple,enchoisissantdeuxgrandsnombrespremiers, ilestfaciledelesmultiplier.Actuellement,leseulproduitnepermetpourtantpasderetrouverlesfacteurssiceux-cisontchoisis assez grands. La multiplication des entiers est une fonction à sens unique. Elle est un casparticulierdesproblèmesqu'onnesaitpasrésoudre,mais,unefoislasolutionconnue,ilestaisédelavérifier.

Sijevousdonne,parexemple,ledéfidefactoriserlenombre2.027.651.281,vousaurezsansdoutebeaucoupde

Page 26: Cryptologie Art Codes Secrets

Dossier>Cryptologie:l'artdescodessecrets Futura-Sciences

Source:http://www.futura-sciences.com/magazines/mathematiques/infos/dossiers/d/mathematiques-cryptologie-art-codes-

Page26/30

malà trouver les facteurssansunoutilperformantdecalcul.Enrevanche,si jevousannoncequeces facteurssont46.061et44.021,uneminutevoussuffirapourvérifierquecettesolutionestlabonne.

Vued'artistedelamachinedeTuring(sanslatabledetransition).©Schadel,DP

Le souci est que l'existence de tels problèmes n'est pas assurée. Les chercheurs n'ont pas pu jusqu'à présentprouver que la factorisation des entiers était vraiment un problème difficile. La seule observation que nouspuissions faireestque,dans l'étatactueldenosconnaissances, ceproblèmeest loind'êtreaiséà résoudre.Denombreux et impressionnants progrès ont été accomplis depuis que lesmathématiciens s'y intéressent. Larésolution est passée en quelques dizaines d'années d'une complexité exponentielle à une complexité sous-exponentielleenfonctiondunombredechiffresdunombreàfactoriser.Lesprogrèss'arrêteront-ilslà,oud'autresprogrèssont-ilsencoreàespérer?

LamachinedeTuring

Onnesaittoujourspassic'estseulementnotreignoranced'algorithmesplusperformantsquirendlafactorisationdifficile,ousicettedifficultéestdans lanaturemêmeduproblème.LesnotionsdecalculabilitéetdecomplexitéducalculontétémodéliséesparAlanTuringdansunemachineabstraite.LamachinedeTuringcomprend:

uneunitécentraledecalculquipeutsetrouverdansunnombrefinid'états;unrubanillimitéoùfigurentaudépartlesdonnéesàtraiter,etoùs'écriventlesrésultats;cesdonnéess'exprimentàl'aided'unalphabetdetaillefinie;unetêtedelecture-écriturequipeutremplaceruncaractèreparunautresurleruban,oubiendéplacerleruband'unepositionverslagaucheouversladroite.

Schémadeprinciped'unemachinedeTuring,constituéed'unrubanillimitépouvantsedéplaceràdroiteouàgauche,d'unetêtedelecture-écritureetd'uneunitécentralecontrôlantlesactions.©P.Guillot

Page 27: Cryptologie Art Codes Secrets

Dossier>Cryptologie:l'artdescodessecrets Futura-Sciences

Source:http://www.futura-sciences.com/magazines/mathematiques/infos/dossiers/d/mathematiques-cryptologie-art-codes-

Page27/30

Leprogrammed'unetellemachineestunelisted'instructionsconstituéeschacunedequatredonnées:unétatq,unsymboles,unnouvelétatr,etuneactionadelatêtedelecture.Si lamachinesetrouvedansl'étatq,etsielle lit le symbolessur le ruban, alors elle passe dans l'étatret réalise l'actiona qui consiste soit à écrire unsymbolesurlerubanàlaplacedes,soitàdéplacerlerubandansunsensoudansl'autre.

UnemachinedeTuringestdite«déterministe»sisonprogrammenecomprendqu'uneinstructionpourunétatetunsymboledonnés.Unproblèmeappartientà laclasseP (pour«polynomial»)s'ilexisteunemachinedeTuringdéterministequi lerésoutenexécutantunnombred'instructionsbornéparunpolynômede latailledesdonnées.Unproblèmen'appartenantpasàcetteclasseseratenupourdifficile,dumoinspourcertainesdonnées.

Si,aucontraire,ilexisteplusieursinstructionspossiblescorrespondantàunétatetunsymboledonnés,lamachineestdite«nondéterministe».Unemachinenondéterministerésout leproblèmes'ilexisteunesuited'instructionsquiconduitaurésultat,autrementdits'ilexisteunoraclequiindiqueàlamachinequelleestlabonneinstructionàexécuterparmiplusieurschoixpossibles.Onpeutsimulerunemachinenondéterministeavecunnombreillimitédemachinesdéterministes, chacune choisissant l'unedes instructions à exécuter dansunétat donné.Unproblèmeappartient à la classe NP s'il existe une machine de Turing non déterministe qui le résout en un nombred'instructionsbornéparunpolynômede latailledesdonnées.Cesontprécisément lesproblèmesquisevérifientaisément,lasolutionjouantlerôled’oraclequiindiquelechoixdesinstructionsconduisantaurésultat.

Siunproblèmeappartientà laclasseP,alors ilappartientaussià laclasseNP.Undesgrandsproblèmesouvertsde la théorie de la complexité est de savoir si la classeNPest strictement plus grandeque la classe P ounon,questionquipeutserésumerainsi:existe-t-ilunproblèmeaisémentvérifiablequiestdifficileàrésoudre?

Si un tel problème existe, ce qui n'est toujours pas prouvé, la factorisation des entiers est un candidatvraisemblable.

Page12/13-Cryptologie:lesmondesd'Impagliazzo

Sansproblèmedifficile,ilnepeutpasyavoirdecryptologieautrequecelledumasquejetable.Deplus,letitulairedelaclédoitpouvoirdéchiffrerfacilementlemessage,lesproblèmesdelacryptologiedoiventdoncêtreaisémentvérifiables.

Ils doivent appartenir à la classe NP. Un problème appartenant à la classe NP sans appartenir à la classe P neconviendraitpasforcément.Onpourraitadmettrel'existenced'untelproblème,quiseraitdifficileàrésoudredansle pire des cas, mais facile en général. Ce type de problème ne permettrait pas de réaliser unecryptologieapplicable. Le cryptogramme doit être indéchiffrable quel que soit le message, et non dans le pire des casseulement.

Page 28: Cryptologie Art Codes Secrets

Dossier>Cryptologie:l'artdescodessecrets Futura-Sciences

Source:http://www.futura-sciences.com/magazines/mathematiques/infos/dossiers/d/mathematiques-cryptologie-art-codes-

Page28/30

LechercheuraméricainRussellImpagliazzoaimaginédesmondes(listésdansletexteetempiléssurlapyramidedelafiguresuivante)selonlesrésultatsfutursquelathéoriedelacomplexiténousapportera.©

UCSDCSE

Cryptomania

Cryptomaniaestlemondedanslequelnousvivonsvirtuellement.Ilexistedesfonctionsàsensuniqueavectrappe.Onpeutposerunproblèmedifficileetdonneruneindicationàcertainsseulementpourqu'ilspuissentlerésoudre.Le problème restera difficile pour les autres. C'est ce qui se passe avec la fonctionRSA : le déchiffrement estimpossible,saufpourceuxquiconnaissentlafactorisationdumodule.

Minicrypt

Cemonde imaginairepourraitdevenir réelsionpouvaitdémontrerque toute fonctionàsensuniquenepeutpasavoir de trappe. Cela remettrait en question le chiffrement àclé publique, mais on pourrait toujours signer lesdocuments. La réalisation d'une fonction de signature se contente de l'existence d'une fonction à sens unique.Danscemonde,unprofesseurpeutposerunproblèmedifficileàsaclasse,maisnepeutpasdonnerd'indicationàcertainsseulementpourlerésoudre.

Pessiland

Selon Impagliazzo, ce monde imaginaire serait le pire qui soit. Il y existe des problèmes faciles à vérifier, maisdifficiles à résoudre, et pas de fonction à sens unique. Toutes les fonctions facilement calculables y sont aussifacilementinversibles.Certainsproblèmesrestentdifficiles,maiscettedifficulténesetraduitparaucunavantagepour réaliser de la cryptographie.Dans cemonde et dans les suivants, aucune cryptologie autre que lemasquejetablen'estenvisageable.

Heuristica

Danscemonde, lesproblèmesfacilesàvérifiersontenmoyenneaussi facilesàrésoudre,mais ilpeutresterdesinstancesdifficiles.Celacommenceàêtresatisfaisantpourlesapplications.Parexemple,danslaplupartdescas,lemarchand de pommes pourra facilement choisir les fruits de son étalage afin de satisfaire un client qui lui endemandepouruncertainpoids.

Page 29: Cryptologie Art Codes Secrets

Dossier>Cryptologie:l'artdescodessecrets Futura-Sciences

Source:http://www.futura-sciences.com/magazines/mathematiques/infos/dossiers/d/mathematiques-cryptologie-art-codes-

Page29/30

Algorithmica

Cemondeest finalementceluioùP=NP.Toutproblèmefacileàvérifierest facileàrésoudre,ycomprisdans lepiredescas.

Lescinqmondesd'Impagliazzo.Cesontdesmondesimaginairesenvisageablesenl'étatactueldenosconnaissances.Ledéveloppementdelathéoriepourraitsoitlesrendreréels,soitlesfairedisparaître.Toutelacryptographie,etenparticulierlechiffrementàclépublique,appartientàCryptomaniaquiestnotremondeempiriqueactuel.LechiffrementsymétriqueetlasignatureàclépubliqueappartiennentaumondeMinicrypt.

Laseulecryptographieutilisabledanslesautresmondesestlacryptographieinconditionnellementsûre,commelechiffredeVernamavecbandealéatoire.IlestétonnantdeconstaterquelasignatureàclépubliqueappartientaumondeMinicrypt,alorsquelechiffrementàclépubliqueappartient,lui,aumondeCryptomania.

©P.Guillot

Cesmondes constituentunehiérarchiedemondespossiblesou impossibles selonque la théoriede la complexitédémontrera l'existence de problèmes difficiles ou l’infirmera en découvrant desalgorithmes efficaces pour lesrésoudre.

Page13/13-Découvrezlelivresurlacryptologie

À découvrir aux éditionsEDP Sciences,Cryptologie, l'art des codes secrets, un ouvrage de PhilippeGuillot.

Page 30: Cryptologie Art Codes Secrets

Dossier>Cryptologie:l'artdescodessecrets Futura-Sciences

Source:http://www.futura-sciences.com/magazines/mathematiques/infos/dossiers/d/mathematiques-cryptologie-art-codes-

Page30/30

Cliquezpouracheterlelivre

Lacryptologie rassemble les techniquesdestinéesàdissimuler le sensd'unmessageà toutepersonneautrequeson destinataire. Elle est restée longtemps confinée auxmilieuxmilitaires et diplomatiques. Aujourd'hui, avec lagénéralisationdestechnologiesnumériques,elleestomniprésentedansnotreviequotidienne.

Chiffrementdesmessagesetopérationscryptographiques

La présentation de Philippe Guillot s'appuie sur l'histoire de cette discipline, depuis l'Antiquité jusqu'auxdéveloppements les plus récents. Son utilisation va aujourd'hui au-delà du seul chiffrement des messages, elleinclutlasignaturenumériqueettouslesservicesquicontribuentàprotégerlesinformationspersonnelles.L'auteurexpose les opérations cryptographiques qui sous-tendent nombre de nos gestes quotidiens comme lepaiementsécuriséenligne,leretraitd'espècesauxdistributeursdebilletsoulesappelssurlestéléphonesportables.

L'ouvragedéveloppeaussi lacryptanalyse,quiseplacedupointdevued'unadversairecherchantà fairesauterles protectionsmises en place. Les attaques portent sur l'aspect logicomathématique du procédé,mais aussi àpartir des mesures physiques effectuées sur le dispositif qui réalise la protection. Un chapitre expose lesdéveloppementsrécentsd'unethéoriecryptologique,dontl'objectifestdevaliderlasécuritédesprocédésutilisés.Ledernierchapitreprésente lesperspectivesoffertespar laphysiquequantiquequi laisseentrevoirdenouveauxcalculateurspermettant,s'ilsvoyaientlejour,decasserlescodesclassiqueslespluscourants,etfourniraient,encontrepartie,unprocédéd'échangedesecretenprincipeinviolable.