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

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))

811
1021155542174262752533391982443

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):
    p = getPrime(t)
    while not(isPrime((p-1)//2)):
        p = getPrime(t)
    g = 2
    while pow(g, (p-1)//2, p) != 1:
        g += 1
    return [p, g]

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.

import random

def init_exchange(params):
    p, g = params
    a = random.randint(1, (p-1)//2 - 1)
    alpha = pow(g, a, p)
    return [a, alpha]

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.

def compute_common_value(params, secret, received):
    p, g = params
    key = pow(received, secret, p)
    return key

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.

params = set_global_parameters(t=256)

alice = init_exchange(params)
bob = init_exchange(params)

key1 = compute_common_value(params, alice[0], bob[1])
key2 = compute_common_value(params, bob[0], alice[1])
print(key1)
print(key2)

23664730605607983958198864687986132237085478719540199988546400017781430535643
23664730605607983958198864687986132237085478719540199988546400017781430535643

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 :

  1. Initialiser \(s = r\)

  2. 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\)

  3. 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\).

def multiplicative_order(x, p, factors):
    s = p-1
    k = len(factors)
    for i in range(k):
        while (pow(x, s, p) == 1) and (s % factors[i] == 0):
            s //= factors[i]
        if pow(x, s, p) != 1:
            s *= factors[i]
    return s

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]

 
FACT = { 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]
         }

for p in FACT:
    f = FACT[p]
    x = 10
    print(p, multiplicative_order(10, p, f))

547 91
829 276
577 576
735821558575852047177156941659 735821558575852047177156941658
1137117441125669215421702626619 1137117441125669215421702626618
1070938697827903187221632294947 535469348913951593610816147473

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\) ?

def is_generator(x, p, factors):
    return all(pow(x, (p-1)//q, p) != 1 for q in factors)

print([p for p in FACT if is_generator(7, p, FACT[p])])

[547, 577]

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.

def smallest_generator(p, factors):
    s = 1
    x = 1
    while not(is_generator(x, p, factors)):
        x += 1
    return x
    
for p in FACT:
    f = FACT[p]
    x = smallest_generator(p, f)
    print(p, x, multiplicative_order(x, p, f))

547 2 546
829 2 828
577 5 576
735821558575852047177156941659 2 735821558575852047177156941658
1137117441125669215421702626619 2 1137117441125669215421702626618
1070938697827903187221632294947 2 1070938697827903187221632294946
Contenu