En 1883, dans le Journal des sciences militaires, Auguste Kerckhoffs énonce six règles pour les chiffres de campagne. Cinq sont datées — elles parlent de télégraphe et de portabilité. La seconde a fondé la discipline : le système ne doit pas exiger le secret, et doit pouvoir tomber sans inconvénient entre les mains de l'ennemi.

Ce premier chapitre ne chiffre rien. Il installe le vocabulaire sans lequel les treize suivants seraient une collection de recettes : ce qu'on protège, contre quel adversaire, et ce que « sûr » signifie exactement — car ce mot, employé sans modèle, ne veut rien dire.

Quatre garanties, à ne pas confondre

Un système cryptographique ne protège jamais « en général ». Il offre des garanties nommées, et l'erreur la plus commune consiste à croire que l'une entraîne les autres.

Deux confusions méritent d'être défaites tout de suite.

Chiffrer n'est pas protéger l'intégrité. Un message chiffré en mode flot — ou en CTR, que le chapitre 4 détaillera — se modifie sans être lu. Le chiffré est le clair masqué par une suite pseudo-aléatoire ; inverser un bit du chiffré inverse le bit correspondant du clair. Si le message est VIREMENT 0100 EUR, un attaquant qui sait où se trouve le montant le change sans posséder la clé et sans jamais lire le message. C'est la malléabilité, et c'est la raison d'être du chapitre 8.

Un MAC n'apporte pas la non-répudiation. Un code d'authentification repose sur une clé partagée : Alice et Bob la détiennent tous les deux. Si Bob présente à un juge un message authentifié, Alice répond qu'il a pu le fabriquer lui-même — et elle a raison, rien ne les distingue. Seule une signature à clé publique, où la clé de vérification n'est pas la clé de production, oppose une preuve à un tiers. C'est le chapitre 9.

Le principe de Kerckhoffs, et ce qu'il ne dit pas

La formulation moderne du principe tient en une phrase : toute la sécurité doit résider dans la clé. Shannon la reprendra en 1949 sous une forme plus brutale — l'ennemi connaît le système.

La justification est pratique avant d'être théorique. Une clé se change ; une conception ne se change pas. Le jour où un employé part, où un boîtier est démonté, où un binaire est décompilé, un système dont le secret était la conception est perdu définitivement, et pour tous ses utilisateurs à la fois. L'histoire a tranché sans appel : CSS des DVD, A5/1 du GSM, Crypto1 des cartes MIFARE — tous conçus dans le secret, tous cassés dans les semaines qui ont suivi leur rétro-ingénierie.

Une nuance d'honnêteté s'impose cependant, car le principe est souvent récité trop vite. Kerckhoffs n'interdit pas de garder une architecture confidentielle : il interdit d'en dépendre. Ne pas publier la topologie de son réseau interne est une mesure de défense en profondeur raisonnable. Faire reposer la confidentialité des communications sur le fait que personne ne devinera l'algorithme ne l'est pas. La différence est celle entre une couche supplémentaire et une fondation.

L'adversaire : ce qu'il voit, ce qu'il peut

On distingue d'abord deux postures.

L'attaquant passif observe. Il enregistre le trafic et l'analyse hors ligne, parfois des années plus tard — c'est le modèle du « récolter maintenant, déchiffrer plus tard » qui motive toute la migration post-quantique du chapitre 14.

L'attaquant actif intervient. Il modifie, rejoue, supprime, injecte, se place entre les correspondants. Un protocole sûr contre le premier peut s'effondrer entièrement devant le second : Diffie-Hellman non authentifié, au chapitre 10, en est l'exemple canonique.

Ces postures se raffinent en modèles d'attaque, qui précisent ce que l'adversaire obtient. Ils ne décrivent pas des attaquants réels ; ils décrivent des contrats. Prouver qu'un schéma résiste dans un modèle, c'est s'engager sur ce que l'adversaire peut faire, et sur rien d'autre.

Le sens de la progression est qu'un modèle plus fort n'est pas une paranoïa d'universitaire. CPA est le minimum dès que l'attaquant peut provoquer un chiffrement — c'est-à-dire dès qu'il y a un navigateur en face. CCA2 est le minimum dès qu'un serveur déchiffre ce qu'on lui envoie et se comporte différemment selon le résultat, ne serait-ce qu'en renvoyant un message d'erreur ou en répondant plus lentement. Les deux attaques les plus célèbres de la cryptographie appliquée — Bleichenbacher sur PKCS#1 en 1998, Vaudenay sur le padding CBC en 2002 — sont exactement cela : des attaques CCA contre des systèmes qu'on croyait déployés en sécurité.

Sécurité inconditionnelle et sécurité calculatoire

Deux ambitions très différentes coexistent sous le mot « sûr ».

La sécurité inconditionnelle ne suppose rien de l'adversaire : ni son temps, ni sa puissance, ni ses algorithmes. Le chiffré ne contient tout simplement pas l'information cherchée. Le masque jetable en est le seul exemple usuel, et le chapitre 3 montrera que cette perfection se paie d'une clé aussi longue que le message — ce qui la rend inutilisable dans presque tous les cas.

La sécurité calculatoire suppose l'adversaire limité, et c'est sur elle que repose la totalité de la cryptographie déployée. L'énoncé prend la forme : tout adversaire s'exécutant en temps polynomial probabiliste ne réussit qu'avec une probabilité négligeable. Trois termes techniques s'y cachent.

Un algorithme est PPT (probabiliste, polynomial) si son temps d'exécution est borné par un polynôme en le paramètre de sécurité $n$ et s'il peut tirer à pile ou face. Le probabilisme n'est pas un détail : un chiffrement déterministe ne peut pas être sûr contre CPA, et vous allez le vérifier vous-même dans un instant.

Une fonction $\varepsilon(n)$ est négligeable si elle décroît plus vite que l'inverse de tout polynôme : pour tout $c$, il existe $N$ tel que $\varepsilon(n) < n^{-c}$ pour $n > N$. En pratique, $2^{-128}$.

L'avantage d'un adversaire est l'écart entre son taux de succès et celui du hasard. Deviner un bit avec probabilité $1/2$ n'est pas une attaque ; le faire avec probabilité $1/2 + \varepsilon$ pour $\varepsilon$ non négligeable en est une.

On parle de « sécurité 128 bits » lorsque la meilleure attaque connue demande de l'ordre de $2^{128}$ opérations. L'ordre de grandeur mérite d'être posé une fois pour toutes : à $10^{12}$ essais par seconde et par machine, avec un milliard de machines, $2^{128}$ essais demandent environ $10^{7}$ fois l'âge de l'univers. Ce n'est pas « très difficile », c'est d'une autre nature. Toute la question est de savoir si la meilleure attaque connue est bien la meilleure attaque.

Ce que « cassé » veut dire

Le vocabulaire académique est plus exigeant que l'intuition. Un schéma est cassé dès qu'existe un algorithme qui fait mieux que l'attaque générique, même si cet algorithme reste hors de portée. La meilleure attaque publiée sur AES-128 demande environ $2^{126{,}1}$ opérations : c'est une cassure au sens théorique — elle bat la recherche exhaustive — et elle n'a strictement aucune conséquence pratique.

Cette exigence n'est pas un excès de rigueur. Les attaques ne s'améliorent jamais dans le sens de la difficulté : la première brèche sur MD5 était théorique en 1996, les collisions sont devenues pratiques en 2004, et un faux certificat a été forgé en 2008. Un affaiblissement théorique est un préavis, et la seule question raisonnable est de savoir combien de temps il laisse.

Symétriquement, un schéma prouvé sûr ne l'est que dans un modèle, sous une hypothèse, et pour les capacités que ce modèle accorde à l'adversaire. Aucune preuve du chapitre 12 ne protège contre une clé lue dans la mémoire, un générateur aléatoire défaillant ou un temps d'exécution qui dépend du secret. La cryptographie déployée casse presque toujours par là.

À vous

Le meilleur moyen de comprendre un modèle de sécurité est de tenir le rôle de l'adversaire. Le jeu ci-dessous est celui d'IND-CPA, réduit à son squelette : vous choisissez deux messages, le défieur en chiffre un au hasard en mode ECB, et vous devez dire lequel.

Vous ne chercherez aucune clé. Une attaque, dans ce cadre, c'est une question bien posée.

// Le jeu IND-CPA, en miniature.
//
// Le défieur choisit une clé et un bit secret b. Vous lui soumettez DEUX
// messages ; il chiffre celui d'indice b et vous rend le chiffré. Vous gagnez
// si vous devinez b mieux qu'à pile ou face.
//
// Le chiffrement ci-dessous est un mode ECB : chaque bloc de 4 caractères est
// chiffré indépendamment, avec la même clé.

const BLOC = 4;

// Une permutation jouet : le vrai AES ne changerait rien à l'attaque.
function chiffrerBloc(bloc, cle) {
  let sortie = "";
  for (let i = 0; i < bloc.length; i++) {
    sortie += String.fromCharCode(((bloc.charCodeAt(i) + cle * (i + 7)) % 26) + 97);
  }
  return sortie;
}

function ecb(message, cle) {
  let sortie = "";
  for (let i = 0; i < message.length; i += BLOC) {
    sortie += chiffrerBloc(message.slice(i, i + BLOC), cle);
  }
  return sortie;
}

// ── Le défieur ────────────────────────────────────────────────────────────
function defieur(m0, m1) {
  const cle = 1 + Math.floor(Math.random() * 25);
  const b = Math.random() < 0.5 ? 0 : 1;
  return { chiffre: ecb(b === 0 ? m0 : m1, cle), b };
}

// ── À VOUS ────────────────────────────────────────────────────────────────
// 1. Choisissez deux messages de MÊME longueur (8 caractères, soit 2 blocs).
//    Un seul des deux doit produire deux blocs chiffrés identiques.
// 2. Écrivez le distingueur : il ne voit que le chiffré et doit rendre 0 ou 1.

const m0 = "aaaabbbb"; // à modifier
const m1 = "aaaabbbb"; // à modifier

function distinguer(chiffre) {
  const bloc1 = chiffre.slice(0, BLOC);
  const bloc2 = chiffre.slice(BLOC, 2 * BLOC);
  return 0; // à compléter
}

// ── Mesure ────────────────────────────────────────────────────────────────
let succes = 0;
for (let essai = 0; essai < 10000; essai++) {
  const { chiffre, b } = defieur(m0, m1);
  if (distinguer(chiffre) === b) succes++;
}
console.log("taux de succès :", (succes / 100).toFixed(1) + " %");
console.log("le hasard donnerait 50 %. Au-dessus de 51 %, ECB est distingué.");

// Le message m0 répète le même bloc : en ECB, deux blocs identiques en clair
// donnent deux blocs identiques en chiffré. Le message m1 ne le fait pas.
const m0 = "aaaaaaaa"; // deux fois le bloc "aaaa"
const m1 = "aaaabbbb"; // deux blocs différents

function distinguer(chiffre) {
  const bloc1 = chiffre.slice(0, BLOC);
  const bloc2 = chiffre.slice(BLOC, 2 * BLOC);
  // Blocs chiffrés égaux ⇒ c'est m0 qui a été chiffré ⇒ b = 0.
  return bloc1 === bloc2 ? 0 : 1;
}

// Taux de succès : 100 %. Pas 51 %, pas 60 % — l'attaque est déterministe.
// Aucune clé n'a été retrouvée, et pourtant le schéma est cassé au sens
// IND-CPA : l'adversaire apprend quelque chose du clair, ce qui est
// exactement ce que la définition interdit.

Ce que la suite en fait

Le vocabulaire posé ici sert de grille de lecture à tout le cours. Chaque construction sera présentée avec le modèle dans lequel elle tient : AEAD au chapitre 8 vise la sécurité CCA pour le chiffrement symétrique, OAEP au chapitre 9 vise IND-CCA2 pour RSA, et le chapitre 12 donnera enfin la forme exacte de ces énoncés et la mécanique des réductions qui les démontrent.

Avant cela, le chapitre 2 installe les outils mathématiques dont tous ces schémas dépendent — sans quoi RSA reste une formule et le logarithme discret un mot.

À retenir

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.