Examen Cryptographie | Système RSA – Inversible

Thèmes :

Question de cours: Système RSA
Exercice 1: Nombre premier / Divisibilité / Inversible / Division euclidien
Exercice 2: Nombre premier / Division euclidienne / Facteurs premiers /
Exercice 3: x²+y²=z² / Équation / PGCD / Modulo / Nombres premiers / Divisibilité

Extrait :

Cours Alice souhaite utiliser le système RSA pour recevoir des messages
cryptés ; elle choisit donc deux grands nombres premiers p₁ et p₂, calcule leur
produit . Elle calcule ensuite , choisit un entier compris entre 2 et — 1, premier avec , et calcule l’entier compris entre
2 et. Elle publie alors le couple qui est sa clef secrète, et garde pour elle l’entier qui est sa clef privée.

1/ Pourquoi un entier ayant les propriétés ci—dessus existe-t-il ? Comment Alice va-t-elle le calculer ?

2/ Bob souhaite envoyer un message m, vu comme un entier compris
entre 2 et — 1 à Alice.

a/ Quel calcul effectue Bob avant d’envoyer son message ?

b/ Quel calcul doit effectuer Alice pour décrypter le message de Bob ?
Pourquoi ?

c/ Pourquoi un observateur, qui aurait lu le message envoyé par Bob
ne peut espérer retrouver le message original, même en connaissant la clef
publique d’Alice ?

d/ Pourquoi est-il déconseillé à Alice de choisir pour p₁ et p₂ deux entiers
proches ?

Exercice 1. Répondre en justifiant aux questions suivantes :

i) trouver l’unique nombre premier qui s’écrit avec 7 chiffres en base 2 et
4 chiflres en base 5 ;

ii) pour quelles valeurs de l’entier n le nombre + 1 est-il divisible
par 7 ?

iii) pourquoi le nombre 14 est-il inversible dans ℤ/393ℤ ? calculer son
inverse

iv) calculer les restes des divisions euclidiennes de par 25 en fonction de
l’entier n ;
v) montrer qu‘un entier p est premier si et seulement si p ne divise pas
(p — 1)!

Soit n un entier qui n’est multiple ni de 2 ni de 3 ni de 5 ; montrer
qu’on a

Exercice 2. On veut montrer qu’il y a une infinité de nombres premiers
congrus à 3 modulo 4, comme 3, 7, 11,… .

1/ Soit p > 2 un nombre premier ; quels sont les restes possibles pour la
division euclidienne de p par 4 ?

2/ Soit n un entier naturel dont tous les facteurs premiers p vérifient
; montrer que En déduire que si , alors n a au
moins un facteur premier p tel que

3/ On suppose qu‘il n’y a. qu’un nombre fini de nombres premiers
congrus à trois modulo 4 ; en considérant l’entier — 1, trouver une contradiction, et déduire le résultat.

Téléchargement :