Université Paris 8 J.
Lavauzelle
Master 1 Mathématiques et applications — année 2023–24
Cryptographie à clé publique – Feuille de TD 3
05/02/2024
Le corrigé de certains exercices sera disponible à l’adresse suivante :
[Link]
(⋆) exercice fondamental (⋆⋆) pour s’entraîner (⋆⋆⋆) pour aller plus loin § sur machine
××
Exercice 1.
Exercice (⋆) Structure
1. (⋆) Structure de QR×
de QR × .
nn .
nn
Pour m ≥ 2 un entier, on rappelle que l’on note
QR× ×
m := { x | x ∈ (Z/mZ) }
2
l’ensemble des résidus quadratiques inversibles modulo m.
Dans cet exercice, on considère p et q deux nombres premiers impairs distincts et on note n = pq.
Question 1.– Démontrer que si x ∈ QR×
n , alors x est un carré modulo p.
Question 2.– Démontrer que le groupe QR× × ×
n est isomorphe au groupe produit QR p × QRq . En
déduire que le cardinal de QR×
n est ϕ ( n ) /4, où ϕ ( n ) est l’indicatrice d’Euler de n.
Considérons maintenant l’application d’élévation au carré
f : QR×n → QR×
n
m 7→ m2 mod n
Question 3.– On suppose ici que p ≡ q ≡ 3 mod 4. Démontrer que f est un automorphisme
du groupe QR×n.
Exercice 2. (⋆) Racine carrée modulo p pour p ≡ 3 mod 4.
Dans cet exercice, on considère p un nombre premier tel que p ≡ 3 mod 4.
Question 1.– Soit y un carré dans F p . Démontrer que y( p+1)/2 = y.
Question 2.– En déduire que, dans le contexte de l’exercice (p ≡ 3 mod 4), on peut obtenir
une racine carrée de y dans F p en calculant y( p+1)/4 .
Question 3.– Quelle est la complexité du calcul précédent, en nombre d’opérations élémentaires
dans F p ?
1
Exercice 3.
Exercice (⋆⋆) Réduction
3. (⋆⋆) Réduction de
de la
la factorisation
factorisation àà l’extraction
l’extraction de
de racine
racine carrée.
carrée.
Soit SQRT le problème du calcul de racine carrée modulo n :
Instance : une paire (n, x ) où n = pq avec p et q des nombres premiers distincts, et x = y2
mod n pour un certain y ∈ (Z/nZ)× .
Objectif : calculer un y tel que y2 ≡ x mod n.
Soit également FACT le problème de la factorisation d’un entier produit de deux nombres pre-
miers distncts n :
Instance : un entier n où n = pq avec p et q des nombres premiers distincts.
Objectif : calculer p et q.
On admet qu’on dispose d’algorithmes efficaces pour calculer, si elles existent, des racines car-
rées modulo un nombre premier.
Question 1.– Démontrer que SQRT se réduit à FACT. Autrement dit, démontrer que si l’on
dispose d’un algorithme qui factorise n, alors on peut extraire n’importe quelle racine carrée
modulo n.
Question 2.– Démontrer que FACT se réduit à SQRT.
Indication : pour cela, on pourra appeller l’algorithme qui résout SQRT, en fournissant des entrées dont
on connaît a priori une racine carrée.
Exercice 4. (⋆⋆)
Exercice 4. (⋆⋆) Autour
Autour du
du chiffrement
chiffrement de
de Goldwasser–Micali.
Goldwasser–Micali.
On considère p et q deux nombres premiers distincts tels que p ≡ q ≡ 3 mod 4. On note n = pq
et on rappelle que
QR× n := { x | x ∈ (Z/nZ) }
2 ×
représente l’ensemble des résidus quadratiques inversibles modulo n.
Question 1.– Démontrer que pour x = n − 1, on a
x x
= = −1 .
p q
Question 2.– Le résultat de la question précédente reste-t-il vrai si p ̸≡ 3 mod 4 ?
On appelle « pseudo-carré inversible modulo n » un élément x ∈ (Z/nZ)× tel que
x
= 1 et x ∈ / QR×
n .
n
×
On note QRn l’ensemble des pseudo-carrés inversibles modulo n.
×
Question 3.– Démontrer que n − 1 ∈ QRn .
×
Question 4.– L’ensemble QRn est-il un groupe ?
× ×
Question 5.– Fixons y ∈ QRn . Démontrer que QR× n et QRn ont même cardinal. Pour cela, on
pourra construire une bijection entre ces deux ensembles.
On rappelle dans les Algorithmes 1, 2 et 3 comment fonctionne le cryptosystème de Goldwasser–
Micali dans le cas où p ≡ q ≡ 3 mod 4 et où l’on choisit l’élément public x = n − 1.
2
Question 6.– Rappeler de quelle taille doit être n pour qu’il soit supposé calculatoirement
infaisable de le factoriser.
Question 7.– Pour des raisons d’efficacité, Bob choisit d’utiliser un générateur de nombres
aléatoires tels que les yi sont tous ≤ 2128 . Il pense que comme il y a 2128 possibilités pour chaque
yi , le système reste sûr. Est-ce vraiment le cas ? Justifier.
Question 8.– On note E la fonction de chiffrement de Goldwasser–Micali, pour une paire de clé
fixée. Démontrer que si
m = a ⊕ b := ( a1 + b1 , a2 + b2 , . . . , ak + bk ) ,
alors E( a) ⋆ E(b) est un chiffré valide de E(m), où ⋆ représente le produit coordonnée par
coordonnée. On parle alors de chiffrement homomorphe.
Algorithme 1 : Génération de clés dans le cryptosystème de Goldwasser–Micali
Entrée : un paramètre de sécurité
Sortie : une paire de clés publique/privée
1 Choisir aléatoirement deux grands nombres premiers distincts p et q tels que p ≡ q ≡ 3
mod 4.
2 Calculer n = pq.
3 Retourner la clé publique n, et la clé privée ( p, q ).
Algorithme 2 : Chiffrement dans le cryptosystème de Goldwasser–Micali
Entrée : la clé publique n, un message m = (m1 , . . . , mk ) ∈ {0,1}k
Sortie : un chiffré c = (c1 , . . . , ck ) ∈ (Z/nZ)k
1 Pour tout i = 1, . . . , k faire
2 Choisir aléatoirement yi ∈ (Z/nZ)× .
3 Définir ci = y2i · (−1)mi mod n.
4 Retourner c = (c1 , . . . , ck ).
Algorithme 3 : Déchiffrement dans le cryptosystème de Goldwasser–Micali
Entrée : la clé privée p,q, un chiffré c = (c1 , . . . , ck ) ∈ (Z/nZ)k
Sortie : un message m = (m1 , . . . , mk ) ∈ {0,1}k
1 Pour tout i = 1, . . . , k faire
2 Calcule a = ci mod p.
3 Si a est un carré modulo p
4 Affecter mi = 0.
5 Sinon
6 Affecter mi = 1.
7 Retourner m = (m1 , . . . , mk ).
3
Exercice 5.
Exercice § (⋆)
5. § (⋆) Implantation
Implantation du
du calcul
calcul du
du symbole
symbole de
de Jacobi.
Jacobi.
Question 1.– Implanter un algorithme de calcul du symbole de Jacobi na , où a et n sont deux
entiers tels que n est impair. On n’utilisera pas d’algorithme de factorisation, mais on pourra se
référer par exemple à l’Algorithme 4.
a
Algorithme 4 : Algorithme Jacobi pour le calcul du symbole n
Entrée : a ∈ Z et n ∈ N impair
Sortie : le symbole de Jacobi na
1 Si a = 0
2 Retourner 0
3 Si a = 1
4 Retourner 1
5 Si a = n − 1
6 Si a ≡ 0 mod 4
7 Retourner 1
8 Sinon
9 Retourner −1
10 Si a ≡ 0 mod 2
11 Si n ≡ 1 mod 8 ou n ≡ 7 mod 8
12 Retourner Jacobi(a/2, n)
13 Sinon
14 Retourner (−1) × Jacobi( a/2, n)
15 Si a ≥ n
16 Retourner Jacobi(a mod n, n)
17 Si a ≡ 1 mod 4 ou n ≡ 1 mod 4
18 Retourner Jacobi(n, a)
19 Sinon
20 Retourner (−1) × Jacobi(n, a).
