RSA et factorisation d'entiers

Le RSA est le cryptosystème à clé publique le plus largement connu, offrant des services de chiffrement et de signatures numériques dont la sécurité repose sur la difficulté de factoriser le produit de deux grands nombres premiers.

Definition

Le RSA est un cryptosystème à clé publique dans lequel un module public n est le produit de deux nombres premiers secrets ; le chiffrement élève le message à un exposant public modulo n, et le déchiffrement utilise un exposant privé dérivable uniquement de la factorisation de n.

Scope

Ce sujet couvre l'algorithme RSA — la génération de clés, le chiffrement, le déchiffrement et la signature via l'exponentiation modulaire — ainsi que le problème de la factorisation d'entiers sur lequel il repose, les algorithmes de factorisation qui le menacent, et les schémas de remplissage (OAEP, PSS) qui rendent le RSA « de manuel » sécurisé en pratique. Il aborde les recommandations concernant la taille des clés et les attaques d'implémentation telles que les attaques temporelles et par faute. Il exclut les schémas basés sur le logarithme discret et la cryptographie sur courbes elliptiques, qui sont traités séparément.

Core questions

• Comment les exposants public et privé du RSA découlent-ils de la structure de l'arithmétique modulaire ?
• Pourquoi la sécurité du RSA dépend-elle de la difficulté de factoriser le module ?
• À quelle vitesse les grands entiers peuvent-ils être factorisés, et qu'est-ce que cela implique pour les tailles de clés ?
• Pourquoi le RSA « de manuel » est-il non sécurisé, et comment les schémas de remplissage comme OAEP et PSS y remédient-ils ?
• Quelles attaques au niveau de l'implémentation (temporelles, par faute, aléatoire faible) menacent le RSA en pratique ?

Key concepts

• exponentiation modulaire
• exposants public et privé
• fonction totient d'Euler et fonction de Carmichael
• problème de factorisation
• crible général de corps de nombres
• remplissage OAEP
• remplissage PSS pour signature
• taille de clé et niveau de sécurité

Key theories

Permutation à sens unique à trappe RSA

Le RSA définit une permutation à sens unique à trappe : l'élévation à l'exposant public modulo n est facile, mais son inversion nécessite l'exposant privé, qui ne peut être calculé qu'à partir de la factorisation en nombres premiers de n — la trappe.

Hypothèse de factorisation et taille de clé

La sécurité pratique du RSA suit les meilleurs algorithmes de factorisation (actuellement le crible général de corps de nombres, sous-exponentiel par rapport à la longueur du module) ; leur résistance est la raison pour laquelle le RSA moderne utilise des modules de 2048 bits ou plus.

Mechanisms

La génération de clés choisit deux grands nombres premiers aléatoires p et q, définit n = p*q, sélectionne un exposant public e premier avec (p-1)(q-1), et calcule l'exposant privé d comme l'inverse modulaire de e. Le chiffrement calcule c = m^e mod n ; le déchiffrement récupère m = c^d mod n. La correction découle du théorème d'Euler. Un déploiement sécurisé enveloppe le texte en clair dans un remplissage OAEP pour le chiffrement et utilise PSS pour les signatures, car le RSA « de manuel » brut est malléable et déterministe.

Clinical relevance

Le RSA sécurise des décennies d'infrastructures déployées : certificats de serveur TLS, signature de code, clés SSH, e-mails PGP/S-MIME, cartes à puce et signature de documents. Bien que les schémas à courbes elliptiques soient de plus en plus privilégiés pour les nouveaux systèmes en raison de clés plus petites, le RSA reste omniprésent dans les certificats et les protocoles hérités, et sa compréhension est essentielle pour évaluer le risque cryptographique réel.

Evidence & guidelines

Le RSA est normalisé dans PKCS #1 (RFC 8017), qui spécifie OAEP et PSS. Le NIST (SP 800-57) recommande un module minimum de 2048 bits, avec 3072 bits pour des niveaux de sécurité plus élevés. Des défaillances notables (le bogue de clé faible de Debian, la faille ROCA dans la génération de clés Infineon, et la rétrogradation FREAK vers le RSA d'exportation de 512 bits) soulignent l'importance d'une génération de clés et de tailles de paramètres correctes.

History

Le RSA a été publié en 1977-1978 par Rivest, Shamir et Adleman au MIT, constituant la première réalisation pratique du concept de clé publique proposé par Diffie et Hellman. (Clifford Cocks avait découvert un schéma équivalent secrètement au GCHQ en 1973.) Les avancées en matière de factorisation — le crible quadratique puis le crible général de corps de nombres dans les années 1980-1990 — ont progressivement augmenté la taille de clé sécurisée, et les défis de factorisation RSA (RSA Factoring Challenges) ont suivi les progrès pratiques.

Key figures

• Ronald Rivest
• Adi Shamir
• Leonard Adleman
• Carl Pomerance
• Arjen Lenstra

Seminal works

• rivest1978
• katz2020
• menezes1996

Frequently asked questions

Le RSA est-il cassé ?

Aucune attaque classique ne compromet un RSA correctement implémenté avec un module suffisamment grand (2048 bits ou plus). Les défaillances réelles du RSA proviennent de clés trop petites, d'une génération de nombres aléatoires faible, ou d'un remplissage manquant/incorrect, et non d'une rupture de l'algorithme lui-même. Un grand ordinateur quantique, cependant, casserait le RSA via l'algorithme de Shor.

Pourquoi ne puis-je pas simplement chiffrer directement avec la fonction RSA ?

Le RSA « de manuel » brut est déterministe et malléable, ce qui entraîne des fuites d'informations et permet la manipulation du texte chiffré. Une utilisation sécurisée nécessite un remplissage aléatoire tel que OAEP pour le chiffrement et PSS pour les signatures, c'est pourquoi les normes imposent ces schémas.