Français
Menu

RSA vs courbes elliptiques vs cryptographie post-quantique : clés, vitesse, résistance quantique

Tous trois relèvent de la cryptographie à clé publique, utilisée pour partager des clés (échange ou encapsulation de clés) et pour les signatures numériques. RSA repose sur la difficulté de factoriser de grands nombres, et la cryptographie sur courbes elliptiques sur la difficulté du problème du logarithme discret sur les courbes elliptiques ; à sécurité égale, la cryptographie sur courbes elliptiques nécessite des clés bien plus courtes que RSA. Les deux seraient cependant cassées par l’algorithme de Shor dès qu’existerait un grand ordinateur quantique tolérant aux fautes. La cryptographie post-quantique repose sur des problèmes, comme les problèmes de réseaux euclidiens, que l’on pense difficiles même pour les ordinateurs quantiques ; en août 2024, le NIST américain a publié des normes, dont le mécanisme d’encapsulation de clés ML-KEM (FIPS 203) et le schéma de signature ML-DSA (FIPS 204). Leur principal inconvénient est la grande taille des clés et des signatures.

CritèreRSACryptographie sur courbes elliptiquesCryptographie post-quantique (ML-KEM, ML-DSA)
Problème difficile sous-jacentLa factorisation de grands nombresLe problème du logarithme discret sur les courbes elliptiquesPour ML-KEM et ML-DSA, des problèmes de réseaux euclidiens (comme Module-LWE : retrouver un secret à partir d’équations linéaires auxquelles on a ajouté de petites erreurs) ; il existe aussi SLH-DSA (FIPS 205), un schéma de signature fondé uniquement sur des fonctions de hachage
Taille de clé (repère)Dans le tableau de la NIST SP 800-57, le repère pour une sécurité de 128 bits est un n de 3072 bits (384 octets) ; 2048 bits correspondent à une sécurité de 112 bitsDans le même tableau, le repère pour une sécurité de 128 bits est de 256 bits ; dans l’échange de clés X25519, la valeur publique envoyée fait 32 octetsUne clé publique (clé d’encapsulation) ML-KEM-768 fait 1 184 octets, bien plus que les 32 octets de X25519
Taille des chiffrés et des signaturesLes chiffrés comme les signatures ont la longueur de n (384 octets pour 3072 bits)Une signature ECDSA (P-256) se compose de deux valeurs de 256 bits, r et s, soit 64 octets (un peu plus selon l’encodage)Un chiffré ML-KEM-768 fait 1 088 octets et une signature ML-DSA-65 fait 3 309 octets
VitesseComme l’exposant public peut être petit (comme 65537), le chiffrement et la vérification de signature sont rapides ; le déchiffrement, la signature et la génération de clés sont lourdsLa génération de clés et la signature sont bien plus rapides qu’avec RSA à sécurité égale ; la vérification de signature est souvent plus lente qu’avec RSALes calculs de ML-KEM sont légers et réputés pas plus lents qu’un échange de clés sur courbes elliptiques ; la taille des données envoyées pose généralement plus de problèmes que le calcul
Résistance quantiqueAucune : l’algorithme de Shor le casse sur un grand ordinateur quantique tolérant aux fautesAucune : l’algorithme de Shor résout aussi le problème du logarithme discret, elle est donc cassée comme RSARéputée difficile à résoudre efficacement même avec des ordinateurs quantiques (cela n’est pas démontré)
NormalisationInventé en 1977 ; en pratique utilisé avec un bourrage aléatoire comme OAEP pour le chiffrement et PSS pour les signaturesDes courbes comme P-256, ainsi que X25519 et Ed25519 fondées sur Curve25519, sont largement utiliséesPubliées par le NIST en août 2024 sous les noms FIPS 203 (ML-KEM), FIPS 204 (ML-DSA) et FIPS 205 (SLH-DSA)
Usages typiques actuelsAu milieu des années 2020, surtout les certificats et la signature de logiciels ; TLS 1.3 a supprimé l’échange de clés consistant à envoyer le matériel de clé chiffré avec RSAAu milieu des années 2020, pilier de l’échange de clés TLS (ECDHE) ; aussi les signatures ECDSA et EdDSA, et les appareils aux ressources limitées comme les cartes à puce et les systèmes embarquésDepuis 2025, l’échange de clés hybride combiné à X25519 (comme X25519MLKEM768) commence à être utilisé dans TLS 1.3 ; la migration des signatures suit celle de l’échange de clés
MigrationUne cible de la migration vers la cryptographie post-quantique ; le remplacement des signatures, comme dans les certificats et la signature de code, est le principal défiUne cible de la migration ; pendant la transition, elle sert de moitié de l’échange de clés hybride avec ML-KEM et assure la sécurité face aux ordinateurs classiquesPour l’instant, la migration progresse par étapes avec des schémas hybrides qui la combinent à la cryptographie classique ; on privilégie les conceptions qui facilitent le remplacement ultérieur des algorithmes (agilité cryptographique)
Précautions d’implémentationNe jamais utiliser le RSA « de manuel » sans bourrage ; la génération de clés exige un aléa de bonne qualitéRéutiliser ou biaiser la valeur aléatoire propre à chaque signature (nonce) permet de retrouver la clé privée ; il faut aussi vérifier que les points reçus se trouvent sur la bonne courbeLa grande taille des clés et des signatures impose de vérifier l’impact sur la taille des paquets et sur les appareils à mémoire limitée ; attention aux bogues des nouvelles implémentations et aux attaques par canal auxiliaire

Les valeurs indiquées sont des ordres de grandeur typiques et varient selon la génération de procédé et le produit.

Quand choisir l'un ou l'autre ?

RSA
Lorsque la compatibilité avec les certificats et systèmes existants est requise. Sa vérification rapide convient aux usages comptant de nombreux vérificateurs, mais un plan de migration vers la cryptographie post-quantique est nécessaire.
Cryptographie sur courbes elliptiques
Lorsque de nouveaux systèmes ont besoin aujourd’hui d’échange de clés et de signatures avec des clés courtes et peu de données. Elle convient aussi aux cartes à puce et aux systèmes embarqués. Prévoir le passage à des schémas hybrides pour se préparer aux ordinateurs quantiques.
Cryptographie post-quantique (ML-KEM, ML-DSA)
Lorsqu’on protège des données qui doivent rester secrètes longtemps. Pour se prémunir du « récolter maintenant, déchiffrer plus tard » (harvest now, decrypt later), où un chiffré enregistré aujourd’hui est déchiffré dans le futur, on l’adopte d’abord pour l’échange de clés dans un schéma hybride.

Questions fréquentes

Pourquoi la cryptographie sur courbes elliptiques nécessite-t-elle des clés plus courtes que RSA ?

Parce que les meilleures attaques connues n’ont pas le même coût. La factorisation dispose de méthodes bien plus rapides que la force brute, si bien que les clés RSA doivent être assez longues. Pour le problème du logarithme discret sur courbes elliptiques, même les meilleures attaques connues demandent un travail de l’ordre de la moitié de la longueur de clé en bits : la clé n’a donc besoin que d’environ deux fois le niveau de sécurité. Dans le tableau de la NIST SP 800-57, le repère pour une sécurité de 128 bits est de 3072 bits pour RSA contre 256 bits pour la cryptographie sur courbes elliptiques.

Pourquoi migrer maintenant alors que les ordinateurs quantiques n’existent pas encore ?

Parce que des chiffrés interceptés et stockés aujourd’hui pourraient être déchiffrés par de futurs ordinateurs quantiques (récolter maintenant, déchiffrer plus tard). En outre, remplacer la cryptographie dans les logiciels, les appareils et l’infrastructure de certificats prend de nombreuses années. C’est pourquoi la migration commence par l’échange de clés, qui transporte des données devant rester secrètes longtemps.

Les ordinateurs quantiques casseront-ils aussi les chiffrements symétriques comme AES ?

Ils ne sont pas visés par l’algorithme de Shor. Selon la règle simple voulant que l’algorithme de Grover accélère quadratiquement la recherche de clé, le niveau de sécurité en bits est divisé par deux, ce que l’on compense en choisissant AES-256 là où une sécurité à long terme est nécessaire. Ce qu’il faut remplacer, c’est surtout la cryptographie à clé publique comme RSA et la cryptographie sur courbes elliptiques.

Qu’est-ce qu’un schéma hybride ?

Un schéma qui utilise en même temps la cryptographie classique et la cryptographie post-quantique et combine les résultats. Dans l’échange de clés, les secrets partagés issus de X25519 et de ML-KEM entrent tous deux dans la dérivation de clé, de sorte que la clé obtenue reste protégée tant que l’un des deux est sûr. Les schémas post-quantiques sont récents et les erreurs d’implémentation ou de nouvelles attaques ne peuvent pas encore être totalement exclues : l’approche hybride sert donc d’assurance pendant la transition.

Vérifier vos connaissances

Dans le tableau de NIST SP 800-57, quelle combinaison de longueur de clé RSA (nombre de bits de n) et de longueur de clé pour la cryptographie sur courbes elliptiques est donnée comme repère pour une sécurité comparable à celle de la cryptographie symétrique à 128 bits (AES-128) ?

  1. AEnviron 128 bits pour RSA et environ 128 bits pour la cryptographie sur courbes elliptiques
  2. BEnviron 2048 bits pour RSA et environ 128 bits pour la cryptographie sur courbes elliptiques
  3. CEnviron 3072 bits pour RSA et environ 256 bits pour la cryptographie sur courbes elliptiques
Afficher la réponse et l'explication

Réponse : C. Environ 3072 bits pour RSA et environ 256 bits pour la cryptographie sur courbes elliptiques

Pour obtenir la même sécurité, la cryptographie à clé publique a besoin de clés plus longues que la cryptographie symétrique. Dans le tableau de NIST SP 800-57 Part 1, le repère pour une sécurité de 128 bits est de 3072 bits pour RSA et de 256 à 383 bits pour la cryptographie sur courbes elliptiques. Pour la cryptographie sur courbes elliptiques, les meilleures attaques connues demandent un effort d'environ la moitié de la longueur de clé en bits ; une clé d'environ deux fois le nombre de bits de sécurité suffit donc, ce qui donne la même sécurité qu'avec RSA avec une clé bien plus courte. RSA à 2048 bits est le repère pour une sécurité de 112 bits.

Quelle association entre les normes de cryptographie post-quantique publiées par le NIST américain en août 2024 et leur type est correcte ?

  1. AFIPS 203 ML-KEM est un schéma de signature à base de réseaux euclidiens, FIPS 204 ML-DSA un mécanisme d'encapsulation de clés à base de fonctions de hachage, et FIPS 205 SLH-DSA un chiffrement symétrique
  2. BFIPS 203 ML-KEM, FIPS 204 ML-DSA et FIPS 205 SLH-DSA sont tous des schémas de signature à clés courtes fondés sur des problèmes sur courbes elliptiques
  3. CFIPS 203 ML-KEM est un mécanisme d'encapsulation de clés à base de réseaux euclidiens, FIPS 204 ML-DSA un schéma de signature à base de réseaux euclidiens, et FIPS 205 SLH-DSA un schéma de signature à base de fonctions de hachage
Afficher la réponse et l'explication

Réponse : C. FIPS 203 ML-KEM est un mécanisme d'encapsulation de clés à base de réseaux euclidiens, FIPS 204 ML-DSA un schéma de signature à base de réseaux euclidiens, et FIPS 205 SLH-DSA un schéma de signature à base de fonctions de hachage

Le 13 août 2024, le NIST a publié trois FIPS comme premières normes de cryptographie post-quantique. FIPS 203 ML-KEM (anciennement CRYSTALS-Kyber) est un mécanisme d'encapsulation de clés servant à partager des clés, tandis que FIPS 204 ML-DSA (CRYSTALS-Dilithium) et FIPS 205 SLH-DSA (SPHINCS+) sont des schémas de signature numérique. ML-KEM et ML-DSA reposent sur la difficulté de problèmes de réseaux euclidiens, comme le problème Module-LWE, qui consiste à retrouver un secret à partir d'un système d'équations linéaires auxquelles on a ajouté de petites erreurs. SLH-DSA ne repose que sur la sécurité des fonctions de hachage ; ses signatures sont donc grandes et lentes, mais il constitue une parade au cas où une faiblesse serait découverte dans les problèmes de réseaux euclidiens.

Quelle affirmation décrit correctement l'idée de l'échange de clés hybride, utilisé pendant la migration vers la cryptographie post-quantique, qui combine X25519 (échange de clés Diffie-Hellman sur une courbe elliptique) et ML-KEM ?

  1. ALes deux secrets partagés obtenus par les deux schémas entrent dans la dérivation de clés, si bien que la clé obtenue est sûre tant que l'un des deux l'est
  2. BDes deux schémas, seul le secret partagé de celui qui termine le premier pendant la poignée de main est utilisé, et l'autre est jeté
  3. CML-KEM n'est pas utilisé tant que les ordinateurs quantiques ne sont pas une réalité ; les deux sont préparés pour que la bascule soit automatique le moment venu
Afficher la réponse et l'explication

Réponse : A. Les deux secrets partagés obtenus par les deux schémas entrent dans la dérivation de clés, si bien que la clé obtenue est sûre tant que l'un des deux l'est

ML-KEM est un schéma récent, et l'on ne peut pas encore totalement exclure que des erreurs d'implémentation ou de nouvelles attaques soient découvertes. X25519, en revanche, est vulnérable aux ordinateurs quantiques mais a fait ses preuves depuis longtemps face aux ordinateurs classiques. Dans l'échange de clés hybride, les deux secrets partagés sont concaténés et passés à une fonction de dérivation de clé ; un attaquant doit donc casser les deux pour obtenir la clé, et les communications enregistrées aujourd'hui sont aussi protégées contre un déchiffrement par de futurs ordinateurs quantiques. En 2025, cette combinaison (comme X25519MLKEM768) commence à être utilisée dans TLS 1.3.

  1. Une fois que de grands ordinateurs quantiques tolérants aux fautes auront été construits, quels chiffrements devraient voir leur sécurité sérieusement compromise par l'algorithme de Shor ?
  2. Quelle est la raison la plus appropriée de hâter la migration vers la cryptographie post-quantique avant même que de grands ordinateurs quantiques existent ?
  3. Quelle affirmation décrit correctement un problème posé par l'utilisation, dans de vraies communications et sans remplissage, du RSA « de manuel » (qui calcule directement c = m^e mod n à partir du texte clair m) ?

Questions d'entraînement sur Bases et applications de la cryptographie

Termes clés expliqués

Cryptosystème RSA
Cryptosystème à clé publique conçu en 1977 par Rivest, Shamir et Adleman. La clé publique est formée du produit n de deux grands nombres premiers p et q et d'un exposant public e, et la clé privée est le d qui vérifie e × d ≡ 1 (mod (p − 1)(q − 1)). Le chiffrement se fait par c = m^e mod n et le déchiffrement par m = c^d mod n. Sa sécurité repose sur la difficulté de factoriser n, et il peut servir aussi bien au chiffrement qu'aux signatures. En pratique, on le combine avec un remplissage aléatoire comme OAEP ou PSS.
Cryptographie sur courbes elliptiques
Famille de cryptosystèmes à clé publique qui utilisent l'arithmétique des points d'une courbe elliptique sur un corps fini. Leur sécurité repose sur la difficulté de retrouver l'entier secret k à partir du point kG, c'est-à-dire du point G de la courbe multiplié par k (problème du logarithme discret sur courbe elliptique). Pour une même sécurité, ils exigent des clés bien plus courtes que RSA : une clé de 256 bits est le repère pour une sécurité à peu près équivalente à celle de RSA à 3072 bits (sécurité de 128 bits). Ils servent à l'échange de clés (ECDH et ECDHE) et aux signatures (ECDSA et EdDSA), avec des courbes largement utilisées comme P-256 et Curve25519. Comme l'algorithme de Shor les casse, ils font partie des schémas à remplacer par la cryptographie post-quantique.
Cryptographie post-quantique (PQC)
Cryptographie qui fonde sa sécurité sur des problèmes mathématiques réputés difficiles à résoudre efficacement même pour les ordinateurs quantiques, comme les problèmes de réseaux euclidiens et les fonctions de hachage. Elle fonctionne sur les ordinateurs conventionnels et sert à remplacer RSA et la cryptographie sur courbes elliptiques, que l'algorithme de Shor peut casser.
ML-KEM
Mécanisme d'encapsulation de clés (KEM) à base de réseaux euclidiens, normalisé par le NIST américain en août 2024 sous le nom de FIPS 203. Le nom signifie Module-Lattice-Based Key-Encapsulation Mechanism, et il est fondé sur CRYSTALS-Kyber. Sa sécurité repose sur la difficulté du problème Module-LWE, qui consiste à retrouver un secret à partir d'un système d'équations linéaires auxquelles on a ajouté de petites erreurs, problème réputé difficile même pour les ordinateurs quantiques. Il existe trois jeux de paramètres : ML-KEM-512, ML-KEM-768 et ML-KEM-1024. Il est utilisé dans des protocoles comme TLS pour remplacer l'échange de clés ECDHE ou pour s'y combiner.
Algorithme de Shor
Algorithme quantique qui résout en temps polynomial la factorisation de grands entiers et le problème du logarithme discret en trouvant des périodes grâce à la transformée de Fourier quantique. Il a été publié par Peter Shor en 1994. Il peut casser RSA et la cryptographie sur courbes elliptiques, mais son exécution demande un grand ordinateur quantique tolérant aux fautes.
Échange de clés Diffie-Hellman
Méthode par laquelle deux parties créent un secret partagé en n'utilisant qu'un canal public, publiée par Diffie et Hellman en 1976. Un nombre premier p et un générateur g sont publics ; A et B choisissent des valeurs secrètes a et b, s'envoient g^a mod p et g^b mod p, et chacun élève la valeur de l'autre à la puissance de son propre secret, si bien que tous deux obtiennent le même g^(ab) mod p. Sa sécurité repose sur la difficulté du problème du logarithme discret. La version sur courbe elliptique s'appelle ECDH, et les versions qui utilisent des valeurs jetables pour chaque connexion s'appellent DHE et ECDHE ; ces dernières assurent la confidentialité persistante. La méthode n'authentifie pas l'autre partie ; on la combine donc avec des signatures et des certificats pour empêcher les attaques de l'homme du milieu.
Agilité cryptographique (crypto-agilité)
Capacité à passer à un autre schéma sans refonte majeure d'un système lorsqu'un algorithme cryptographique ou une longueur de clé perd sa sûreté. On l'accroît en tenant un inventaire de la cryptographie utilisée et de ses emplacements, en rendant les algorithmes sélectionnables par configuration ou par négociation dans le protocole, et en incluant des identifiants d'algorithmes dans les formats de données. Elle est mise en avant lors des migrations qui abandonnent MD5, SHA-1 et les clés RSA courtes, ainsi que lors de la migration vers la cryptographie post-quantique.
Cryptographie à clé publique (cryptographie asymétrique)
Méthode cryptographique qui utilise, pour le chiffrement et le déchiffrement, une paire de clés différentes et appariées : une clé publique et une clé privée. La clé publique peut être connue de tous, tandis que seul son propriétaire détient la clé privée. Elle facilite la distribution des clés mais ses calculs sont lourds ; on la combine donc avec la cryptographie symétrique pour chiffrer les données elles-mêmes. RSA et la cryptographie sur courbes elliptiques en sont des exemples typiques.

Comparatifs associés