Feuille 3 : RSA 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.

Licence 3 - MHT633 Université Bordeaux 1

2009/2010

Feuille 3 : RSA

Exercice 1. Chiffrement RSA

1. Soitn=pqoùpetqsont des nombres premiers distincts. Le système RSA chiffre

x?Z/nZenxb?Z/nZ. Puis on déchiffrey?Z/nZparya?Z/nZpoura?Ztel queab≡1 (mod?(n)) (a) Quelle est la clé publique? la clé privée? (b) Montrer que six?(Z/nZ)×alorsd◦e(x) =x. (c) La composée de deux chiffrements RSA est-elle un chiffrement RSA? (d) Dans cette question on fixepetqdeux nombres premiers distincts. Combien a-t-on de choix de clé?

2. Dans cette question on souhaite implémenter un système RSA avecn= 221.

(a) Calculer?(n). (b) Vérifier que l"on peut choisir7comme exposant de chiffrement. (c) Chiffrer le messageM= 3pour cette exposant. (d) Calculer l"exposant de déchiffrement. Préciser alors la clé publique et la clé privée. (e) Déchiffrer le messageC= 2.

Exercice 2. Mauvais choix depetq

On note(n,b)la clé publique d"un système RSA.

1. Sin= 35déterminer tous lesbpossibles.

2. Sin= 211×499peut-on prendreb= 1623?

3. Si la clé publique est(492153,2237), quelle est la clé privée?

4. Même question avec(2173,361). Lequel de ces deux choix de clé privée est le plus

judicieux? Que doit-on éviter dans les choix depetq? 1 Exercice 3. Une majoration de la complexité de l"algorithme d"Euclide Soientaetbdeux entiers tels quea > b. On noter0=aetr1=b. On applique l"algortihme d"Euclide àaetbde la manière suivante : a=r0=r1q1+r2 r

1=r2q2+r3

r n-2=rn-1qn-1+rn oùrn= pgcd(a,b). L"objectif de cet exercice est de majorer la complexité de l"algorithme d"Euclide. On rappelle que la complexité de la division euclidienne dexparypeut s"écrire O(logylogq)oùqest le quotient de la division euclidienne dexpary.

1. Montrer que la complexité est majorée parO¡logblog(Qn

i=1qi)¢.

2. Prouver que pourk= 1,...,n, on aa > rkqkqk-1...q1. Conclure.

3. En remarquant, que la multiplication et la division euclidienne ont la même com-

plexité, que peut-on dire de la complexité de l"algorithme d"Euclide étendu.

Exercice 4. Déchiffrement de RSA

Dans cette exercice, on montre comment on peut accélérer le déchiffrement du système RSA en utilisant le théorème des restes chinois. Soitn=pqproduit de deux nombres premiers etd?N. Supposons que la fonction de déchiffrement de RSA soit donnée par :dK(y) =yd(modn).

1. Calculerxp=yd(modp)etxq=yd(modq).

2. Résoudre le système dansZ/nZ:

(x≡xp(modp), x≡xq(modq). Justifier que sixest solution du système ci dessus alorsx≡yd(modn).

3. Sachant que la complexité de l"algorithme d"Euclide étendu entre deux entiersa

etbestO(logalogb). Calculer la complexité de cet algorithme de déchiffrement Comparer avec la complexité de l"algorithme de déchiffrement naïf.

4. En utilisant cette méthode déchiffrer le messageC= 2pourn= 221 = 13.17et

d= 63. Exercice 5. Connaîtrepetq, c"est connaître?(n) On suppose quenest un entier naturel non nul dont la décomposition en facteurs premiers estn=pq. 2

1. Exprimer?(n)en fonction depetq.

2. Exprimerpqetp+qen fonction denet?(n). En déduire une méthode pour obtenir

petqlorsque l"on connaitnet?(n).

3. Sin= 17063et?(n) = 16800, calculerpetq.

Exercice 6. Une attaque sur RSA : petit exposant public commun On suppose quekpersonnesB1,...,Bkont pour exposant public RSAe= 3avec des

1. Pourquoi est-il raisonnable de supposer que les

premiers entre eux?

2. Alice envoie les chiffrés d"un même messagemà tous lesBi. Montrer qu"un attaquant

peut déterminerm3moduloP:=Qk i=1ni; en déduire qu"il peut calculermsiP > m3.

3. Quel est la valeur minimale dekqui permet de toujours faire cette attaque?

Exercice 7. Une attaque sur RSA : module commun

Bob et Catherine ont choisi le même module RSAn. Leurs exposants publicseBeteC sont distincts.

1. Expliquez pourquoi Bob peut déchiffrer les messages reçus par Catherine et récipro-

quement.

2. On suppose queeBeteCsont premiers entre eux et qu"Alice envoie les chiffrés d"un

même messagemà Bob et à Catherine. Expliquez comment l"attaquant Oscar peut obtenirm.

3. Application : Bob a la clef publique(221,11)et Catherine la clef(221,7). Oscar inter-

cepte les chiffrés210et58à destinations respectives de Bob et Catherine. Retrouver le messagem.

Exercice 8. Module RSA avec deux facteurs proches

Supposons quensoit un entier produit de deux nombres premierspetq,p > q. On suppose quepetqsont proches, c"est à dire que?:=p-qest petit. On poset=p+q 2 et s=p-q 2

1. Montrer quen=t2-s2.

2. Quel est la taille des? Comparertet⎷

3. Montrer comment utiliser cela pour écrire un algorithme (de Fermat) factorisantn.

4. Application : factoriser11598781.

5. Déterminer le nombre d"itérations de l"algorithme en fonction depet den. Que se

passe t"il sip-⎷ n <

4⎷

4n? 3 Exercice 9. Dans RSA, connaîtredest équivalent à connaîtrepetq Supposons quensoit un entier produit de deux nombres premiers distinctspetq. On notee, premier avec?(n), l"exposant public d"un système RSA de modulon. Connaissantp etq, l"exposant privédse calcule en temps polynomial. Le but de l"exercice est de montrer que si un attaquant connaîtdalors il peut factorisernen temps polynomial.

1. Montrer comment à partir dee,detnon peut construire un multipleBde?(n).

2. On noteλ= ppcm(p-1,q-1).Montrer que pour touta?(Z/nZ)×,aλ= 1. Montrer

queaλ/2peut prendre 4 valeurs et que 2 de ces valeurs permettent de factorisern.

3. On poseH={a?(Z/nZ)×, aλ/2≡ ±1}. Montrer queHest un sous-groupe de

(Z/nZ)×.

4. Montrer qu"il existeb?(Z/nZ)×tel quebsoit d"ordrep-1modulopet d"ordre

(q-1)/2moduloq.

5. On posep-1 = 2vpp?etq-1 = 2vqq?avecp?,q?impairs et on suppose, sans perte

de généralité quevp≥vq. Exprimerλ/2en fonction devpet du ppcm dep?,q?. En déduire quebn"appartient pas àH. Si on prendxau hasard dans(Z/nZ)×, montrer que la probabilité quexn"appartienne pas àHest supérieure ou égale à1/2.

6. Soitx?(Z/nZ)×. Montrer queλdiviseBet en déduire qu"il existe un entierktel

quexλ/2=xB/2k+1.

7. Conclure : donner un algorithme probabiliste polynomial qui factorisenétant donné

n,eetdet donner sa probabilité de succés.

8. Application :n= 77,e= 7,d= 43

4quotesdbs_dbs29.pdfusesText_35

[PDF] Feuille 3 : RSA

Comment fonctionne l'algorithme RSA ?

Comment coder en RSA ?

C'est quoi le chiffrement en informatique ?

Licence 3 - MHT633 Université Bordeaux 1

2009/2010

Feuille 3 : RSA

Exercice 1. Chiffrement RSA

1. Soitn=pqoùpetqsont des nombres premiers distincts. Le système RSA chiffre

2. Dans cette question on souhaite implémenter un système RSA avecn= 221.

Exercice 2. Mauvais choix depetq

1. Sin= 35déterminer tous lesbpossibles.

2. Sin= 211×499peut-on prendreb= 1623?

3. Si la clé publique est(492153,2237), quelle est la clé privée?

4. Même question avec(2173,361). Lequel de ces deux choix de clé privée est le plus

1=r2q2+r3

1. Montrer que la complexité est majorée parO¡logblog(Qn

2. Prouver que pourk= 1,...,n, on aa > rkqkqk-1...q1. Conclure.

3. En remarquant, que la multiplication et la division euclidienne ont la même com-

Exercice 4. Déchiffrement de RSA

1. Calculerxp=yd(modp)etxq=yd(modq).

2. Résoudre le système dansZ/nZ:

3. Sachant que la complexité de l"algorithme d"Euclide étendu entre deux entiersa

4. En utilisant cette méthode déchiffrer le messageC= 2pourn= 221 = 13.17et

1. Exprimer?(n)en fonction depetq.

2. Exprimerpqetp+qen fonction denet?(n). En déduire une méthode pour obtenir

3. Sin= 17063et?(n) = 16800, calculerpetq.

1. Pourquoi est-il raisonnable de supposer que les

2. Alice envoie les chiffrés d"un même messagemà tous lesBi. Montrer qu"un attaquant

3. Quel est la valeur minimale dekqui permet de toujours faire cette attaque?

Exercice 7. Une attaque sur RSA : module commun

1. Expliquez pourquoi Bob peut déchiffrer les messages reçus par Catherine et récipro-

2. On suppose queeBeteCsont premiers entre eux et qu"Alice envoie les chiffrés d"un

3. Application : Bob a la clef publique(221,11)et Catherine la clef(221,7). Oscar inter-

Exercice 8. Module RSA avec deux facteurs proches

1. Montrer quen=t2-s2.

2. Quel est la taille des? Comparertet⎷

3. Montrer comment utiliser cela pour écrire un algorithme (de Fermat) factorisantn.

4. Application : factoriser11598781.

5. Déterminer le nombre d"itérations de l"algorithme en fonction depet den. Que se

4⎷

1. Montrer comment à partir dee,detnon peut construire un multipleBde?(n).

2. On noteλ= ppcm(p-1,q-1).Montrer que pour touta?(Z/nZ)×,aλ= 1. Montrer

3. On poseH={a?(Z/nZ)×, aλ/2≡ ±1}. Montrer queHest un sous-groupe de

4. Montrer qu"il existeb?(Z/nZ)×tel quebsoit d"ordrep-1modulopet d"ordre

5. On posep-1 = 2vpp?etq-1 = 2vqq?avecp?,q?impairs et on suppose, sans perte

6. Soitx?(Z/nZ)×. Montrer queλdiviseBet en déduire qu"il existe un entierktel

7. Conclure : donner un algorithme probabiliste polynomial qui factorisenétant donné

8. Application :n= 77,e= 7,d= 43