Onze chapitres durant, « sûr » a été employé au fil de l'eau — IND-CPA au chapitre 4, EUF-CMA au chapitre 8, IND-CCA2 pour OAEP au chapitre 9. Il est temps de donner à ces sigles leur sens exact. C'est l'objet de la sécurité prouvée : définir précisément ce qu'on démontre, et par quel mécanisme — la réduction — on le rattache à un problème réputé difficile.

Ce chapitre arrive délibérément après les constructions asymétriques. Une réduction reste un exercice formel creux tant qu'on n'a pas RSA et ElGamal en tête comme objets concrets à réduire. Placé au début d'un cours, ce chapitre fait fuir ; placé ici, il range enfin ce qu'on a déjà manipulé.

Prouver, mais prouver quoi ?

La cryptographie ne prouve presque jamais qu'un schéma est sûr dans l'absolu — une telle preuve impliquerait $P \neq NP$, hors de portée. Elle prouve des énoncés conditionnels : si tel problème est difficile, alors tel schéma est sûr. Toute la valeur est dans la qualité de l'implication et dans la solidité de l'hypothèse.

Trois ingrédients composent un énoncé de sécurité, et il faut les nommer séparément :

• Un objectif — que veut-on empêcher l'adversaire d'obtenir ? (distinguer deux chiffrés, forger une signature.)
• Un modèle d'attaque — de quels moyens l'adversaire dispose-t-il ? (les modèles COA à CCA2 du chapitre 1.)
• Une hypothèse — quel problème suppose-t-on difficile ? (factorisation, logarithme discret, DDH.)

Un schéma n'est jamais « sûr » tout court : il est sûr pour tel objectif, dans tel modèle, sous telle hypothèse.

Les jeux de sécurité

On formalise l'objectif comme un jeu entre un défieur et un adversaire. La sécurité est l'affirmation que l'avantage de l'adversaire — l'écart entre son taux de succès et celui du pur hasard — reste négligeable pour tout adversaire polynomial (le vocabulaire du chapitre 1).

IND-CPA (indistinguabilité sous clairs choisis). L'adversaire soumet deux messages $m_0, m_1$ de même longueur. Le défieur tire un bit $b$, chiffre $m_b$, rend le chiffré. L'adversaire annonce $b'$. Son avantage est $|\Pr[b' = b] - 1/2|$. Que gagner ce jeu soit infaisable est la définition du secret : le chiffré ne dit rien du clair. On retrouve pourquoi un chiffrement déterministe échoue (chapitre 1) — l'adversaire y soumet deux fois le même message et distingue.

IND-CCA2 (sous chiffrés choisis, adaptatif). Même jeu, mais l'adversaire dispose en plus d'un oracle de déchiffrement qu'il peut interroger avant et après avoir reçu le défi — sur tout chiffré sauf le défi lui-même. C'est le modèle le plus fort, et le bon défaut dès qu'un serveur déchiffre : l'oracle de padding du chapitre 4 était précisément une attaque CCA. OAEP vise ce niveau ; le chiffrement authentifié du chapitre 8 l'atteint.

EUF-CMA (inforgeabilité existentielle sous messages choisis). Le jeu des signatures. L'adversaire obtient les signatures de messages de son choix, et gagne s'il produit une signature valide pour un message nouveau. C'est ce que garantissent RSA-PSS (chapitre 9) et ECDSA (chapitre 11).

La réduction, mécanique centrale

Comment démontre-t-on qu'un schéma gagne un jeu ? Par réduction — l'outil que le chapitre 2 a esquissé avec les classes de complexité, ici mis au travail.

On raisonne par contraposée. On suppose qu'existe un adversaire $\mathcal{A}$ qui gagne le jeu, et l'on construit avec lui un algorithme $\mathcal{B}$ qui résout le problème réputé difficile. Comme ce dernier est infaisable, un tel $\mathcal{A}$ ne peut exister. La forme est toujours la même :

C'est l'exact analogue des réductions de complexité — on ramène la sécurité d'un objet compliqué à la difficulté d'un problème simple et étudié. On l'a déjà croisée sans la nommer : Merkle-Damgård (chapitre 7) réduit la résistance du haché à celle de sa compression ; la sécurité de RSA (chapitre 9) se raccroche à la factorisation.

Rien ne vaut de l'exécuter une fois. L'exercice transforme un adversaire IND-CPA contre un chiffrement à flot en un distingueur du générateur pseudo-aléatoire sous-jacent, et mesure l'avantage qui se transfère de l'un à l'autre.

// Chiffrement : c = m ⊕ PRG(clé, nonce). S'il existe un adversaire A qui gagne
// le jeu IND-CPA, on FABRIQUE avec lui un distingueur du PRG. Donc : PRG sûr ⇒
// chiffrement IND-CPA. On code la réduction et on la mesure.

// Une suite FRAÎCHE à chaque appel (nouveau nonce). Deux mondes :
//   pseudo = true  : pseudo-aléatoire, avec une FAILLE volontaire — le bit de
//                    poids faible du premier octet est toujours 0 ;
//   pseudo = false : vraiment aléatoire, aucune structure à exploiter.
let compteurNonce = 1;
function suiteFraiche(pseudo, longueur) {
  if (!pseudo) {
    return Array.from({ length: longueur }, () => (Math.random() * 256) | 0);
  }
  let x = (compteurNonce++ * 2654435761) >>> 0 || 1;
  const out = [];
  for (let i = 0; i < longueur; i++) {
    x ^= x << 13; x >>>= 0; x ^= x >> 17; x ^= x << 5; x >>>= 0;
    out.push(i === 0 ? (x & 0xfe) : (x & 0xff)); // biais sur l'octet 0
  }
  return out;
}
const xor = (a, b) => a.map((v, i) => v ^ b[i]);

// ── L'adversaire IND-CPA ──────────────────────────────────────────────────
// Il soumet m0 et m1 (de bits 0 différents sur l'octet 0), reçoit le chiffré de
// l'un, et devine lequel en exploitant le biais : l'octet 0 de la suite ayant
// son bit 0 à 0, l'octet 0 du clair a le même bit 0 que celui du chiffré.
function adversaire(chiffre, m0) {
  const bit0Clair = chiffre[0] & 1;
  return bit0Clair === (m0[0] & 1) ? 0 : 1;
}

// ── À COMPLÉTER : la réduction ────────────────────────────────────────────
// Le distingueur joue le jeu IND-CPA en masquant avec le PRG testé, sur de
// NOMBREUX défis indépendants (un masque frais par défi). Si l'adversaire gagne
// bien plus qu'une fois sur deux, le PRG était pseudo-aléatoire : le biais l'a
// trahi. Sinon, il était vrai aléa.
function tauxDeSucces(pseudo) {
  const m0 = [0, 0, 0, 0]; // bit 0 de l'octet 0 = 0
  const m1 = [1, 0, 0, 0]; // bit 0 de l'octet 0 = 1
  let succes = 0, tours = 2000;
  for (let t = 0; t < tours; t++) {
    const b = Math.random() < 0.5 ? 0 : 1;
    const s = suiteFraiche(pseudo, 4); // masque FRAIS à chaque défi
    // à compléter : chiffrer m_b avec s, interroger l'adversaire, compter succès
  }
  return succes / tours;
}

// ── Mesure : la réduction sépare-t-elle les deux mondes ? ──────────────────
const tauxPseudo = tauxDeSucces(true);
const tauxVrai = tauxDeSucces(false);
console.log("succès de l'adversaire, PRG PSEUDO-aléatoire :", (tauxPseudo * 100).toFixed(0) + " %");
console.log("succès de l'adversaire, vrai aléa         :", (tauxVrai * 100).toFixed(0) + " %");
console.log("avantage transféré au PRG :", ((tauxPseudo - tauxVrai) * 100).toFixed(0), "points");

function tauxDeSucces(pseudo) {
  const m0 = [0, 0, 0, 0];
  const m1 = [1, 0, 0, 0];
  let succes = 0, tours = 2000;
  for (let t = 0; t < tours; t++) {
    const b = Math.random() < 0.5 ? 0 : 1;
    const s = suiteFraiche(pseudo, 4);
    const chiffre = xor(b === 0 ? m0 : m1, s);
    if (adversaire(chiffre, m0) === b) succes++;
  }
  return succes / tours;
}

// Résultat : ~100 % sous le PRG pseudo-aléatoire (le biais de l'octet 0 laisse
// tout passer), ~50 % sous le vrai aléa (rien à exploiter). L'écart d'environ
// 50 points EST l'avantage que la réduction transfère du chiffrement au PRG.
//
// C'est cela, une RÉDUCTION. On ne prouve pas directement que le chiffrement
// est sûr : on établit une IMPLICATION. « Si un adversaire gagne le jeu
// IND-CPA avec un avantage ε, alors on distingue le PRG avec un avantage ε. »
// Par contraposée : PRG indistinguable ⇒ chiffrement IND-CPA. La sécurité du
// schéma est RÉDUITE à celle d'une brique — même mouvement que Merkle-Damgård
// ramenant la résistance du haché à celle de sa compression (chapitre 7).
//
// Le jeu IND-CPA : le défieur tire b, chiffre m_b, l'adversaire rend b' ;
// l'avantage est |Pr[b' = b] − 1/2|, qui doit être négligeable pour tout
// adversaire polynomial (chapitre 1). IND-CCA2 ajoute un oracle de
// déchiffrement même après le défi ; EUF-CMA est le jeu des signatures. Une
// même mécanique partout : un jeu, un avantage, une réduction.

La qualité d'une réduction se mesure. Une réduction est serrée (tight) si $\mathcal{B}$ réussit avec à peu près le même avantage et le même temps que $\mathcal{A}$. Elle est lâche si $\mathcal{B}$ perd un facteur — disons le nombre de requêtes de l'adversaire. Ce n'est pas un détail théorique : une réduction lâche oblige à augmenter la taille des clés pour compenser la perte, avec un coût de performance bien réel. La finesse de la preuve a un prix en octets.

Le modèle de l'oracle aléatoire, et sa controverse

Beaucoup de schémas efficaces — OAEP, PSS, la plupart des signatures — ne se prouvent que dans le modèle de l'oracle aléatoire (ROM). On y fait une idéalisation : la fonction de hachage est traitée comme une fonction parfaitement aléatoire, une boîte noire que tout le monde interroge et qui répond de façon uniforme et cohérente.

Cette idéalisation rend les preuves possibles, et donne à la réduction un pouvoir supplémentaire : elle peut « programmer » l'oracle, choisir ses réponses pour piéger l'adversaire. C'est puissant, et c'est précisément là qu'est la critique.

Car aucune fonction réelle — ni SHA-256, ni SHA-3 — n'est un oracle aléatoire : ce sont des algorithmes publics, déterministes, courts à décrire. Canetti, Goldreich et Halevi ont même construit, en 1998, des schémas prouvés sûrs dans le ROM et cassés dès qu'on remplace l'oracle par n'importe quelle fonction réelle. La preuve ROM n'est donc pas une garantie au sens strict ; c'est une heuristique — un argument de bonne conception, un filtre qui élimine les schémas manifestement faibles, sans certifier les survivants.

La position raisonnable, et celle qu'adopte la pratique : une preuve dans le modèle standard (sans oracle idéalisé) est préférable ; une preuve ROM vaut mieux qu'aucune preuve ; et aucune de l'une ni de l'autre ne protège contre ce qu'aucun modèle ne capture — un canal auxiliaire, un générateur aléatoire défaillant, une clé lue en mémoire. Les preuves cadrent la primitive ; elles ne couvrent pas l'implémentation, qui est le sujet du chapitre 13.

Ce que la suite en fait

Ce chapitre a donné aux mots leur sens exact. Le chapitre 13 quitte les primitives isolées pour les protocoles : TLS 1.3, où un échange de clés authentifié doit atteindre des objectifs de sécurité composés, et où l'on verra que prouver un protocole entier est bien plus dur que prouver une brique. Il montrera aussi combien les hypothèses de ce chapitre sont fragiles face à la réalité — un générateur pseudo-aléatoire biaisé fait s'effondrer des schémas parfaitement prouvés.

À retenir

Les douze chapitres précédents ont forgé des primitives : chiffrements, MAC, signatures, échanges de clés. Un protocole réel les assemble — et c'est un art distinct, car un montage de briques parfaites peut fuir par ses jointures. Ce chapitre montre comment on établit une communication sûre entre deux inconnus, prend TLS 1.3 comme cas d'étude, et finit sur le maillon qu'aucune preuve ne protège : l'aléa.

Échange de clés authentifié

Le chapitre 10 l'a établi sans détour : Diffie-Hellman brut tombe devant l'homme du milieu. Mallory établit un secret avec chacun et relaie en clair. Le problème n'est pas le secret — il est bien calculé — mais l'identité : rien ne dit à Alice que $g^b$ vient de Bob.

La réponse est l'échange de clés authentifié. On lie l'échange à une identité vérifiable en signant les messages du protocole avec une clé de long terme, elle-même attestée par un certificat. Alice ne se contente plus de recevoir $g^b$ : elle reçoit $g^b$ signé par une clé dont un certificat garantit qu'elle est celle de Bob. Mallory, incapable de produire cette signature, ne peut plus s'intercaler.

Une propriété qu'on exige en plus, et qui a un nom : la confidentialité persistante (forward secrecy). Les clés de session sont dérivées d'un Diffie-Hellman éphémère — un $g^a, g^b$ neuf à chaque session, jeté ensuite. Conséquence : si la clé privée de long terme de Bob est compromise demain, les sessions d'hier restent illisibles, car leur secret éphémère n'existe plus nulle part. C'est le « récolter maintenant, déchiffrer plus tard » du chapitre 1 rendu inopérant — du moins tant que Diffie-Hellman tient, ce que le chapitre 14 viendra nuancer.

TLS 1.3, l'assemblage de tout le cours

TLS protège l'essentiel du trafic web, et sa version 1.3 (2018) est une refonte disciplinée par vingt ans d'attaques. Elle est le point de convergence du cours entier.

Sa poignée de main (handshake) établit une session en un seul aller-retour : ECDH éphémère (chapitre 11) pour le secret, signature (chapitre 9 ou 11) attestée par certificat pour l'authentification, HKDF (chapitre 8) pour dériver les clés de session, et AEAD (chapitre 8) pour chiffrer et authentifier les données. Chaque brique de ce cours y a sa place exacte.

Ce que TLS 1.3 a retiré est aussi instructif que ce qu'il garde, car chaque suppression est une attaque refermée. Exit RSA pour le transport de clé — il n'offrait pas la forward secrecy et traînait l'attaque de Bleichenbacher (chapitre 1) depuis 1998. Exit CBC et ses oracles de padding (chapitre 4). Exit les suites cryptographiques négociables à l'ancienne, dont la négociation elle-même se faisait attaquer (dégradation forcée vers un chiffre faible). TLS 1.3 impose forward secrecy et AEAD, sans option de s'en passer. La leçon de conception : réduire la surface, ne laisser aucun choix dangereux ouvert. C'est l'exact pendant de Curve25519 (chapitre 11), sûre par défaut.

PKI et certificats X.509

Reste la question qui fonde tout : comment Alice sait-elle que telle clé publique est vraiment celle de Bob ? Par un certificat — la clé publique de Bob, son identité, et une signature d'une autorité de certification (AC) qui atteste le lien. Alice fait confiance à l'AC (sa clé est préinstallée dans le navigateur), donc à ce qu'elle signe. C'est l'infrastructure à clé publique (PKI), et le format des certificats est X.509.

La confiance se délègue en chaîne : une AC racine signe des AC intermédiaires, qui signent les certificats des sites. Le navigateur remonte la chaîne jusqu'à une racine qu'il connaît. Ce système marche à l'échelle du web — mais sa sécurité est celle de son maillon le plus faible, et le maillon est humain autant que mathématique. Une AC compromise signe de faux certificats pour n'importe qui : c'est arrivé avec DigiNotar en 2011, dont les faux certificats Google ont servi à espionner des dizaines de milliers d'Iraniens. La réponse a été la transparence des certificats (Certificate Transparency) — des journaux publics et inaltérables où tout certificat émis est inscrit, rendant une émission frauduleuse détectable.

Le maillon qu'aucune preuve ne couvre : l'aléa

Toute la cryptographie de ce cours suppose de l'aléa de qualité : les nonces, les clés éphémères, les premiers de RSA, le $k$ de DSA. Un générateur défaillant anéantit des schémas parfaitement prouvés — c'est le rappel brutal du chapitre 12 sur ce que les preuves ne couvrent pas.

Les défaillances sont de deux ordres. Il y a les accidents : le bug OpenSSL de Debian (2006-2008) qui réduisait l'espace des clés à 32 768 valeurs, ou les objets connectés qui engendrent leurs clés à froid, sans entropie. Et il y a le sabotage : Dual_EC_DRBG, un générateur normalisé par le NIST dont les constantes, on l'a appris avec Snowden, portaient une porte dérobée permettant à qui connaissait le secret de prédire toute la sortie. C'est ce soupçon, bien réel cette fois, qui a nourri la défiance envers les courbes NIST du chapitre 11.

La conséquence la plus tangible tient en un pgcd. Quand un parc d'appareils produit des clés RSA à faible entropie, certaines partagent un facteur premier — et le pgcd de deux modules publics les factorise toutes les deux d'un coup, sans jamais résoudre la factorisation. Montez-le.

// On collecte des clés publiques RSA (juste les modules n). Sur un parc
// d'objets à faible entropie — routeurs, cartes à puce démarrant à froid — le
// générateur produit parfois le MÊME premier dans deux clés distinctes.

function pgcd(a, b) {
  while (b > 0n) { [a, b] = [b, a % b]; }
  return a;
}

// Six premiers. Volontairement, deux modules vont partager p3.
const p1 = 10007n, p2 = 10009n, p3 = 10037n, p4 = 10039n, p5 = 10061n;

// Trois modules publics, tels qu'un scanner d'Internet les récolterait.
const modules = [
  { nom: "clé A", n: p1 * p2 },
  { nom: "clé B", n: p3 * p4 },
  { nom: "clé C", n: p5 * p3 }, // partage p3 avec la clé B — la faille
];

// ── À COMPLÉTER ───────────────────────────────────────────────────────────
// Pour chaque PAIRE de modules, calculer pgcd(n_i, n_j). S'il vaut plus que 1,
// c'est un facteur premier COMMUN : les deux clés sont factorisées d'un coup,
// sans jamais résoudre le problème de la factorisation.

function casserLeParc(modules) {
  const casses = [];
  for (let i = 0; i < modules.length; i++) {
    for (let j = i + 1; j < modules.length; j++) {
      // à compléter : g = pgcd des deux modules ; si g > 1, on tient un facteur
    }
  }
  return casses;
}

const resultats = casserLeParc(modules);
console.log("clés factorisées :", resultats.length ? resultats : "aucune");

function casserLeParc(modules) {
  const casses = [];
  for (let i = 0; i < modules.length; i++) {
    for (let j = i + 1; j < modules.length; j++) {
      const g = pgcd(modules[i].n, modules[j].n);
      if (g > 1n) {
        // g est un facteur commun : chaque module se scinde en g et n/g.
        casses.push({
          paire: [modules[i].nom, modules[j].nom],
          facteurCommun: g.toString(),
          [modules[i].nom]: [g.toString(), (modules[i].n / g).toString()],
          [modules[j].nom]: [g.toString(), (modules[j].n / g).toString()],
        });
      }
    }
  }
  return casses;
}

// Les clés B et C tombent : leur pgcd révèle p3 = 10037, et chacun des deux
// modules se scinde aussitôt. On n'a JAMAIS factorisé un module isolé — la
// difficulté du chapitre 9 est intacte. On a exploité une CORRÉLATION entre
// clés, née d'un générateur d'aléa défaillant.
//
// Ce n'est pas un exercice d'école. En 2012, l'étude « Mining Your Ps and Qs »
// a passé au pgcd des millions de clés RSA récoltées sur Internet et en a
// factorisé des dizaines de milliers — des équipements générant leurs clés au
// tout premier démarrage, avant d'avoir accumulé la moindre entropie. Le pgcd
// de deux nombres de 2048 bits est instantané ; le coût total est celui du
// balayage des paires.
//
// La leçon rejoint le chapitre 12 : une clé RSA parfaitement conforme, avec
// OAEP et PSS impeccables, est anéantie par un générateur pseudo-aléatoire
// défaillant. Aucune preuve de sécurité ne couvre l'aléa d'où sort la clé —
// c'est le maillon du chapitre, et l'un des plus fragiles.

Ce que la suite en fait

Ce chapitre a montré que la sécurité d'un système réel dépasse la solidité de ses primitives : elle tient à leur assemblage, à la gestion des identités, et à la qualité de l'aléa. Le chapitre 14, dernier du cours, change d'horizon temporel. Toute la clé publique déployée ici — RSA, ECDH, ECDSA, la PKI qui les atteste — repose sur des problèmes que l'algorithme de Shor résout en temps polynomial sur un ordinateur quantique. La forward secrecy elle-même n'y résiste pas contre un adversaire qui a enregistré le trafic. Il faut donc migrer, et l'agilité cryptographique que TLS 1.3 a commencé à outiller devient la compétence centrale.

À retenir

QCM de synthèse — Bloc IV — Protocoles et pratique

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.