[PDF] Cours numéro 6 : Arithmétique et cryptographie

View - Download Cours numéro 6 : Arithmétique et cryptographie

Previous PDF

Next PDF

Cours numero 6 :

Arithmetique et cryptographie

1 Introduction

Si l'on m'avait demande quand j'etais jeune chercheur, dans les annees

1970, 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 bougon

1, 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 nombres

2de 1 a 26. On traduit

le message en chires. Par exemple si le message est A L'AIDE il devient

1 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 deviner

3. 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 pas

a 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 nombrexmodulo

26, 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 ni

q1). 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 environ

30 secondes pour le factoriser.

Voici precisement la methode de codage. Le message est un nombrea < pq et premier

6avecpetq. 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. 4

3.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 2511

3361sinon 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 5868

10modulon, soit 9609, puis 960910modulon, soit 2083. Ce

nombre n'est autre que 2511

1000modulon. On eleve ce nombre au cube, ce

qui donne 1146 (on a ainsi la puissance 3000), on trouve de m^eme la puissance

300 : 11138 et on calcule directement 2511

612990 (modn). En multipliant

les trois on a 2511

33619404 (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 base

2, 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 simple

8, mais le second bien plus rapide

(pour le calcul ci-dessus les deux donnent la reponse instantanement, mais pour calculer 12345678987654321

135792468modulo 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):=f

Local 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); sinonquotesdbs_dbs28.pdfusesText_34

[PDF] cours de cryptographie decrypter les codes secrets

[PDF] cryptographie sécurité informatique

[PDF] cryptographie et sécurité informatique pdf

[PDF] exercices de guitare pour les nuls pdf

[PDF] cours langage c pdf gratuit

[PDF] cours complet langage c

[PDF] cours langage c pour debutant

[PDF] table de division pdf

[PDF] table de multiplication de 12 ? imprimer

[PDF] langage c pdf exercices corrigés

[PDF] cours langage c++ pour débutants pdf

[PDF] cours langage c pdf pour debutant

[PDF] langage c++ cours pdf

[PDF] apprendre le latin livre

[PDF] apprendre latin autodidacte