Cryptographie sur les courbes elliptiques

La cryptographie sur les courbes elliptiques (ECC) met en œuvre des schémas à clé publique basés sur le groupe de points d'une courbe elliptique, offrant le même niveau de sécurité que RSA ou Diffie-Hellman sur corps finis avec des clés de taille bien inférieure.

Definition

La cryptographie sur les courbes elliptiques est une cryptographie à clé publique dont le groupe sous-jacent est l'ensemble des points sur une courbe elliptique sur un corps fini, la sécurité étant fondée sur la difficulté du problème du logarithme discret sur les courbes elliptiques.

Scope

Ce sujet aborde la loi de groupe des courbes elliptiques sur les corps finis, le problème du logarithme discret sur les courbes elliptiques, et les schémas qui en découlent : Diffie-Hellman sur les courbes elliptiques (ECDH), les schémas de signature ECDSA et EdDSA, ainsi que les courbes modernes comme Curve25519. Il explique pourquoi les logarithmes discrets sur les courbes elliptiques sont plus difficiles à résoudre que ceux sur les corps finis (absence de calcul d'indice sous-exponentiel) et les préoccupations d'implémentation telles que la réutilisation de nonce dans ECDSA. Il exclut RSA et les schémas de logarithme discret sur corps finis, traités dans des sujets connexes.

Core questions

• Comment l'addition géométrique de points sur une courbe elliptique forme-t-elle un groupe cryptographique ?
• Pourquoi le logarithme discret sur les courbes elliptiques est-il plus difficile que son analogue sur corps finis, permettant ainsi des clés plus petites ?
• Comment Diffie-Hellman et les signatures numériques sont-ils instanciés sur les courbes elliptiques ?
• Qu'est-ce qui rend les courbes modernes comme Curve25519 plus sûres à implémenter que les anciennes courbes NIST ?
• Pourquoi l'unicité du nonce par signature est-elle critique dans ECDSA ?

Key concepts

• loi de groupe des courbes elliptiques
• multiplication scalaire
• problème du logarithme discret sur les courbes elliptiques
• ECDH
• ECDSA
• EdDSA et Ed25519
• Curve25519
• vulnérabilité de réutilisation de nonce
• taille de clé vs RSA

Key theories

Problème du logarithme discret sur les courbes elliptiques

Étant donné les points P et Q = kP sur une courbe, la récupération du scalaire k est considérée comme nécessitant un effort pleinement exponentiel pour des courbes bien choisies, car les attaques par calcul d'indice qui affaiblissent les logarithmes discrets sur corps finis ne s'appliquent pas.

Clés plus petites pour une sécurité équivalente

Étant donné que les meilleures attaques contre les logarithmes discrets sur les courbes elliptiques sont des algorithmes génériques de racine carrée, une courbe elliptique de 256 bits offre une sécurité d'environ 128 bits — comparable à un RSA de 3072 bits — ce qui permet des opérations plus rapides et des clés et signatures plus petites.

Mechanisms

Les points sur une courbe elliptique sur un corps fini forment un groupe abélien sous une loi d'addition géométrique ; l'addition répétée d'un point de base P à lui-même k fois (multiplication scalaire, kP) est efficace, mais la récupération de k à partir de kP constitue le problème difficile. ECDH réalise Diffie-Hellman en échangeant des multiples scalaires d'un point de base ; ECDSA et EdDSA produisent des signatures à partir d'un scalaire par message (un nonce) — lequel, s'il est répété ou prévisible, peut compromettre la clé privée, comme l'ont montré plusieurs incidents réels.

Clinical relevance

L'ECC est le choix par défaut pour les clés publiques dans les nouveaux systèmes : ECDHE assure l'échange de clés à secret parfait (forward secrecy) dans TLS 1.3, Ed25519 signe les clés SSH, les mises à jour logicielles et les certificats, et Curve25519 sécurise Signal, WireGuard et la messagerie moderne. Ses clés de petite taille et ses opérations rapides la rendent bien adaptée aux appareils mobiles, aux cartes à puce et au matériel IoT contraint.

Evidence & guidelines

ECDSA est normalisé dans FIPS 186, ECDH dans NIST SP 800-56A, et EdDSA/Ed25519 dans RFC 8032 ; Curve25519/X25519 dans RFC 7748. La pratique moderne privilégie les courbes d'Edwards et X25519 pour leur résistance aux pièges d'implémentation. La défaillance d'ECDSA lors de la réutilisation de nonces (notamment l'extraction de clé de la Sony PlayStation 3 en 2010) constitue un exemple standard de mise en garde.

History

Neal Koblitz et Victor Miller ont proposé indépendamment l'utilisation des courbes elliptiques pour la cryptographie entre 1985 et 1987. L'adoption a été initialement lente en raison de préoccupations liées aux brevets, à la confiance et à la complexité des courbes NIST, mais l'ECC est devenue dominante dans les années 2010 à mesure que l'efficacité de la taille des clés devenait plus importante et que Curve25519 (2006) et Ed25519 de Bernstein offraient des conceptions rapides et résistantes aux erreurs d'utilisation, désormais largement déployées.

Key figures

• Neal Koblitz
• Victor Miller
• Daniel J. Bernstein
• Alfred Menezes
• Scott Vanstone

Seminal works

• koblitz1987
• hankerson2004
• katz2020

Frequently asked questions

Pourquoi une clé de courbe elliptique de 256 bits équivaut-elle à une clé RSA de 3072 bits ?

Les meilleures attaques connues contre le logarithme discret sur les courbes elliptiques sont génériques et prennent un temps proportionnel à la racine carrée de la taille du groupe, tandis que la factorisation et les logarithmes discrets sur corps finis disposent d'algorithmes sous-exponentiels plus rapides. Les courbes elliptiques nécessitent donc beaucoup moins de bits pour le même niveau de sécurité.

Les courbes elliptiques NIST sont-elles fiables ?

Les courbes P standard du NIST sont largement utilisées et ne sont pas connues pour être compromises, mais leurs choix de constantes inexpliqués et leur difficulté d'implémentation ont conduit de nombreux acteurs à préférer Curve25519 et Ed25519, qui présentent des justifications de conception transparentes et sont plus faciles à implémenter en toute sécurité en temps constant.