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.

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

import random

def elgamal_keygen(params):
    p, g = params
    sk = random.randint(1, (p-1)//2 - 1)
    pk = pow(g, sk, p)
    return pk, sk

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.

def elgamal_encrypt(params, m, pk):
    p, g = params
    k = random.randint(1, (p-1)//2 - 1)
    c1 = pow(g, k, p)
    c2 = (pow(pk, k, p) * m) % p
    return (c1, c2)

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.

def elgamal_decrypt(params, c, sk):
    p, g = params
    c1, c2 = c
    return (c2 * pow(c1, -sk, p) % p)

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.

params = set_global_parameters(256)
print("(p, g) =", params)
pk, sk = elgamal_keygen(params)
print("Clé publique :", pk)
print("Clé privée   :", sk)

(p, g) = [111605053003637884049571197076028145042706675612854018604052879183395618912923, 3]
Clé publique : 5803232045546808295225020889909397398002702601239061400886757624594780823559
Clé privée   : 10020243278238861498182232351166588974103067920827100950874151219448296869679

p, g = params
m = pow(g, 18031871, p)
enc_1 = elgamal_encrypt(params, m, pk)
enc_2 = elgamal_encrypt(params, m, pk)
print(enc_1 != enc_2)

True

import random

for _ in range(100):
    m = random.randint(1, (p-1)//2-1)
    c = elgamal_encrypt(params, m, pk)
    if (m != elgamal_decrypt(params, c, sk)):
        print("Erreur")

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.

import math

def baby_step_giant_step(params, y):
    p, g = params
    m = math.ceil(math.sqrt((p-1)//2))
    x = pow(g, -m, p)
    D = dict()
    z = 1
    for i in range(m):
        D[z] = i
        z = z*g % p
    j = 0
    while not(y in D):
        y = y*x % p
        j += 1
    return D[y] + j*m
    
params = set_global_parameters(32)
p, g = params
a = random.randint(0, (p-1)//2-1)
y = pow(g, a, p)
print(a)
print(baby_step_giant_step(params, y))

1731297411
1731297411

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

import time
import matplotlib.pyplot as plt


T = [ t for t in range(10, 32) ]
TIMES = []
N = 200

for t in T:
    params = set_global_parameters(t)
    p, g = params
    total_time = 0
    for _ in range(N):
        a = random.randint(0, (p-1)//2-1)
        y = pow(g, a, p)
        start = time.time()
        baby_step_giant_step(params, y)
        total_time += (time.time() - start)
    TIMES.append(total_time/N)
    

plt.plot(T, [ math.log(x, 2) for x in TIMES ], ls='', marker='o', color='red')
plt.show()
_images/a4eb920421cf2c129e3c204ec26c9ec974cfa0f2e011c19880593770af6e7455.png

Le graphique ci-dessus trace le logarithme (en base \(2\)) du temps de calcul moyen de \(N = 200\) logarithmes discrets en fonction de \(t\). On oberve des points alignés sur une droite de pente \(\simeq 0.5\). Comme \(p \simeq 2^t\), cela signifie que le temps de calcul se comporte bien en \(O(\sqrt{p})\).

Contenu