[PDF] Correction Exercice 1 : RSA Correction Exercice 2 : Diffie Hellman

View - Download Correction Exercice 1 : RSA Correction Exercice 2 : Diffie Hellman

Previous PDF

Next PDF

Lebanese International University (LIU) en Mauritanie corrigé TD4 asymmetric ciphers

R. Rhouma 1

Correction Exercice 1 : RSA

1) n = p*q= 253

Phi(n) = (p - 1)(q - 1 ) = 10 * 22 = 220

e=3 (e =2 a rejeter puique gcd(2,220) =2 ; e=1 n"est clairement pas un bon choix ) cherher d tel que d =e -1 mod phi(n) = 3-1 mod 220 pour cela on applique l"alg d"euclide etendu :

220 = 3 * 73 + 1

1 = 220 - 3 *73

-73 = 3 -1 mod 220 = 147 mod 220

Donc d =147

2) on a n=253, la taille de bloc du plaintext k = E[log

4 253] = 4ln

253ln = 3.

3) la taile maximale d"un bloc du ciphertext sera donc k +1 = 4

4) le message abb correspond à 122 d"apres le tableau. 122 correspond au nombre :

1* 4

2 + 2 * 41 + 2*40 = 26

Donc P =26. le chiffrement de P est donné par C = P e mod n = 263 mod 253 = 119

Le nombre 119 correspond à :

119 = 1 * 4

3 + 3 * 42 + 1* 41 + 3*40

Donc le nombre decimal 119 correspond au nombre dans la base 4 : 1313 qui correspond au message "acac ».

5) le dechiffrement se fait comme suit :

le ciphertext acac correspond à 1313 ds la base 4 qui correspond au nombre : 1 * 4

3 + 3 * 42 + 1* 41 + 3*40 = 119

M = C d mod n = 119147 mod 253 = ? Exponentiation rapide, on a 147 = 128 + 16 + 2 +1 = (10010011) 2

I 7 6 5 4 3 2 1 0

bi 1 0 0 1 0 0 1 1

Exp 1 2 4 9 18 36 73 147

Res 119 246 49 82 146 64 146 26

Donc le plaintext en decimal c"est 26 qui s"ecrit en base 4 sous la forme :

26 = 1* 4

2 + 2* 41 + 2 *40

Donc 26 = (122)

4 qui correspond d"apres le tableau au plaintext " abb »

Correction Exercice 2 : Diffie Hellman

- Alice calcule A = ga mod p = 37 mod 17 = 11 et envoye A à Bob Bob calcule B = gb mod p = 34 mod 17 = 13 et envoye B à Alice Alice calcule la clé secrete par K = Ba mod p = 137 mod 17 = 4 Bob calcule la clé secrete K par K = Ab mod p = 114 mod 17 = 4

Correction Exercice 3 : Hash

1) H(01101) = 1

Lebanese International University (LIU) en Mauritanie corrigé TD4 asymmetric ciphers

R. Rhouma 2

2) H(msg de 1 pair) = 0 et H(msg 1 impaire) = 1

3) 111 et 100

4) H est une fonction à sens unique. Les autres proprétés ne sont pas verifiés ( strong and

weak collision) Solution Exercice 4 : Fonctions de hachage et paradoxe des anniversaires

2^160=1.4 * 10^48

1) Cet exercice est une illustration

du paradoxe des anniversaires : quelle est la probabilité pour que, dans un groupe, au moins deux personnes aient la même date d"anniversaire? La probabilité qu"au moins deux personnes dans un groupe de 23 personnes aient la même date d"anniversaire est supérieure à

0,5, ce qui est bien supérieur à ce que l"on pourrait penser intuitivement, d"où le terme de

paradoxe.

1. Soit p la probabilité qu"au moins une personne possède un certificat ayant la même

empreinte que Foulen fouleni et p la probabilité complémentaire, c"est-à-dire la probabilité que personne ne possède un certificat ayant la même empreinte que celle de foulen. Soit H le nombre d"empreintes possibles (2

160) et N le nombre d"habitants sur Terre. La probabilité

qu"une personne donnée ait la même empreinte que foulen est 1/H ; la probabilité qu"elle en ait un différent est alors 1 - 1/H. Il y a N - 1 autres personnes.

On en déduit donc p :

On obtient une bonne approximation en utilisant deux fois le fait que xex-=-1 pour x proche de 0 :

2) Soit maintenant p" la probabilité qu"au moins deux personnes sur Terre possèdent des

certificats ayant la même empreinte. Soit "p la probabilité complémentaire c"est-à-dire la

probabilité que tous les habitants de la Terre possèdent des certificats distincts. Pour calculer

"p on imagine une table contenant H cases. Chacune des N personnes vient faire une croix dans la case correspondante à son empreinte. La première croix tombe forcément sur une case libre. Pour la deuxième il y a (H - 1 )/H chances qu"elle tombe sur une case libre. Pour la troisième (H-2) / H et ainsi de suite. On a alors : Doncquotesdbs_dbs4.pdfusesText_8

[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

[PDF] section rhénanes alcools

[PDF] cubisme def