[PDF] Examen Final – Cryptographie PDF

Appliquez cet algorithme pour factoriser. 899 110417

1 Codage et décodage RSA. 2 Cryptographie RSA et authentification

Ceci fonde la robustesse de l'algorithme RSA; mais cela ne justifie pas pour autant une Dans tout l'exercice p et q désignent deux nombres premiers ...

Feuille 3 : RSA

(c) La composée de deux chiffrements RSA est-elle un chiffrement RSA? (d) Dans L'objectif de cet exercice est de majorer la complexité de l'algorithme d ...

Exercice 1 cryptographie symétrique TD Cryptographie et ACL

Exercice 2 : chiffrement RSA. Question 1 : Effectuer le chiffrement et le déchiffrement en utilisant l'algorithme RSA pour les valeurs suivantes: Les deux

Exercice 3 : chiffrement à clé publique

Exercice 3 : chiffrement à clé publique. Remarques : • Les exercices sont algorithme RSA pour les valeurs suivantes : a. p = 3 ; q = 11 ; e = 7 ; M ...

Corrigé

On appliquera l'algorithme d'Euclide étendu pour trouver U tel que aU + Considérons la fonction f : Z → Zn définie par f(x) = x2 mod n pour n un module RSA.

MPSI/PCSI TD dinformatique Pr. Youssef Ouassit Algorithmique et

FinTantQue. Fin. Exercice N° 5 : Ecrire un algorithme qui affiche les nombres 1 jusqu'à 40. Correction : Algorithme compter. Variables i : Entier. Début. I ← 1.

Feuille dexercices 4

— (Syst`eme RSA) Soit n un entier ≥ 1. Alice utilise le cryptosyst`eme RSA l'algorithme d'Euclide ce qui conduit `a l'égalité 1 = 3 × 139 − 2 × 208 ...

Exo7 Arithmétique : en route pour la cryptographie Un MOOC

Cryptographie. Notre motivation : comprendre le chiffrement RSA. – Chapitre 3. Algorithme. Nous aurons besoin d'un petit peu de programmation pour casser des

[PDF] Algorithmes - Exo7 - Cours de mathématiques

exercice de le prouver). • Dans la pratique on calcule la somme à un certain ordre ... cryptographie RSA (que nous détaillerons plus tard) : connaître p et q ...

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

Exercice 1 On consid`ere les valeurs p = 53q = 11 et e = 3. a) Calculez la valeur publique n. b) Calculez la fonction d'Euler ?(n)=(p ? 1)(q ?

1 Codage et décodage RSA. 2 Cryptographie RSA et authentification

Ceci fonde la robustesse de l'algorithme RSA; mais cela ne justifie pas pour Dans tout l'exercice p et q désignent deux nombres premiers différents de ...

Corrigé

Corrigé. Cryptographie `a clé publique. I. Chiffrement multiplicatif (15 pts) On appliquera l'algorithme d'Euclide étendu pour trouver U tel que aU + ...

Feuille 3 : RSA

(c) La composée de deux chiffrements RSA est-elle un chiffrement RSA? L'objectif de cet exercice est de majorer la complexité de l'algorithme d'Euclide.

Examen Final – Cryptographie

Examen Final – Cryptographie jeudi 19 janvier 2006. Correction. Exercice 1. Alice change sa clé RSA tous les 25 jours. Bob lui change sa clé tous les 31

Correction Exercice 1 : RSA Correction Exercice 2 : Diffie Hellman

Lebanese International University (LIU) en Mauritanie corrigé TD4 asymmetric ciphers. R. Rhouma. 1. Correction Exercice 1 : RSA.

Exercice 3 : chiffrement à clé publique

Les exercices sont attribués en fonction de l'ordre alphabétique de votre nom le chiffrement et le déchiffrement en utilisant l'algorithme RSA pour les.

Exercice 1 cryptographie symétrique TD Cryptographie et ACL

Exercice 2 : chiffrement RSA. Question 1 : Effectuer le chiffrement et le déchiffrement en utilisant l'algorithme RSA pour les valeurs suivantes:.

1 Codage et décodage RSA. 2 Cryptographie RSA et authentification

Ceci fonde la robustesse de l'algorithme RSA; mais cela ne justifie pas pour Dans tout l'exercice p et q désignent deux nombres premiers différents de ...

APPLICATIONS DES MATHEMATIQUES Cryptographie Partie 2

c) Le système de chiffrement RSA parait résister encore à notre époque aux algorithmes de cryptanalyse les plus récents et à la puissance de calculs des

[PDF] TD 2 : Le cryptosyst`eme RSA 1 Example de protocole RSA - DI ENS

Exercice 1 On consid`ere les valeurs p = 53q = 11 et e = 3 a) Calculez la valeur publique n b) Calculez la fonction d'Euler ?(n)=(p ? 1)(q ?

[PDF] 1 Codage et décodage RSA 2 Cryptographie RSA et authentification

Ceci fonde la robustesse de l'algorithme RSA; mais cela ne justifie pas pour Dans tout l'exercice p et q désignent deux nombres premiers différents de

td2 RSA Corrige PDF PDF Public-key cryptography Algorithmes

Avis 50

[PDF] Feuille 3 : RSA

Exercice 1 Chiffrement RSA 1 Soit n = pq où p et q sont des nombres premiers distincts Le système RSA chiffre x ? Z/nZ en xb ? Z/nZ

[PDF] Diffie Hellman Correction Exercice 3 : Hash - Esentn

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(2220) =2 ; e=1 n'est clairement pas

[PDF] Exercice 3 : chiffrement à clé publique - MONTEFIORE - Who is who?

1) Effectuer le chiffrement et le déchiffrement en utilisant l'algorithme RSA pour les valeurs suivantes : a p = 3 ; q = 11 ; e = 7 ; M = 5

[PDF] Exercice 1 cryptographie symétrique TD Cryptographie et ACL

Exercice 2 : chiffrement RSA Question 1 : Effectuer le chiffrement et le déchiffrement en utilisant l'algorithme RSA pour les valeurs suivantes:

cryptographie algorithme RSA Exercices Corriges PDF

Les TDs seront composés d'exercices théoriques portant sur les thèmes du cours Ils serviront à illustrer 5 4 Cryptographie : algorithme RSA

[PDF] CHIFFREMENT PAR LE SYSTÈME RSA - JoseOuinfr

Préambule Cette méthode a été inventée en 1978 par trois mathématiciens Rivet Shamir et Adleman Ce qui fait son originalité c'est que l'algorithme de

[PDF] Examen Final – Cryptographie

jeudi 19 janvier 2006 Correction Exercice 1 Alice change sa clé RSA tous les 25 jours Bob lui change sa clé tous les 31 jours

Comment fonctionne l'algorithme RSA ?
Le cryptage RSA fonctionne en utilisant une paire de clés - clés publiques et privées - pour crypter et décrypter les données. La clé publique est utilisée pour chiffrer les données, tandis que la clé privée est utilisée pour déchiffrer les données.
Comment coder en RSA ?
Protocole RSA pour le codage
e × d + m × (p – 1)(q – 1) = 1 Pour ce faire, elle peut utiliser un algorithme de calcul très connu depuis l'Antiquité (vers 300 ans avant Jésus-Christ) appelé algorithme d'Euclide. Elle calcule également n = p × q.
C'est quoi le chiffrement en informatique ?
Le chiffrement est un procédé de cryptographie qui consiste à protéger des données qui sont alors incompréhensibles pour celui qui ne dispose pas de la clef du chiffrement.
La cryptographie est principalement utilisée pour protéger un message considéré comme confidentiel. Cette méthode est utilisée dans un grand nombre de domaines, tels que la défense, les technologies de l'information, la protection de la vie privée, etc.

Examen Final - Cryptographie

jeudi 19 janvier 2006

Correction

Exercice 1

Alice change sa cl´e RSA tous les 25 jours. Bob lui change sa cl´e tous les 31 jours.

Sachant qu"Alice change sa cl´e aujourd"hui et que Bob a chang´e sa cl´e il y a trois jours,

d´eterminer quand sera la prochaine fois qu"Alice et Bob changeront leur cl´e le mˆeme jour. Solution.Notonsdle nombre de jours jusqu"`a ce que Alice et Bob changent leur cl´e

le mˆeme jour. Puisque Alice change sa cl´e tous les 25 jours et qu"elle a chang´e sa cl´e

aujourd"hui,ddoit ˆetre divisible par 25. Puisque Bob change sa cl´e tous les 31 jours et qu"il a chang´e sa cl´e il y a trois jours,d+ 3 doit ˆetre divisible par 31. Ainsiddoit v´erifier le syst`eme de congruences : d≡0 (mod 25) d≡ -3 (mod 31). Par le th´eor`eme des restes chinois, ce syst`eme ´equivaut `a la congruence d≡400 (mod 775), et donc Alice et Bob changeront leurs cl´es le mˆeme jour dans 400 jours.

Exercice 2

Bob utilise le protocole RSA et publie sa cl´e publiqueN= 187 ete= 3.

1. Encoder le messagem= 15 avec la cl´e publique de Bob.

2. En utilisant le fait que?(N) = 160, retrouver la factorisation deN, puis la cl´e

priv´ee de Bob.

Solution.

1. Le message cod´e estc= 153mod 187 = 9.

2. EcrivonsN=pq. On a donc?(N) = (p-1)(q-1) =pq-p-q+1 =N-(p+q)+1,

et ainsi p+q=N-?(N) + 1 = 187-160 + 1 = 28.

Les nombrespetqsont racines du polynˆome

2-(p+q)X+pq=X2-28X+ 187.

Le discriminant est 28

2-4×187 = 36 et ainsip= (28-6)/2 = 11 etq=

(28 + 6)/2 = 17.

Exercice 3

Soientpetqdeux nombres premiers impairs tels quep≡1 (mod 3) etq≡1 (mod 3).

On poseN=pq.

1. Montrer que

?3N = (-1)(N-1)/2.

2. On suppose de plus queN≡3 (mod 4). En d´eduire que : ou bien 3 est un carr´e

modulopet 3 n"est pas un carr´e moduloq; ou bien 3 n"est pas un carr´e modulo pet 3 est un carr´e moduloq.

Solution.

1. Par la loi de r´eciprocit´e quadratique, on a

?3 N? = (-1)(N-1)/2?pqN et commepq≡1 (modN), on trouve que?pqN = 1, d"o`u le r´esultat.

2. On aN-1≡2 (mod 4) et ainsi (N-1)/2≡1 (mod 2). Par la question 1., il suit

que?3N =-1. Puisque?3N =?3p 3q , on trouve que : ou bien?3p = 1 et ?3q =-1 d"o`u 3 est un carr´e modulop, mais pas moduloq; ou bien?3p =-1 et ?3q = 1 d"o`u 3 est un carr´e moduloq, mais pas modulop.

Exercice 4

Bob

1et Bob2ont pour cl´e publique RSA respectivement (N,e1) et (N,e2) avece1ete2

premiers entre eux. Alice envoie le mˆeme messagemcrypt´e par les cl´es publiques RSA de Bob1et Bob2en c

1etc2.

Expliquer comment Eve, qui intercepte les deux messages crypt´es et qui connait les cl´es publiques de Bob

1et Bob2, peut retrouver le message clairm.

Solution.Puisquee1ete2sont premiers entre eux, il existe deux entiersuetvtels que ue

1+ve2= 1. Eve peut calculeruetv, et finalement retrouve le message en faisant

Exercice 5

On consid`ere un texte de 2nlettres dans lequel exactement une lettre sur deux est un "A".

1. Quelle est la contribution de la lettre "A" dans l"indice de co¨ıncidence de ce texte ?

2. En d´eduire que sin≥2, alors l"indice de co¨ıncidence est≥1/6.

3. Supposons `a pr´esent que toute les lettres autres que "A" sont des "B". Vers quelle

valeur l"indice de co¨ıncidence du texte tend quandntend vers l"infini ? Pourquoi cette r´eponse est-elle bien celle que l"on attend ?

Solution.

1. Puisque le nombre de "A" dans le texte estn, la contributioncAdeAest

A=n(n-1)2n(2n-1)=n-12(2n-1).

2. On a (n-1)/(4n-2)≥1/6 si et seulement 6n-6≥4n-2 si et seulement 2n≥4

si et seulement sin≥2, d"o`u le r´esultat.

3. NotonscBla contribution de "B". Puisqu"une lettre sur deux est un "B", on a donc

par la question 1. quecB= (n-1)/(4n-2). La contribution des autres lettres est nulle et donc l"indice de co¨ıncidence du texte est c

A+cB=n-12n-1.

Il suit que la limite de l"indice de co¨ıncidence quandntend vers +∞est 1/2. On explique pourquoi cette r´eponse est conforme `a ce qu"on attend. En effet, si on prend une lettre au hasard, elle peut ˆetre un "A" ou un "B" avec la mˆeme probabilit´e. Ainsi, si on prend deux lettres au hasard, on a les quatre possibilit´es suivantes avec la mˆeme probabilit´e : AA, AB, BA, BB. Donc la probabilit´e que deux lettres choisit au hasard soient ´egales est bien 1/2.

Exercice 6

On consid`ere un diagramme de Feistel `a deux rondes sur des chaˆınes de 8 bits avec deux fonctionsf1etf2.

1. On pose

1(a) :=a?1011 etf2(a) := ¯a?0101

pour toute chaˆıneade 4 bits. (a) Calculer l"image de la chaˆıne 11010011 par ce diagramme. (b) D´eterminer une chaˆıne de 8 bits dont l"image par le diagramme est elle-mˆeme.

2. La propri´et´e pr´ec´edente, `a savoir il existe une chaˆıne dont l"image par le diagramme

de Feistel est elle-mˆeme, est-elle vraie pour toutes les fonctionsf1etf2? Justifier votre r´eponse par une d´emonstration ou un contre-exemple.

Solution.

1. (a) On calcule les formules donnant le mot de sortiew?1·w?2en fonction du mot

d"entr´eew1·w2: w ?1=f2(f1(w1)?w2)?w1=w

1?1011?w2?0101

=w1?w2?1111?0101 =w1?w2?1010, w ?2=f1(w1)?w2=w1?w2?1011. Ainsi pourw1= 1101 etw2= 0011, on obtientw?1= 1101?0011?1010 =

0100 etw?2= 1101?0011?1011 = 0101. Donc finalement l"image de 11010011

par ce diagramme est 01000101. (b) On veut quew?1=w1etw?2=w2. En rempla¸cant dans les formules ci-dessus, on obtient w

1=w1?w2?1010,

2=w1?w2?1011.

et doncw1?1010 = 0000 etw1= 0101,w2?1011 = 0000 d"o`uw2= 0100. En conclusion, le mot 01010100 est invariant par le diagramme.

2. On consid`ere l"´equationw?2=f1(w1)?w2. Si on prendf1telle quef1(w1)?= 0000

pour toutw1, alors on ne peut jamais avoirw?2=w2et donc, pour ce choix def1, il n"existe pas de mot invariant.quotesdbs_dbs4.pdfusesText_7

[PDF] [PDF] Examen Final – Cryptographie

Comment fonctionne l'algorithme RSA ?

Comment coder en RSA ?

C'est quoi le chiffrement en informatique ?

Examen Final - Cryptographie

Correction

Exercice 1

Exercice 2

1. Encoder le messagem= 15 avec la cl´e publique de Bob.

2. En utilisant le fait que?(N) = 160, retrouver la factorisation deN, puis la cl´e

Solution.

1. Le message cod´e estc= 153mod 187 = 9.

2. EcrivonsN=pq. On a donc?(N) = (p-1)(q-1) =pq-p-q+1 =N-(p+q)+1,

Les nombrespetqsont racines du polynˆome

2-(p+q)X+pq=X2-28X+ 187.

Le discriminant est 28

2-4×187 = 36 et ainsip= (28-6)/2 = 11 etq=

Exercice 3

On poseN=pq.

1. Montrer que

2. On suppose de plus queN≡3 (mod 4). En d´eduire que : ou bien 3 est un carr´e

Solution.

1. Par la loi de r´eciprocit´e quadratique, on a

2. On aN-1≡2 (mod 4) et ainsi (N-1)/2≡1 (mod 2). Par la question 1., il suit

Exercice 4

1et Bob2ont pour cl´e publique RSA respectivement (N,e1) et (N,e2) avece1ete2

1etc2.

1et Bob2, peut retrouver le message clairm.

1+ve2= 1. Eve peut calculeruetv, et finalement retrouve le message en faisant

Exercice 5

1. Quelle est la contribution de la lettre "A" dans l"indice de co¨ıncidence de ce texte ?

2. En d´eduire que sin≥2, alors l"indice de co¨ıncidence est≥1/6.

3. Supposons `a pr´esent que toute les lettres autres que "A" sont des "B". Vers quelle

Solution.

1. Puisque le nombre de "A" dans le texte estn, la contributioncAdeAest

A=n(n-1)2n(2n-1)=n-12(2n-1).

2. On a (n-1)/(4n-2)≥1/6 si et seulement 6n-6≥4n-2 si et seulement 2n≥4

3. NotonscBla contribution de "B". Puisqu"une lettre sur deux est un "B", on a donc

A+cB=n-12n-1.

Exercice 6

1. On pose

1(a) :=a?1011 etf2(a) := ¯a?0101

2. La propri´et´e pr´ec´edente, `a savoir il existe une chaˆıne dont l"image par le diagramme

Solution.

1. (a) On calcule les formules donnant le mot de sortiew?1·w?2en fonction du mot

1?1011?w2?0101

0100 etw?2= 1101?0011?1011 = 0101. Donc finalement l"image de 11010011

1=w1?w2?1010,

2=w1?w2?1011.

2. On consid`ere l"´equationw?2=f1(w1)?w2. Si on prendf1telle quef1(w1)?= 0000