RSA : ce que la procédure laisse dans l'ombre

On peut fort bien savoir exécuter RSA — générer les clés, chiffrer, déchiffrer — sans en avoir jamais saisi les ressorts. La présentation procédurale, celle que j’ai résumée dans la note principale, a ce défaut : elle enchaîne des gestes corrects sans toujours dire pourquoi ils le sont. Je consigne ici les intuitions que cette mécanique passe sous silence, parce que ce sont elles, et non la recette, qui font comprendre où loge réellement la sécurité.

Pourquoi RSA fonctionne vraiment

L’identité $m^{ed}\equiv m(\mathrm{mod}n)$ n’a rien d’une formule magique ; elle se démontre en deux temps. Lorsque $\gcd (m,n)=1$, le théorème d’Euler donne $m^{\phi (n)}\equiv 1(\mathrm{mod}n)$. Or l’exposant privé a été construit de sorte que $ed\equiv 1(\mathrm{mod}\phi (n))$, c’est-à-dire $ed=1+k\phi (n)$. On a donc

$m^{ed}=m^{1+k\phi (n)}=m\cdot (m^{\phi (n)}{)}^k\equiv m(\mathrm{mod}n).$

Quand $\gcd (m,n)\ne 1$ — cas marginal mais qui doit être traité —, l’égalité reste vraie, cette fois par le théorème des restes chinois appliqué séparément modulo $p$ et modulo $q$. La correction de RSA n’est donc pas un postulat : elle découle de la construction de $d$.

Ce que $\phi (n)$ dissimule

Dans la procédure, $\phi (n)=(p-1)(q-1)$ n’apparaît que comme une quantité à calculer. C’est en réalité la pièce maîtresse. Le point décisif, presque jamais énoncé, est celui-ci :

Calculer $d$ sans connaître $\phi (n)$ est équivalent à factoriser $n$.

Toute la sécurité de RSA tient dans cette équivalence. Connaître $\phi (n)$, c’est connaître $p$ et $q$ ; et retrouver $d$ suppose de connaître $\phi (n)$. La difficulté de la factorisation n’est donc pas une propriété adjacente au système — elle en est le fondement. Sans ce lien, RSA semble reposer sur rien.

De même, la condition $\gcd (e,\phi (n))=1$ n’a rien d’arbitraire : c’est une condition d’existence. Si $e$ et $\phi (n)$ n’étaient pas premiers entre eux, l’inverse modulaire $d$ n’existerait tout simplement pas, et le déchiffrement serait mathématiquement impossible.

Pourquoi le calcul reste faisable

L’exponentiation modulaire rapide n’apporte pas qu’un gain de vitesse : elle rend le calcul possible. Le gain vient de deux faits conjoints. D’une part, la complexité est logarithmique en l’exposant — on n’effectue jamais $e$ multiplications, mais de l’ordre de ${\log }_{2}e$. D’autre part, et surtout, on ne quitte jamais l’arithmétique modulo $n$ : chaque multiplication est immédiatement réduite, si bien que l’on ne manipule jamais des entiers de taille $m^e$, mais toujours des nombres bornés par $n$. C’est cette réduction systématique qui empêche l’explosion combinatoire.

Pourquoi RSA brut est dangereux

Dire qu’il faut un bourrage sans en donner la raison, c’est demander un acte de foi. Les raisons sont pourtant précises. RSA « nu » est déterministe — un même clair produit toujours le même chiffré, ce qui autorise à deviner un message parmi un petit ensemble de candidats en les chiffrant tous. Il est surtout malléable, du fait de sa structure multiplicative :

$\mathrm{Enc}(m_1)\cdot \mathrm{Enc}(m_2)\equiv \mathrm{Enc}(m_1{m}_2)(\mathrm{mod}n).$

De cette seule propriété découlent les attaques algébriques, les attaques à texte choisi, et la falsification de signatures non hachées. Le bourrage n’est donc pas une précaution cosmétique : il brise précisément le déterminisme et la malléabilité qui rendent le système attaquable.

Ce que la signature emprunte aux mêmes fragilités

La règle « Hash-and-Sign » se comprend enfin à cette lumière. Signer $m$ directement, c’est en calculer une exponentiation modulaire — donc s’exposer aux mêmes attaques algébriques que le chiffrement brut. Passer par une empreinte de taille fixe casse la structure multiplicative et retire à l’adversaire la prise qu’elle lui offrait. La malléabilité de RSA et la nécessité du hachage ne sont ainsi que les deux faces d’un même fait.

La non-répudiation, rendue concrète

La distinction entre MAC et signature reste creuse tant qu’on ne la rapporte pas à une scène concrète. Avec un MAC, la clé étant partagée, le vérificateur peut lui-même forger un code valide : aucune preuve n’est donc opposable à un tiers, puisque rien ne distingue ce qu’a produit l’émetteur de ce qu’aurait pu produire le récepteur. Avec une signature, seul le détenteur de la clé privée a pu produire $\sigma$ ; la preuve tient devant quiconque. La non-répudiation n’est rien d’autre que cette dissymétrie de production.

La PKI, un mal nécessaire

On présente souvent la PKI comme une pure affaire d’administration. C’est manquer sa nécessité cryptographique. Le fait brut à retenir tient en une phrase :

Une clé publique non authentifiée ne vaut rien.

Sans certificat, rien ne relie une clé à une identité, et l’attaque de l’homme du milieu n’est pas un risque contingent mais une possibilité structurelle : l’adversaire n’a qu’à substituer sa propre clé. La PKI vient combler ce que la cryptographie seule ne peut garantir — le lien entre une clé et un nom.

Reste que cette réponse a un coût. La confiance y est transitive et donc centralisée : compromettre une AC racine, c’est compromettre tout ce qu’elle a signé, ce qui concentre une surface d’attaque considérable en quelques points. Le séquestre de clés, enfin, mérite qu’on s’en méfie : une clé privée séquestrée n’est plus vraiment privée, ce qui ruine la non-répudiation et crée un point unique de compromission. La PKI n’a rien de « naturel » — c’est un compromis fragile que l’on adopte faute de mieux.