Cryptographie sur les courbes elliptiques

La cryptographie sur les courbes elliptiques (en anglais, elliptic curve cryptography ou ECC) regroupe un ensemble de techniques cryptographiques qui utilisent une ou plusieurs propriétés des courbes elliptiques, ou plus généralement d'une variété abélienne. L'usage des courbes elliptiques en cryptographie a été suggéré, de manière indépendante, par Neal Koblitz et Victor S. Miller en 1985. L'utilisation de ces propriétés permet d'améliorer les primitives cryptographiques existantes, par exemple en réduisant la taille des clés cryptographiques, ou de construire de nouvelles primitives cryptographiques qui n'étaient pas connues auparavant. En 2005, la NSA a officiellement annoncé la Suite B de ses recommandations cryptographiques, qui utilise exclusivement la cryptographie sur les courbes elliptiques pour l'échange de clé et les signatures numériques. Courbe elliptique La motivation initiale pour l'introduction des courbes elliptiques est qu'il existe des algorithmes sous-exponentiels pour résoudre le problème du logarithme discret sur les corps de nombres, en particulier le crible généralisé du corps de nombre. Or c'est sur la difficulté du logarithme discret que s'appuient une partie des primitives cryptographiques utilisées pour l'échange de clé ou la signature. Pour assurer un niveau de sécurité suffisant, il faut donc travailler dans des corps de nombres assez larges, ce qui implique un coût d'implémentation, de transmission, et un temps de calcul augmentés d'autant. En 1985, Koblitz et Miller remarquent que de tels algorithmes ne sont pas connus pour résoudre le logarithme discret dans le groupe des points rationnels d'une courbe elliptique, qui est une variété algébrique, c'est-à-dire une collection de points satisfaisant une équation du type avec appartenant à un corps fini. De manière remarquable, les solutions de cette équation peuvent être dotées d'une loi de groupe. Complétées d'un fictif « point à l'infini », qui joue le rôle de l'élément neutre, ces solutions forment un groupe abélien fini.