Comment l`arithmétique est devenue science appliquée
Contents
1. 1917 gt Il est difficile d changer une clef avec un correspondant loign gt Surtout si l on doit recommencer l change chaque envoi gt Le chiffre de Vernam a peu t employ gt Am ricains et russes l auraient utilis sur la ligne rouge apr s la crise de Cuba 1962 Les premiers chiffrements modernes gt Principe de Kerckhoff publicit des algorithmes gt Fin des petits alphabets chiffrement par blocs Principe de Kerckhoff Auguste Kerckhoff professeur l Ecole des Hautes Etudes Commerciales crivait en 1883 dans le Journal Des Sciences Militaires si l Administration veut mettre profit tous les services que peut rendre un syst me de correspondance cryptographique bien combin elle doit absolument renoncer aux m thodes secr tes et tablir en principe qu elle n acceptera qu un proc d qui puisse tre enseign au grand jour dans nos coles militaires que nos l ves seront libres de communiquer qui leur plaira Le principe de Kerckhoff pourquoi gt On ne peut jamais garantir qu un secret sera pr serv gt Les algorithmes de chiffrement et de d chiffrement sont publics mais Alice et Bernard partagent une clef secr te gt Il est plus facile de changer de clef que d algorithme de chiffrement gt La publicit de l algorithme est le meilleur moyen de s assurer de sa robustesse Le chiffrement par blocs gt Les pages pr c dentes ont mis2. par la permutation inverse 1_ ABCDEFGHIJKLMNOPQRSTUVWXYZ EGUCDFVMNZXSWRHJYPTVCKQLBI D cryptage du chiffrement par substitution On essaie toutes les clefs gt Nombre de clefs 26 1 x 2 x 3 x x 26 403291461126605635584000000 gt Mais il est assez facile de d crypter en analysant les fr quences d occurences des caract res Une attaque redoutable l analyse des fr quences Al Kindi 801 873 Premi re page du manuscrit de Al Kindi sur le d chiffrement des red LAS TETE MEN iar ale ree ice 1h ous Do SULS Moss bo pia the oA sijaa vers a COPA re siie HAS Peer tae rar Gel rast The first page of al Kindi s a manuscript On Deciphering Cryptographic Messages containing the oldest known description of cryptanalysis by frequency analysis messages cryptographiques par analyse des fr quences Fr quences d occurence des lettres en fran ais Fr quences d apparition des lettres en fran ais 5 10 15 20 25 Le A le pic du E le I et les bosses LMNOP et RSTUV D cryptage d un chiffrement par substitution On utilise les informations statistiques sur les occurences de certains assemblages de lettres gt Le E l emporte de loin gt Les lettres les plus fr quentes sont ensuite 0 A I gt bigrammes les plus fr quents ES DE LE gt Lettres doubl es les plus fr quentes EE SS LL gt La connaissance de ces informations l habilet et l intuition fais
3. 15 20 25 Histogramme des fr quences du Cryptograme 4 0 La premi re lettre de la clef est 11 4 7 H Calcul de la longueur de la clef d un chiffre de Vigen re gt Nous venons de voir que si l on connait la longueur de la clef l analyse des fr quences permet de d crypter facilement un cryptogramme gt Le d cryptage du chiffrement de Vigen re se r duit donc la d termination de la longueur de la clef Il suffit de recommencer ce que l on vient de faire en essayant les longueurs de clef 2 3 4 jusqu obtenir le texte clair Les derniers chiffrements par substitution gt La machine l ctrom canique Enigma con ue en 1918 par Arthur Scherbius sera utilis e par l arm e allemande partir de 1926 Son chiffrement tait un renforcement du chiffre de Vigen re gt Les cryptanalystes eurent le plus grand mal d crypter ses messages Les premiers succ s sont d s au polonais M Rejewsky dans les ann es 1930 Peu avant l invasion de la Pologne Rejewsky transmet ses informations aux fran ais et britanniques gt Pendant la 2 guerre mondiale le gouvernement britannique tablit Bletchley Park une importante quipe 7 000 personnes r unissant des math maticiens des logiciens comme Turing des linguistes et m me des cruciverbistes gt Sous la direction d A Turing et l aide de gros calculateurs lectrom caniques puis lectroniques ils vinrent bout des chiffrements pro
4. en vidence les dangers des substitutions alphab tiques sur de petits alphabets gt Elles ouvrent une br che au cryptanalyste l analyses des fr quences d occurences des caract res gt En cryptographie moderne l unit de chiffrement n est pas la lettre On commence par regrouper les caract res du message chiffrer en blocs d une taille fixe gt On remplace ainsi l alphabet des caract res par l alphabet des blocs gt Le nombre de lettre de l alphabet est tout petit mais le nombre de blocs d une taille donn e est grand Pour une taille de bloc de 16 octets soit 128 bits le nombre de blocs diff rents est PE lie gt L analyse des fr quence devient consid rablement plus difficile Transformer un message en une suite de blocs D coupons le message MAITRE CORBEAU SUR UN ARBRE en blocs de 4 charact res ou en base 2 01001101 01000001 01001001 01010100 En juxtaposant ces 4 nombres on obtient l criture binaire d un entier 01001101010000010100100101010100 dont l criture d cimale est 1296124244 Le message est de cette fa on transform en une suite d entiers L algorithme de chiffrement va transformer chacun des ces entiers en un autre entier 2 American Standard Code for Information Interchange Chiffrements sym triques modernes D E S et A E S En 1973 le N B S lance un appel d offres pour un chiffrement public a clef secr te qui donne naissance en 1976 au protocole domin
5. gt L exponentiation modulaire x g est un cadenas Calculer x partir de g est le probl me du logarithme discret 5 Ici p n est pas tr s grand et x 3448023049106610243104979 Un autre cadenas gt Soit p et q deux nombres premiers de 150 chiffres Il est facile de calculer N px4 gt Mais partir de la seule donn e de N aujourd hui personne n est capable de retrouver p et q gt La fonction p q gt pq est le cadenas qui est la base du syst me R S A Le tournant des ann es 1975 1980 Au d but des ann es 1970 gt Chiffrements rapides et surs avec D E S puis A E S gt condition de partager une clef avec chaque correspondant gt De plus en plus d echanges de plus en plus lointains gt Le probl me du partage de clef devient inextricable Diffie et Hellmann apportent deux solutions ce probl me gt Le protocole de Diffie Hellman Il est possible d changer un clef secr te au moyen d une conversation que tout le monde peut entendre gt La cryptographie asym trique clef de chiffrement publique clef de d chiffrement secr te 1999 2000 2000 1999 6 Institute of Electrical and Electronics Engineers Le protocole de Diffie Hellman ou comment changer un secret sur une place publique gt Alice et Bernard d sirent partager une clef secr te Eve intercepte toutes leurs conversations gt Le probl me semble insoluble gt W Diffie et M Hellman propos
6. 9 7 6 5 0 L exponentiation modulaire L op ration arithm tique la plus utilis e en cryptographie moderne est l exponentiation modulaire m u et b sont trois entiers II s agit de calculer u mod m c est dire le r sultat de la multiplication modulo m de u par lui m me r p t e b fois Si m 10 u 7 et b 3 Modulo 10 on obtient successivement eu ES Oe a a x 08 Pour de grandes valeurs de u b m quelques centaines de chiffres d cimaux il est absolument exclu d effectuer b multiplications Comment faire Multiplication du pauvre Pour multiplier 19 par 37 n m N A O O 37 74 148 296 592 19 x 37 37 74 592 703 Ecriture d cimale de 2357 Comment obtenir les chiffres de l criture en base 10 de 2357 2357 235 23 2 N ON gt droite le reste de la division par la base 10 gt Au dessous le quotient de la division par 10 Ecriture binaire de 19 Comment obtenir les chiffres de l criture en base 2 de 19 Au lieu de diviser par 10 on divise par 2 NA Es Of 19 1x16 0x8 0x441x241 Explication criture binaire de 19 Revenons la multiplication du pauvre en ajoutant deux colonnes 19 1 il Sif 9 1 2 74 4 0 4 148 200 8 296 il i te 592 Voila l explication 19 1 2 16 L algorithme d exponentiation modulaire Pour calculer 3719 mod 100 dans la derni re colonne on remplace t 2t par t t modulo 100 19 9 4 2 1 37 m
7. Cryptographie Comment l arithm tique est devenue science appliqu e Marc Del glise Universit Ouverte Lyon 1 Des math matiques tout autour de nous 18 octobre 2012 Biblioth que Marie Curie INSA de Lyon Les vraies math matiques n ont aucun effet sur la guerre Personne n a encore trouv un objectif militaire qui serait d pendant de la th orie des nombres G H Hardy The Mathematician s Apology 1940 Vocabulaire gt Chiffrer un message c est le rendre incompr hensible au non destinataire Un cryptogramme est un message chiffr gt D chiffrer le cryptogramme c est retrouver le message clair l aide du mode d emploi C est la t che du destinataire r gulier gt D crypter le cryptogramme c est retrouver le message clair sans disposer du mode d emploi C est le travail de l espion gt Les cryptographes con oivent les syst mes de chiffrement gt Les cryptanalystes sont les sp cialistes du d cryptement L histoire de la cryptographie est celle de la lutte opposant cryptographes et cryptanalystes qui sont souvent les m mes personnes Il y a un peu plus de 2000 ans le chiffrement de C sar Soit l alphabet ABCDEFGHI JKLMNOPQRSTUVWXYZ C sar choisit une clef par exemple la clef C Le chiffrement est le d calage qui envoie A sur C le d calage de 2 DEMAIN MATIN A LYON FGOCKP OCVKP C NAQP D chiffrement et d cryptage du Chiffre de C sar gt D chiffrement Le destinatair
8. GUMTGUMTGUMTGUMTGUMTGUM AUCLAIRDELALUNEMONAMIPIERROT Chiffrement de Vigen re D cryptage gt Le chiffrement de Vigen re a t consid r comme ind cryptable pendant pr s de 300 ans gt C Babbage et F Kasiski on cass ce chiffrement 1850 D cryptage de Vigen re longueur de clef connue Si la longueur de la clef est connue le d cryptage est tr s simple D cryptons le cryptogrammme suivant chiffr avec une clef inconnue mais de longueur connue 4 TUOHYYICYVKOBMAFBHGFILKDLLIVLNKBHCZSUMUBIYIIUZXC TUMSTUOHY YXSUUXRWUXZVXKIYURZLWNSSOOHPHZOWYADYYYQ LFGBNUMSOYHCUDUIYGUBZCKIYXAQVLHSHOWILPUIZYZSZDUZ PKASCIAGTYYSTVRSGVKOBMGBZGKBACXGPPUHYYXOTUMSZYXO WJUFAYGJVNXSWFAAHAKJVOYSAYYZLJNSUCDRLMNCAYYRLWKG IIOGHWKGTIZGSYICYVKOBHKGLMKBAJGGKYPCPYKHWIAFTITH YYXGHVKZSYBCPROZVOBFLOTZHLMSIYIZHCYGLNUAIYXGHJXC PYRSYYTOYXYSUMGWZCZSAXOHTITPVHSCUMOSBLGDWLKBLTWI LNUIAZROANKIYPOHHODRLJKBZXKQLFAWXOOZLWUIAYISANKZ LWUBCUAHICKBBHLFVGGULMGBZXUIAYRSJIXPLUAVVHZSBRKH JITTBMPIYUSOPMABWYAHHLJEBITBLFEDYYTRYUOHWF AG D cryptage de Vigen re avec clef de longueur 4 Cryptogramme 4 0 de 4 en 4 partant du rang 0 TYYBBILLHUIUTTYUWVYLSPWYLNOUYZYVHLZZPCTTGBZAPYTZ WAVWHVALULALIHTSYBLAKPWTYHSPVLHIHLIHPYYUZATVUBWL LAAYHLZLXLAALCIBVLZAJLVBJBYPWHBLYYW Puisque la longueur de clef est 4 ce cryptogramme s obtient en ajoutant chaque lettre du message clair la premi re lettre de la clef C est donc un chiffrement de C sar naomb Ne 5 10
9. M photon polaris vers la gauche Pour coder le 0 SNo elle envoie un photon polaris vers la droite Bernard utilise un polariseur d axes obliques Alice et Bernard partagent un mot sur l alphabet 0 1 gt Alice choisit x1 x2 x2000 l ments de 0 1 gt Pour chaque i 1 2000 elle choisit au hasard l un des 2 protocoles ou B et transmet x en utilisant ce protocole gt Bernard ne connait pas les choix d Alice Il est r duit pour chaque choisir au hasard A ou B Il re oit ainsi y qui est gal x si Bernard a fait le bon choix Sinon c est avec quiprobabilt x ou 1 x gt Quand la transmission des 2000 quBits est termin e sur une ligne t l phonique ordinaire Alice envoie Bernard la liste des protocoles utilis s Bernard lui r pond en donnant les valeurs de i pour lesquelles il a fait le bon choix gt La clef partag e par Alice et Bernard est la suite des x yj restreinte ces valeurs de de longueur environ 1000 Que se passe t il si Eve espionne la transmission gt Si Eve interpose un polariseur sur le trajet du photon une fois sur deux elle choisit la mauvaise orientation ce qui une fois sur deux modifie la polarisation du photon gt Il ne lui est donc pas possible de r mettre Bernard un photon identique l original Un fois sur deux elle fera suivre Bernard un signal oppos celui qu elle a re u gt Au cours de leur conversation
10. aient la qualit du cryptanalyste dans les si cles pass s Jusqu la deuxi me guerre mondiale les bureaux du chiffre employaient des linguistes des rudits ou m me des cruciverbistes D cryptage graphique d un chiffre de C sar Histogramme d un message chiffr par C sar La clef est 14 4 10 K Chiffrement de Vigen re gt Au XV si cle les chiffrements utilis s reposaient essentiellement sur la substitution gt Malgr quelques perfectionnements les cryptanalystes les brisaient de plus en plus facilement L avantage tait du c t des cryptanalystes gt Reprenant des id es de Leon Battista Alberti 1467 puis de Giovan Battista Bellaso 1550 le diplomate fran ais Vigen re publie son Trait des chiffres en 1586 Chiffrement de Vigen re le chiffrement gt La clef secr te est un mot Choisissons la clef HUGO gt Les lettres successives du message sont chiffr es par la m thode de C sar avec les clefs successives HUGOHUGOH Alice chiffre en effectuant lettre par lettre les additions AUCLATRDELALUNEMONAMIPIERROT HUGOHUGOHUGOHUGOHUGOHUGOHUGO HOIZHCXRLFGZBHKAVHGAPJOSYLUH Chiffrement de Vigen re D chiffrement Comme le chiffrement en rempla ant la clef par son oppos e HUGO 7 20 6 14 L oppos de HUGO est TGUM TGUM 19 6 20 12 AAAA 0 0 0 0 Bernard d chiffre le message re u d Alice en effectuant les additions HOIZHCXRLFGZBHKAVHGAP JOSYLUH TGUMT
11. ant des ann es 1980 2000 le protocole D E S gt Clefs de 56 bits Chiffrement par blocs de 8 charact res 64 bits Aujourd hui avec de puissants moyens de calcul on peut d crypter un message chiffr l aide de D E S en quelques jours 1997 Un nouvel appel d offres du N S T4 conduit l adoption en 2001 de A E S gt Robuste et impl mentable sur toutes sortes de machines gt Assez rapide il chiffre couramment 10 Mo par seconde 3 National Bureau of Standards 4 National Institute of Standards and Technology La situation de la d c nnie 1970 1980 v On ne chiffre plus lettre par lettre mais par bloc de quelques dizaines ou centaines de bits v Les algorithmes sont publics v Chiffrements rapides et surs v A condition de partager une clef avec chaque correspondant v De plus en plus d echanges de plus en plus lointains v L change de clefs devient un probl me s rieux La multiplication modulaire gt R duire un nombre modulo m c est le remplacer par le reste de sa division par m gt Effectuer la multiplication modulo m de x par y c est multiplier x par y puis r duire le r sultat modulo m gt Si mest un entier gt 1 on note Z l ensemble des entiers r duits modulo m muni de la multiplication modulo m Par exemple Zio est l ensemble 0 1 2 3 4 5 6 7 8 9 muni de la multiplication modulo 10 Voici quelques multiplications dans Z10 3 2 6 3
12. c d permettant de garantir que l exp diteur est bien Alice C est ce qu on appelle un algorithme de signaure Tout syst me de chiffrement deux clefs fournit en prime un algorithme de signature La situation aujourd hui v Il n y a plus de probl me d change de clef v Le probl me de signature a une solution simple v Les chiffrements clef publique sont lents environ 1000 fois plus lents que A E S v Ce n est pas g nant car pour envoyer un message 1 On partage une clef sym trique c par un proc d lent RSA ou Diffie Hellman 2 Le message proprement dit qui peut tre long est crypt avec un chiffrement sym trique rapide commes A E S en utilisant la clef secr te partag e c Le futur Remplacement des ensembles Zm par des courbes elliptiques gt La cryptographie quantique Zp est il indispensable gt Si G est un groupe dont un l ment g est fix Le probl me du logarithme discret en base g est Soit u g Calculer x en ne connaissant que g et u gt Les protocoles actuels utilisant le probl me du logarithme discret modulo p peuvent tre remplac s par des protocoles bas s sur les logarithmes discrets sur le groupe constitu des points d une courbe elliptique Les courbes elliptiques gt Une courbe elliptique est une courbe sans points singuliers d finie par une quation P x y 0 o P est un polyn me de degr 3 La courbe de droite a un poin
13. duits par Enigma et ses perfectionnements Un exemplaire de la machine Enigma 1944 Premi re machine l ctronique et non plus lectrom canique Conclusion sur les chiffrements alphab tiques Le talon d Achille commun tous les proc d s de chiffrement alphab tique est la petite taille des alphabets utilis s L alphabet source et l alphabet de chiffrement sont constitu s d au plus quelques dizaines de caract res Ceci permet au cryptanalyste d analyser les fr quences d occurences de certains caract res ou petits groupes de caract res et d identier de courts extraits du message clair Une exception le chiffrement de G Vernam 1917 G Vernam ing nieur l A T T la propos en 1917 de chiffrer un message par la m thode de Vigen re avec une clef al atoire de m me longueur que le message DEMAINNEUFHEURESALYON HUDECJHETONLACDEPKGSQ KYPEKWUICTUPUTHWPVEGD DEMAINDIXHEURESAPARIS HUDECJRAFMQVDPPWAVNYL KYPEKWUICTUPUTHWPVEGD 1 American Telegraph amp Telephon Le chiffre de Vernam est parfait mais difficilement utilisable gt gt gt gt Ceci montre qu un m me texte chiffr peut tre le chiffrement de n importe quel message clair en choisissant convenablement la clef Ce proc d de chiffrement est donc parfait A condition de ne pas r utiliser la clef Et d utiliser une clef al atoire Pourquoi l histoire de la cryptographie ne s est elle pas achev e en
14. e effectue le d calage inverse de celui utilis pour chiffrer gt Le d cryptage est un jeu d enfant car l ensemble des clefs est tr s petit On essaie successivement les 26 clefs possibles D cryptons C FHOCKP gt Clef A C FHOCKP C FHOCKP gt Clef B C FHOCKP B EGNBJO gt Clef C C FHOCKP A DEMAIN Un peu darithm tique C sar et l addition modulo 26 Num rotons les lettres de 0 25 Nj GD ee WMO A 1 2 8 amp amp GO oon A Bl QB BE Ws Le chiffrement de C sar agit sur les num ros 0 i123 4 5 6 20 21 22 23 24 25 Aa amp amp O6 Ff soo 2 2 22 MD C 1 Le rang du chiffrement de X s obtient en ajoutant 2 au rang de X et si le r sultat est gt 26 on en retranche 26 Cette op ration s appelle addition modulo 26 D chiffrement du Chiffre de C sar et addition des lettres On chiffre en ajoutant la clef on d chiffre en soustrayant la clef c est dire en ajoutant l oppos de la clef 26 0 A donc l oppos de C est Y Y C 24 2 DEMAIN A LYON FGOCKO C NAQP CCCCCC C CCCC ON DONNE NON FGOCKO C NAQP DEMAIN A LYON Chiffrement par substitution alphab tique La clef secr te est une permutation o des 26 lettres de l alphabet Fes ABCDEFGHIJKLMNOPQRSTUVWXYZ GYDEAFBOZPVXHIURWNLSCTMKQJ Pour chiffrer un message on applique la substitution chacune des lettres de ce message DEMAIN A LYON EAHGZI G XQUI On d chiffre en rempla ant
15. ent en 1976 une solution simple Voici le dialogue d Alice et Bernard gt Alice p 30967624360979079013 g 11595598273653509247 gt J ai choisi secr tement a et calcul A g mod p A g 23606831717615331161 gt Peux tu choisir en secret b et me donner la valeur de B g gt Bernard Voici ma r ponse B 14308194949994250745 gt Alice Calcule A pendant que de mon c t je calcule B C est le secret que nous partageons car modulo p A ey ge g B Que peut faire Eve v Elle connait A B p et g Elle ne connait pas ab Comment trouver g v gt On ne voit pas A moins de savoir calculer les logarithmes en base g v Car dans ce cas partir de A g on calcule a puis de m me b partir de B g Ce protocole permet il de communiquer gt Remarquons que ni Alice ni Bernard ne connait a priori le secret partag gt Le protocole de Diffie Hellman lui tout seul ne permet pas d changer des informations gt permet d obtenir une clef secr te puis de l utiliser pour chiffrer des messages l aide par exemple de A E S Les chiffrements clef publique Diffie publie en 1975 un article dans lequel il propose le d veloppement de nouveaux syst mes de chiffrement gt Pourquoi la s curit du chiffrement devrait elle n cessairement reposer sur la partage par Alice et Bernard d une clef secr te gt semblait
16. n des entiers o du calcul d un logarithme discret Mais la superposition quantique est tr s fragile L ordinateur quantique n est peut tre qu un r ve Cryptographie quantique gt Si l ordinateur quantique est encore lointain la cryptographie quantique est d ja presque r alit gt Alice et Bernard utilisent le protocole de Vernam La polarisation d un photon et sa mesure gt Un photon se propageant dans la direction de l axe Oz peut tre polaris selon un axe quelconque du plan x0y Les lois de la physique quantique ont des repercussions drastiques sur la mesure de la polarisation gt Pour mesurer la polarisation d un photon on est oblig de choisir a priori deux directions perpendiculaires Apr s la mesure le photon sera polaris dans l une ou l autre de ces 2 directions gt Le seul cas o la mesure n affecte pas la polarisation du photon est le cas o celui ci tait d ja polaris selon l une des deux directions de l appareil de mesure Transmettre un quBit Les protocoles et B Protocole Alice emet un photon polaris FU S verticalement ou horizontalement Pour coder le 1 a ee Alice envoie un photon polaris verticalement P Pour coder le 0 elle envoie un photon polaris Le horizontalement Bernard utilise un polariseur d axes vertical et horizontal Protocole B Alice emet un photon polaris A 7 obliquement Pour coder le 1 Alice envoie un CoO o
17. od 100 372 mod 100 692 mod 100 61 mod 100 212 mod 100 87 60 A En multipliant les l ments non ray s de la derni re colonne on obtient modulo 100 3719 37 x 372 x 3716 37 x 69 x 41 73 Co t de l exponentiation modulaire 1 000 000 000 000 gt Pour calculer u mod m il suffit d environ 70 multiplications gt En r alit il faut tenir compte du fait que le co t d une multiplication d entiers de m me taille est proportionnel au carr de leur taille gt Si on remplace m par un entier 10 fois plus long le temps de calcul est multipli par 10 x 10 x 10 1000 Zp poss de un g n rateur lorsque p est premier Consid rons l l ment g 5 de Z7 0 1 2 3 4 5 6 Partons de 1 et multiplions par g en n oubliant pas de r duire le r sultat modulo 7 chaque fois T5 ANG 23 On obtient tous les l ments non nuls de Z7 On dit encore que 5 est un g n rateur multiplicatif de Z7 On d montre que chaque fois que p est un nombre premier Zp poss de au moins un g n rateur multiplicatif L exponentiation modulaire est un cadenas 4867276362311402684918941 est un nombre premier et 2 un g n rateur multiplicatif de Zp Comment calculer x tel que modulo p on ait 2 10 q P R ponse On ne sait pas si p a plus de 200 chiffres d cimaux gt A partir de x on calcule facilement u 2 mod p gt Impossible de revenir en arri re i e retrouver x partir de u
18. que personne n avait encore imagin qu on puisse s carter de ce sch ma 7 Selon le gouvernement anglais la cryptographie publique a t invent e par James Ellis au d but des ann es 1970 Mais son travail tait alors couvert par le secret Cryptographie deux clefs Voici la proposition de Diffie gt Chaque individu dispose d une clef publique c et d une clef priv e k gt Deux algorithmes publics Chiffre et Dechiffre Chiffre c x y et Dechiffre k y r x gt Les clefs publiques c sont disponibles sur un annuaire gt Si ca est la clef publique d Alice pour lui adresser le message x on lui envoie le cryptogramme y Chiffre c x gt Avec sa clef secr te ka Alice obtient x Dechiffre k y Chiffrement de Rivest Shamir et Adleman 1977 C est le premier syst me de chiffrement deux clefs qui se soit impos II est le plus utilis aujourd hui gt Les clefs publique et priv e d Alice sont Co Noe et kd N pq est le produit de deux grands nombres premiers p et q ed 1 est un multiple de p 1 q 1 gt Le chiffrement est l application x gt x mod N gt Le d chiffrement est l application y y mod N Signature Qui m envoie ce message Bernard banquier d Alice re oit ce message Veuillez pr lever 10 000 sur mon compte et exp dier cette somme mon adresse Alice 18 rue des Tilleuils L exp diteur est il Alice ou Eve Il faut un pro
19. s mais remplaceront les algorithmes actuels dans un futur proche Physique quantique Les grandeurs de la physique classique la position d un objet sa vitesse ont tout instant une valeur d termin e susceptible d tre mesur e avec une pr cision arbitraire sans que cette mesure n affecte sensiblement l tat de l objet l chelle microscopique les objets satisfont les lois de la physique quantique qui sont contraires notre intuition La superposition quantique Tant que l on ne cherche pas mesurer une grandeur cette grandeur n a en g n ral pas de valeur d termin e Comme si l objet flottait entre diff rents tats On dit que l objet est dans un tat de superposition chaque mesure est associ un ensemble d tats et la mesure force l objet consid r choisir de mani re al atoire l un de ces tats En particulier imm diatement apr s une mesure l objet n est plus dans un tat de superposition L ordinateur quantique mythe ou r alit On peut envisager la construction de circuits logiques quantiques semblables aux circuits logiques la base des ordinateurs classiques Mais gr ce au ph nom ne de superposition ces circuits seraient susceptibles d effectuer en parall le tous les calculs qu un circuit classique ne pourrait effectuer que les uns apr s les autres L ordinateur quantique rendrait caducs tous les protocoles actuels bas s sur la difficult de la factorisatio
20. t l phonique Alice et Bernard apr s avoir chang la liste des num ros des bons choix de Bernard s assurent sur un chantillon de valeurs de pour lesquelles Bernard a fait le bon choix qu on a bien x y Si ce n est pas le cas c est que Eve a brouill la communication R alisabilit de la cryptographie quantique Un photon est un objet tr s fragile et pour le moment on ne peut pas transporter un photon sur plus de quelques dizaines de kilom tres Mais des chercheurs travaillent la r alisation de r p teurs quantiques qui rendraient viable la cryptographie quantique grande distance 8 La situation n est pas encore fig e un article r cent 2 pr sente une attaque contre ce proc d de chiffrement 8 Un r p teur quantique n est en theorie pas plus complexe qu un ordinateur quantique a 2 quBits 9 Hacking commercial quantum cryptography systems by tailored bright illu mination Nature Photonics 4 686 689 2010 Conclusion g n rale gt On ne peut pas pr juger de l applicabilit de la recherche fondamentale gt L arithm tique beaucoup apport la cryptographie gt Inversement les probl mes pos s par la cryptographie on revivifi des domaines math matiques d j anciens comme l tude des courbes elliptiques en y apportant nouveaux points de vue et des nouvelles questions Bibliographie gt Histoire des codes secrets Simon Singh J C Latt s 1999 Traduction par Ca
21. t singulier rx x ox gt Th or me on peut munir chaque courbe elliptique d une addition des points qui fait de cette courbe un groupe commutatif Additions sur la courbe r elle y x 1 x x 6 A B B U U U Courbe y x 1 x x 2 sur Z23 10 F 10 e ee e P 2P 9P 4p e e ee e 7P e 6P 1 e L 5 10 15 e ee e e 5P e e 8P e ee 11P 10P 3P Les coordonn es des points sont des l ments de Zo3 au lieu d tre des r els Il n y a plus d interpr tation g om trique de l addition On calcule la somme de deux points avec les m mes formules que dans le cas r el Les courbes elliptiques sonts plus conomiques gt Le calcul d un logarithme discret dans Zp est difficile mais il existe des algorithmes de calcul du logarithme discret fonctionnant pour les valeurs de p mod r ment grandes C est pourquoi les protocoles cryptographiques bas s sur le probl me du logarithme discret dans Zp n cessitent de grandes valeurs de p pour se prot ger des attaques environs 200 chiffres d cimaux gt Pour le calcul du logarithme discret sur une courbe elliptique on ne connait pas d algorithme efficace m me pour des valeurs de p moyennement grandes Pour le m me niveau de s curit il suffit donc d utiliser des nombres plus petits ce qui permet des calculs plus rapides gt Les algorithmes utilisant les courbes elliptique ne sont pas encore utilis
22. therine Coqueret de The Code Book gt Histoire des codes secrets LGF Livre de Poche 2001 Compl ment Chiffrement asym trique et signature Alice s pare le corps du texte x et sa signature s x Veuillez pr lever s Alice 18 rue des Tilleuils 1 Elle commence par d chiffrer s et obtient s Dechiffre k s 2 Elle chiffre normalement x et s envoie Bernard les cryptogrammes y Chiffre cp x et t Chiffre cz s1 3 Bernard les d chiffre et retrouve x Dechiffre kp y et s Dechiffre k t 4 Enfin il chiffre s avec la clef publique d Alice et obtient Chiffre c s1 Chiffre c Dechiffre k s s Alice est bien l exp diteur car pour construire sj il faut utilser ka que seule Alice connait
Download Pdf Manuals
Related Search