Nom : CHOUBIK
Prénom : HOUSSAM
Filière : CS2C-1
Exercice 0-1 : Euclide étendu et inversion modulaire
- Ecrire une fonction EuclidEtendu(a,b) qui retourne u,v calculé à partir de l’algorithme de Euclide étendu tels que : a.u + b.v = pgcd(a,b)
- En déduire une fonction invMod(a,b) qui retourne l’inverse de a modulo b (vérifier que a∧b=1)
- Retrouver le résultat de la question 2 via la fonction python : pow(a,p,m)
def euclide_etendu(a, b):
if a == 0:
return b, 0, 1
gcd, u1, v1 = euclide_etendu(b % a, a)
u = v1 - (b // a) * u1
v = u1
return gcd, u, v
def inv_mod(a, m):
gcd, u, v = euclide_etendu(a, m)
if gcd != 1:
raise ValueError(f"L'inverse modulaire n'existe pas pour {a} mod {m}")
return u % m
print(inv_mod(17, 3120), pow(17, -1, 3120)) # même résultat : 2753
2753 2753
Exercice 0-2 : Théorèmes des restes chinois
def trc(restes, moduli):
total_product = 1
for m in moduli:
total_product *= m
result = 0
for r, m in zip(restes, moduli):
partial_product = total_product // m
inverse = inv_mod(partial_product, m)
result += r * partial_product * inverse
return result % total_product
# x = 2 mod 3, x = 3 mod 5, x = 2 mod 7 -> x = 23
print(trc([2, 3, 2], [3, 5, 7]))
23
Exercice 1 : Mise en œuvre, Attaque et Optimisation du système RSA
import time
import random
import math
p_rsa = 9973
q_rsa = 11251
public_exponent = 65537
plaintext_msg = 132596
n_rsa = p_rsa * q_rsa
phi_n = (p_rsa - 1) * (q_rsa - 1)
private_exponent = inv_mod(public_exponent, phi_n)
ciphertext = pow(plaintext_msg, public_exponent, n_rsa)
decrypted_msg = pow(ciphertext, private_exponent, n_rsa)
print(f"I. Chiffrement RSA: n={n_rsa}, d={private_exponent}")
print(f" Message chiffré: {ciphertext}, Déchiffré: {decrypted_msg}")
I. Chiffrement RSA: n=112206223, d=40098473 Message chiffré: 83110143, Déchiffré: 132596
def brute_force_factorization(n):
for i in range(2, math.isqrt(n) + 1):
if n % i == 0:
return i, n // i
return None
def pollard_rho(n):
x = random.randint(2, n - 1)
y = x
d = 1
f = lambda val: (val**2 + 1) % n
while d == 1:
x = f(x)
y = f(f(y))
d = math.gcd(abs(x - y), n)
if d == n:
return None
return d, n // d
start_bf = time.perf_counter()
p_bf, q_bf = brute_force_factorization(n_rsa)
time_bf = time.perf_counter() - start_bf
start_pr = time.perf_counter()
p_pr, q_pr = pollard_rho(n_rsa)
time_pr = time.perf_counter() - start_pr
print(f"II. Force brute: p={p_bf}, temps={time_bf:.6f}s")
print(f" Pollard-Rho: p={p_pr}, temps={time_pr:.6f}s")
II. Force brute: p=9973, temps=0.001280s
Pollard-Rho: p=11251, temps=0.000148s
def decrypt_rsa_crt(c, d, p, q):
dp = d % (p - 1)
dq = d % (q - 1)
mp = pow(c, dp, p)
mq = pow(c, dq, q)
q_inv = inv_mod(q, p)
h = (q_inv * (mp - mq)) % p
return mq + h * q
decrypted_crt = decrypt_rsa_crt(ciphertext, private_exponent, p_rsa, q_rsa)
print(f"III. Déchiffrement RSA-CRT: {decrypted_crt}")
III. Déchiffrement RSA-CRT: 132596
p_80 = 821664027145220167960399
q_80 = 1116629742743296920375667
n_160 = p_80 * q_80
phi_160 = (p_80 - 1) * (q_80 - 1)
d_160 = inv_mod(65537, phi_160)
c_160 = pow(123456789, 65537, n_160)
start_std = time.perf_counter()
for _ in range(100):
pow(c_160, d_160, n_160)
time_std = time.perf_counter() - start_std
start_crt = time.perf_counter()
for _ in range(100):
decrypt_rsa_crt(c_160, d_160, p_80, q_80)
time_crt = time.perf_counter() - start_crt
print(f"IV. Temps standard (100x) : {time_std:.4f}s")
print(f" Temps RSA-CRT (100x) : {time_crt:.4f}s")
print(f" Gain de vitesse : {time_std / time_crt:.2f}x") # [cite: 95]
IV. Temps standard (100x) : 0.0122s
Temps RSA-CRT (100x) : 0.0090s
Gain de vitesse : 1.35x
Exercice 2 : Analyse de Complexité (Baby-Step Giant-Step)
def baby_step_giant_step(alpha, beta, p):
m = math.ceil(math.sqrt(p - 1))
lookup_table = {}
for j in range(m):
value = pow(alpha, j, p)
lookup_table[value] = j
alpha_inv_m = pow(inv_mod(alpha, p), m, p)
current_gamma = beta
for i in range(m):
if current_gamma in lookup_table:
return i * m + lookup_table[current_gamma]
current_gamma = (current_gamma * alpha_inv_m) % p
return None
p_dlp = 23549
alpha_dlp = 2
beta_dlp = 13245
start_bsgs = time.perf_counter()
secret_x = baby_step_giant_step(alpha_dlp, beta_dlp, p_dlp)
time_bsgs = time.perf_counter() - start_bsgs
print(f"Secret trouvé : x = {secret_x}")
print(f"Vérification : 2^{secret_x} mod {p_dlp} = {pow(alpha_dlp, secret_x, p_dlp)}")
print(f"Temps d'exécution : {time_bsgs:.6f} secondes")
Secret trouvé : x = 4191 Vérification : 2^4191 mod 23549 = 13245 Temps d'exécution : 0.000168 secondes
Exercice 3 : Chiffrement ElGamal et Attaque sur l'Aléa (Nonce)
Objectif : Implémenter le cryptosystème ElGamal et démontrer mathématiquement pourquoi l'utilisation d'un même secret éphémère pour deux messages différents permet à un attaquant de casser la confidentialité sans résoudre le PLD.
I. Implémentation du Chiffrement ElGamal
p = 31847
a = 5
d = 789
beta = pow(a, d, p)
print(f"1. Clé publique de Bob (beta) : {beta}")
1. Clé publique de Bob (beta) : 12008
M1 = 9876
i = 888
c1 = pow(a, i, p)
beta_i = pow(beta, i, p)
c2 = (M1 * beta_i) % p
print(f"2. Message chiffré par Alice (c1, c2) : ({c1}, {c2})")
2. Message chiffré par Alice (c1, c2) : (17648, 25315)
c1_d = pow(c1, d, p)
c1_d_inv = pow(c1_d, -1, p)
M_dechiffre = (c2 * c1_d_inv) % p
print(f"3. Message déchiffré par Bob : {M_dechiffre}")
assert M_dechiffre == M1, "Erreur lors du déchiffrement !"
print(" -> Vérification réussie : Bob retrouve bien M1 = 9876.\n")
3. Message déchiffré par Bob : 9876 -> Vérification réussie : Bob retrouve bien M1 = 9876.
II. Simulation de l'Attaque (Réutilisation de l'Aléa i)
c1_1, c2_1 = 15682, 12754
M1_connu = 9876
c1_2, c2_2 = 15682, 20560
if c1_1 == c1_2:
print("Vulnerabilité détectée : L'aléa 'i' a été réutilisé")
c2_1_inv = pow(c2_1, -1, p)
M2_retrouve = (M1_connu * c2_2 * c2_1_inv) % p
print(f"Message M2 intercepté et déchiffré sans la clé privée : {M2_retrouve}")
else:
print("L'aléa semble unique, l'attaque n'est pas possible.")
Vulnerabilité détectée : L'aléa 'i' a été réutilisé Message M2 intercepté et déchiffré sans la clé privée : 9668