Séance 3 : Chiffrement ElGamal

Séance 3 : Chiffrement ElGamal#

Exercice 1 : ElGamal dans \(\mathrm{QR}_p^\times\)#

Le but de cet exercice est d’implémenter le chiffrement ElGamal, sur le groupe des résidus quadratiques \(\mathrm{QR}_p^\times\), avec \(p\) un nombre premier sûr, c’est-à-dire tel que \((p-1)/2\) est également premier.

Question 1. Reprendre la question de la séance 1 qui permet d’engendrer les paramètres globaux du chiffrement ElGamal dans le contexte de l’exercice, à savoir un nombre premier sûr \(p\) de taille \(t\) bits et un générateur \(g\) du groupe des résidus quadratiques \(\mathrm{QR}_p^\times\). On appellera une nouvelle fois set_global_parameters(t) la fonction qui retourne ces paramètres.

# à compléter

Question 2. Écrire une fonction elgamal_keygen(params), qui prend en entrée les paramètres globaux du système, et qui retourne une paire de clés publique/privée pour le chiffrement ElGamal.

# À compléter

Question 2. Écrire une fonction elgamal_encrypt(params, m, pk), qui prend en entrée params les paramètres globaux du système, m un message à chiffrer (que l’on supposera élément du groupe \(\mathrm{QR}_p^\times\)) et pk une clé publique ElGamal, et qui retourne le chiffré correspondant sous forme de couple.

# À compléter

Question 3. Écrire une fonction elgamal_decrypt(params, c, sk), qui prend en entrée params les paramètres globaux du système, c un chiffré ElGamal sous forme de couple d’entiers, et sk une clé privée ElGamal, et qui retourne le déchiffré de c par la clé sk.

# À compléter

Question 4. Test.

  1. Créer une paire de clés publique/privée pour \(t = 256\) (pour que cela ne prenne pas trop de temps).

  2. Vérifier que deux chiffrés du même message sont distincts.

  3. Vérifier, sur une centaine de tests, que le déchiffrement du chiffré d’un message aléatoire se déroule correctement.

# À compléter

Exercice 2 : logarithme discret par baby-step giant-step#

Le but de cet exercice est d’implanter l’algorithme baby-step giant-step de calcul de logarithme discret. Nous allons l’implanter dans le contexte de l’exercice précédent, à savoir le groupe des résidus quadratiques \(\mathrm{QR}_p^\times\), avec \(p\) un nombre premier sûr.

Rappel de l’algorithme :

Entrée : les paramètres du groupe \(\mathrm{QR}_p^\times\) (nombre premier \(p\) et générateur \(g\)), et un élément \(y \in \mathrm{QR}_p^\times\).

Sortie : le logarithme discret de \(y\) en base \(g\).

  1. Calculer \(m = \lceil \sqrt{n} \rceil\).

  2. Calculer \(x = g^{-m} \!\!\mod p\).

  3. (Précalcul) Construire un dictionnaire D dont les clés sont les \(g^i \!\! \mod p\), pour \(0 \le i < m\), et la valeur associée à \(g^i\) est \(i\).

  4. Initialiser \(j = 0\)

  5. Tant que \(y\) n’est pas une clé du dictionnaire :

    1. Mettre à jour \(y\) en \(y \cdot x \!\!\mod p\).

    2. Incrémenter \(j\).

  6. Retourner \(i + jm\), où \(i\) est la valeur associée à \(y\) dans le dictionnaire D.

Question 1. Implanter l’algorithme baby-step giant-step dans une fonction baby_step_giant_step(params, y), où params désigne le couple de paramètres (module \(p\), générateur \(g\)) du groupe \(\mathrm{QR}_p^\times\), et où y est l’élément du groupe dont on cherche le logarithme en base \(g\). Puis, tester votre fonction avec un module \(p\) de taille \(t = 32\) bits.

# À compléter

Question 2. Tracer l’évolution du temps de calcul d’un logarithme discret en fonction de l’ordre du groupe (ou de \(t\)). Commenter.

# À compléter
Contenu