Arithmetique et cryptographie¶

Chaque connexion HTTPS repose sur de l'arithmetique modulaire — comprendre ces bases, c'est comprendre pourquoi vos données restent privées.

Division euclidienne et PGCD¶

Tout commence par la division euclidienne. Diviser un entier \(a\) par un entier \(b > 0\) produit deux entiers uniques \(q\) (quotient) et \(r\) (reste) tels que :

Le reste \(r\) est noté \(a \bmod b\). C'est le fondement de toute l'arithmetique modulaire.

Le PGCD (Plus Grand Commun Diviseur) de deux entiers \(a\) et \(b\) est le plus grand entier qui divise les deux. L'algorithme d'Euclide le calcule efficacement en exploitant la propriété :

Ce qui converge car \(a \bmod b < b\), et le processus s'arrêté quand le reste est zero.

def pgcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

# Exemple
pgcd(252, 105)  # -> 21
# 252 = 105*2 + 42
# 105 = 42*2  + 21
#  42 = 21*2  + 0   <- PGCD = 21

Algorithme d'Euclide étendu et identité de Bezout¶

L'identité de Bezout affirme que si \(d = \text{PGCD}(a, b)\), il existe deux entiers \(u\) et \(v\) tels que :

L'algorithme d'Euclide étendu calcule ces coefficients \(u\) et \(v\). C'est la clé pour trouver l'inverse modulaire.

def euclide_etendu(a, b):
    if b == 0:
        return a, 1, 0
    d, u, v = euclide_etendu(b, a % b)
    return d, v, u - (a // b) * v

# Exemple : trouver u, v tels que 252*u + 105*v = 21
d, u, v = euclide_etendu(252, 105)
# d=21, u=-2, v=5
# Verification : 252*(-2) + 105*5 = -504 + 525 = 21 ✓

Arithmetique modulaire¶

Travailler "modulo \(n\)" signifie que seul le reste de la division par \(n\) compte. On peut imaginer un cercle de \(n\) positions : après la position \(n-1\), on revient à \(0\). Deux entiers sont dits congruents modulo \(n\) s'ils ont le même reste :

Opérations modulaires¶

Les opérations standard se transportent naturellement :

La division ne s'effectue pas directement — il faut passer par l'inverse modulaire.

Inverse modulaire¶

L'inverse de \(a\) modulo \(n\), noté \(a^{-1} \bmod n\), est l'entier \(x\) tel que :

Il existe si et seulement si \(\text{PGCD}(a, n) = 1\) (\(a\) et \(n\) sont premiers entre eux). On le calcule avec l'algorithme d'Euclide étendu :

def inverse_modulaire(a, n):
    d, u, v = euclide_etendu(a, n)
    if d != 1:
        raise ValueError(f"{a} n'a pas d'inverse mod {n} (PGCD={d})")
    return u % n

# Exemple : inverse de 3 mod 7
inverse_modulaire(3, 7)  # -> 5
# Verification : 3 * 5 = 15 = 2*7 + 1 ≡ 1 (mod 7) ✓

Petit théorème de Fermat¶

Si \(p\) est un nombre premier et \(a\) n'est pas divisible par \(p\), alors :

Conséquence directe : \(a^{-1} \equiv a^{p-2} \pmod{p}\). On peut donc calculer l'inverse modulaire par exponentiation quand le modulo est premier — ce que RSA exploite.

Exponentiation rapide¶

Calculer \(a^e \bmod n\) navement (multiplier \(a\) par lui-même \(e\) fois) est inutilisable quand \(e\) est grand (des centaines de bits en RSA). L'algorithme d'exponentiation rapide (square-and-multiply) divise le travail en \(O(\log e)\) multiplications :

def expo_rapide(base, exposant, modulo):
    resultat = 1
    base = base % modulo
    while exposant > 0:
        if exposant % 2 == 1:          # bit courant = 1
            resultat = (resultat * base) % modulo
        exposant = exposant >> 1       # diviser par 2
        base = (base * base) % modulo  # carrer la base
    return resultat

# Calculer 5^117 mod 1000 en quelques etapes seulement
expo_rapide(5, 117, 1000)  # -> 125

Trace pour \(5^{13} \bmod 7\) (13 = 1101 en binaire) :

\(5^{13} \bmod 7 = 5\) en 4 étapes au lieu de 12.

Nombres premiers¶

Un entier \(p > 1\) est premier s'il n'est divisible que par 1 et lui-même. Les nombres premiers sont les "atomes" de l'arithmetique — tout entier se decompose de façon unique en produit de premiers (théorème fondamental de l'arithmetique).

Crible d'Eratosthene¶

Pour trouver tous les premiers jusqu'à \(n\) : partir de 2, marquer tous ses multiples comme non-premiers, passer au suivant non-marque, recommencer.

def crible(n):
    est_premier = [True] * (n + 1)
    est_premier[0] = est_premier[1] = False
    for i in range(2, int(n**0.5) + 1):
        if est_premier[i]:
            for j in range(i*i, n + 1, i):
                est_premier[j] = False
    return [i for i, p in enumerate(est_premier) if p]

premiers = crible(50)
# [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

Complexité : \(O(n \log \log n)\) — efficace pour les petites valeurs, mais inutilisable pour les entiers de 1024 bits de RSA.

Test de Miller-Rabin (version simplifiée)¶

Pour tester si un grand entier est premier, on utilisé des tests probabilistes. Miller-Rabin s'appuie sur la propriété suivante : si \(p\) est premier et \(p-1 = 2^s \times d\) avec \(d\) impair, alors pour tout \(a\) non-multiple de \(p\) :

• soit \(a^d \equiv 1 \pmod{p}\)
• soit il existe \(r < s\) tel que \(a^{2^r \times d} \equiv -1 \pmod{p}\)

Si ces conditions ne sont pas satisfaites, \(p\) est certainement compose. Si elles le sont, \(p\) est "probablement premier". Répéter avec plusieurs bases \(a\) réduit la probabilite d'erreur a moins de \(4^{-k}\) avec \(k\) rounds.

import random

def miller_rabin(n, k=20):
    if n < 2: return False
    if n == 2 or n == 3: return True
    if n % 2 == 0: return False

    # Ecrire n-1 = 2^s * d
    s, d = 0, n - 1
    while d % 2 == 0:
        s += 1
        d //= 2

    for _ in range(k):
        a = random.randrange(2, n - 1)
        x = expo_rapide(a, d, n)
        if x == 1 or x == n - 1:
            continue
        for _ in range(s - 1):
            x = expo_rapide(x, 2, n)
            if x == n - 1:
                break
        else:
            return False  # certainement compose
    return True  # probablement premier

# Generer un premier de 512 bits
def premier_aleatoire(bits):
    while True:
        p = random.getrandbits(bits) | (1 << bits - 1) | 1  # impair, bon MSB
        if miller_rabin(p):
            return p

RSA simplifie¶

RSA (Rivest–Shamir–Adleman, 1977) est le système de cryptographie asymetrique le plus connu. Sa sécurité repose sur la difficulté de factoriser le produit de deux grands nombres premiers.

Génération des clés¶

1. Choisir deux grands premiers distincts \(p\) et \(q\)
2. Calculer \(n = p \times q\) (le modulus public)
3. Calculer \(\varphi(n) = (p-1)(q-1)\) (indicatrice d'Euler)
4. Choisir \(e\) tel que \(1 < e < \varphi(n)\) et \(\text{PGCD}(e, \varphi(n)) = 1\) (\(e = 65537\) est standard)

5. Calculer \(d = e^{-1} \bmod \varphi(n)\) (l'inverse modulaire via Euclide étendu)

6. Clé publique : \((n, e)\)

7. Clé privee : \((n, d)\) — garder \(p\), \(q\), \(\varphi(n)\) secrets

Chiffrement et dechiffrement¶

La correction repose sur le petit théorème de Fermat : \((m^e)^d = m^{ed} \equiv m \pmod{n}\) parce que \(ed \equiv 1 \pmod{\varphi(n)}\).

Exemple numérique complet¶

Avec de petits nombres pour l'illustration (RSA réel utilise des entiers de 2048+ bits) :

# Parametres jouets
p, q = 61, 53
n = p * q          # n = 3233
phi = (p-1)*(q-1)  # phi = 3120
e = 17             # PGCD(17, 3120) = 1 ✓

# Cle privee : d = inverse de 17 mod 3120
d = inverse_modulaire(e, phi)  # d = 2753
# Verification : 17 * 2753 = 46801 = 15*3120 + 1 ≡ 1 (mod 3120) ✓

# Cle publique : (3233, 17)
# Cle privee  : (3233, 2753)

# Chiffrement du message m = 65
m = 65
c = expo_rapide(m, e, n)  # c = 65^17 mod 3233 = 2790

# Dechiffrement
m_dechiffre = expo_rapide(c, d, n)  # 2790^2753 mod 3233 = 65 ✓
assert m_dechiffre == m

Pourquoi factoriser n casse RSA¶

Connaître \(n = p \times q\) publiquement ne suffit pas. Mais si on pouvait factoriser \(n\) pour retrouver \(p\) et \(q\), on recalculerait \(\varphi(n)\) et donc \(d\). Le meilleur algorithme connu de factorisation (GNFS) s'exécuté en temps sous-exponentiel mais pratiquement inutilisable pour des moduli de 2048 bits — d'ou la recommandation de cette taille minimale.

Fonctions de hachage cryptographiques¶

Une fonction de hachage prend une entree de taille arbitraire et produit une sortie de taille fixe (le "digest" ou "empreinte"). Les propriétés cryptographiques qui importent :

SHA-256¶

SHA-256 produit un digest de 256 bits (32 octets, 64 caractères hexa). C'est la référence actuelle pour la majorité des usages. Il traite le message en blocs de 512 bits via 64 rounds de compression.

import hashlib

msg = b"Hello, world"
digest = hashlib.sha256(msg).hexdigest()
# "315f5bdb76d078c43b8ac0064e4a0164612b1fce77c869345bfc94c75894edd3"

# Un seul bit change :
msg2 = b"Hello, World"  # W majuscule
digest2 = hashlib.sha256(msg2).hexdigest()
# "dffd6021bb2bd5b0af676290809ec3a53191dd81c7f70a4b28688a362182986d"
# Completement different -> effet avalanche ✓

Usage dans Git¶

Git identifie chaque objet (commit, tree, blob) par son hash SHA-1 (en cours de migration vers SHA-256). Le digest est à la fois l'identifiant et la vérification d'intégrité :

$ git cat-file -p HEAD
tree a8f4d...
parent 3b2c1...
author ...
committer ...

Message du commit

Le hash du commit dépend du hash du tree, qui dépend des hashs des blobs. Modifier un seul octet d'un fichier change son hash, celui du tree, et celui du commit — rendant toute falsification immédiate a détecter.

Usage dans les blockchains¶

Dans Bitcoin, chaque bloc contient le hash du bloc précédent. Modifier un bloc historique changerait son hash, brisant le lien avec le suivant — il faudrait recalculer tous les blocs suivants plus vite que le réseau entier ne les produit. Le coût énergétique du proof-of-work rend cela pratiquement impossible.

Bloc 1: hash = SHA256(SHA256(header))
Bloc 2: hash = SHA256(SHA256(header avec prev_hash = hash(bloc 1)))
Bloc 3: hash = SHA256(SHA256(header avec prev_hash = hash(bloc 2)))

Signatures numériques¶

Une signature numérique permet à Bob de vérifier qu'un message vient bien d'Alice et n'a pas été altere — sans que personne d'autre ne puisse forger cette signature.

Schéma simplifie avec RSA¶

Alice (clé privée \(d_A\), clé publique \(e_A\)) :

Bob (connait la clé publique d'Alice) :

En pratique, on signe le hash du message (pas le message entier) parce que RSA ne peut signer que des entiers inférieurs a \(n\).

Certificats X.509¶

Un certificat X.509 est un document structure qui associe une clé publique a une identité (nom de domaine, organisation). Il est signe par une Autorité de Certification (CA) dont la clé publique est pre-installee dans les navigateurs.

Certificat de www.example.com :
  Sujet     : CN=www.example.com
  Cle pub   : RSA 2048 bits (e=65537, n=...)
  Emetteur  : DigiCert Inc.
  Validite  : 2024-01-01 -> 2025-01-01
  Signature : hash(contenu)^d_DigiCert mod n_DigiCert

Quand votre navigateur vérifié ce certificat, il calcule \(\text{signature}^{e_{\text{DigiCert}}} \bmod n_{\text{DigiCert}}\) et compare au hash du contenu — exactement comme la vérification RSA vue plus haut.

Applications : TLS handshake en détail¶

Quand votre navigateur ouvre https://example.com, voici ce que les mathématiques font concretement :

sequenceDiagram
    participant C as Client
    participant S as Serveur

    C->>S: ClientHello (versions TLS supportees, suites crypto, nonce client)
    S->>C: ServerHello (suite choisie, nonce serveur)
    S->>C: Certificate (certificat X.509)
    S->>C: ServerHelloDone

    Note over C: Verifier la signature du certificat\n(RSA ou ECDSA avec cle publique CA)
    Note over C: Extraire la cle publique du serveur

    C->>S: ClientKeyExchange (pre-master secret chiffre avec cle pub serveur)
    Note over C,S: Les deux derivent le master secret :\nmaster = PRF(pre_master, "master secret",\n           nonce_client + nonce_serveur)
    Note over C,S: Derivation des cles symetriques AES\net des cles HMAC depuis master secret

    C->>S: ChangeCipherSpec + Finished (HMAC de toute la session)
    S->>C: ChangeCipherSpec + Finished (HMAC de toute la session)
    Note over C,S: Canal chiffre etabli — AES-GCM en pratique

HMAC¶

HMAC (Hash-based Message Authentication Code) combine une clé secrète et une fonction de hachage pour produire un code d'authentification :

Usage concret : authentifier les messages dans une API REST avec une clé partagee, sans avoir recours à la cryptographie asymetrique.

import hmac, hashlib, secrets

cle_secrete = secrets.token_bytes(32)  # generer une cle solide

def signer(message: bytes) -> bytes:
    return hmac.new(cle_secrete, message, hashlib.sha256).digest()

def verifier(message: bytes, signature: bytes) -> bool:
    expected = signer(message)
    return hmac.compare_digest(expected, signature)  # comparaison en temps constant

Key derivation (PBKDF2, Argon2)¶

Stocker un mot de passe en clair est une faute grave. Mais stocker SHA256(password) est presque aussi grave — les rainbow tables pre-calculent les hashs des mots de passe courants.

La solution : une fonction de derivation de clé (KDF) qui ajoute un sel aléatoire et rend le calcul intentionnellement lent :

import hashlib, os

def hacher_mdp(mdp: str) -> tuple[bytes, bytes]:
    sel = os.urandom(16)
    cle = hashlib.pbkdf2_hmac('sha256', mdp.encode(), sel,
                               iterations=600_000)  # 600k iterations
    return sel, cle

def verifier_mdp(mdp: str, sel: bytes, cle_stockee: bytes) -> bool:
    cle = hashlib.pbkdf2_hmac('sha256', mdp.encode(), sel, 600_000)
    return hmac.compare_digest(cle, cle_stockee)

Argon2 (vainqueur du Password Hashing Compétition 2015) est aujourd'hui préféré a PBKDF2 car il est aussi résistant aux attaques GPU et FPGA grâce à sa dépendance mémoire.

Recapitulatif¶