Rappels mathématiques et algorithmiques

La cryptographie moderne n'emprunte aux mathématiques qu'un outillage restreint. Ce chapitre le rassemble une fois pour toutes, avec un critère de sélection strict : chaque notion présentée ici sert dans un chapitre ultérieur, et aucune n'est là pour la culture.

Un conseil de méthode avant de commencer. Ne cherchez pas à retenir les démonstrations, mais les énoncés et leurs conséquences opératoires : ce que le théorème des restes chinois autorise à calculer, ce que l'ordre d'un élément interdit de faire, pourquoi un test de primalité probabiliste est acceptable pour engendrer une clé RSA.

Arithmétique modulaire

Travailler modulo $n$, c'est travailler dans $\mathbb{Z}/n\mathbb{Z}$, l'ensemble des restes $\{0, 1, \dots, n-1\}$ muni de l'addition et de la multiplication. Addition, soustraction et multiplication s'y comportent normalement. La division, non — et c'est le seul point délicat.

L'élément $a$ est inversible modulo $n$ s'il existe $b$ tel que $ab \equiv 1 \pmod n$. Cela se produit exactement quand $\gcd(a, n) = 1$, et l'algorithme d'Euclide étendu fournit l'inverse en calculant les coefficients de Bézout $au + nv = 1$.

Cherchons l'inverse de 17 modulo 43. La descente d'Euclide donne $43 = 2 \times 17 + 9$, puis $17 = 1 \times 9 + 8$, puis $9 = 1 \times 8 + 1$. En remontant :

Donc $-5 \times 17 \equiv 1 \pmod{43}$, et l'inverse est $-5 \equiv 38$. Vérification : $17 \times 38 = 646 = 15 \times 43 + 1$.

Cet algorithme est la brique qui produit l'exposant privé de RSA : $d$ est précisément l'inverse de $e$ modulo $\varphi(n)$.

Groupes, ordre, générateurs

Les éléments inversibles modulo $n$ forment un groupe multiplicatif noté $(\mathbb{Z}/n\mathbb{Z})^*$, de cardinal $\varphi(n)$ — l'indicatrice d'Euler. Pour $n = pq$ produit de deux premiers distincts, $\varphi(n) = (p-1)(q-1)$, l'égalité sur laquelle RSA est bâti tout entier.

L'ordre d'un élément $a$ est le plus petit $k > 0$ tel que $a^k = 1$. Le théorème de Lagrange affirme qu'il divise l'ordre du groupe, d'où le théorème d'Euler :

et son cas particulier, le petit théorème de Fermat : $a^{p-1} \equiv 1 \pmod p$ pour $p$ premier et $p \nmid a$.

Un groupe est cyclique s'il possède un générateur, c'est-à-dire un élément dont les puissances parcourent tout le groupe. Le résultat utile : $(\mathbb{Z}/p\mathbb{Z})^*$ est cyclique d'ordre $p-1$ pour tout $p$ premier. Prenons $p = 7$ et $g = 3$ :

Les six valeurs non nulles apparaissent : 3 est bien un générateur. Ce n'est pas le cas de tout élément — $2$ a pour puissances $2, 4, 1$ et engendre un sous-groupe d'ordre 3 seulement. Le nombre de générateurs est $\varphi(p-1)$, soit ici $\varphi(6) = 2$.

Cette distinction n'est pas décorative. Au chapitre 10, un Diffie-Hellman dont le générateur engendre un petit sous-groupe est cassé immédiatement : l'attaquant n'a qu'un petit nombre de valeurs à énumérer. Vérifier l'ordre du générateur fait partie de la mise en œuvre correcte, et son oubli a produit des vulnérabilités réelles.

Corps finis

Un corps fini $\mathbb{F}_q$ existe pour $q = p^k$, $p$ premier, et il est unique à isomorphisme près. Deux cas nous concernent.

Pour $k = 1$, $\mathbb{F}_p = \mathbb{Z}/p\mathbb{Z}$ : tout élément non nul y est inversible, puisque $p$ est premier. C'est le terrain du logarithme discret et des courbes elliptiques.

Pour $p = 2$, $\mathbb{F}_{2^k}$ se construit comme les polynômes à coefficients dans $\{0,1\}$ modulo un polynôme irréductible de degré $k$. Un octet devient un polynôme de degré au plus 7, l'addition devient le XOR, et la multiplication devient un produit de polynômes réduit modulo l'irréductible. AES travaille dans $\mathbb{F}_{2^8}$ avec

Ce n'est pas un détail d'implémentation : la boîte de substitution de l'AES est l'inversion dans ce corps, suivie d'une application affine. Le chapitre 4 montrera pourquoi ce choix donne à l'AES sa résistance différentielle.

Le théorème des restes chinois

Si $m$ et $n$ sont premiers entre eux, l'application

est un isomorphisme d'anneaux. Autrement dit : connaître $x$ modulo $m$ et modulo $n$ équivaut à le connaître modulo $mn$, et les opérations se font indifféremment d'un côté ou de l'autre.

L'exemple de Sun Tzu, vieux de dix-sept siècles : trouver $x$ tel que $x \equiv 2 \pmod 3$, $x \equiv 3 \pmod 5$, $x \equiv 2 \pmod 7$. La solution est $x = 23$ modulo 105.

L'usage cryptographique est immédiat. Le déchiffrement RSA calcule $c^d \bmod n$ avec $n = pq$ ; en travaillant séparément modulo $p$ et modulo $q$, les exposants sont deux fois plus courts et les modules deux fois plus petits, ce qui donne un facteur d'accélération d'environ 4. Toutes les implémentations sérieuses le font.

Et immédiatement, le revers : si une erreur matérielle survient pendant l'un des deux calculs — un rayonnement, une injection de faute volontaire — la signature produite est correcte modulo $p$ et fausse modulo $q$. Alors $\gcd(s^e - m, n)$ livre $p$. Une seule signature fautive suffit à factoriser le module. C'est l'attaque de Boneh, DeMillo et Lipton (1997), et c'est la raison pour laquelle une implémentation correcte revérifie sa propre signature avant de la publier.

Exponentiation rapide

Tous les schémas asymétriques calculent des $a^e \bmod n$ avec des exposants de plusieurs centaines de bits. Multiplier $e$ fois est hors de question ; on lit l'exposant en binaire.

Pour $3^{13} \bmod 7$, avec $13 = 1101_2$ :

Résultat 3, en quatre carrés et trois multiplications au lieu de treize. Le coût passe de $O(e)$ à $O(\log e)$, et c'est ce qui rend l'asymétrique praticable.

Une mise en garde qui portera ses fruits au chapitre 9 : cet algorithme, écrit naïvement, n'est pas à temps constant. La multiplication n'a lieu que pour les bits à 1 de l'exposant ; la durée du calcul dépend donc du secret quand cet exposant est la clé privée. Mesurée assez finement, elle le révèle bit par bit. La parade usuelle est l'échelle de Montgomery, qui effectue les deux opérations à chaque tour et jette l'une des deux.

// Calculer a^e mod n sans jamais former a^e.
//
// BigInt est indispensable : en RSA, a et n font 2048 bits. L'écriture 3n
// désigne le BigInt 3.

// ── Version naïve, fournie pour la comparaison ────────────────────────────
function puissanceNaive(a, e, n) {
  let r = 1n, mults = 0n;
  for (let i = 0n; i < e; i++) {
    r = (r * a) % n;
    mults++;
  }
  return { valeur: r, mults };
}

// ── À COMPLÉTER : exponentiation par carrés ───────────────────────────────
// Principe : lire l'exposant en binaire. À chaque bit, on élève au carré ;
// quand le bit vaut 1, on multiplie en plus par la base.
//
//   a^13 = a^(1101 en binaire) = ((a^2 · a)^2)^2 · a
//
// Renvoyez aussi le nombre de multiplications effectuées.
function puissanceRapide(a, e, n) {
  let resultat = 1n;
  let base = a % n;
  let exposant = e;
  let mults = 0n;

  while (exposant > 0n) {
    // à compléter : traiter le bit de poids faible, puis passer au suivant
    exposant = exposant >> 1n;
  }

  return { valeur: resultat, mults };
}

// ── Vérification ──────────────────────────────────────────────────────────
const p = 1000003n; // premier
const a = 123456n;
const e = 65537n;   // l'exposant public usuel de RSA

const lent = puissanceNaive(a, e, p);
const vif = puissanceRapide(a, e, p);

console.log("naïve  :", lent.valeur, "en", lent.mults, "multiplications");
console.log("rapide :", vif.valeur, "en", vif.mults, "multiplications");
console.log(vif.valeur === lent.valeur ? "✓ même résultat" : "✗ résultats différents");

// Le rapport que vous devez observer : 65537 contre une vingtaine.
// Avec l'exposant privé d de RSA-2048, la version naïve demanderait 2^2048
// multiplications — c'est-à-dire jamais.

function puissanceRapide(a, e, n) {
  let resultat = 1n;
  let base = a % n;
  let exposant = e;
  let mults = 0n;

  while (exposant > 0n) {
    // Bit de poids faible à 1 : le facteur courant entre dans le résultat.
    if (exposant % 2n === 1n) {
      resultat = (resultat * base) % n;
      mults++;
    }
    // Passage au bit suivant : la base est élevée au carré.
    base = (base * base) % n;
    mults++;
    exposant = exposant >> 1n;
  }

  return { valeur: resultat, mults };
}

// 65537 = 2^16 + 1 : dix-sept bits, dont deux à 1.
// La boucle fait 17 carrés et 2 multiplications, soit 19 au lieu de 65537.
//
// Le coût est donc en log2(e), pas en e. C'est toute la différence entre
// « RSA chiffre en quelques millisecondes » et « RSA ne terminerait jamais ».
//
// Attention pour la suite : cette écriture est correcte mais NON constante en
// temps. Le test « if » ne s'exécute que pour les bits à 1 de l'exposant, donc
// la durée du calcul révèle le poids de Hamming de l'exposant — et, mesurée
// finement, ses bits un par un. Quand l'exposant est la clé PRIVÉE d, c'est
// une fuite directe. Le chapitre 9 y revient ; la parade usuelle est l'échelle
// de Montgomery, qui fait les deux opérations à chaque tour.

Tester la primalité

Engendrer une clé RSA demande deux grands premiers. On les obtient en tirant des entiers impairs au hasard et en les testant — la densité des premiers autour de $2^{1024}$ étant d'environ $1/\ln(2^{1024}) \approx 1/710$, un candidat impair sur 355 environ est premier.

Le test de Fermat, qui vérifie $a^{n-1} \equiv 1 \pmod n$, ne suffit pas : les nombres de Carmichael le passent pour toute base première avec eux. Le plus petit est $561 = 3 \times 11 \times 17$.

Miller-Rabin corrige ce défaut. On écrit $n - 1 = 2^s d$ avec $d$ impair, et l'on teste si la suite $a^d, a^{2d}, \dots, a^{2^{s-1}d}$ se comporte comme elle le devrait dans un corps, où $1$ n'a que deux racines carrées. Pour $n$ composé, au moins trois quarts des bases sont des témoins de composition ; $k$ tirages indépendants laissent donc une probabilité d'erreur inférieure à $4^{-k}$.

Deux précisions honnêtes. La borne $4^{-k}$ est le pire cas ; pour un entier tiré au hasard, l'erreur réelle est très inférieure, et les standards de génération de clés s'en servent pour justifier une poignée de tours seulement. Et un test déterministe polynomial existe depuis 2002 — l'algorithme AKS — mais il est trop lent pour un usage pratique : la cryptographie déployée utilise Miller-Rabin.

Ce qu'on appelle « efficace »

Un dernier point de vocabulaire, sans lequel les énoncés de difficulté n'ont pas de sens. La complexité se mesure en la taille de l'entrée en bits, pas en la valeur de l'entrée. Factoriser $n$ par divisions successives coûte $O(\sqrt{n})$ opérations, soit $O(2^{\ell/2})$ pour $\ell$ bits : c'est exponentiel en la taille.

La dernière ligne explique à elle seule le chapitre 11 : aucun algorithme sous-exponentiel n'étant connu sur les courbes, une clé de 256 bits y offre le niveau de sécurité qu'un module RSA de 3072 bits atteint péniblement.

Ce que la suite en fait

Chaque outil de ce chapitre a son échéance. L'inverse modulaire produit l'exposant privé de RSA au chapitre 9 ; les corps $\mathbb{F}_{2^8}$ portent la boîte S de l'AES au chapitre 4 ; les groupes cycliques et l'ordre des éléments fondent Diffie-Hellman au chapitre 10 ; les restes chinois accélèrent RSA et le fragilisent dans le même mouvement.

Le chapitre 3 marque une rupture de ton : il s'agira d'un seul théorème, celui de Shannon, et de ce qu'il interdit.

À retenir

QCM de synthèse — Bloc 0 — Socle

Le QCM ci-dessous porte sur l'ensemble du bloc : plusieurs questions relient les leçons entre elles. En cas d'erreur, le bilan indique le chapitre à revoir.