Cryptographie sur les courbes elliptiques

Additions de points sur une courbe elliptique

La cryptographie sur les courbes elliptiques 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 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.

Histoire et motivation

Koblitz et Miller

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 large, 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 est une variété algébrique, c'est-à-dire une collection de points satisfaisant une équation du type $y^{2}=ax^{3}+bx+c$ avec $x,y$ 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. Qui plus est, ces opérations possèdent une interprétation géométrique. On peut donc calculer des « additions » de points sur la courbe.

Si le groupe est d'ordre premier, il est cyclique, c'est-à-dire qu'il existe un point $P=(x,y)$ qui engendre le groupe par additions successives. Cela est tout à fait analogue à la situation dans les corps finis, où un élément $g$ engendre le sous-groupe $\langle g\rangle =\{1,g^{2},\dotsc ,g^{k}\}$. Ainsi, toutes les constructions qui s'appuient sur un groupe du type $\langle g\rangle$ peuvent immédiatement utiliser à la place le groupe $E$ des points rationnels d'une courbe elliptique.

Par exemple, l'échange de clé de Diffie-Hellman se transporte directement en un algorithme sur courbes elliptiques.

Au moment de leur introduction en cryptographie par Koblitz et Miller, seuls les algorithmes génériques, comme l'algorithme de Shanks, pouvaient résoudre le logarithme discret dans le groupe de points d'une courbe elliptique. Cela rendait l'attaque beaucoup plus difficile sur une courbe elliptique que sur un corps de nombre. En conséquence, il était possible de conserver un niveau de sécurité satisfaisant, tout en diminuant la taille des données manipulées, d'où un gain de vitesse, une réduction des coûts d'implémentation et de transmission.

Plongements et attaque MOV

Il est toutefois apparu rapidement que certaines courbes elliptiques ne sont pas appropriées à cet usage. C'est notamment le cas des courbes supersingulières, pour lesquelles il est possible de ramener le problème du logarithme discret dans un corps fini (où on peut utiliser un algorithme plus efficace pour attaquer). D'une manière générale, toute courbe elliptique sur $\mathbb {F} _{q}$ possède un degré de plongement $k$, tel que le problème du logarithme discret sur la courbe se plonge dans un problème du logarithme discret sur $\mathbb {F} _{q}^{k}$. Ce plongement est donné par l'accouplement de Weil, un élémént efficacement calculable $e(P,Q)$ qui satisfait notamment $e(P,nQ)=e(P,Q)^{n}=e(nP,Q)$. C'est le principe de l'attaque MOV, décrite en 1993 par Menezes, Okamoto et Vanstone.

D'autres accouplements ont été employés pour monter des attaques similaires, notamment l'accouplement de Tate et ses variantes (Ate, Eta etc.).

La contre-mesure consiste à choisir, ou construire lorsque c'est possible, des courbes ayant un degré de plongement assez élevé.

Cryptographie à base de couplages

En 2002, Joux montre comment utiliser l'accouplement de Weil pour effectuer un échange de clé tripartite efficace. C'est le point de départ de la cryptographie à base de couplages, qui offre une manière nouvelle de construire des primitives cryptographiques, sous une hypothèse différente que celle de la difficulté du calcul du logarithme discret, et permet de concevoir des primitives pour lesquelles aucune autre implémentation n'est connue. Un autre intérêt de cette approche est la réalisation de schémas de signature numérique courts, comme le schéma de Boneh-Lynn-Shacham en 2004.

Endomorphismes efficaces : GLV et GLS

Sur certaines courbes, il existe en sus de l'opération d'addition entre points un endomorphisme $\phi :E\to E$ tel que $\phi (P)=\lambda P$ pour un certain $\lambda$. Si $\phi$ est efficacement calculable, par exemple une opération arithmétique simple sur les coordonnées, alors il permet un « raccourci » : au lieu de calculer $\lambda P=P+P+\cdots +P$ par une succession d'additions, on l'obtient en un seul coup par application de $\phi$. En fait, il est possible d'accélérer le calcul d'un multiple arbitraire $nP$ en décomposant $n=n_{1}+\lambda n_{2}$ et en calculant $nP=n_{1}P+n_{2}\phi (P)$ de sorte à répartir l'effort de calcul entre les deux parties. C'est l'idée de la méthode GLV dûe à Gallant, Lambert et Vanstone en 2001. En 2009, Galbraith, Lin et Scott décrivent une manière de construire des courbes ayant des endomorphismes efficaces, dites courbes GLS.

Cryptographie à base d'isogénies

Une isogénie est un morphisme de groupes entre les points de deux courbes elliptiques, qui préserve l'élément neutre. Les isogénies des courbes elliptiques possèdent une riche structure, appelée le volcan d'isogénies. Pour les courbes supersingulières, cette structure est un graphe de Ramanujan et il devient possible de construire des protocoles cryptographiques reposant sur les propriétés de ce graphe. Un des intérêts de ce point de vue c'est qu'il est complètement indépendant de la question du logarithme discret. Ainsi la cryptographie à base d'isogénies constitue l'une des pistes de recherche en cryptographie post-quantique.

Cryptographie sur courbes hyperelliptiques

Pour des raisons d'efficacité, il est possible de travailler sur des variétés abéliennes de genre plus grand (généralement de genre 2). Il existe sur les courbes de genre trop grand des méthodes d'indice qui permettent de résoudre le logarithme discret efficacement, ce qui diminue l'intérêt de telles courbes. La théorie des courbes hyperelliptique est moins bien comprise toutefois que celle des courbes elliptiques.

Courbes de Montgomery

Une particularité de l'expression $y^{2}=ax^{3}+bx+c$ est qu'il existe en général, pour une valeur de $x$ donnée, deux valeurs de $y$ possibles, symétriques par rapport à l'axe des abscisses. Ainsi en principe, il est possible de calculer sur une courbe elliptique uniquement à partir de la coordonnée $x$, si on ne se préoccupe pas du signe de $y$. Cette idée est rendue concrète par l'utilisation de courbes de Montgomery (aussi appelées surfaces de Kummer, surtout pour les courbes de genre plus grand) qui sont définies comme le quotient de la courbe par l'involution $y\mapsto -y$. L'intérêt de ne travailler qu'avec une coordonnée est une réduction de la quantité de données manipulées ou transmises, et pour des courbes bien choisies, une réduction du nombre d'opérations effectuées.

Courbes d'Edwards

Le calcul d'un multiple $nP=P+P+\cdots +P$ se fait généralement par addition et doublement. En général, il y a donc une différence entre l'opération d'addition et de doublement ; et une différence supplémentaire, dans chaque cas, entre une opération impliquant le point à l'infini et une opération ne l'impliquant pas. Ainsi celui qui veut implémenter de tels algorithmes doit être prudent, sans quoi il s'expose potentiellement à une attaque par canaux auxiliaires. Sur les courbes d'Edwards, découvertes par Harold Edwards en 2007 et introduites en cryptographie par Bernstein et Lange, il est possible d'utiliser une même opération pour addition, doublement, avec ou sans points à l'infini, ce qui élimine structurellement ces canaux auxiliaires et facilite l'implémentation.

Attaque en point initial et twists

Dans certains cas, par exemple sur une courbe de Montgomery, ou lors d'une attaque par fautes, il est possible qu'un utilisateur manipule sans le savoir un point qui n'appartient pas à la courbe elliptique. S'il applique néanmoins les opérations d'addition et de doublement, et révèle le résultat, il peut en fait renseigner l'adversaire sur des données secrètes. C'est notamment le cas lors d'une opération de signature, où le signataire calcule un point de la forme $P\mapsto kP$ avec $k$ secret. Dans des conditions normales, retrouver $k$ nécessite de résoudre un problème de logarithme discret, qui est difficile sur la courbe utilisée pour la signature ; mais si l'adversaire parvient à manipuler $P$ alors $kP$ peut appartenir à une courbe beaucoup plus faible, sur laquelle l'adversaire sait calculer le logarithme discret.

Dans le cas d'une courbe de Montgomery, l'adversaire peut aisément modifier un unique bit de la coordonnée $x$, ce qui force sa cible à travailler sur un twist quadratique de la courbe elliptique, c'est-à-dire une courbe d'équation $dy^{2}=ax^{3}+bx+c$ où $d$ n'est pas un résidu quadratique. Si une courbe n'est pas choisie avec précaution, il est possible d'attaquer au moyen de ses twists.

Factorisation par courbes elliptiques

La factorisation de Lenstra par les courbes elliptiques est un algorithme probabiliste rapide pour la décomposition en produit de facteurs premiers qui emploie les courbes elliptiques.

Courbes utilisées en cryptographie

• Curve25519, d'équation y² = x³ + 486662x² + x, une courbe de Montgomery conçue pour l'échange de clé de Diffie-Hellman.
• Ed25519, twist quadratique de la précédente, une courbe d'Edwards conçue pour la signature numérique ECDSA ou EdDSA.
• NIST P-256, définie par la NSA dans sa Suite B.
• secp256k1, utilisée pour les signatures Bitcoin, une courbe GLV.
• Familles Barreto-Naehrig, Miyaji-Nakabayashi-Takano, Brezing-Weng, Kachisa-Shaefer-Scott pour la cryptographie à base de couplages.
• Courbes supersingulières, utilisées pour la cryptographie à base d'isogénies.

Voir aussi

Bibliographie

• (en) Ian F. Blake, Gadiel Seroussi et Nigel P. Smart, Elliptic Curves in Cryptography, Cambridge University Press, 1999 (ISBN 9780521653749)
• (en) Darrel Hankerson, Alfred J. Menezes et Scott Vanstone, Guide to Elliptic Curve Cryptography, Springer-Verlag, 2004 (ISBN 9780387218465)
• (en) Lawrence C. Washington, Elliptic Curves: Number Theory and Cryptography, Chapman & Hall/CRC, 2003 (ISBN 9781420071474)

Articles connexes

• Cryptographie sur les courbes hyperelliptiques
• Certicom
• Cryptographie à base de couplages

Liens externes

• « Chiffrer avec des courbes elliptiques », sur bibmath.net
• (en) ECC a gentle introduction