Examen Cryptographie | Décomposition en facteurs premiers – Bézout

Thèmes :

Exercice 1: Divisibilité / Nombre premier / Congruence / Factorisation
Exercice 2: Fonction indicatrice d’Euler / Décomposition en facteurs premiers
Exercice 3: Système RSA / Protocole de Diffie Helmann / Élément primitif
Exercice 4: Nombre premier / Congruence / Modulo / Bézout

Extrait :

Exercice 1. Montrer les résultats suivants :

a/ Soit n un entier ; alors n⁷ – n est divisible par 42.

b/ Soit n un entier impair ; montrer que 8 divise n² – 1.

c/ Soit p un nombre premier ; montrer que -1 est un carré dans ℤ/pℤ si et seulement si
d/ Résoudre la congruence 1 + x + x² + x³ + x⁴ + x⁵ 0 [13].

e/ Soit n = 16837, et r = 6555. On admet que En déduire la factorisation de n

Exercice 2. (Autour de la fonction indicatrice d’Euler)

1/ Soit n un entier, et sa décomposition en facteurs premiers.

a./ Rappeler la formule qui donne ¢»(n).

b/ Résoudre l’équation = 1

2/ On suppose qu’il n’existe qu’un nombre fini de nombres premiers , et on pose n =
leur produit.

a/ Montrer, à l’aide de la décomposition en facteurs premiers, qu’on a alors = 1
b/ Conclure à l’aide du l/ qu’il existe une infinité de nombres premiers.

3/ Soit n un entier quelconque.

a./ Montrer que si t est un entier compris entre 1 et n – 1, premier avec n, alors n – t a la même propriété.
b / Montrer que la somme des entiers compris entre 1 et n — 1 et premiers avec n vaut

Exercice 3. (Protocoles cryptographiques)
1/ On pose p = 11, q = 19, n = pq et e = 103. Un utilisateur de RSA choisit comme clef publique (n, e).
Quel est son exposant privé ? il reçoit le message crypté 3. Quel est le message Clair ?

2/ a/ Rappeler le protocole de Diffie Helmann. Quel est son intérêt ?

b/ Montrer que 2 est un élément primitif de ℤ/13ℤ

c/ Quel est le secret que partagent A et B en utilisant le protocole de Diffie Helmann avec p = 13, 2
comme élément primitif, et a = 5, b = 7 comme paramètres privés ?

Exercice 4. (Racines carrées modulo pq) On admet dans tout cet exercice que si p est un nombre
premier, et 1 ≤ k ≤ p — 1, alors l’équation admet deux solutions dans ℤ/pℤ, ou n’en admet aucune.
De même, si n = pq est le produit de deux nombres premiers distincts, et 1 ≤ k ≤ n –
1, alors l’équation
admet quatre solutions dans ℤ/nℤ, ou n’en admet aucune.

1/ Supposons que p est un nombre premier congru à 3 modulo. 4, et que l’équation admet deux
solutions dans ℤ/pℤ. Montrer que ces solutions sont et

Téléchargement :