[PDF] [PDF] Corrigé - DI ENS Master 1 Informatique Introduction `a

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

quotesdbs_dbs2.pdfusesText_3

[PDF] les nombres en lettres pdf

[PDF] les nombres en lettres de 0 ? 1000

[PDF] ap seconde chiffres significatifs

[PDF] chiffres significatifs excel

[PDF] les chiffres significatifs cours

[PDF] chiffres significatifs sinus

[PDF] precision d une mesure et chiffres significatifs

[PDF] chiffres significatifs exacts

[PDF] chiffres significatifs exos

[PDF] exercices chiffres significatifs 2nde

[PDF] les nombres cardinaux en anglais pdf

[PDF] les nombres en anglais pdf

[PDF] les nombres et les chiffres en anglais pdf

[PDF] l'heure en anglais pdf

[PDF] les nombres ordinaux anglais de 1 ? 100