Comment une clé douze fois plus courte peut-elle être aussi sûre ?

En bâtissant la serrure sur un problème plus difficile à contourner. La cryptographie à courbe elliptique (ECC) est une cryptographie à clé publique fondée sur la structure algébrique des courbes elliptiques sur des corps finis, et les attaques les plus rapides connues contre elle demandent environ la racine carrée du nombre de possibilités. Une courbe n'a donc besoin que d'environ deux fois plus de bits que le niveau de sécurité visé : 256 bits pour une sécurité de 128 bits. RSA, qui repose sur la factorisation d'un nombre énorme, a besoin d'un nombre de 3 072 bits pour la même protection. Résultat : une clé à courbe elliptique de 256 bits se compare à une clé RSA de 3 072 bits, avec moins de données à stocker et à transmettre.

L'idée a été proposée indépendamment par Neal Koblitz et Victor S. Miller en 1985, même si les algorithmes à courbe elliptique ne sont entrés en usage répandu qu'à partir de 2004. Entre-temps, l'institut américain de normalisation NIST a recommandé en 1999 quinze courbes elliptiques pour son standard de signature numérique, et en 2005 la NSA a annoncé Suite B, qui utilisait l'ECC pour les signatures et l'échange de clés. Bitcoin, lui aussi, a signé ses transactions avec une courbe elliptique sur mesure et l'algorithme ECDSA, jusqu'à ce qu'une mise à jour de 2021 ajoute un autre type de signature.

Le problème difficile lui-même s'énonce simplement : étant donné un point de départ public P sur la courbe et un autre point Q obtenu en additionnant P à lui-même un nombre secret k de fois, il doit être infaisable de retrouver k. Calculer Q à partir de k est rapide ; remonter de Q à k, c'est ce qu'aucun raccourci connu ne rend facile.

Rien de tout cela ne met les courbes elliptiques à l'abri des critiques. Un défi historique de 112 bits sur courbe elliptique a été résolu en 2009 grâce à un cluster de plus de 200 consoles PlayStation 3, et en 2013 le New York Times a rapporté qu'un générateur de nombres aléatoires à courbe elliptique était devenu un standard du NIST sous l'influence de la NSA, avec une faiblesse délibérée dans l'algorithme et dans sa courbe recommandée. Moralité : la courbe et le standard auxquels on se fie comptent autant que les mathématiques.