RSA

Jusqu'ici, chiffrer supposait une clé déjà partagée. Comment deux personnes qui ne se sont jamais rencontrées en établissent-elles une sur un canal public ? La réponse — la cryptographie à clé publique — est l'une des grandes ruptures du XXe siècle, et RSA en est le premier exemple complet, publié en 1977 par Rivest, Shamir et Adleman.

L'idée est asymétrique : une clé publique pour chiffrer ou vérifier, que le monde entier peut connaître, et une clé privée pour déchiffrer ou signer, gardée secrète. Ce chapitre construit RSA, puis — fidèle au fil du cours — le casse partout où il est mal employé.

La construction

Elle repose entièrement sur l'arithmétique du chapitre 2.

1. Choisir deux grands premiers $p$ et $q$, et poser $n = pq$. Le module $n$ est public, mais $p$ et $q$ restent secrets.
2. Calculer $\varphi(n) = (p-1)(q-1)$.
3. Choisir un exposant public $e$ premier avec $\varphi(n)$ — en pratique $e = 65537$.
4. Calculer l'exposant privé $d = e^{-1} \bmod \varphi(n)$, par Euclide étendu.

La clé publique est $(n, e)$, la clé privée est $d$. Chiffrement et déchiffrement :

Le déchiffrement redonne le message parce que $ed \equiv 1 \pmod{\varphi(n)}$, donc $m^{ed} \equiv m \pmod n$ par le théorème d'Euler. La signature inverse simplement les rôles : on signe avec $d$, on vérifie avec $e$.

Sur quoi repose vraiment la sécurité

L'attaquant connaît $n$ et $e$. S'il savait factoriser $n$, il obtiendrait $p$ et $q$, donc $\varphi(n)$, donc $d$ : RSA serait mort. Sa sécurité repose donc sur la difficulté de la factorisation, un problème sous-exponentiel (chapitre 2) mais sans algorithme efficace connu sur machine classique.

Une nuance que les étudiants confondent souvent. Casser RSA — retrouver $m$ à partir de $c$ — n'est pas prouvé équivalent à factoriser : il pourrait exister un raccourci qui contourne la factorisation. On n'en connaît pas, mais l'équivalence n'est pas démontrée. C'est une hypothèse de plus, distincte de la difficulté de factoriser, et le chapitre 12 y reviendra en parlant de l'hypothèse RSA.

Les tailles se déduisent des records de factorisation : RSA-1024 est déconseillé, RSA-2048 est le minimum courant, RSA-3072 vise 128 bits de sécurité. À comparer aux 256 bits des courbes elliptiques du chapitre 11 pour la même sécurité — l'écart qui explique leur adoption.

RSA « textbook » est cassé, et vous allez le casser

Le RSA nu — $c = m^e \bmod n$, sans rembourrage — est un désastre pratique, pour deux raisons qui reprennent tout le chapitre 1. Il est déterministe : le même clair donne le même chiffré, donc un adversaire distingue et devine par dictionnaire. Et il est malléable : $(m_1 m_2)^e = m_1^e \, m_2^e$, l'attaquant transforme le chiffré d'un message en celui d'un multiple sans le déchiffrer.

Le cas le plus spectaculaire combine un petit exposant et un message court. Si $e = 3$ et si $m^3 < n$, la réduction modulo $n$ ne s'applique pas : le chiffré est le cube exact du message, et une simple racine cubique entière le rend — sans clé privée, sans factorisation. Montez-la.

// RSA jouet en BigInt. Le module est grand (RSA-ish), mais le message est
// COURT et le chiffrement n'a AUCUN rembourrage. C'est l'erreur.

// Deux premiers (petits pour l'exemple, la faille est indépendante de la taille).
const p = 32416190071n;
const q = 32416187671n;
const n = p * q;
const e = 3n;                 // exposant public minimal, très répandu

// Chiffrement TEXTBOOK : c = m^e mod n, sans OAEP, sans rien.
function puissanceMod(base, exp, mod) {
  let r = 1n; base %= mod;
  while (exp > 0n) {
    if (exp & 1n) r = (r * base) % mod;
    base = (base * base) % mod;
    exp >>= 1n;
  }
  return r;
}

const m = 1234567n;           // message court : un code PIN, un identifiant...
const c = puissanceMod(m, e, n);
console.log("chiffré c =", c.toString());

// ── L'observation qui tue ─────────────────────────────────────────────────
// Si m^e < n, la réduction « mod n » ne fait RIEN : c = m^e comme entier.
// Retrouver m ne demande alors ni la clé privée, ni de factoriser n —
// seulement une racine e-ième ENTIÈRE.
console.log("m^3 < n ?", m ** 3n < n);

// ── À COMPLÉTER : racine cubique entière par dichotomie ───────────────────
function racineCubiqueEntiere(x) {
  if (x < 2n) return x;
  let lo = 0n, hi = 1n;
  while (hi ** 3n <= x) hi <<= 1n;   // borne haute
  // à compléter : resserrer [lo, hi] jusqu'à la racine cubique entière
  return lo;
}

const retrouve = racineCubiqueEntiere(c);
console.log("m retrouvé :", retrouve.toString());
console.log("correct ?", retrouve === m, "| sans clé privée, sans factoriser n");

Les bons schémas : OAEP et PSS

La leçon n'est pas « RSA est mauvais » mais « RSA ne s'emploie jamais nu ». Deux rembourrages normalisés le rendent sûr.

OAEP (Optimal Asymmetric Encryption Padding) enrobe le message avant chiffrement d'une structure aléatoire construite sur des fonctions de hachage. Trois effets : le chiffrement devient probabiliste (deux chiffrements du même clair diffèrent), le message occupe toujours tout l'espace modulo $n$ (l'attaque à exposant faible s'effondre), et le résultat est sûr contre les attaques à chiffrés choisis — IND-CCA2, la cible du chapitre 12.

PSS (Probabilistic Signature Scheme) fait l'équivalent pour la signature. On ne signe jamais le message brut : on le hache, on lui adjoint un aléa, et l'on signe cette valeur. La signature devient inforgeable au sens EUF-CMA, avec une preuve dans le modèle de l'oracle aléatoire.

Le fil rouge du chapitre 7 se referme ici : puisqu'on signe le haché du message, une collision sur la fonction de hachage est une signature forgée. C'est concret — un faux certificat X.509 a été fabriqué en 2008 en exploitant une collision MD5, exactement de cette manière. La sécurité d'une signature n'excède jamais la résistance aux collisions du haché qu'elle emploie.

Les attaques qui restent, même bien rembourré

OAEP et PSS ferment les failles mathématiques, mais l'implémentation en ouvre d'autres.

Module commun, exposant faible. Un même message envoyé à trois destinataires d'exposant $e = 3$ (modules distincts) se reconstitue par les restes chinois puis racine cubique — l'attaque de Håstad. Deux clés partageant un facteur premier se factorisent par un simple pgcd de leurs modules ; un balayage de clés publiques réelles en 2012 a ainsi cassé des milliers de clés RSA dont les premiers avaient été mal tirés.

Coppersmith. Sa méthode, fondée sur la réduction de réseaux (le monde du bloc V), trouve les petites racines d'un polynôme modulaire. Elle casse RSA quand une partie du message est connue, ou quand une fraction des bits d'un facteur premier fuit. C'est un pont inattendu entre RSA et les réseaux euclidiens du post-quantique.

Canaux auxiliaires. L'exponentiation modulaire naïve du chapitre 2 n'est pas à temps constant : sa durée, sa consommation électrique, ses accès au cache dépendent des bits de $d$. Une mesure fine les révèle. La parade a un nom, le blinding : on randomise l'entrée avant l'exponentiation pour décorréler la fuite du secret. Et l'attaque par faute du chapitre 2 rôde toujours — d'où la vérification de signature avant publication.

Ce que la suite en fait

RSA a montré qu'une seule fonction à sens unique — la multiplication facile, la factorisation dure — suffit à bâtir chiffrement et signature. Le chapitre 10 rebâtit tout sur un autre problème difficile, le logarithme discret, avec un avantage décisif : il rend naturel l'échange de clés, là où RSA ne fait que transporter un secret choisi par l'un des deux. Le chapitre 11 y ajoutera les courbes elliptiques et leurs clés courtes, et le chapitre 14 rappellera que Shor, sur un ordinateur quantique, factorise et calcule les logarithmes discrets en temps polynomial — abattant RSA et le chapitre 10 d'un même coup.

À retenir