Corrig e - DIENS

Introduction a la cryptographie Examen (d) (4pts) Identi er et expliquer quelles sont les vulnerabilit es d’un tel cryptosyst eme Solution 1 Il s’agit d’un chi rement sym etrique, la cl e de d echi rement peut ^etre facilement d eduite a partir de la cl e de chi rement (c’est l’inverse modulo 30)

Cryptographie Paris 13

La cryptographie est l’art de rendre inintelligible, de crypter, de coder, un message pour ceux qui ne sont pas habilit´es a en prendre connaissance Le chiﬀre, le code est le proc´ed´e, l’algorithme, la fonction, qui permet de

Exercices et problèmes de cryptographie - Dunod

Exercices et problèmes de cryptographie déjà un véritable spécialiste, capable de se confronter aux multiples concepts que la cryptologie moderne a développés ces trente dernières années A un moment où la cryptologie est au cœur de la société de l’information, de l’internet aux moyens de

TD Cryptographie et ACL

Exercice 1 cryptographie symétrique Soit M un message divisé en blocs {x1,x2,x3, xp}chacun de taille n bits et soit K une clé de même taille que les blocs (n bits) Soit {c1,c2,c3, cp}les cryptogrammes des blocs obtenus en appliquant la clé K aux blocs Le chiffrement des blocs se fait selon le schéma suivant:

TD 2 : Le cryptosyst eme RSA 1 Example de protocole RSA

Introduction a la cryptographie TD 2 2 Applications Exercice 5 Connaissant la cl e publique (n = 119;e = 5) de ce cryptogramme RSA 7 bits, (on consid ere des nombres a 7 bits soit inf erieurs a 27 = 128) : 090 086 036 067 032 001 003 031 059 031 1 Calculez (par tout les moyens a votre disposition) p et q 2 Calculez la cl e secr ete d 3

Exercices de cryptographie - univ-reunionfr

Exercices de cryptographie M1 informatique 1 Cryptographieclassique 1 1 Divers 1 Donnezletexteenclaircorrespondantautextecryptésuivant: irwimkriqirx hi wigyvmxi

1 Le chiffrement de César - Cours et exercices de

Les ordinateurs ont révolutionné la cryptographie et surtout le décryptage d’un message intercepté Nous montrons ici, à l’aide du langage Pythoncomment programmer et attaquer le chiffrement de César Tout d’abord la fonction de chiffrement se programme en une seule ligne : Code 1 (cesar py (1)) def cesar_chiffre_nb(x,k): return (x

Feuille d’exercices 8

Universit¶e Pierre et Marie Curie M1 Cryptographie Ann¶ee 2010 Feuille d’exercices 8 Avertissement: tous les exercices ne seront pas trait¶es durant les s¶eances; pour en suivre l’avancement veuillez consulter mon site personnel dans la rubrique Forum Cryptosystµemes Exercice 1 Soit E la cubique d¶eﬂnie sur F11 d’¶equation y2

Exercices sur : Sécurité des réseaux

1 Codage et décodage RSA - imag

4 Cryptographie à clef publique par résidu quadra-tique Soient a et b deux entiers; on dit que a 6= 0 est un arrcé (ou ésidur quadratique ) modulo b ssi il existe x tel que x2 ≡ a mod b On dit alors que x est une aciner arrceé de a modulo b Dans tout l'exercice, p et q désignent deux nombres premiers di érents de 2 et n = p q 1

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] Corrig e - DIENS

Introduction a la cryptographie Annee 2015-2016

Corrige

Cryptographie a cle publique

I. Chirement multiplicatif (15 pts)

Solution.C'est exactement les elements

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

UN ORNITHORYNQUE TRISTE

Solution.On obtient nalement le texte

UTRCLTOHBCLMT,UWRHLOYHW

Introduction a la cryptographie Examen

C' estu nc hirementc ommutative:

II. Factorisation (3 pts)

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

III. Fonctions de hachage (7 pts)

Introduction a la cryptographie Examen

0|g(x)sinon