Cryptographie - Exo7 - Cours de mathématiques [PDF] exercice chiffrement de césar
[PDF] livre mathématiques pour l'ingénieur
[PDF] mathématiques pour les sciences de l'ingénieur - t
[PDF] exercice excel 2010 avancé
[PDF] exercice excel debutant pdf
[PDF] exercices excel avec corrigés pdf
[PDF] exercice excel 2013 pdf
[PDF] exercice complément du nom cm2
[PDF] les expansions du nom cm1
[PDF] le fait divers définition
[PDF] test de niveau français a1
[PDF] controle fonction de reference seconde
[PDF] généralités sur les fonctions + exercices corrigés
[PDF] définition musculation eps
[PDF] test admission advf
[PDF] livre mathématiques pour l'ingénieur
[PDF] mathématiques pour les sciences de l'ingénieur - t
[PDF] exercice excel 2010 avancé
[PDF] exercice excel debutant pdf
[PDF] exercices excel avec corrigés pdf
[PDF] exercice excel 2013 pdf
[PDF] exercice complément du nom cm2
[PDF] les expansions du nom cm1
[PDF] le fait divers définition
[PDF] test de niveau français a1
[PDF] controle fonction de reference seconde
[PDF] généralités sur les fonctions + exercices corrigés
[PDF] définition musculation eps
[PDF] test admission advf
Cours numero 6 :
Arithmetique et cryptographie
1 Introduction
Si l'on m'avait demande quand j'etais jeune chercheur, dans les annees1970, a quoi servaient les nombres premiers dans la vie courante, j'aurais
repondu sans hesiter, a rien, et j'aurais peut-^etre ajoute comme un de mes vieux collegues, un peu bougon1, qu'en tout cas ils ne servaient pas a faire
la bombe atomique. En fait, j'aurais dit une b^etise, puisque les nombres premiers, avec le code RSA, jouent maintenant un r^ole de premier plan dans tous les secteurs de la communication, de la nance, etc. et que parmi leurs principaux utilisateurs se trouvent justement ... les militaires.2 La cryptographie
La cryptographie (du greccrypto, cache etgraphie, ecrire) est la science des codes secrets. Elle remonte a l'antiquite et Jules Cesar l'a employee pour coder ses messages. Il utilisait le systeme le plus simple, celui des alphabets decales d'un ou plusieurs crans (ou l'on remplace, par exemple,AparB,B parC, etc). Ainsi peut-on penser qu'il envoya au senat, apres sa victoire sur Pharnace a la bataille de Zela, le message suivant : TCLG TGBG TGAG. Bien entendu des methodes beaucoup plus sophistiquees ont ete inventees depuis. Le plus souvent ces methodes utilisent le principe suivant. On code les lettres de l'alphabet de A a Z par les nombres2de 1 a 26. On traduit
le message en chires. Par exemple si le message est A L'AIDE il devient1 12 1 9 4 5. Ensuite on permute les nombres de 1 a 26 selon une certaine
regle. On obtient par exemple ici 25 14 25 17 22 21 avec une regle tres simple que je vous laisse deviner3. On retraduit alors le message en lettres et on
a YNYQVU. On notera que dans ce message on voit tout de suite qu'une1. Un indice : lui aussi a ecrit un cours d'algebre.
2. Dans la realite on utilise plus de symboles, par exemple ceux du code ASCII.
3. Une methode tres simple de codage consiste a transformer l'entierzvariant entre 1
et 26 enaz+baveca;bentiers etapremier a 26, et a reduire ce nombre modulo 26, voir ci-dessous. 1 lettre intervient deux fois (leY, traduction deA). Le defaut de ce genre de methodes est dans cette remarque : elles ne resistent pas au decryptage par analyse de frequences qui consiste a identier quelles sont les lettres qui interviennent le plus. C'est d'ailleurs ainsi que Marie Stuart, princesse ecossaise, reine de France (1559-1560) puis d'Ecosse, a peri. En eet, elle etait l'ennemie de la reine d'Angleterre Elisabeth premiere et elle fut capturee par elle en 1568. En 1586 elle participe de sa prison a un complot contre Elisabeth et communique avec ses partisans au moyen de messages codes. Mais ceux-ci sont interceptes par les anglais et son code est decrypte par Thomas Phelippes. Marie est accusee de complot, condamnee et decapitee en 1587. Ce procede est explique dans la nouvelle d'Edgar Poe :Le scarabee d'or. Il s'agit de dechirer un grimoire ecrit par le capitaine Kidd, qui indique ou se trouve le tresor cache par les pirates. Voici ce message :53zz+305))6*;4826)4z4z);806*;48+8 960))85;1z(; :+*8+83(88)5*+
;46(;88*96 *?;8)*z(;485);5*+2 :*z(;4956*2(5*-4)8 98*;4069285);)6 +8)4zz;1(z9;48081;8 :8z1;48+85;4)485+528806*81(z9;48;(88;4 (z?34;48)4z;161; :188;z?;
Le heros de l'histoire, William Legrand, apres avoir determine que le message est en anglais, part de la remarque que, dans cette langue, la lettre la plus frequente est leE, ce qui lui donneE= 8. Il continue ainsi de proche en proche (notamment en identiant la suite de caracteres ;48 comme l'article THE). Par cette methode, vous devez reussir a dechirer le message ci-dessous 4:ONYPAUNKPZPOLOPFYH
en sachant qu'en francais les lettres statistiquement les plus frequentes sont, dans l'ordre, E, puis S et A, puis R, I, N et T, puis U, puis O et L, etc. Bien entendu on peut parfois avoir quelques surprises comme avec le texte suivant : Un voisin compatissant l'accompagna a la consultation a l'h^opital Cochin. Il donna son nom, son rang d'immatriculation a l'Association du travail. On l'invita a subir auscultation, palpation, puis radio. Il fut d'accord. On l'informa : sourait{il? Plus ou moins, dit{il. Qu'avait{il? Il n'arrivait pasa dormir? Avait{il pris un sirop? Un cordial? Oui, il avait, mais ca n'avait4. Indication permettant de raccourcir notablement le travail : le codage est de la forme
x7!ax+bmodulo 26. 2 pas agi. Avait{il parfois mal a l'iris? Plut^ot pas. Au palais? Ca pouvait; Au front? Oui. Aux conduits auditifs? Non, mais il y avait, la nuit, un bourdon qui bourdonnait. On voulut savoir : un bourdon ou un faux-bourdon?Il l'ignorait.
Il fut bon pour l'oto-rhino, un gars jovial, au poil ras, aux longs favoris roux, portant lorgnons, papillon gris a pois blancs, fumant un cigarillo qui puait l'alcool. L'oto-rhino prit son pouls, l'ausculta, introduisit un miroir rond sous son palais, tripota son pavillon, farfouilla son tympan, malaxa son larynx, son naso{pharynx, son sinus droit, sa cloison. L'oto-rhino faisait du bon travail, mais il siotait durant l'auscultation; ca nit par aigrir Anton. (Il s'agit d'un extrait du livre de 319 pages de Georges Perec (1969), intituleLa disparitionet qui ne comporte pas la lettre E.)3 Le code RSA
3.1 Le principe
La methode RSA dont nous allons parler a ete inventee en 1978 par Rivest, Shamir et Adleman (RSA) et repose sur les nombres premiers. La problematique de cette methode est la suivante. Imaginons un espion E (Ernesto), loin de son pays et de son chef C (Car- los). Il doit transmettre des messages secrets a C. Pour cela, il a besoin d'une cle pour coder ses messages. Cette cle doit lui ^etre transmise par son chef. Le probleme, de nos jours, avec Internet et tous les satellites qui nous tournent autour, c'est qu'on n'est pas s^ur du tout que les ennemis n'ecoutent pas les messages transmis. Avec la plupart des systemes de codage, si l'on conna^t la cle de codage, on sait aussi decoder les messages. Par exemple, imaginons que la cle soit l'operation qui a une lettre, representee par un nombrexmodulo26, associe 11x8 (toujours modulo 26), ce qui associe par exemple a la
lettreEla lettreU. On calcule alors facilement l'operation inverse5, ce qui permet de decoder les messages. L'inter^et du code RSA, au contraire, c'est qu'il est a sens unique : la cle de codage n'est pas une cle de decodage! Voici le principe de cette methode. Le chef C calcule deux grands nombres premierspetq(disons de l'ordre de 200 chires, on verra plus loin qu'on sait faire bien mieux), il calcule ensuite le produitpq(cela ne represente qu'une fraction de seconde pour une machine). Il choisit aussi un nombreepremier avecp1 etq1 (il y en a beaucoup, par exemple un nombre premier qui ne divise nip1 niq1). Il transmet a E la cle de codage, qui est constituee du nombrepq5. C'estx7! 7x4, voir ci-dessous.
3 et du nombree(mais il garde jalousement secrets les deux nombrespetq). La cle estpublique: peu importe si l'ennemi l'intercepte. Pour coder le message, E n'a besoin quepqet dee, en revanche, pour le decoder, le chef C a besoin des deux nombrespetq. Le principe qui fonde le code RSA c'est qu'il est beaucoup plus facile de fabriquer de grands nombres premierspetq (et de calculerpq) que de faire l'operation inverse qui consiste a decomposer le nombrepqen le produit de ses facteurs premiers. Pour illustrer ce point, un bon exemple, avecxcasest le nombre de 65 chires suivant : c= 332632908199295426868481488176973051559279283861330833890007590997: La machine repond instantanement qu'il n'est pas premier, mais met environ30 secondes pour le factoriser.
Voici precisement la methode de codage. Le message est un nombrea < pq et premier6avecpetq. Pour le coder,Ecalculeaemodulopq(le resterde
a edans la division parpq). La encore, une machine fait cela instantanement, voir ci-dessous. C'est ce nombrerqu'il envoie a son chef. Comment faire pour retrouveraa partir der? Nous l'expliquons en detail au paragraphe suivant. L'idee est la suivante : commeeest premier avec pq, le theoreme de Bezout montre qu'il existe un nombredtel quede1 (mod (p1)(q1)). On montre que gr^ace a cedon peut calculeraen faisant l'operation a l'envers :a=rd(modpq). Il sut donc de calculerd. Quand on conna^t (p1)(q1), trouverdest facile (c'est l'algorithme d'Euclide). Mais voila : on a (p1)(q1) =pqpq+1 et pour conna^tre ce nombre il nous fautp+q, doncpetqet ca, on ne sait pas faire et c'est ce qui assure la securite du code RSA.3.2 Quelques resultats arithmetiques
Rappelons d'abord le petit theoreme de Fermat (voir par exempleMathema- tiques d'Ecole) :3.1 Theoreme.Soientpun nombre premier eta2Z. Alorspdiviseapa
donc on aapamodulop. Si de plusaest premier avecp, on aap11 (modp).On a un corollaire de ce theoreme :6. Pour ^etre s^ur de realiser cela on prendra des messages plus petits quepetq. Par
exemple sipqa 200 chires, on prendra des messages de (nettement) moins de 100 chires. Ce seront des messageselementaires, il en faudra sans doute plusieurs pour faire un message reel. 43.2 Corollaire.Soientpetqdeux nombres premiers distincts et soita
premier avecpq. Alors on aa(p1)(q1)1 (modpq). Demonstration.Il sut de montrer que la congruence est vraie modulopet moduloq. Pour cela on note que, commeap1est congru a 1 modulop, on a aussia(p1)(q1)= (ap1)q11q1= 1 (modp). On procede de m^eme pour q. Le resultat suivant concerne encore les congruences (et c'est aussi la re- cette pour resoudre des equations du genreaxb(mods)) :3.3 Proposition.Soitsun entier>0et soiteun entier>0premier avec
s. Alors il existe un entierd >0tel quede1 (mods). Demonstration.On applique le theoreme de Bezout asete: il existe des entiersetavecs+e= 1. Siest>0 il sut de poserd=. Sinon, on remplacepar+sketparekaveckassez grand. Enn, le dernier resultat est la base de la methode RSA :3.4 Proposition.Soientpetqdeux nombres premiers distincts et soita >0
premier avecpq. Soiteun entier>0premier avec(p1)(q1)et soitd >0 tel quedesoit congru a1modulo(p1)(q1)(un tel entier existe par 5.3).Alors, on aadea(modpq).
Demonstration.On ade= 1 +m(p1)(q1), avecm >0, donc, en vertu de 3.2 : a de=aa(p1)(q1)ma1m=a(modpq):3.3 Methodes de calcul : puissances
3.3.1 Un exemple
Considerons l'exemple suivant
7:n=pq= 11639,e= 3361 et supposons
que le messageaest egal a 2511. Il s'agit de calculeraemodulopq. Dans ce qui suit on eectuera les calculs avec l'ordinateur et le logicielxcas.3.3.2 Avec l'ordinateur, sans programme
Attention, on ne peut pas calculer directement 25113361sinon la machine
repondintegertoolargefordisplaycar on a depasse sa capacite. Le prin-cipe est de reduire a chaque pas modulon. Une methode elementaire, mais7. En fait, le choix deeest tres mauvais. En eet, avec cette valeur il y a de nombreux
adont le codage est egal aa, voir ci-dessous Annexe 5. 5 deja ecace, est la suivante. On calculeirem(251110;11639) (le reste de la puissance dans la division par 11639). On trouve 5868. On recommence en calculant 586810modulon, soit 9609, puis 960910modulon, soit 2083. Ce
nombre n'est autre que 25111000modulon. On eleve ce nombre au cube, ce
qui donne 1146 (on a ainsi la puissance 3000), on trouve de m^eme la puissance300 : 11138 et on calcule directement 2511
612990 (modn). En multipliant
les trois on a 251133619404 (modn).
3.3.3 Avec l'ordinateur, la voie des puissances de2
C'est une methode plus astucieuse qui va donner un algorithme tres ra- pide. Elle combine deux types d'operations simples :1) l'elevation au carre,
2) la multiplication para= 2511.
La methode est la suivante : on part dee, sieest pair on le divise par 2, sinon on lui retranche 1, il est alors pair, on le divise par 2 et on recommence avec le quotient. On nit par aboutir a 1. (Si on ecriteen base2, les operations consistent a supprimer le dernier chire si c'est un 0 ou a le
changer en 0 si c'est un 1.) Avece= 3361 on obtient successivement les nombres 3360, 1680, 840,420, 210, 105, 104, 52, 26, 13, 12, 6, 3, 2, 1, autrement dit, on a ecrit, en base
2 :3361 = 1010010001000001:
On obtient alors le resultat en partant de la gauche de ce nombre et en multipliant par 2511 chaque fois qu'on rencontre un 1 et en elevant au carre pour chaque 0 (et bien entendu en reduisant modulona chaque pas). Voici les intermediaires : 8422, 11218, 2656, 1102, 8679, 9072, 1815, 388, 8231, 10381,11299, 10849, 7233, 10623, et enn 9404.A faire a la main c'est penible, mais
on va ecrire un programme qui fait le m^eme travail.3.3.4 Programmes
Voici deux programmes surxcaspour faire automatiquement ces calculs de puissances. Le premier est plus simple8, mais le second bien plus rapide
(pour le calcul ci-dessus les deux donnent la reponse instantanement, mais pour calculer 12345678987654321135792468modulo 98765432123456789 le pre-
mier met 17 minutes et 34 secondes, tandis que le second est instantane). Chacun de ces programmes calcule la puissancer-ieme deamodulop. Le premier consiste a multiplierakparaet a reduire modulopa chaque pas :8. Et facile a retrouver. 6 power(a,r,p):=fLocal z;
z:=1; pour k de 1 jusque r faire z:=irem(a*z,p); fpour retourne z; g:; Le second programme utilise les puissances de 2, comme explique plus haut, pour grimper plus vite 9: powerv(a,r,p):=f local z; z:=1; tantque r>0 faire si floor(r/2)=r/2 alors r:=r/2; a:=irem(a^ 2,p); sinon r:=(r-1)/2; z:=irem(z*a,p); a:=irem(a^ 2,p); fsi ftantque retourne z; g:; Ce programme merite un mot d'explication. On chercheb:=ar(modp). On entrea;r;pet on posez= 1. On a doncarz=ar=b. Dans le programme, les quantitesa;r;zevoluent de telle sorte quearzreste constant. En eet, sirest pair,zne change pas,adevienta2etrdevientr=2, doncarzest invariant. Sirest impair,r= 2k+ 1,adevienta2,rdevientketzdevientaz, doncarzdevient (a2)kaz=a2k+1z=arz.A la derniere etape on ar= 0, doncarz=zet cette quantite est bien le
bcherche.3.4 Methodes de calcul : les coecients de Bezout
Reprenons notre exemple :n=pq= 11639,e= 3361 eta= 2511. On a trouveae9404 (modn).9. La commandefloorest la partie entiere et elle sert a tester la parite der. 7 Pour inverser le processus, il y a besoin de conna^tre (p1)(q1), donc petq. Ici, ce n'est pas trop complique : on ap= 103 etq= 113, d'ou (p1)(q1) = 11424 = 253717. Commeeest premier, il est bien premier avec ce nombre. Il s'agit maintenant de trouverdtel quede1 (mod 11424). Pour cela, on utilise l'algorithme d'Euclide pour trouver les coecients de Bezout.3.4.1 L'algorithme d'Euclide
On considerea;b2Navecb6= 0. On posea=r0,b=r1. On eectue la division euclidienne deaparb:a=bq+ravec 0r < b. On poseq=q1, r=r2. On a doncr0=r1q1+r2avec 0r2< r1etd=pgcd(a;b) = pgcd(r0;r1) =pgcd(r1;r2). On construit ainsi par recurrence des entiersr0;r1;;rk;rk+1etq1;;qk avecrk1=qkrk+rk+1, 0rk+1< rketd=pgcd(rk;rk+1). Si on ark+1= 0 on ad=rket on s'arr^ete, sinon on continue l'algorithme en divisantrkpar r k+1.Comme on a 0rk+1< rk<< r1on voit que l'on obtient
necessairement un reste nul au bout d'au plusr1operations. Si on designe par r nle dernier reste non nul on a doncrn1=qnrnd'ou,d=pgcd(rn1;rn) = r n.3.4.2 Le theoreme de Bezout
Pour montrer Bezout, on utilise l'algorithme d'Euclide. On va montrer, par recurrence surkque, pour toutkavec 0kn, il existe des entiers u k;vk2Zveriantrk=uka+vkb. L'assertion est vraie pourk= 0 puisqu'on ar0=a= 1a+ 0bet pourk= 1 puisqu'on ar1=b= 0a+1b. Supposons l'assertion prouvee pour tout entierk, aveckxe veriant 1k < n, et montrons la pour k+1. On ark+1=rk1qkrk=uk1a+vk1bqk(uka+vkb) d'ou la relation cherchee en posantuk+1=uk1qkuketvk+1=vk1qkvk. Si on applique l'assertion au cask=n, comme on arn=d=pgcd(a;b), on obtient bien la relation de Bezout cherchee.3.4.3 Calcul avecxcas
Le logicielxcasa une commande qui donne directement les coecients de Bezout :iegcd(a,b)renvoie dans l'ordreu;v;tels queua+vb== pgcd(a;b). Dans le cas present on trouveu=198 etv= 673. Ce dernier nombre est l'exposantdcherche. On verie qu'on a bien 94046732511 (modn). 8Si l'on y tient
10on peut aussi ecrire un programme. Le suivant utilise des
listes de trois termes et il est facile de comprendre son fonctionnement en le testant sur un exemple, a condition de savoir trois choses :La conditionb!=0signieb6= 0.
La commandeiquo (a,b)est le quotient euclidien deaparb. L'ecriturela[2]designe le terme d'indice 2 de la listela(qui commence a 0). Ici, c'est donca.Avec ces precautions, voici le programme :
Bezout(a,b):=f
local la, lb, lr, q; la:=[1,0,a]; lb:=[0,1,b]; tantque b!=0 faire q:=iquo(la[2],b); lr:=la+(-q)*lb; la:=lb; lb:=lr; b:=lb[2]; ftantque retourne la; g:;3.5 Trouver de grands nombres premiers
On sait depuis Euclide qu'il y a une innite de nombres premiers mais il n'est pas si facile d'en donner explicitement de tres grands. Pierre de Fermat (1601-1665) avait cru trouver une formule donnant a coup s^ur des nombres premiers. Il pretendait que, pour tout entiern, le nombre11Fn= 22n+1 etait premier. C'est eectivement le cas pourn= 0;1;2;3;4 qui correspondent respectivement aux nombres premiers 3;5;17;257;65537, mais ce n'est pas vrai pourF5comme l'a montre Euler12. On peut faire le calcul a la main jusqu'a 257. Pour voir que 65537 est premier, mais que 232+ 1, 264+ 1 et 2128+ 1 ne le sont pas on peut utiliser
la fonctionisprimedexcasqui repond presque instantanement. (Jusqu'a10. Ou si le jury de CAPES y tient ...