RSA : trappe, padding et usages restreints

RSA (Rivest, Shamir, Adleman, du nom de ses inventeurs, 1977) est la plus ancienne primitive à clé publique encore massivement déployée : certificats, signatures de code, jetons, modules matériels. Elle est aussi la plus exigeante. Le module peut être parfaitement dimensionné et la clé tomber quand même, par un remplissage mal choisi, une génération d’aléa défaillante ou une implémentation trop bavarde. Ce chapitre présente la trappe mathématique, puis tout ce qu’il faut ajouter autour pour qu’elle serve à quelque chose sans servir l’attaquant.

→ Lire l’explication complète de la marmotte

Intuition de la trappe

Une fonction à trappe est facile à calculer, difficile à inverser, sauf pour qui détient une information secrète, la trappe. RSA en fournit une à partir de la multiplication. On tire deux grands nombres premiers p et q, on calcule le module N = p × q, puis λ(N) = ppcm(p − 1, q − 1) (la fonction d’Euler φ(N) = (p − 1)(q − 1) convient aussi). On choisit un exposant public e premier avec λ(N), presque toujours 65 537, et l’on calcule l’exposant privé d, inverse de e modulo λ(N). La clé publique est (N, e), la clé privée d, ou plus pratiquement p, q et des valeurs dérivées.

L’opération publique est c = m^e mod N, l’opération privée m = c^d mod N. Un exemple jouet, classique : p = 61, q = 53, donc N = 3 233 et φ(N) = 3 120. Avec e = 17, on obtient d = 2 753, puisque 17 × 2 753 = 46 801 = 15 × 3 120 + 1. Le message m = 65 donne c = 65^17 mod 3 233 = 2 790, et 2 790^2 753 mod 3 233 redonne bien 65.

Toute la sécurité repose sur la difficulté de retrouver p et q à partir de N : qui factorise le module calcule d en une ligne. Le record public de factorisation porte sur un module de 829 bits (RSA-250, 2020). Un module de 2 048 bits offre une sécurité estimée à environ 112 bits, 3 072 bits environ 128 bits, selon les tables du NIST (National Institute of Standards and Technology). L’ANSSI (Agence nationale de la sécurité des systèmes d’information) fixe 2 048 bits comme minimum pour un usage ne dépassant pas 2030, et 3 072 bits au-delà. La factorisation par un ordinateur quantique suffisamment grand, via l’algorithme de Shor, rendrait RSA caduc quelle que soit la taille ; c’est l’objet de la migration post-quantique.

Chiffrer peu, chiffrer hybride

Pourquoi RSA ne chiffre pas un fichier

RSA ne chiffre qu’un nombre inférieur à N, soit au plus quelques centaines d’octets, et chaque opération privée coûte des millions de cycles. On ne chiffre donc jamais un fichier avec RSA. On tire une clé symétrique aléatoire, on chiffre le fichier avec un algorithme symétrique authentifié, et l’on chiffre seulement cette clé avec RSA : c’est le chiffrement hybride.

La malléabilité du RSA nu

Le RSA « de manuel », sans remplissage, est déterministe et malléable. Déterministe : le même message donne toujours le même chiffré, ce qui permet de tester des hypothèses. Malléable : la structure multiplicative passe à travers le chiffrement. Si c = m^e, alors c × 2^e mod N est le chiffré de 2m. Dans l’exemple jouet, un attaquant qui intercepte 2 790 et le multiplie par 2^17 modulo 3 233 obtient un chiffré qui se déchiffre en 130, sans avoir jamais connu 65. Avec un petit exposant comme e = 3 et un message court tel que m^3 < N, c’est pire : il suffit d’extraire une racine cubique entière, sans modulo.

OAEP et encapsulation de clé

Le remplissage OAEP (Optimal Asymmetric Encryption Padding, Bellare et Rogaway, 1994), normalisé dans PKCS#1 version 2 (aujourd’hui RFC 8017), mélange le message avec un aléa au moyen de fonctions de hachage avant l’exponentiation. Le chiffrement devient probabiliste, et toute modification du chiffré produit un bloc incohérent, rejeté au déchiffrement.

Une approche plus propre encore est l’encapsulation de clé, ou KEM (Key Encapsulation Mechanism). Au lieu de remplir un message choisi, on tire un nombre aléatoire r inférieur à N, on transmet r^e mod N, et les deux parties dérivent la clé symétrique de r par une fonction de dérivation. Il n’y a plus de remplissage à vérifier, donc plus d’oracle de remplissage possible. Le KEM est aussi la forme qu’adoptent les algorithmes post-quantiques comme ML-KEM, ce qui facilite les migrations. TLS 1.3 a, de son côté, supprimé purement et simplement le transport de clé par RSA au profit d’échanges Diffie-Hellman éphémères (voir Établir une clé avec Diffie-Hellman).

Signer correctement

Hacher, puis remplir

On ne signe pas un message, on signe son empreinte. La signature « de manuel », s = h^d mod N, hérite des défauts du chiffrement nu : le produit de deux signatures est la signature du produit des deux empreintes, et n’importe qui peut choisir un s, calculer s^e et prétendre que c’est une empreinte signée. Le hachage complet de domaine, ou FDH (Full Domain Hash), corrige l’idée théoriquement en hachant vers l’ensemble des valeurs inférieures à N, mais n’est guère utilisé tel quel.

Le schéma recommandé est PSS (Probabilistic Signature Scheme, Bellare et Rogaway, 1996), dans PKCS#1 version 2.1 et suivantes. Il ajoute un sel aléatoire et dispose d’une preuve de sécurité. Ses paramètres doivent être fixés et vérifiés : fonction de hachage (SHA-256 ou plus), fonction de génération de masque (MGF1 avec la même fonction de hachage) et longueur du sel, couramment égale à celle de l’empreinte.

L’ancien format de signature PKCS#1 v1.5 reste très répandu, notamment dans les certificats, et n’est pas cassé en lui-même. Il l’est par les vérificateurs laxistes : en 2006, Bleichenbacher a montré que des implémentations qui analysaient la structure 00 01 FF…FF 00 DigestInfo sans vérifier qu’il ne restait rien après l’empreinte acceptaient, avec e = 3, des signatures forgées sans la clé. D’où la règle de vérification stricte : reconstruire l’encodage attendu octet par octet et le comparer en entier, plutôt que l’analyser.

Atelier : générer, signer avec PSS, vérifier strictement

openssl genpkey -algorithm RSA -pkeyopt rsa_keygen_bits:3072 -out test.key
openssl pkey -in test.key -pubout -out test.pub
openssl dgst -sha256 -sign test.key -sigopt rsa_padding_mode:pss \
  -sigopt rsa_pss_saltlen:32 -out doc.sig doc.txt
openssl dgst -sha256 -verify test.pub -sigopt rsa_padding_mode:pss \
  -sigopt rsa_pss_saltlen:32 -signature doc.sig doc.txt

La dernière commande affiche Verified OK. Deux contre-expériences sont instructives. Modifier un seul caractère de doc.txt fait échouer la vérification. Vérifier sans l’option rsa_padding_mode:pss échoue aussi : le vérificateur attend alors du v1.5 et refuse. C’est le comportement souhaité ; une politique de vérification décide d’un format, d’une fonction de hachage et d’une taille de clé minimale, et rejette tout le reste, au lieu d’essayer successivement les formats jusqu’à ce que l’un d’eux passe. Rejeter les vieux formats par défaut, c’est retirer à l’attaquant le choix du terrain.

Une clé, un usage

Une même clé RSA ne doit jamais servir à signer et à déchiffrer. Les deux opérations sont la même exponentiation privée : un serveur qui déchiffre tout ce qu’on lui envoie peut être amené à « déchiffrer » une valeur choisie qui est en réalité une empreinte à signer. Les attaques par oracle de déchiffrement se transforment ainsi en falsification de signature. L’extension Key Usage des certificats sert précisément à séparer ces rôles ; une clé de chiffrement et une clé de signature ont aussi des cycles de vie différents, puisque la première doit parfois être séquestrée et la seconde jamais.

Implémentation et fautes

CRT, fautes et blinding

Le déchiffrement et la signature utilisent en pratique le théorème des restes chinois, ou CRT (Chinese Remainder Theorem) : on calcule m_p = c^(d mod (p − 1)) mod p et m_q = c^(d mod (q − 1)) mod q, puis on recombine. Les opérations portent sur des nombres deux fois plus courts, d’où un gain de l’ordre d’un facteur trois à quatre. Ce gain a un prix : si une faute, provoquée ou accidentelle, corrompt un seul des deux calculs, le pgcd entre N et la différence entre le résultat fautif élevé à e et le message révèle p. C’est l’attaque de Bellcore (Boneh, DeMillo, Lipton, 1997), décrite dans Quand l’implémentation parle. La protection consiste à vérifier le résultat avec la clé publique avant de le renvoyer.

Contre les attaques temporelles, on applique le blinding : multiplier le chiffré par r^e pour un aléa r, effectuer l’opération privée, puis diviser par r. L’exponentiation porte alors sur une valeur inconnue de l’attaquant. Les bibliothèques maintenues le font par défaut ; le code maison, en général, non.

Messages d’erreur et oracle de padding

Le déchiffrement PKCS#1 v1.5 attend un bloc de la forme 00 02 [octets non nuls] 00 [message]. En 1998, Bleichenbacher a montré qu’un serveur qui indique, même indirectement, si ce format est respecté sert d’oracle : par des milliers à des millions de requêtes ajustées, l’attaquant déchiffre un message capturé. Analyser un tel oracle revient à recenser tout ce qui distingue un bloc mal formé d’un bloc bien formé mais dont le contenu est ensuite rejeté : code d’erreur, alerte TLS, durée, fermeture de connexion. L’attaque ROBOT (2017) a retrouvé ce défaut, dix-neuf ans plus tard, chez plusieurs grands équipementiers ; la brèche la question qui rend le module bavard la raconte. La parade de TLS 1.2 consiste, en cas de bloc invalide, à poursuivre avec une valeur aléatoire sans rien laisser paraître ; la parade durable est de ne plus utiliser ce format de chiffrement.

Génération des premiers

La clé n’est jamais meilleure que l’aléa qui a produit p et q. En 2012, deux équipes ont collecté des millions de clés publiques sur Internet et calculé les pgcd deux à deux : des dizaines de milliers de modules partageaient un facteur premier, à cause d’équipements embarqués qui généraient leurs clés au démarrage, avant d’avoir accumulé assez d’entropie. Un pgcd suffit alors à factoriser les deux modules. En 2017, la vulnérabilité ROCA a montré qu’une bibliothèque de carte à puce générait des premiers d’une forme si particulière que les modules devenaient factorisables. La leçon est double : générer les clés avec une bibliothèque éprouvée et une source d’aléa saine (voir Produire de l’aléa utilisable), et ne jamais réutiliser un module entre plusieurs entités, même avec des exposants différents, puisque deux chiffrés d’un même message sous un module commun suffisent à le retrouver.

À ne pas confondre

RSA-OAEP est un schéma de chiffrement, RSA-PSS un schéma de signature : ils partagent la trappe, pas l’usage. Une clé de chiffrement et une clé de signature sont deux clés, même quand elles ont la même taille. PKCS#1 v1.5 est un héritage qu’on vérifie strictement en signature et qu’on abandonne en chiffrement. Enfin, le chiffrement RSA d’une clé choisie et un KEM RSA ne se confondent pas : le second ne transporte aucune donnée choisie, seulement un aléa dont on dérive la clé, et n’offre donc aucun remplissage à interroger.

🐝 Ce qui arrive si on s’en passe

Sans remplissage moderne ni vérification stricte, un serveur qui déchiffre avec RSA devient un instrument au service de l’attaquant : chaque réponse différente à un message mal formé lui apprend un peu du contenu chiffré, jusqu’à le reconstituer entièrement, comme le montre la brèche « la question qui rend le module bavard ». La clé n’est jamais volée, elle est simplement utilisée à distance, ce qui ne laisse dans les journaux qu’une rafale de requêtes rejetées. Une clé partagée entre signature et déchiffrement étend la fuite : la même série de questions qui déchiffre un secret peut produire une signature valide sur un document que son propriétaire n’a jamais vu.

🦫 Explication de la marmotte 🍫

Cette méthode repose sur une opération facile dans un sens et très difficile dans l’autre. Multiplier deux très grands nombres premiers est rapide ; retrouver ces deux nombres à partir de leur produit, appelé module, est hors de portée quand ils sont assez grands. À partir de ces deux nombres, on calcule un exposant public, que tout le monde peut connaître, et un exposant privé, gardé secret. Chiffrer consiste à élever le message à la puissance publique, en ne gardant que le reste de la division par le module ; déchiffrer utilise de la même façon la puissance privée. Utilisée telle quelle, cette opération est dangereuse : un attaquant peut modifier un message chiffré de façon prévisible. On ajoute donc un remplissage, c’est-à-dire des octets structurés et en partie aléatoires placés autour du message avant le calcul. Le même principe vaut pour la signature, qui s’applique à l’empreinte du message avec un remplissage adapté. La méthode est lente : elle sert à protéger une petite clé, qui chiffre ensuite le vrai contenu avec un autre algorithme. Les échecs viennent souvent de la mise en œuvre : des messages d’erreur trop précis permettent de déchiffrer par essais successifs, une erreur matérielle provoquée pendant un calcul accéléré peut révéler la clé, et un temps de calcul variable trahit des informations. Enfin, une même clé ne doit jamais servir à la fois à signer et à déchiffrer.

Pages voisines

La citent

RSA : trappe, padding et usages restreints

Elle cite

: les deux pages se citent l’une l’autre.

RSA : trappe, padding et usages restreints

RSA : trappe, padding et usages restreints

Intuition de la trappe

Chiffrer peu, chiffrer hybride

Pourquoi RSA ne chiffre pas un fichier

La malléabilité du RSA nu

OAEP et encapsulation de clé

Signer correctement

Hacher, puis remplir

Atelier : générer, signer avec PSS, vérifier strictement

Une clé, un usage

Implémentation et fautes

CRT, fautes et blinding

Messages d’erreur et oracle de padding

Génération des premiers

À ne pas confondre

🐝 Ce qui arrive si on s’en passe

🦫 Explication de la marmotte 🍫

À lire aussi

Pages voisines