TD 1

Télécharger au format pdf ou txt
Télécharger au format pdf ou txt
Vous êtes sur la page 1sur 4

Université Paris 8 J.

Lavauzelle
Master 1 Mathématiques et applications — année 2022–23

Cryptographie à clé publique – Feuille de TD 1


27/01/2023

Le corrigé de certains exercices sera disponible à l’adresse suivante :


www.math.univ-paris13.fr/∼lavauzelle/teaching/2022-23/clef-publique.html

(?) exercice fondamental (??) pour s’entraîner (???) pour aller plus loin § sur machine

Exercice 1. (?)
Exercice 1. (?) Application
Application du
du protocole
protocole de
de Diffie–Hellman.
Diffie–Hellman.
On exécute le protocole de Diffie–Hellman dans le groupe multiplicatif G = F×
p avec les para-
mètres suivants :
— p = 19,
— le générateur du groupe est g = 2,
— la valeur secrète d’Alice est a = 4,
— la valeur secrète de Bob est b = 6.
Question 1.– Quelle est la valeur commune obtenue par Alice et Bob ?
On souhaite maintenant exécuter le protocole de Diffie–Hellman dans le sous-groupe des résidus
×
quadratiques de F×
p , que l’on note QR p . Pour cela on garde la valeur p = 19.

Question 2.– L’élément g = 2 reste-t-il un générateur de QR×


p ?

Question 3.– Démontrer que 5 est un générateur de QR×


p.

Question 4.– Exécuter le protocole de Diffie–Hellman dans QR×


p avec les valeurs suivantes :
— p = 19,
— g = 5,
— la valeur secrète d’Alice a = 4,
— la valeur secrète de Bob est b = 6.

1
Exercice 2.
Exercice (??) Protocole
2. (??) Protocole de
de Diffie–Hellman
Diffie–Hellman dans Z/nZ, +)
dans ((Z/nZ, +)..
On considère une variante additive du protocole de Diffie–Hellman dans le groupe fini G =
(Z/nZ, +) où n est un très grand nombre entier. Pour cela, on fixe un générateur M 6= 0 du
groupe G, que l’on publie. Dans cette version « additive », le protocole devient donc :

Alice Bob

engendre a ∈ Z/nZ engendre b ∈ Z/nZ


u = aM mod n

v = bM mod n
calcule av mod n calcule bu mod n

Question 1.– Donner une caractérisation simple des générateurs du groupe additif (Z/nZ, +).
Puis, proposer un exemple de générateur qui convient pour tout n.

Question 2.– Vérifier que lorsqu’ils suivent le protocole ci-dessus, Alice et Bob détiennent bien
un secret commun.

Question 3.– Rappeler un algorithme qui calcule l’inverse modulaire dans Z/nZ (autrement
dit, qui effectue l’opération x 7→ x −1 mod n). La complexité de cet algorithme est-elle polyno-
miale en log n ?

Question 4.– Selon vous, la variante du protocole de Diffie–Hellman proposée dans cet exercice
est-elle sûre ? Justifier.

Exercice 3.
Exercice (??) Échange
3. (??) Échange de
de clefs
clefs et
et masque
masque jetable.
jetable.
On note X = F2n l’ensemble des chaînes de bits de longueur n, munies de l’opération de xor
bit-à-bit, notée ⊕. On considère le protocole d’échange de clefs suivant.

Alice Bob

engendre aléatoirement k, r ∈ X engendre aléatoirement t ∈ X


s = k⊕r

u = s⊕t

v = u⊕r

détient k détient v ⊕ t

Question 1.– Vérifier qu’Alice et Bob détiennent bien un secret commun.

Question 2.– Le protocole est-il sûr ? Justifier.

2
Exercice 4.
Exercice (??) Une
4. (??) Une variante
variante de
de Diffie–Hellman.
Diffie–Hellman.
Alice et Bob souhaitent échanger un secret commun. Pour cela, ils mettent en place une variante
du protocole de Diffie–Hellman. On se place donc dans un groupe cyclique G d’ordre q. On
suppose que q est premier. Enfin, un générateur g de G est donné publiquement.
On suppose qu’Alice a engendré une valeur secrète aléatoire a ∈ (Z/qZ)× , et a publié g a ∈ G.
De même, Bob a engendré une valeur secrète b ∈ (Z/qZ)× et publié gb ∈ G. Le protocole
d’échange de secret commun est décrit ci-dessous.

Alice Bob

détient gb ∈ G et a ∈ (Z/qZ)× détient g a ∈ G et b ∈ (Z/qZ)×

engendre aléatoirement y ∈ Z/qZ engendre aléatoirement x ∈ Z/qZ


u= gy

v = gx
calcule et obtient g ax+by calcule et obtient g ax+by

Question 1.– Détailler les calculs permettant à Alice et Bob de calculer la valeur commune
g ax+by , à partir des valeurs que chacun détient. En donner la complexité.

Question 2.– Une fois que les entiers a et b sont fixés, quelle est la taille de l’ensemble des
valeurs communes possibles ?

Question 3.– Pourquoi l’attaque de la personne au milieu (man-in-the-middle), telle que décrite
dans le cours pour le protocole de Diffie–Hellman, ne fonctionne-t-elle pas dans le cas présent ?

Question 4.– Supposons que l’on détienne un algorithme A qui sache résoudre efficacement
le problème CDH (Diffie–Hellman calculatoire). Démontrer qu’on peut alors retrouver la valeur
commune détenue par Alice et Bob en observant leurs échanges (c’est-à-dire en procédant à une
attaque passive).

Exercice 5. (???)
Exercice 5. (???) Problèmes
Problèmes DH
DH et
et sqDH.
sqDH.
Soit G un groupe cyclique d’ordre r, et g ∈ G un générateur du groupe. On rappelle que le
problème calculatoire de Diffie–Hellman dans G est :

CDH : étant donné ( g, g a , gb ), calculer g ab

On définit maintenant le problème de « Diffie–Hellman carré » dans G comme :

2
sqDH : étant donné ( g, g a ), calculer g a .

Question 1.– Expliquer en quoi sqDH peut être vu comme un sous-problème de CDH.

Question 2.– Supposons que l’on détienne un algorithme A qui résout efficacement sqDH.
Démontrer qu’à partir d’une instance ( g, g a , gb ) de CDH, on peut calculer g2ab .

3
Question 3.– Pour simplifier, on suppose ici que r est impair. On dit que x est un carré dans
G s’il existe un y ∈ G tel que x = y2 . Décrire un algorithme qui calcule une racine carrée d’un
carré x ∈ G.

Question 4.– Toujours dans le cas où r est impair, en conclure que CDH se réduit à sqDH.

×
× ×
Exercice 6.
Exercice § Implantation
(??) §
6. (??) Implantation de
de Diffie–Hellman
Diffie–Hellman dans QRp×
dans QR ppp ..

Dans cet exercice on suppose que p est un nombre premier de taille importante tel que p0 =
( p − 1)/2 est également un nombre premier. Un tel nombre premier p est appelé nombre
premier sûr, tandis que p0 est un nombre premier de Sophie Germain.
Question 1.– Trouver dans les bibliothèques random et math de python comment :
— tirer uniformément un entier entre 1 et x,
— calculer efficacement une puissance modulaire,
— calculer efficacement un inverse modulaire.

Question 2.– Écrire une fonction is_square(x, p) qui teste si un entier x est un résidu quadra-
tique modulo p.

Question 3.– Écrire une fonction random_QR_generator(p) qui retourne un générateur aléatoire
du groupe des résidus quadratiques modulo p. On rappelle que l’on suppose que p0 = ( p − 1)/2
est également un nombre premier.

Question 4.– Écrire les fonctions suivantes du protocole de Diffie–Hellman :


— une fonction system_parameters(t) qui définit les paramètres du protocole : un nombre
premier p aléatoire de taille t bits tel que p0 = ( p − 1)/2 est aussi premier, et le générateur
aléatoire g de QR× p,
— une fonction random_secret(p) qui définit la valeur secrète x engendrée par un participant
au protocole,
— une fonction to_send(x, g, p) qui déduit de la valeur secrète x et du générateur g la
valeur à transmettre à l’autre participant,
— une fonction shared_value(gy, x, p) qui déduit de la valeur reçue gy (= gy ) et de lm
valeur secrète x, la valeur commune aux deux participants.
Pour l’implantation de la fonction system_parameters(t), on pourra notamment s’aider de la
fonction Crypto.Util.number.getPrime(t) de la bibiothèque Crypto.Util, voir :

https://pycryptodome.readthedocs.io/en/latest/src/util/util.html#Crypto.Util.number.getPrime

Question 5.– En choisissant une taille t = 64 (exemple-jouet), tester vos fonctions en exécutant
les actions successives d’Alice et Bob dans le protocole de Diffie–Hellman.

Vous aimerez peut-être aussi