[PDF] [PDF] Corrigé - DI ENS Corrigé Cryptographie `a clé publique

View - Download [PDF] Corrigé - DI ENS

Previous PDF

Next PDF

Universite Paris 13 Villetaneuse Master 1 Informatique

Introduction a la cryptographie Annee 2015-2016

Corrige

Cryptographie a cle publique

I. Chirement multiplicatif (15 pts)

On considere l'anneauZ30={0,1,2,...,29}des entiers modulo 30. Rappelons qu'un elementa?Z30est inversible si, et seulement si, pgcd(a,30) = 1. 1. ( 2pts) Enumerer tous les elements deZ?30(les elements deZ30inversibles). Solution.30 = 2×15 = 2×3×5, donc tous les elements deZ30non divisibles par2,3et5 sont premiers avec30. Il s'agit donc deZ?30={1,7,11,13,17,19,23,29}. 2. ( 3pts)Cal culerl 'inversed ansZ?30des elements trouves a la question precedente. Solution.On appliquera l'algorithme d'Euclide etendu pour trouverUtel queaU+30V= 1: a17111317192329 a -111311723191729 3. O nd enitl ep rocedede c hirementm ultiplicatifs urZ30de la facon suivante : E a(x) =axmod 30. (a) ( 1pt)Cal culerl en ombred ecl esp ossibles.

Solution.C'est exactement les elements

deZ?30: il y en a huit. (b) ( 1pt)D ecrirel af onctionde d echirement D apoura? K.

Solution.Da(y) =a-1ymod 30.

(c) ( 4pts)Ch irerl em essages uivanta vecl a clea= 13(vous donnerez le resultat sous la forme du texte correspondant a la suite de nombres) :

UN ORNITHORYNQUE TRISTE

Solution.On obtient nalement le texte

chire suivant :

UTRCLTOHBCLMT,UWRHLOYHW

Introduction a la cryptographie Examen

(d) (4pts) Identier et expliquer quelles sont les vulnerabilites d'un tel cryptosysteme. Solution.1.Il s 'agitd'u nc hirements ymetrique,la c lede d echirementp eut^ etref acilement deduite a partir de la cle de chirement (c'est l'inverse modulo 30). 2. C' estu nc hirementd eterministe,de s ubstitutionm ono-alphabetique,i lp eutdonc ^ etrec asse facilement par une analyse des frequences des lettres. 3. L' espaced ec lese stde p etitet aille.U ner echerchee xhaustivede la c lee stp ossibledans un temps raisonable. 4. C' estu nc hirementhom omorphep arr apport al 'operationd' addition: E a(x+y) =ax+ay=Ea(x) +Ea(y) mod 30. 5.

C' estu nc hirementc ommutative:

E b(Ea(x)) =Ea(Eb(x)) =Eba(x).

II. Factorisation (3 pts)

1. ( 1pt)En ad mettantq uel' entier14803 es tl epr oduitd ede uxnom bresp remiers,p ouvez-vous facilement le factoriser? Expliquez pourquoi. Solution.La factorisation est un probleme connu comme dicile. La methode nave pour

factoriser un entiernest enO(n1/2)operations : on divisenpar tous les entiers inferieurs a⎷n. Dans notre cas on a besoin de faire au maximum 121 divisions.

2. ( 2pts)Si en ou tre,on r evelequ e?(14803) = 14560, la factorisation est-elle possible? Donnez les deux facteurs. Solution.Ecrivonsn=pq. On a donc?(n) = (p-1)(q-1) =pq-p-q+1 =n-(p+q)+1, et ainsip+q=n-?(n) + 1 = 14803-14560 + 1 = 244. Les nombrespetqsont racines du polynome

P(X) =X2-(p+q)X+pq=X2-244X+ 14803.

Le discriminant estΔ = 2442-4×14803 = 324 = 182et ainsip= (244-18)/2 = 113et q= (244 + 18)/2 = 131.

III. Fonctions de hachage (7 pts)

Le but de l'exercice est de montrer les liens d'implication ou de non-implication parmi les proprie-

tes des fonctions de hachage :•Resistance a la preimage: etant donneh, on ne peut pas trouver en un temps

raisonnable dextels queh=H(x) •Resistance a la seconde preimage: etant donnex, on ne peut pas trouver en un temps raisonnable dey?=xtels queH(y) =H(x) •Resistance aux collisions: on ne peut pas trouver en un temps raisonnable de couplesxetytels queH(x) =H(y)Proprietes www.di.ens.fr/≂nitulesc/teaching 2 anca.nitulescu@ens.fr

Introduction a la cryptographie Examen

1. ( 2pts)M ontreru ner elationen trel ar esistance ala s econdep reimagee tl ar esistanceau x collisions d'une fonction de hachage. Solution.La resistance aux collisions implique la resistance a la seconde preimage. Pour la resistance a la seconde preimage, l'attaquant recoit unxxe et il doit trouver uny dierent dextel qu'ils ont la m^eme empreinteH(y) =H(x). Pour la resistance aux collisions, l'adversaire est libre a choisir les deux messagesxetytels que leurs empreintes coincident. S'il existe un attaque pour trouver une seconde peimage, on peut facilement l'utiliser pour trouver une collision : On veux trouver dey?=xtels queH(y) =H(x). Fixons unxau hasard. D'apres notre hypothese on peut facilement trouver uny?=xtel queH(y) =H(x), d'ou la collision. 2. Con sideronsla f onctionf:Z→Zndenie parf(x) =x2modnpournun module RSA. (a) ( 1pt)J ustierqu el af onctionf es tr esistante al apr eimage. Solution.Lorsquenest un module RSA (le produit de deux grands nombres premiers), l'extraction d'une racine carree modulonest un probleme repute dicile, la fonctionfest donc resistante a la preimage. (b) ( 1pt)J ustierq uel afon ctionn' estp asr esistance al ase condepr eimage. Solution.Puisquef(x) =f(-x), cette fonction n'est pas resistante a la seconde preimage. Ainsi, la resistance a la preimage n'entra^ne pas la resistance a la seconde preimage. 3. Con sideronsu nef onctiond ehac hageg:{0,1}?→ {0,1}nresistante a la collision. Considerons ensuite la fonction de hachagehqui calcule des empreintes de longueurn+1construites de la facon suivante : h:{0,1}?→ {0,1}n+1 h(x) =?1|xsixest de longueurn

0|g(x)sinon

ou|designe l'operation de concatenation. (a) ( 1pt)M ontrerq uec ettef onctione str esistante al ac ollision Solution.Cette fonction est resistante a la collision notamment cargl'est : Sih(x) =h(y) alors le premier bit ne peut etre egal a1car sinon on auraith(x) = 1|x=h(y) = 1|ydonc x=y(ce ne serait plus une collision). Donc le premier bit est0et on a necessairement g(x) =g(y), ce qui veut dire quexetyforment une collision surg. Par hypothese,gest resistante aux collisions, doncxetysont diciles a trouver, et donchest resistante aux collisions. (b) ( 1pt)M ontrerq uece ttefon ctionn' estpas r esistante al ap reimage Solution.Cette fonction n'est pas resistante a la preimage car il est facile de determiner un antecedent pour la moitie des images (celles qui commencent par1). L'antecedent de la valeurh= 1|xest juste la suite binairex. Ainsi, la resistance a la collision n'entra^ne pas la resistante a la preimage. 4. ( 1pt)D onneru nex empled efon ctionr esistanteau xcol lisionset al ase condepr eimage,mai s pas a la preimage. Est-ce une fonction de hachage? Solution.La fonction identite est resistante (inniment) aux collisions et aux secondes pre- images. Par contre, ce n'est pas une fonction de hachage car elle ne condense pas le message. www.di.ens.fr/≂nitulesc/teaching 3 anca.nitulescu@ens.fr

Introduction a la cryptographie Examen

IV. Signature RSA (3 pts)

Alice a mis a la disposition du public les cles pu- bliques RSA(e= 17,n= 437). Elle garde secret l'exposantd. 1. ( 1pt)G enereru nesi gnaturev alideσ(sans contr^ole sur le messagemsigne). 2. ( 1pt)S oient(m1,σ1) = (100,156)et (m2,σ2) = (2,257)deux documents signes par Alice. Montrer qu'il est facile de fabri- quer une signature valide pour le message m= 200. 3. ( 1pt)M ontreru neat taque acl airsc hoisisq ui permet de signer n'importe quel messagem. (Falsication Universelle)•Generation des cles pk:n,e(mod?(n)) sk:d(mod?(n)) •Signature

S(d,m) =σ

σ=md(mod n)

•Verication

V(e,m,σ) =oui/non

m ?=σe(mod n)Algorithmes Solution.1.F alsicationEx istentielle: On p eutc hoisiru nev aleurσau hasard et calculer le messagempour lequelσest une signature valide de la maniere suivante :m=σemodn. 2. En u tilisantl ap roprietede hom omorphismep arr apport ala m ultiplicationde l as ignature RSA on obtient une signature valide pour le messagem1m2= 200en faisant le produit de deux signaturesσ1σ2= 325 mod 437. 3. F alsicationUn iverselle: O np euts ignern 'importeq uelm essagemen demandant deux signa- turesσ1,σ2pour les messages clairsm1=m/2etm2= 2. Pour obtenir la signature valide du messagemon n'a que a multiplier les signaturesσ1etσ2. V. Preuves de connaisance sans divulgation (6 pts) Le but de l'exercice est de s'identier en tant que le possesseur d'une cle publique El Gamal.

On rappelle l'algorithme de generation de cles ElGamal :•Soit un premierpet le groupe cycliqueZ?p•Soitqun diviseur premier de(p-1).

•Soitg?Z?pun element d'ordreq. •Soit une cle secretesk:x(mod q). •Soit la cle publiquepk:y=gx(mod p).Cles ElGamal Alice pretend ^etre en possession de la cle secretexassociee a la cle publiquey. 1. ( 2pts)Comm entAl ice,p eut-ellepr ouverl av alidited esa c lep ubliqueysans reveler sa cle secretex. Solution.Le protocole de Schnorr est un protocole de divulgation nulle de connaissance pour le secretxassocie a une cle publiquey=gxmodp. Le protocole est illustre dans la gure 1. 2. ( 2pts)M ontrerde uxmo yensdi erentsq uip ermetent aAl iced et richerdan sl epr otocole precedent. www.di.ens.fr/≂nitulesc/teaching 4 anca.nitulescu@ens.fr

Introduction a la cryptographie Examen

Alice Bob

r←$ modqt=grmodpt----→e ←----e? {0,1}s=r-exmodqs----→t?=gsyemodpFigure1 { Protocole de Schnorr

Solution.Alice ne connaissant pasxa deux choix :

(a)

A licene tr ichep aslor sde l apr emiere etape:

(calcul et envoi det=gr) Si e= 0elle pourra repondre toujours correctement a la question du Bob avecs=r. Si e= 1, elle devra choisir un nombre au hasards, et il n'a pas plus d'une chance sur q-1de tomber surr-ex. (b) A licetr ichel orsde l 'envoide t. Dans ce cas, elle peut parier des le depart sur le biteque

Bob enverra :

Si e llep ariee= 0, elle envoie eectivementt=gr, puis ensuites=r. Si e llep ariee= 1, elle envoie alorst=grymodp, puis ensuites=rqui verie bien t=gsy. 3. ( 2pts)Av ecq uellepr obabiliteau ra-t-ellel ac hanced en ousf airecr oireq u'ellep osedel ese cret xapres20executions du protocole? Solution.Alice a une chance sur deux de gagner dans chacun des deux cas. Avec un tour de ce protocole, Alice a une probabilitepde faire le bon choix (avecp≈1/2siq est grand). En repetant ce protocole 20 fois, Bob pourra s'assurer de la honn^etete d'Alice : la

probabilite qu'elle lui faire croire qu'elle posede le secret sans le conna^tre en realite est≈12

20.

Question bonus (1 pt)

Que dit Pat a Mickey?

(Source : Le Journal de Mickey, n 2119, p. 46) Solution."Tu as perdu Mickey tout ce tresor est a moi" www.di.ens.fr/≂nitulesc/teaching 5 anca.nitulescu@ens.frquotesdbs_dbs4.pdfusesText_8

[PDF] exercice corrigé elgamal

[PDF] exercice corrigé cryptographie rsa

[PDF] exercice corrigé data encryption standard

[PDF] chiffrement symétrique avantages

[PDF] chiffrement symétrique et asymétrique

[PDF] carte badgeo etudiant

[PDF] ejemplos del verbo ser

[PDF] ejercicios ser estar español para extranjeros

[PDF] ejercicios verbo ser y estar para imprimir

[PDF] arts plastiques 3ème cube

[PDF] vecteur dans l espace terminale s

[PDF] sujets bac géométrie dans l espace

[PDF] géométrie dans lespace 3ème exercices corrigés pdf

[PDF] structure cubique centrée

[PDF] compacité cubique simple