ECDLP : Elliptic Curve Discrete Logarithm Problem
Cryptographie
ECDLP : Elliptic Curve Discrete Logarithm Problem, problème du logarithme discret sur courbe elliptique. « Retrouver combien de fois un point a été ajouté à lui-même quand on ne connaît que le résultat », par analogie avec un promeneur dont on connaît le départ et l'arrivée mais pas le nombre de pas, sur un terrain où chaque pas le téléporte à un endroit d'apparence quelconque.
Énoncé : Sur une courbe elliptique définie sur un corps fini, avec un point de base G d'ordre premier n, calculer Q = k·G est rapide ; retrouver k à partir de G et de Q est l'ECDLP. La clé privée est k, la clé publique Q : ECDH, ECDSA, EdDSA et X25519 reposent tous sur la difficulté de ce problème.
Meilleure attaque : Sur une courbe bien choisie, les meilleurs algorithmes classiques connus sont génériques, comme la méthode rho de Pollard, en environ racine de n opérations : une courbe de 256 bits offre donc environ 128 bits de sécurité. Aucun équivalent des algorithmes sous-exponentiels qui imposent à RSA des modules de 3072 bits n'est connu, d'où la compacité des clés.
Courbes faibles : Certaines courbes ramènent le problème à un cas plus simple : courbes anormales, dont l'ordre égale la caractéristique du corps (attaque de Smart, 1999), ou courbes à faible degré de plongement, transportées vers un logarithme discret dans un corps fini par l'attaque MOV (1993). Les courbes normalisées sont choisies pour les éviter.
Quantique : L'algorithme de Shor résout l'ECDLP en temps polynomial. Les estimations publiées indiquent même qu'une courbe de 256 bits demanderait moins de qubits logiques qu'un module RSA de 3072 bits de sécurité classique comparable : la compacité ne protège de rien ici.
Ce qui arrive si on s'en passe
L'ECDLP résiste presque toujours ; ce sont les implémentations qui cèdent. Un nonce ECDSA réutilisé ou biaisé livre la clé privée par simple algèbre, sans résoudre le moindre logarithme : c'est ainsi que la clé de signature de la PlayStation 3 a été extraite en 2010. Un point reçu sans vérification de son appartenance à la courbe permet l'attaque par courbe invalide, qui déplace le calcul sur une courbe faible choisie par l'attaquant. Valider les points, employer des nonces déterministes (RFC 6979) ou EdDSA, et s'en remettre à des bibliothèques éprouvées évitent de rendre facile un problème difficile.
Explication de la marmotte
Sur une courbe elliptique, on sait « additionner » un point avec lui-même des milliards de milliards de fois très rapidement. Mais si l'on ne montre que le point d'arrivée, retrouver combien de fois on a additionné est pratiquement impossible pour un ordinateur ordinaire. Ce nombre secret sert de clé privée. Beaucoup de systèmes de sécurité, dont les connexions aux sites web, reposent sur cette difficulté.
Où ce terme est utilisé
- Courbes elliptiques : compacité, validation et pièges (4 occurrences)