Courbes elliptiques : compacité, validation et pièges

La cryptographie sur courbes elliptiques, ou ECC (Elliptic Curve Cryptography), a remplacé RSA dans la plupart des usages nouveaux pour une raison simple : à sécurité égale, ses clés sont dix fois plus courtes. Une clé publique Ed25519 tient en 32 octets, là où RSA réclame 3072 bits, soit 384 octets, pour un niveau comparable. Cette compacité a un prix : les courbes elliptiques pardonnent mal les erreurs de détail. Un point mal validé, un nombre aléatoire réutilisé ou une clé employée sur la mauvaise courbe suffisent à faire fuir la clé privée. Ce chapitre donne l’intuition nécessaire sans algèbre superflue, puis s’attarde là où les implémentations trébuchent.

→ Lire l’explication complète de la marmotte

Intuition sans algèbre lourde

Une courbe elliptique cryptographique est l’ensemble des points (x, y) qui vérifient une équation du type y² = x³ + ax + b, où toutes les opérations se font modulo un grand nombre premier p. Ce n’est donc pas une courbe que l’on dessine, mais un nuage fini de points, auquel on ajoute un point à l’infini qui joue le rôle de zéro.

Sur ce nuage, on définit une addition : deux points P et Q donnent un troisième point P + Q, par une formule fixe. Additionner un point avec lui-même s’appelle le doublement. Ces opérations font des points un groupe : l’addition est associative, possède un élément neutre et chaque point a un opposé. Dans les courbes utilisées, on travaille dans un sous-groupe d’ordre premier n, engendré par un point de base G public.

La multiplication scalaire k·G consiste à ajouter G à lui-même k fois. Avec la méthode « doubler et ajouter », un scalaire de 256 bits ne demande qu’environ 256 doublements et autant d’additions au plus : calculer k·G est instantané. Revenir de k·G à k, en revanche, est le problème du logarithme discret sur courbe elliptique, ou ECDLP (Elliptic Curve Discrete Logarithm Problem). Pour une courbe bien choisie, le meilleur algorithme connu est générique, la méthode rho de Pollard, en environ √n opérations. Un sous-groupe de 256 bits offre donc environ 128 bits de sécurité. C’est cette absence de raccourci, contrairement à la factorisation qui profite d’algorithmes sous-exponentiels, qui explique la compacité.

La clé privée est le scalaire k, tiré au hasard entre 1 et n − 1. La clé publique est le point K = k·G. Rien de plus.

Niveau visé	Courbe	Clé publique compressée	RSA équivalent
~128 bits	P-256, Curve25519	33 ou 32 octets	3072 bits
~192 bits	P-384	49 octets	7680 bits
~224 bits	Curve448	56 octets	au-delà de 7680 bits
~256 bits	P-521	67 octets	15360 bits

Un ordinateur quantique suffisamment grand résoudrait l’ECDLP en temps polynomial par l’algorithme de Shor, tout comme la factorisation. La compacité ne protège pas de ce risque, traité dans Préparer la migration post-quantique.

ECDH et signatures

L’ECDH (Elliptic Curve Diffie-Hellman) établit un secret commun. Alice publie A = a·G, Bob publie B = b·G ; Alice calcule a·B, Bob calcule b·A, et tous deux obtiennent le même point ab·G, qu’un observateur ne sait pas calculer. Ce point n’est pas une clé : il passe par une fonction de dérivation comme HKDF avant de servir. X25519 (RFC 7748) est la fonction ECDH sur Curve25519 : elle ne manipule que la coordonnée x, accepte n’importe quelle chaîne de 32 octets comme clé publique et force certains bits du scalaire, ce qui supprime une bonne partie des pièges de validation. X448 en est l’équivalent sur Curve448. Le détail des échanges de clés, KEM compris, figure dans Établir une clé : Diffie-Hellman, KEM et HPKE.

L’ECDSA (Elliptic Curve Digital Signature Algorithm) signe un condensé z avec la clé privée d : il tire un nonce k, calcule le point k·G dont l’abscisse donne r, puis s = k⁻¹(z + r·d) mod n. La signature est le couple (r, s). Tout repose sur k : il doit être secret, unique et uniformément aléatoire. Si deux messages sont signés avec le même k, le r est identique et un peu d’arithmétique livre la clé :

k = (z1 − z2) / (s1 − s2) mod n
d = (s1·k − z1) / r        mod n

C’est exactement ce qui est arrivé à la console PlayStation 3 en 2010, dont la clé de signature de Sony utilisait un nonce constant. Un nonce simplement biaisé de quelques bits suffit aussi, avec assez de signatures, à reconstruire la clé par des attaques sur réseaux euclidiens. Le RFC 6979 décrit un ECDSA à nonce déterministe, dérivé de la clé et du message, qui élimine la dépendance au générateur aléatoire.

L’EdDSA (Edwards-curve Digital Signature Algorithm), et son instance Ed25519 (RFC 8032), a été conçue pour éviter ces écueils : le nonce est dérivé de façon déterministe d’une moitié secrète de la clé et du message, les formules d’addition sont complètes, sans cas particulier exploitable, et l’implémentation en temps constant est plus naturelle. Une signature Ed25519 fait 64 octets, une clé publique 32. Le NIST (National Institute of Standards and Technology) l’a intégrée à la norme de signature FIPS 186-5 en 2023.

Choisir une courbe

Les courbes NIST P-256, P-384 et P-521 sont les courbes standards : imposées dans les environnements certifiés, présentes dans toutes les bibliothèques et dans tous les composants matériels, HSM (Hardware Security Module) et cartes à puce compris. Leurs constantes ont été générées à partir de graines dont l’origine n’a jamais été expliquée, ce qui nourrit une méfiance persistante, sans qu’aucune faiblesse n’ait été démontrée. Leurs formules d’addition comportent des cas particuliers qui compliquent l’implémentation en temps constant.

Les courbes modernes Curve25519, sous sa forme Montgomery pour X25519 et sa forme Edwards edwards25519 pour Ed25519, et Curve448 ont des paramètres justifiés, sont rapides et se prêtent à des implémentations sûres. Elles portent en revanche un cofacteur : le nombre total de points vaut 8 fois l’ordre du sous-groupe utile pour Curve25519, 4 fois pour Curve448. Les courbes NIST ont un cofacteur de 1.

Les courbes à couplage (pairing-friendly), comme BLS12-381, permettent des constructions impossibles autrement : signatures agrégeables BLS, preuves à divulgation nulle de connaissance. Elles demandent une analyse particulière : la courbe BN254, longtemps présentée comme offrant 128 bits, a vu son niveau réel ramené autour de 100 bits par des progrès de cryptanalyse en 2016. Elles n’ont rien à faire dans un simple échange de clés.

Le choix se fait donc rarement sur des critères mathématiques. Il obéit à l’interopérabilité et aux contraintes de certification. Côté navigateurs, TLS 1.3 négocie X25519 en priorité, avec P-256 et P-384 en repli, et les navigateurs majeurs activent depuis 2024 l’échange hybride X25519MLKEM768. Côté certificats publics, ECDSA s’y emploie sur P-256 et P-384, et Ed25519 n’a pas cours dans les certificats web. Côté SSH, Ed25519 est le choix recommandé. Le comparatif détaillé pour les certificats figure dans Signature courbe elliptique ou RSA. La politique la plus saine tient en une liste courte et explicite de courbes acceptées, écrite par composant ; tout le reste est refusé.

Valider et encoder

L’attaque par courbe invalide est le danger principal des courbes de Weierstrass. Les formules d’addition n’utilisent pas le coefficient b de l’équation. Si un serveur accepte un point reçu sans vérifier qu’il est sur la bonne courbe, l’attaquant peut lui envoyer un point d’une autre courbe, choisie pour posséder un sous-groupe d’ordre très petit, disons 7. Le résultat k·P ne peut prendre que 7 valeurs : en observant si le secret dérivé fonctionne, l’attaquant apprend k modulo 7. Il recommence avec des ordres 11, 13, 17 et ainsi de suite, puis recompose k par le théorème des restes chinois. En 2017, plusieurs bibliothèques JOSE (JavaScript Object Signing and Encryption) ont été trouvées vulnérables exactement de cette façon, via l’ECDH de JWE.

La parade est la validation du point : vérifier que les coordonnées sont dans l’intervalle [0, p − 1], que le point satisfait l’équation, qu’il n’est pas le point à l’infini et, si le cofacteur dépasse 1, qu’il appartient au bon sous-groupe (subgroup check, n·P = point à l’infini). Pour X25519, la courbe est choisie de sorte que sa « jumelle » (twist) soit également sûre, et la fonction ne manipule que x : aucun point invalide n’y a d’effet exploitable. Il reste les points de petit ordre, qui conduisent à un secret partagé nul ; le RFC 7748 autorise à vérifier que la sortie n’est pas entièrement composée de zéros, et les protocoles qui veulent lier le secret aux deux participants doivent le faire.

Côté signatures, l’Ed25519 a ses propres ambiguïtés : encodages non canoniques des points ou du scalaire s, vérification avec ou sans multiplication par le cofacteur. Une étude publiée en 2020 a montré que des bibliothèques répandues donnaient des verdicts différents sur les mêmes signatures limites. Pour une signature ordinaire, c’est sans importance ; pour un consensus distribué où tous les nœuds doivent trancher à l’identique, c’est une fourche assurée.

Les encodages ajoutent une couche de confusion. Un point P-256 s’écrit non compressé, 04 ‖ X ‖ Y sur 65 octets, ou compressé, 02 ou 03 selon la parité de Y, suivi de X, sur 33 octets. Une clé Ed25519 brute (raw) fait 32 octets. Les mêmes clés s’emballent ensuite en DER (Distinguished Encoding Rules), structure binaire ASN.1 de type SubjectPublicKeyInfo, en PEM (Privacy-Enhanced Mail), qui n’est que du DER en Base64 entre deux lignes d’en-tête, en JWK (JSON Web Key), ou dans un certificat X.509, qui associe la clé à une identité. Une signature ECDSA voyage elle aussi sous deux formes : DER, de 70 à 72 octets environ pour P-256, ou brute r ‖ s sur 64 octets, comme l’exige JOSE.

Exemples et ateliers

Générer une clé Ed25519, signer et vérifier avec OpenSSL 3 :

openssl genpkey -algorithm ed25519 -out ed.pem
openssl pkey -in ed.pem -pubout -out ed.pub
printf 'facture 42' > msg.txt
openssl pkeyutl -sign -inkey ed.pem -rawin -in msg.txt -out sig.bin
openssl pkeyutl -verify -pubin -inkey ed.pub -rawin -in msg.txt -sigfile sig.bin
# Signature Verified Successfully

L’option -rawin est requise : Ed25519 hache lui-même le message et refuse un condensé précalculé.

Faire un échange X25519 entre deux parties :

openssl genpkey -algorithm X25519 -out alice.pem
openssl genpkey -algorithm X25519 -out bob.pem
openssl pkey -in alice.pem -pubout -out alice.pub
openssl pkey -in bob.pem -pubout -out bob.pub
openssl pkeyutl -derive -inkey alice.pem -peerkey bob.pub -out s_alice.bin
openssl pkeyutl -derive -inkey bob.pem -peerkey alice.pub -out s_bob.bin
cmp s_alice.bin s_bob.bin && echo "secret identique"

Les 32 octets obtenus passent ensuite dans une KDF, jamais directement dans un chiffrement.

Identifier trois formats de la même clé publique :

PEM   -----BEGIN PUBLIC KEY-----
      MCowBQYDK2VwAyEA...            (Base64 d'une structure DER)
DER   30 2a 30 05 06 03 2b 65 70 03 21 00 ‖ 32 octets de clé
JWK   {"kty":"OKP","crv":"Ed25519","x":"..."}   (x en Base64url)

Le préfixe DER de 12 octets contient l’identifiant d’algorithme 2b 65 70, soit l’OID 1.3.101.112 d’Ed25519 ; les 32 derniers octets sont la clé brute. Une clé X25519 porte l’OID 1.3.101.110 : deux clés de 32 octets, deux usages, et seul l’emballage les distingue.

Pièges classiques

Réutiliser un nonce ECDSA, ou le tirer d’un générateur faible, livre la clé privée. Mélanger Ed25519 et X25519, en convertissant une clé de signature en clé d’échange pour économiser une paire, crée des interactions entre protocoles que personne n’a analysées. Accepter une clé de courbe inconnue, parce que la bibliothèque la sait lire, revient à laisser l’attaquant choisir le terrain. Ne pas valider les points quand la bibliothèque l’exige, notamment avec les API de bas niveau des courbes de Weierstrass, ouvre l’attaque par courbe invalide.

À ne pas confondre

Une courbe elliptique est un objet mathématique ; une signature elliptique est un algorithme qui l’emploie. ECDSA dépend d’un nonce aléatoire et de formules incomplètes ; EdDSA est déterministe et conçu pour la robustesse. Un point public est une clé nue ; un certificat est un document signé qui l’associe à une identité, voir Relier une clé à une identité. Curve25519 désigne la courbe, X25519 la fonction d’échange de clés et Ed25519 le schéma de signature sur la forme Edwards de cette courbe.

🐝 Ce qui arrive si on s’en passe

Sans validation des points reçus, un service qui accepte n’importe quelle clé publique calcule avec elle son secret partagé et renvoie, à chaque échange, un fragment d’information sur sa propre clé privée : un attaquant patient n’a qu’à multiplier les requêtes. Sans liste explicite des courbes acceptées, chaque composant retient celles que sa bibliothèque connaît, et l’interopérabilité devient l’argument qui fait tout passer. Sans distinction stricte des encodages, deux composants lisent la même clé différemment : l’un vérifie autre chose que ce que l’autre a signé, ce qui produit des refus inexpliqués ou, plus fâcheux, des acceptations inexpliquées, que personne ne songe à signaler puisque tout semble fonctionner.

🦫 Explication de la marmotte 🍫

Une courbe elliptique est un ensemble de points définis par une équation. On sait additionner deux points de cette courbe pour en obtenir un troisième, et répéter cette addition un grand nombre de fois : c’est la multiplication par un nombre, appelé scalaire. Partir d’un point de départ public et d’un nombre secret donne facilement un point résultat. L’opération inverse, retrouver le nombre secret à partir du point résultat, est considérée comme hors de portée : c’est ce qui rend les clés sûres. Le nombre secret est la clé privée, le point obtenu est la clé publique. Deux usages en découlent. Dans l’échange de clés, deux personnes combinent chacune leur clé privée avec la clé publique de l’autre et obtiennent le même secret partagé. Dans la signature, une clé privée produit une preuve que tout détenteur de la clé publique peut vérifier ; certaines méthodes exigent un nombre aléatoire neuf à chaque signature, et le réutiliser compromet la clé. Les problèmes viennent surtout des détails. Un point reçu qui n’appartient pas vraiment à la courbe attendue peut faire fuir des informations sur le secret. Une clé prévue pour l’échange ne doit pas servir à signer. La même clé peut s’écrire dans plusieurs formats qu’il faut savoir distinguer. Le choix de la courbe dépend enfin de la compatibilité des logiciels et des certifications exigées.

Pages voisines

La citent

Courbes elliptiques : compacité, validation et pièges

Elle cite

Courbes elliptiques : compacité, validation et pièges

Courbes elliptiques : compacité, validation et pièges

Intuition sans algèbre lourde

ECDH et signatures

Choisir une courbe

Valider et encoder

Exemples et ateliers

Pièges classiques

À ne pas confondre

🐝 Ce qui arrive si on s’en passe

🦫 Explication de la marmotte 🍫

À lire aussi

Pages voisines