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 :

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

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 $p\equiv 1\left[ 4 \right]$
d/ Résoudre la congruence 1 + x + x² + x³ + x⁴ + x⁵ $\equiv$ 0 [13].

e/ Soit n = 16837, et r = 6555. On admet que ${ r }^{ 2 }\equiv 1\left[ n \right]$ En déduire la factorisation de n

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

1/ Soit n un entier, et $n={ p }_{ 1 }^{ { m }_{ 1 } }...{ p }_{ k }^{ { m }_{ k } }$ sa décomposition en facteurs premiers.

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

b/ Résoudre l’équation $\phi (n)$ = 1

2/ On suppose qu’il n’existe qu’un nombre ﬁni de nombres premiers ${ p }_{ 1 },...,{ p }_{ t }$ , et on pose n = ${ p }_{ 1 },...,{ p }_{ t }$
leur produit.

a/ Montrer, à l’aide de la décomposition en facteurs premiers, qu’on a alors $\phi (n)$ = 1
b/ Conclure à l’aide du l/ qu’il existe une inﬁnité 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 $\frac { 1 }{ 2 } n\phi (n)$

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 ${ \bar { x } }^{ 2 }=\bar { k }$ 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
${ \bar { x } }^{ 2 }=\bar { k }$ 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 ${ \bar { x } }^{ 2 }\equiv \bar { k }$ admet deux
solutions dans ℤ/pℤ. Montrer que ces solutions sont ${ k }^{ -\frac { p\div 1 }{ 4 } }$ et $-{ k }^{ -\frac { p+1 }{ 4 } }$