Module 1 — Fondements Mathematiques | TP : Arithmetique Modulaire avec Python
MODULE 1 — FONDEMENTS MATHEMATIQUES
TP : Arithmetique Modulaire avec Python
Travaux Pratiques — Duree : 2 heures
Objectifs du TP
Implementer en Python pur : l'algorithme d'Euclide etendu, le CRT, l'exponentiation
modulaire rapide, un mini-RSA de demonstration et les operations dans GF(2^8). Toutes
ces implementations seront reutilisees dans les TPs suivants.
Partie 1 — Algorithme d'Euclide Etendu
TACHE 1.1
Implementez pgcd(a, b) et l'algorithme d'Euclide etendu retournant (pgcd, u, v) tels que a*u
+ b*v = pgcd.
# TP_fondements_math.py
# Module 1 — Fondements Mathematiques de la Cryptographie
# =============================================
# PARTIE 1 : ALGORITHME D'EUCLIDE ETENDU
# =============================================
def pgcd(a: int, b: int) -> int:
"""PGCD par l'algorithme d'Euclide iteratif."""
while b != 0:
a, b = b, a % b
return abs(a)
def euclide_etendu(a: int, b: int) -> tuple:
"""
Algorithme d'Euclide etendu.
Retourne (g, u, v) tels que a*u + b*v = g = pgcd(a, b).
"""
if b == 0:
return a, 1, 0
g, u1, v1 = euclide_etendu(b, a % b)
# a*u1 + b*v1 = g => b*u1 + (a%b)*v1 = g
# a%b = a - (a//b)*b => b*u1 + (a - (a//b)*b)*v1 = g
# a*v1 + b*(u1 - (a//b)*v1) = g
Page 1
Module 1 — Fondements Mathematiques | TP : Arithmetique Modulaire avec Python
u = v1
v = u1 - (a // b) * v1
return g, u, v
def inverse_mod(a: int, n: int) -> int:
"""Inverse modulaire de a modulo n. Leve ValueError si non inversible."""
g, u, _ = euclide_etendu(a, n)
if g != 1:
raise ValueError(f'{a} n\'est pas inversible modulo {n} (pgcd={g})')
return u % n
# --- TESTS ---
print('=== PARTIE 1 : Euclide Etendu ===')
a, b = 1071, 462
g, u, v = euclide_etendu(a, b)
print(f'pgcd({a}, {b}) = {g}')
print(f'Coefficients de Bezout : {a}*({u}) + {b}*({v}) = {a*u + b*v}')
assert a*u + b*v == g
# Inverse modulaire
inv_17_3120 = inverse_mod(17, 3120)
print(f'17^{{-1}} mod 3120 = {inv_17_3120}')
print(f'Verification : 17 * {inv_17_3120} mod 3120 = {(17 * inv_17_3120) %
3120}')
assert (17 * inv_17_3120) % 3120 == 1
# Test d'erreur
try:
inverse_mod(462, 1071)
except ValueError as e:
print(f'Erreur attendue : {e}')
print('[OK] Partie 1')
Sortie attendue :
=== PARTIE 1 : Euclide Etendu ===
pgcd(1071, 462) = 21
Coefficients de Bezout : 1071*(-3) + 462*(7) = 21
17^{-1} mod 3120 = 2753
Verification : 17 * 2753 mod 3120 = 1
Erreur attendue : 462 n'est pas inversible modulo 1071 (pgcd=21)
[OK] Partie 1
Partie 2 — Exponentiation Modulaire Rapide
TACHE 2.1
Implementez l'exponentiation rapide par la methode carre-et-multiplie. Comparez avec la
Page 2
Module 1 — Fondements Mathematiques | TP : Arithmetique Modulaire avec Python
methode naive pour mesurer le gain de performance.
# =============================================
# PARTIE 2 : EXPONENTIATION MODULAIRE RAPIDE
# =============================================
def exp_mod(base: int, exp: int, mod: int) -> int:
"""
Calcule base^exp mod n par exponentiation rapide (square-and-multiply).
Complexite : O(log(exp)) multiplications.
"""
result = 1
base = base % mod
while exp > 0:
if exp % 2 == 1: # bit courant = 1
result = (result * base) % mod
exp //= 2 # decalage a droite
base = (base * base) % mod # carre
return result
def exp_naif(base: int, exp: int, mod: int) -> int:
"""Exponentiation naie : exp multiplications. Lent pour grands
exposants."""
result = 1
for _ in range(exp):
result = (result * base) % mod
return result
import time
print('\n=== PARTIE 2 : Exponentiation modulaire ===')
# Test de correction
assert exp_mod(5, 13, 23) == 22
assert exp_mod(7, 222, 11) == 5
print('Tests de correction : OK')
# Comparaison de performance
base, exp, mod = 65537, 2**256 - 1, 2**521 - 1 # Parametres realistes
t0 = time.perf_counter()
r1 = exp_mod(base, exp, mod)
t1 = time.perf_counter()
print(f'Exp rapide : {t1-t0:.6f} s (log2(exp) ~ {exp.bit_length()} bits)')
# [NE PAS EXECUTER exp_naif avec exp=2^256 -- prendrait des annees !]
# Demo sur un petit exposant :
t0 = time.perf_counter()
r2 = exp_naif(base, 10**6, mod)
t1 = time.perf_counter()
print(f'Exp naif (10^6 etapes) : {t1-t0:.4f} s')
Page 3
Module 1 — Fondements Mathematiques | TP : Arithmetique Modulaire avec Python
t0 = time.perf_counter()
r3 = exp_mod(base, 10**6, mod)
t1 = time.perf_counter()
print(f'Exp rapide (meme) : {t1-t0:.6f} s')
assert r2 == r3
print('[OK] Partie 2')
Sortie attendue :
=== PARTIE 2 : Exponentiation modulaire ===
Tests de correction : OK
Exp rapide : 0.000089 s (log2(exp) ~ 256 bits)
Exp naif (10^6 etapes) : 2.3412 s
Exp rapide (meme) : 0.000012 s
[OK] Partie 2
Page 4
Module 1 — Fondements Mathematiques | TP : Arithmetique Modulaire avec Python
Partie 3 — Theoreme Chinois des Restes
TACHE 3.1
Implementez le CRT general pour k congruences. Appliquez-le pour accelerer RSA
(methode CRT-RSA).
# =============================================
# PARTIE 3 : THEOREME CHINOIS DES RESTES
# =============================================
def crt(residus: list, modules: list) -> int:
"""
Resout le systeme x ≡ residus[i] (mod modules[i]) pour tout i.
Precondition : les modules sont deux a deux copremiers.
Retourne x dans {0, ..., N-1} ou N = prod(modules).
"""
N = 1
for m in modules:
N *= m
x = 0
for a_i, n_i in zip(residus, modules):
N_i = N // n_i
y_i = inverse_mod(N_i, n_i)
x += a_i * N_i * y_i
return x % N
print('\n=== PARTIE 3 : CRT ===')
# Test de base
residus = [2, 3, 2]
modules = [3, 5, 7]
x = crt(residus, modules)
print(f'Solution : x = {x}')
for a, m in zip(residus, modules):
assert x % m == a, f'Erreur : {x} mod {m} != {a}'
print('Verification : OK')
# Application : RSA-CRT
def rsa_dechiffrer_crt(c: int, d: int, p: int, q: int) -> int:
"""
Dechiffrement RSA accelere par CRT.
Calcule m = c^d mod (p*q) via c^{d mod p-1} mod p et c^{d mod q-1} mod q.
"""
dp = d % (p - 1) # d mod (p-1)
dq = d % (q - 1) # d mod (q-1)
mp = exp_mod(c, dp, p) # c^dp mod p
Page 5
Module 1 — Fondements Mathematiques | TP : Arithmetique Modulaire avec Python
mq = exp_mod(c, dq, q) # c^dq mod q
# Recombiner par CRT
q_inv = inverse_mod(q, p) # q^{-1} mod p (precalcule en vrai RSA)
h = (q_inv * (mp - mq)) % p
m = mq + h * q
return m % (p * q)
def rsa_dechiffrer_standard(c: int, d: int, n: int) -> int:
"""Dechiffrement RSA standard : m = c^d mod n."""
return exp_mod(c, d, n)
# Parametres RSA de test (petits pour la demo)
p, q = 61, 53
n = p * q # 3233
e = 17
phi_n = (p-1)*(q-1) # 3120
d = inverse_mod(e, phi_n) # 2753
m = 65
c = exp_mod(m, e, n)
import time
print(f'\nRSA demo : n={n}, e={e}, d={d}')
print(f'Message m={m}, Chiffre c={c}')
m_standard = rsa_dechiffrer_standard(c, d, n)
m_crt = rsa_dechiffrer_crt(c, d, p, q)
print(f'Dechiffre standard : {m_standard}')
print(f'Dechiffre CRT : {m_crt}')
assert m_standard == m_crt == m
# Benchmark sur des parametres plus grands
import random
def gen_premier(bits):
"""Generation naive d'un premier (demonstration seulement, pas
securise)."""
from sympy import isprime, nextprime
x = [Link](bits) | 1
return nextprime(x)
# Si sympy est disponible, on fait le benchmark :
try:
p2 = gen_premier(512)
q2 = gen_premier(512)
n2 = p2 * q2
d2 = [Link](1023) | 1
c2 = [Link](2, n2-1)
t0 = time.perf_counter()
rsa_dechiffrer_standard(c2, d2, n2)
t1 = time.perf_counter()
t2 = time.perf_counter()
rsa_dechiffrer_crt(c2, d2, p2, q2)
t3 = time.perf_counter()
print(f'\nBenchmark RSA-1024 :')
Page 6
Module 1 — Fondements Mathematiques | TP : Arithmetique Modulaire avec Python
print(f' Standard : {t1-t0:.4f} s')
print(f' CRT : {t3-t2:.4f} s')
print(f' Gain : x{(t1-t0)/(t3-t2):.1f}')
except ImportError:
print('(sympy non disponible : pip install sympy pour le benchmark)')
print('[OK] Partie 3')
Sortie attendue :
=== PARTIE 3 : CRT ===
Solution : x = 23
Verification : OK
RSA demo : n=3233, e=17, d=2753
Message m=65, Chiffre c=2790
Dechiffre standard : 65
Dechiffre CRT : 65
Benchmark RSA-1024 :
Standard : 0.0412 s
CRT : 0.0108 s
Gain : x3.8
[OK] Partie 3
Page 7
Module 1 — Fondements Mathematiques | TP : Arithmetique Modulaire avec Python
Partie 4 — Corps de Galois GF(2^8) — Base d'AES
TACHE 4.1
Implementez les operations dans GF(2^8) avec le polynome irreductible d'AES P(x) =
x^8+x^4+x^3+x+1 (0x11B). Ces fonctions sont utilisees litteralement dans AES.
# =============================================
# PARTIE 4 : GF(2^8) — CORPS D'AES
# =============================================
# Polynome irreductible d'AES : x^8+x^4+x^3+x+1 = 0b100011011 = 0x11B
AES_POLY = 0x11B
def gf_add(a: int, b: int) -> int:
"""Addition dans GF(2^8) = XOR bit a bit. Pas de module necessaire."""
return a ^ b
def gf_mul(a: int, b: int, poly: int = AES_POLY) -> int:
"""
Multiplication dans GF(2^8) par l'algorithme 'peasant multiplication'.
Complexite : O(8) iterations (8 bits).
"""
result = 0
while b > 0:
if b & 1: # si le bit de poids faible de b est 1
result ^= a # addition GF(2) = XOR
a <<= 1 # multiplication par x (decalage)
if a & 0x100: # si le degre depasse 7 (bit 8 allume)
a ^= poly # reduction modulo le polynome irreductible
b >>= 1 # prochain bit de b
return result & 0xFF # s'assurer qu'on reste sur 8 bits
def gf_inv(a: int, poly: int = AES_POLY) -> int:
"""
Inverse dans GF(2^8) par l'algorithme d'Euclide etendu sur les polynomes.
Utilise le petit theoreme de Fermat : a^{-1} = a^{254} dans GF(2^8).
"""
if a == 0:
raise ValueError('0 n\'a pas d\'inverse dans GF(2^8)')
# Fermat dans GF(2^8) : a^{2^8 - 1} = a^{255} = 1 => a^{-1} = a^{254}
result = a
for _ in range(6): # carres successifs : a, a^2, a^4, a^8, ..., a^{128}
result = gf_mul(result, result, poly) # carre
result = gf_mul(result, a, poly) # a^{128} * a = a^{129}
# En fait, on calcule a^{254} = (a^{127})^2
# Methode directe : exponentiation rapide sur GF(2^8)
exp = 254
Page 8
Module 1 — Fondements Mathematiques | TP : Arithmetique Modulaire avec Python
res = 1
base = a
while exp > 0:
if exp & 1:
res = gf_mul(res, base, poly)
base = gf_mul(base, base, poly)
exp >>= 1
return res
print('\n=== PARTIE 4 : GF(2^8) ===')
# Tests des operations
print(f'0x53 + 0xCA = 0x{gf_add(0x53, 0xCA):02X} (attendu 0x99)')
print(f'0x57 * 0x83 = 0x{gf_mul(0x57, 0x83):02X} (attendu 0xC1, ref AES)')
# Verification de la commutativite
assert gf_mul(0x57, 0x83) == gf_mul(0x83, 0x57)
print('Commutativite de la multiplication : OK')
# Test de l'inverse
for x in [0x01, 0x53, 0x0F, 0xFF, 0xAB]:
inv_x = gf_inv(x)
prod = gf_mul(x, inv_x)
print(f' inv(0x{x:02X}) = 0x{inv_x:02X} {x:#04x}*{inv_x:#04x} =
0x{prod:02X} (doit etre 0x01)')
assert prod == 0x01, f'Erreur inverse pour {x:#04x}'
# Generation de la table S-Box d'AES (SubBytes)
def aes_sbox_element(x: int) -> int:
"""Calcule un element de la S-Box AES = inverse GF(2^8) + transformation
affine."""
if x == 0:
s = 0
else:
s = gf_inv(x)
# Transformation affine : s = s XOR rotation(s, 1) XOR ... XOR 0x63
s = s ^ ((s << 1 | s >> 7) & 0xFF) ^ ((s << 2 | s >> 6) & 0xFF) ^ \
((s << 3 | s >> 5) & 0xFF) ^ ((s << 4 | s >> 4) & 0xFF) ^ 0x63
return s & 0xFF
sbox = [aes_sbox_element(i) for i in range(256)]
# Quelques valeurs de reference AES (FIPS 197)
print(f'\nS-Box AES :')
print(f' sbox[0x00] = 0x{sbox[0x00]:02X} (attendu 0x63)')
print(f' sbox[0x01] = 0x{sbox[0x01]:02X} (attendu 0x7C)')
print(f' sbox[0x53] = 0x{sbox[0x53]:02X} (attendu 0xED)')
assert sbox[0x00] == 0x63
assert sbox[0x01] == 0x7C
print('[OK] Partie 4 — GF(2^8) et S-Box AES')
Sortie attendue :
=== PARTIE 4 : GF(2^8) ===
0x53 + 0xCA = 0x99 (attendu 0x99)
Page 9
Module 1 — Fondements Mathematiques | TP : Arithmetique Modulaire avec Python
0x57 * 0x83 = 0xC1 (attendu 0xC1, ref AES)
Commutativite de la multiplication : OK
inv(0x01) = 0x01 0x01*0x01 = 0x01 (doit etre 0x01)
inv(0x53) = 0xCA 0x53*0xCA = 0x01 (doit etre 0x01)
...
S-Box AES :
sbox[0x00] = 0x63 (attendu 0x63)
sbox[0x01] = 0x7C (attendu 0x7C)
sbox[0x53] = 0xED (attendu 0xED)
[OK] Partie 4 — GF(2^8) et S-Box AES
Partie 5 — Test de Primalite Miller-Rabin
TACHE 5.1
Implementez le test de primalite probabiliste Miller-Rabin. Generez de grands nombres
premiers et mesurez les performances.
# =============================================
# PARTIE 5 : TEST DE PRIMALITE MILLER-RABIN
# =============================================
import random
def miller_rabin_test(n: int, a: int) -> bool:
"""
Test de Miller-Rabin pour un seul temoin a.
Retourne True si n est PROBABLEMENT premier, False si n est certainement
compose.
"""
if n < 2: return False
if n == 2 or n == 3: return True
if n % 2 == 0: return False
# Ecrire n-1 = 2^r * d avec d impair
r, d = 0, n - 1
while d % 2 == 0:
r += 1
d //= 2
# Calculer a^d mod n
x = exp_mod(a, d, n)
if x == 1 or x == n - 1:
return True # n passe le test pour ce temoin
Page 10
Module 1 — Fondements Mathematiques | TP : Arithmetique Modulaire avec Python
# Carres successifs r-1 fois
for _ in range(r - 1):
x = exp_mod(x, 2, n)
if x == n - 1:
return True
return False # n est certainement compose
def est_premier(n: int, k: int = 40) -> bool:
"""
Test de primalite Miller-Rabin avec k temoins aleatoires.
Probabilite d'erreur < (1/4)^k.
k=40 => P(erreur) < 10^{-24}.
"""
if n < 2: return False
# Petits premiers deterministiques
petits_premiers = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]
for p in petits_premiers:
if n == p: return True
if n % p == 0: return False
# k temoins aleatoires
for _ in range(k):
a = [Link](2, n - 1)
if not miller_rabin_test(n, a):
return False
return True
def gen_premier_bits(bits: int) -> int:
"""Genere un nombre premier de la taille specifiee en bits."""
while True:
# Generer un nombre impair de la bonne taille
n = [Link](bits) | (1 << bits - 1) | 1 # MSB et LSB = 1
if est_premier(n):
return n
print('\n=== PARTIE 5 : Test de primalite Miller-Rabin ===')
# Tests de correction
premiers_connus = [2, 3, 5, 7, 11, 101, 1009, 7919, 104729]
composes_connus = [4, 9, 15, 100, 561, 1729] # 561 et 1729 = nombres de
Carmichael
print('Verification sur nombres connus :')
for n in premiers_connus:
assert est_premier(n), f'{n} devrait etre premier'
print(f' {n} : premier ✓')
for n in composes_connus:
assert not est_premier(n), f'{n} devrait etre compose'
print(f' {n} : compose ✓ (Miller-Rabin detecle les nombres de
Carmichael !)')
# Generation de grands premiers
print('\nGeneration de nombres premiers :')
import time
Page 11
Module 1 — Fondements Mathematiques | TP : Arithmetique Modulaire avec Python
for bits in [64, 128, 256, 512]:
t0 = time.perf_counter()
p = gen_premier_bits(bits)
t1 = time.perf_counter()
print(f' {bits} bits : {p} ({t1-t0:.4f} s)')
print('[OK] Partie 5')
Sortie attendue :
=== PARTIE 5 : Test de primalite Miller-Rabin ===
Verification sur nombres connus :
2 : premier ✓
3 : premier ✓
...
104729 : premier ✓
4 : compose ✓
561 : compose ✓ (Miller-Rabin detecte les nombres de Carmichael !)
1729 : compose ✓
Generation de nombres premiers :
64 bits : 15839000541741629... (0.0003 s)
128 bits : 28097867... (0.0021 s)
256 bits : 11408469... (0.0089 s)
512 bits : 12789345... (0.0312 s)
[OK] Partie 5
Bilan du TP
Vous avez implemente : l'algorithme d'Euclide etendu et les inverses modulaires,
l'exponentiation rapide (carre-et-multiplie) avec benchmark, le CRT avec application RSA-
CRT (gain x3.8), les operations dans GF(2^8) et la S-Box d'AES, et le test de primalite
Miller-Rabin avec generation de grands premiers. Ces implementations constituent la boite
a outils mathematique complete pour les modules suivants (AES, RSA, ECC).
Page 12