Séance 1 : autour de l’échange de clefs de Diffie–Hellman

Contenu

Séance 1 : autour de l’échange de clefs de Diffie–Hellman#

Pré-requis : installation de la bibliothèque `pycryptodome`#

Les TPs de ce cours de Cryptographie à clef publique nécessitent l’utilisation d’objets et de fonctions non-natifs de python, c’est-à-dire qui n’existent pas dans la version standard du langage. C’est le cas par exemple de certaines fonctions arithmétiques, ou de fonctions de nature cryptographique que nous n’aurons pas le temps d’implémenter par nous-mêmes.

La bibliothèque pycryptodome contient l’ensemble de ces fonctions. Vous pouvez retrouver la documentation à l’adresse suivante.

Pour l’installer sur votre machine (Linux), ouvrez un terminal et entrez la commande suivante

pip install pycryptodomex

Suivant votre configuration, il se peut que vous deviez remplacer pip ci-dessus par pip3 ou par python -m pip. Appelez l’enseignant si nécessaire. Pour les autres distributions, voir la documentation.

Une fois l’installation réussie, vous pouvez essayer de faire fonctionner cette nouvelle bibliothèque. Pour cela, exécutez le contenu de la cellule suivante :

from Crypto.Util.number import getPrime
print(getPrime(10))
print(getPrime(100))

1019
1039707310245603978534360515813

Vous devriez voir apparaître deux nombres premiers aléatoires de taille $10$ bits et $100$ bits (mais pas nécessairement les mêmes que ceux affichés sur la page web du cours). En effet, à retenir : la fonction getPrime(t) du module Crypto.Util.number retourne un nombre premier aléatoire de taille t bits. Il existe aussi une fonction isPrime(x), du même module, qui permet de tester si un entier $x$ est premier.

Exercice 1 : protocole de Diffie-Hellman dans les résidus quadratiques#

Le but de cet exercice est d’implémenter le protocole d’échange de clés de Diffie-Hellman dans le groupe $\mathrm{QR}_p^\times$ des résidus quadratiques modulo $p$, dans le cas favorable où $p$ est un nombre premier sûr.

On rappelle que $p$ est un nombre premier sûr si $(p-1)/2$ est un nombre premier. Par conséquent, pour un nombre premier sûr, l’ordre du groupe des résidus quadratiques est premier, et tous les éléments différents de $1$ de ce groupe en sont donc des générateurs.

On rappelle aussi que $x \in \mathbb{F}_p^\times$ est un résidu quadratique (non-nul) si $x^{(p-1)/2} = 1$.

Question 1. Écrire une fonction set_global_parameters(t) qui prend en entrée un paramètre de sécurité $t$ (la taille en bits du module $p$), et qui retourne deux entiers : un nombre premier sûr $p$ aléatoire et de taille $t$ bits, ainsi qu’un générateur $g$ du groupe $\mathrm{QR}_p^\times$.

from Crypto.Util.number import getPrime, isPrime

# def set_global_parameters(t):

Question 2. Écrire une fonction init_exchange(params) qui prend en entrée une liste de paramètres (les entiers $p$ et $g$ de la question ci-dessus), et qui exécute la première étape du protocole de Diffie-Hellman :

génération aléatoire d’un entier secret $a$ compris entre $1$ et $r-1$, où $r$ est l’ordre du groupe ;
calcul de $\alpha = g^a$, où $g$ est le générateur du groupe.

Votre fonction retournera les entiers $a$ et $\alpha$. Il faut penser que $a$ est l’entier gardé secrètement, tandis que $\alpha$ est transmis à l’autre participant du protocole.

# Votre réponse ici

Question 3. Écrire une fonction compute_common_values(params, secret, received) qui prend en entrée :

params la liste des paramètres du protocole de Diffie-Hellman ;
secret la valeur gardée secrètement par un des participants ;
received la valeur transmise par l’autre participant ;

et qui retourne la valeur commune calculée dans le protocole de Diffie-Hellman.

# Votre réponse ici

Question 4. Grâce aux fonctions qui ont été implémentées, simuler un échange de clés de Diffie-Hellman entre deux personnes, dans le groupe $\mathrm{QR}_p^\times$, pour une taille $t = 256$. Vérifier que la valeur commune est identique.

# Votre réponse ici

Exercice 2 : calcul d’ordre et de générateur dans $\mathbb{F}_p^\times$#

L’objectif final de cet exercice est de calculer un générateur de $\mathbb{F}_p^\times$ dans un cadre « assez » général, en supposant uniquement connus les diviseurs premiers de $p-1$.

On rappelle que, dans un groupe cyclique $\mathbb{G}$ d’ordre $r$ dont on connaît la factorisation $r = \prod_{i=1}^k p_i^{e_i}$, on peut calculer l’ordre d’un élément $x \in \mathbb{G}$ en calculant successivement certaines puissances de $x$. En effet, si $x$ a pour ordre $s$ dans $\mathbb{G}$, alors $x^s = 1$ et pour tout $s'$ diviseur propre de $s$, on a $x^{s'} \ne 1$ dans $\mathbb{G}$.

Ainsi, l’ordre de $x$ est le produit des $p_i^{d_i}$, où $d_i$ est le plus petit entier compris entre $0$ et $e_i$ tel que $x^{r/(p_i^{e_i-d_i})} = 1$.

Pour calculer l’ordre d’un élément, on a donc l’algorithme suivant :

Initialiser $s = r$
Pour tout $i = 1, ..., k$:
1. Tant que $x^s = 1$ dans $\mathbb{G}$, et si $p_i$ divise $s$, alors faire :
  1. $s = s/p_i$
2. Si $x^s = 1$ dans $\mathbb{G}$, alors faire :
  1. $s = s \times p_i$
Retourner $s$

Question 1. On suppose que pour un nombre premier $p$, les diviseurs premiers de $p-1$ sont connus et stockés dans une liste factors. Implémenter une fonction multiplicative_order(x, p, factors) qui prend en entrée ces valeurs, ainsi qu’un élément $x$ entre $1$ et $p-1$, et qui retourne l’ordre de $x$ dans $\mathbb{F}_p^\times$.

# Votre réponse ici

Question 2. On donne dans le tableau suivant une liste de nombres premiers $p$, et la liste correspondante de diviseurs premiers de $p-1$. Calculer l’ordre de $x = 10$ pour chacun de ces cas.

nombre premier $p$	diviseurs premiers de $p-1$
547	[2, 3, 7, 13]
829	[2, 3, 23]
577	[2, 3]
735821558575852047177156941659	[2, 3, 29, 31, 136414823614358926061764357]
1137117441125669215421702626619	[2, 53, 16312391, 657630327122948771183]
1070938697827903187221632294947	[2, 535469348913951593610816147473]

# Votre réponse ici

Déterminer si $x \in \mathbb{G}$ est un générateur du groupe est plus simple que de calculer son ordre. En effet, il suffit de savoir si $\mathrm{ord}(x) = r$ ou non. On a donc : $$ x \text{ générateur de } \mathbb{G} \; \iff \; x^{r/p_i} \ne 1 \forall i \in \{1, \dots, k\} $$

Question 3. Écrire une fonction is_generator(x, p, factors) qui teste si $x$ est un générateur du groupe multiplicatif $\mathbb{F}_p^\times$. Parmi les nombres premiers $p$ listés plus haut, lequels admettent l’entier $x = 7$ comme générateur de $\mathbb{F}_p^\times$ ?

# Votre réponse ici

Question 4. Écrire une fonction smallest_generator(p, factors) qui retourne le plus petit générateur du groupe multiplicatif $\mathbb{F}_p^\times$. Déterminer les plus petits générateurs des groupes $\mathbb{F}_p^\times$ correspondant aux nombres premiers $p$ listés plus hauts.

# Votre réponse ici

Séance 1 : autour de l’échange de clefs de Diffie–Hellman

Contenu

Séance 1 : autour de l’échange de clefs de Diffie–Hellman#

Pré-requis : installation de la bibliothèque pycryptodome#

Exercice 1 : protocole de Diffie-Hellman dans les résidus quadratiques#

Exercice 2 : calcul d’ordre et de générateur dans \(\mathbb{F}_p^\times\)#

Pré-requis : installation de la bibliothèque `pycryptodome`#