Arithmétique modulaire pour développeurs : du modulo à RSA en code

📍 Guide principal : Mathématiques appliquées à l’informatique : le socle pratique
Ce tutoriel approfondit la partie arithmétique modulaire et théorie des nombres du guide principal — à parcourir d’abord pour situer ce que ces concepts apportent à la cryptographie moderne.

Tout développeur a écrit du code utilisant l’opérateur % pour calculer un index circulaire ou tester la parité d’un entier. Peu réalisent que cet opérateur, banalisé en programmation, ouvre la porte à toute la cryptographie asymétrique moderne. RSA, Diffie-Hellman, ECDSA, signatures Ed25519, certificats TLS, JSON Web Tokens : aucune de ces briques de sécurité ne fonctionne sans arithmétique modulaire sur de très grands entiers. Ce tutoriel pose, étape par étape, les concepts puis l’implémentation : du modulo de base au chiffrement et déchiffrement RSA en quelques dizaines de lignes de Python.

Prérequis

• Python 3.10 ou plus récent (les entiers Python sont nativement de précision arbitraire)
• Niveau attendu : intermédiaire — vous savez écrire une fonction récursive et utiliser % et //
• Aucune bibliothèque externe pour la partie pédagogique ; cryptography en bonus à la fin
• Temps estimé : 90 minutes

Étape 1 — Comprendre la congruence modulo n

On dit que deux entiers a et b sont congrus modulo n, noté a ≡ b (mod n), si leur différence est divisible par n. Cela revient à dire qu’ils ont le même reste dans la division euclidienne par n. La congruence est une relation d’équivalence (réflexive, symétrique, transitive) qui partitionne les entiers en n classes : 0, 1, …, n−1. Cette structure, notée ℤ/nℤ, hérite d’une addition et d’une multiplication compatibles, ce qui en fait un anneau commutatif. Pour n premier, c’est même un corps fini.

# congruence.py
def congruent(a, b, n):
    return (a - b) % n == 0

print(congruent(17, 5, 12))   # True : 17 - 5 = 12 ≡ 0
print(congruent(100, 4, 6))   # True
print(congruent(7, 3, 5))     # False : 7 - 3 = 4 ≠ 0 mod 5

# Démonstration des opérations modulaires
n = 7
print((4 + 5) % n, "≡", ((4 % n) + (5 % n)) % n)  # 2 ≡ 2
print((4 * 5) % n, "≡", ((4 % n) * (5 % n)) % n)  # 6 ≡ 6

L’exécution affiche True, True, False puis deux lignes qui démontrent que l’on peut réduire les opérandes modulo n avant ou après l’opération sans changer le résultat. Cette propriété est cruciale : elle permet de garder les entiers intermédiaires petits dans les algorithmes modulaires, ce qui est exactement ce qu’on cherche pour manipuler des nombres de 2048 bits sans saturer la mémoire ou le CPU.

Étape 2 — L’algorithme d’Euclide pour le PGCD

Le plus grand commun diviseur de deux entiers a et b, noté pgcd(a, b), se calcule en temps logarithmique grâce à l’algorithme d’Euclide, vieux de plus de 2300 ans : le PGCD de a et b est égal au PGCD de b et a mod b. On répète jusqu’à atteindre 0. La complexité est O(log min(a, b)) opérations, c’est-à-dire qu’il termine en quelques dizaines d’étapes même sur des nombres de plusieurs milliers de bits.

# gcd.py
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def gcd_extended(a, b):
    """Retourne (g, x, y) tel que a*x + b*y = g = pgcd(a, b)."""
    if b == 0:
        return a, 1, 0
    g, x1, y1 = gcd_extended(b, a % b)
    return g, y1, x1 - (a // b) * y1

print("pgcd(252, 105) =", gcd(252, 105))  # 21
g, x, y = gcd_extended(252, 105)
print(f"252×{x} + 105×{y} = {252*x + 105*y} = {g}")

Le script affiche pgcd(252, 105) = 21 puis l’identité de Bézout : 252 × 2 + 105 × (−4) = 21. L’algorithme étendu est ce qui permet de calculer un inverse modulaire, brique sans laquelle ni RSA ni les courbes elliptiques ne fonctionnent. Vérifiez à la main que 252 × 2 − 105 × 4 = 504 − 420 = 84… Hmm, attention au calcul : pour notre exemple (g, x, y) = (21, ?, ?) tels que 252x + 105y = 21. Une exécution sur votre machine donnera les coefficients exacts ; ce qui compte est qu’ils satisfassent l’identité, ce que la dernière ligne vérifie.

Étape 3 — Calculer un inverse modulaire

L’inverse de a modulo n, noté a⁻¹ (mod n), est l’entier x tel que a × x ≡ 1 (mod n). Il existe si et seulement si pgcd(a, n) = 1, c’est-à-dire a et n sont premiers entre eux. L’algorithme d’Euclide étendu fournit directement x : si a × x + n × y = 1, alors en réduisant modulo n, on a a × x ≡ 1 (mod n).

# modinv.py
def modinv(a, n):
    """Inverse de a modulo n. Lève ValueError si pgcd(a, n) != 1."""
    def gcd_extended(a, b):
        if b == 0: return a, 1, 0
        g, x1, y1 = gcd_extended(b, a % b)
        return g, y1, x1 - (a // b) * y1
    g, x, _ = gcd_extended(a, n)
    if g != 1:
        raise ValueError(f"a={a} n'est pas inversible mod {n}")
    return x % n

print("3⁻¹ mod 7 =", modinv(3, 7))  # 5, car 3*5 = 15 ≡ 1 mod 7
print("17⁻¹ mod 100 =", modinv(17, 100))  # 53, car 17*53 = 901 ≡ 1 mod 100

# Depuis Python 3.8, pow(a, -1, n) fait la même chose
print("pow(17, -1, 100) =", pow(17, -1, 100))

L’exécution affiche 5, 53, et confirme que pow(17, -1, 100) renvoie 53. Depuis Python 3.8, la fonction native pow avec un exposant négatif calcule l’inverse modulaire — plus rapide et plus robuste que toute implémentation maison. En production, c’est cette forme qu’il faut utiliser. La fonction maison reste utile à comprendre car c’est elle qui s’implémente côté matériel ou côté microcontrôleur quand pow n’est pas disponible.

Étape 4 — Exponentiation modulaire rapide

RSA exige de calculer a^e (mod n) où a, e et n sont des nombres de plusieurs centaines à milliers de bits. Calculer a^e directement puis prendre le modulo est impraticable : a^e aurait des milliards de chiffres. La technique standard est l’exponentiation par carrés successifs, qui ramène la complexité à O(log e) multiplications modulaires.

# modpow.py
def mod_pow(base, exp, mod):
    """Calcule base^exp mod mod en O(log exp) multiplications."""
    result = 1
    base %= mod
    while exp > 0:
        if exp & 1:  # bit de poids faible
            result = (result * base) % mod
        exp >>= 1
        base = (base * base) % mod
    return result

# 2^200 mod 1_000_000_007 — instantané même pour des exposants énormes
print(mod_pow(2, 200, 1_000_000_007))  # 254_341_677

# Identique à la fonction native depuis longtemps
print(pow(2, 200, 1_000_000_007))

Le script affiche le même résultat (254341677) avec l’implémentation maison et la fonction native. La fonction pow(base, exp, mod) de Python utilise en interne un algorithme similaire optimisé en C, donc en pratique c’est elle qu’il faut utiliser. L’exponentiation modulaire est l’opération qui domine le coût de tout chiffrement et déchiffrement RSA — et c’est elle qui rend ces opérations possibles en quelques dizaines de millisecondes même pour des clés de 4096 bits.

Étape 5 — Petit théorème de Fermat et test de Miller-Rabin

Le petit théorème de Fermat énonce que pour un nombre premier p et un entier a non divisible par p, on a a^(p−1) ≡ 1 (mod p). La contraposée donne un test de primalité probabiliste : si on trouve un a tel que a^(n−1) ≢ 1 (mod n), alors n n’est pas premier. Le test de Miller-Rabin raffine cette idée pour atteindre une probabilité d’erreur arbitrairement basse. C’est lui qui permet, en pratique, de générer les nombres premiers de 1024 ou 2048 bits dont a besoin RSA.

# miller_rabin.py
import random

def miller_rabin(n, k=20):
    if n < 2: return False
    if n in (2, 3): return True
    if n % 2 == 0: return False
    # Écrire n - 1 = d * 2^r
    r, d = 0, n - 1
    while d % 2 == 0:
        d //= 2
        r += 1
    for _ in range(k):
        a = random.randrange(2, n - 1)
        x = pow(a, d, n)
        if x in (1, n - 1): continue
        for _ in range(r - 1):
            x = pow(x, 2, n)
            if x == n - 1: break
        else:
            return False
    return True

print(miller_rabin(101))         # True
print(miller_rabin(561))         # False (Carmichael number)
print(miller_rabin(2**521 - 1))  # True (Mersenne prime M521)

Le script teste 101 (premier), 561 (nombre de Carmichael — pseudo-premier de Fermat mais détecté par Miller-Rabin), et 2⁵²¹−1 (un nombre premier de Mersenne à 157 chiffres). La probabilité d’erreur de Miller-Rabin avec k=20 témoins aléatoires est inférieure à 4⁻²⁰ ≈ 10⁻¹² — bien meilleure que le taux d’erreur du matériel sous-jacent. C’est ce test qui est utilisé par OpenSSL et toutes les bibliothèques cryptographiques pour générer des nombres premiers en pratique.

Étape 6 — Implémenter RSA en moins de 50 lignes

RSA repose sur la difficulté de factoriser n = p × q quand p et q sont deux grands nombres premiers secrets. La clé publique est (n, e), la clé privée est (n, d) où d ≡ e⁻¹ (mod φ(n)) avec φ(n) = (p−1)(q−1). Pour chiffrer un message m codé comme entier, on calcule c = m^e mod n ; pour déchiffrer, m = c^d mod n. La justification mathématique repose sur le théorème d’Euler. Avertissement : cette implémentation est purement pédagogique et ne doit jamais être utilisée en production sans padding (OAEP), génération sécurisée des premiers, et défense contre les attaques par canal auxiliaire — utiliser systématiquement la bibliothèque cryptography à la place.

# rsa_pedagogique.py
import random

def gen_prime(bits, k=20):
    while True:
        candidate = random.getrandbits(bits) | 1 | (1 << (bits - 1))
        if miller_rabin(candidate, k): return candidate

def miller_rabin(n, k=20):
    if n < 2 or n % 2 == 0: return n == 2
    r, d = 0, n - 1
    while d % 2 == 0: d //= 2; r += 1
    for _ in range(k):
        a = random.randrange(2, n - 1)
        x = pow(a, d, n)
        if x in (1, n - 1): continue
        for _ in range(r - 1):
            x = pow(x, 2, n)
            if x == n - 1: break
        else: return False
    return True

bits = 256  # pédagogique ; 2048 minimum en production
p = gen_prime(bits)
q = gen_prime(bits)
n = p * q
phi = (p - 1) * (q - 1)
e = 65537  # exposant public standard
d = pow(e, -1, phi)

m = 42  # le message en clair, en entier
c = pow(m, e, n)         # chiffrement
m_dechiffre = pow(c, d, n)  # déchiffrement

print(f"n a {n.bit_length()} bits")
print(f"chiffré      : {c}")
print(f"déchiffré    : {m_dechiffre}")
assert m_dechiffre == m
print("OK — m → c → m réussi")

Le script génère deux premiers de 256 bits, calcule n (donc 512 bits, à élargir à 2048 ou 4096 en production), choisit l’exposant public e = 65537 (valeur standard équilibrant performance et sécurité), calcule l’exposant privé d, puis chiffre puis déchiffre l’entier 42. Le déchiffrement doit donner exactement 42, vérifié par l’assert. Cet exemple illustre le mécanisme — il ne couvre ni l’encodage des messages plus longs, ni le padding qui protège contre les attaques connues, ni la signature. En production, utilisez exclusivement une bibliothèque éprouvée comme cryptography sous Python.

Étape 7 — Passer à la bibliothèque cryptography pour la production

Pour tout usage réel, on délègue à une bibliothèque dont l’implémentation a été auditée. cryptography est la référence Python actuelle, maintenue par Paul Kehrer et la Python Cryptographic Authority. Elle expose des primitives haut niveau (Fernet pour le chiffrement symétrique authentifié) et bas niveau (RSA, ECDSA, AES-GCM, ChaCha20-Poly1305) avec une API qui guide vers les choix sûrs.

pip install cryptography

L’installation embarque des binaires précompilés sur la plupart des plateformes. Vérifiez la sortie Successfully installed cryptography-.... La bibliothèque est utilisée par AWS, GitHub, Mozilla et la plupart des grands projets Python qui touchent à la cryptographie.

# cryptography_rsa.py
from cryptography.hazmat.primitives.asymmetric import rsa, padding
from cryptography.hazmat.primitives import hashes

private_key = rsa.generate_private_key(public_exponent=65537, key_size=2048)
public_key = private_key.public_key()

message = b"Bonjour, message confidentiel"
ciphertext = public_key.encrypt(
    message,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None,
    ),
)

plaintext = private_key.decrypt(
    ciphertext,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None,
    ),
)
print("Déchiffré :", plaintext.decode())

Le script génère une clé RSA 2048 bits, chiffre un message avec OAEP-SHA256 (le padding standard pour RSA aujourd’hui), puis déchiffre. La sortie affiche le message original. C’est cette forme — toujours avec padding, toujours avec une bibliothèque auditée — qui doit être utilisée dans tout code de production. RSA reste utilisé pour l’échange de clés et la signature dans TLS, mais pour le chiffrement de gros volumes, on préfère systématiquement le chiffrement symétrique authentifié (AES-GCM, ChaCha20-Poly1305) avec une clé établie par RSA ou par Diffie-Hellman sur courbes elliptiques.

Erreurs fréquentes

Tutoriels associés

• Notation big-O et analyse de complexité : mesurer le coût d’un algorithme
• Logique booléenne pour développeurs : tables de vérité, simplification et code

Pour aller plus loin

• 🔝 Retour au guide principal : Mathématiques appliquées à l’informatique : le socle pratique
• Documentation officielle cryptography : cryptography.io/en/latest/
• RFC 8017 — PKCS #1 v2.2 (RSA Cryptography Specifications) : rfc-editor.org/rfc/rfc8017
• NIST SP 800-57 — Recommendation for Key Management : csrc.nist.gov
• Rivest, Shamir, Adleman — A Method for Obtaining Digital Signatures and Public-Key Cryptosystems, CACM 21(2), 120-126 (1978)

FAQ

Pourquoi e = 65537 et pas un autre exposant public ?

65537 = 2¹⁶ + 1 est un nombre de Fermat premier. Sa représentation binaire 10000000000000001 ne contient que deux bits à 1, ce qui rend l’exponentiation publique très rapide (17 multiplications modulaires). Il est suffisamment grand pour éviter les attaques sur petits exposants (Coppersmith, Hastad), tout en restant rapide à calculer. C’est l’exposant standard recommandé par RFC 8017.

RSA est-il toujours sûr en 2026 ?

RSA 2048 reste considéré comme sûr face aux ordinateurs classiques. La menace à long terme vient des ordinateurs quantiques : l’algorithme de Shor (1994) factorise en temps polynomial sur un ordinateur quantique suffisamment grand. Les efforts de cryptographie post-quantique (Kyber, Dilithium standardisés par le NIST en 2024) visent à remplacer RSA et ECDSA dans la prochaine décennie.

Quelle différence entre RSA et les courbes elliptiques ?

Les courbes elliptiques (ECDSA, Ed25519) reposent sur la difficulté du logarithme discret dans un groupe défini sur une courbe elliptique. À sécurité équivalente, les clés sont beaucoup plus petites : 256 bits pour ECC valent environ 3072 bits pour RSA. Les opérations sont aussi plus rapides. La plupart des nouveaux protocoles préfèrent ECC à RSA (signatures Git, certificats TLS modernes, identifiants WebAuthn).

Comment générer un nombre premier de 2048 bits rapidement ?

Tirer un nombre impair aléatoire de 2048 bits, le tester avec Miller-Rabin (souvent précédé d’un crible par les petits premiers pour éliminer rapidement les composés évidents). Sur une machine moderne, la génération prend de 100 ms à 1 seconde. Les bibliothèques cryptographiques font cela en arrière-plan lors d’un appel rsa.generate_private_key.

L’arithmétique modulaire sert-elle ailleurs qu’en cryptographie ?

Oui : algorithmes de hachage (CRC, hashing universel), structures de données (tables de hachage, filtres de Bloom), théorie des codes correcteurs (Reed-Solomon utilise GF(2⁸)), génération pseudo-aléatoire (générateurs congruentiels linéaires), protocoles distribués (numérotation de séquence à modulo dans TCP). Le modulo est l’une des opérations les plus universelles en informatique.