Cryptographie sur les courbes elliptiques

Pour les articles homonymes, voir ECC.

Cet article est une ébauche concernant la cryptologie.

Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

Consultez la liste des tâches à accomplir en page de discussion.

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^[1],[2]. 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^[3].

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.

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 ${\displaystyle y^{2}=ax^{3}+bx+c}$ avec ${\displaystyle 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 définir une « addition » de points sur la courbe.

Si le groupe est d'ordre premier, il est cyclique, c'est-à-dire qu'il existe un point ${\displaystyle 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 ${\displaystyle g}$ engendre le sous-groupe ${\displaystyle \langle g\rangle =\{1,g^{2},\dotsc ,g^{k}\}}$. Ainsi, toutes les constructions qui s'appuient sur un groupe du type ${\displaystyle \langle g\rangle }$ peuvent immédiatement utiliser à la place le groupe ${\displaystyle 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.

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 ${\displaystyle \mathbb {F} _{q}}$ possède un degré de plongement ${\displaystyle k}$, tel que le problème du logarithme discret sur la courbe se plonge dans un problème du logarithme discret sur ${\displaystyle \mathbb {F} _{q}^{k}}$. Ce plongement est donné par l'accouplement de Weil, un élément efficacement calculable ${\displaystyle e(P,Q)}$ qui satisfait notamment ${\displaystyle 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^[4].

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

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

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 de 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 2001^[6].

Sur certaines courbes, il existe en sus de l'opération d'addition entre points un endomorphisme ${\displaystyle \phi :E\to E}$ tel que ${\displaystyle \phi (P)=\lambda P}$ pour un certain ${\displaystyle \lambda }$. Si ${\displaystyle \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 ${\displaystyle \lambda P=P+P+\cdots +P}$ par une succession d'additions, on l'obtient en un seul coup par application de ${\displaystyle \phi }$. En fait, il est possible d'accélérer le calcul d'un multiple arbitraire ${\displaystyle nP}$ en décomposant ${\displaystyle n=n_{1}+\lambda n_{2}}$ et en calculant ${\displaystyle 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 due à Gallant, Lambert et Vanstone en 2001^[7]. En 2009, Galbraith, Lin et Scott décrivent une manière de construire des courbes ayant des endomorphismes efficaces, dites courbes GLS^[8].

Une isogénie est un morphisme de groupes entre les points de deux courbes elliptiques, i.e. une fonction qui préserve la loi de groupe et 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.

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^[9], ce qui diminue l'intérêt de telles courbes. La théorie des courbes hyperelliptiques est moins bien comprise toutefois que celle des courbes elliptiques.

Une particularité de l'expression ${\displaystyle y^{2}=ax^{3}+bx+c}$ est qu'il existe en général, pour une valeur de ${\displaystyle x}$ donnée, deux valeurs de ${\displaystyle 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 ${\displaystyle x}$, si on ne se préoccupe pas du signe de ${\displaystyle 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 ${\displaystyle 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.

Le calcul d'un multiple ${\displaystyle 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^[10] et introduites en cryptographie par Bernstein et Lange^[11], il est possible d'utiliser une même opération pour addition, doublement, avec ou sans point à l'infini, ce qui élimine structurellement ces canaux auxiliaires et facilite l'implémentation.

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 ${\displaystyle P\mapsto kP}$ avec ${\displaystyle k}$ secret. Dans des conditions normales, retrouver ${\displaystyle 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 ${\displaystyle P}$ alors ${\displaystyle kP}$ peut appartenir à une courbe beaucoup plus faible, sur laquelle l'adversaire sait calculer le logarithme discret^[12].

Dans le cas d'une courbe de Montgomery, l'adversaire peut aisément modifier un unique bit de la coordonnée ${\displaystyle x}$, ce qui force sa cible à travailler sur un twist quadratique de la courbe elliptique, c'est-à-dire une courbe d'équation ${\displaystyle dy^{2}=ax^{3}+bx+c}$ où ${\displaystyle 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^[13].

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.

De nombreux systèmes basés sur le problème du logarithme discret ont naturellement été adaptés pour le groupe des courbes elliptiques.

• Echange de clefs: ECDH, ECMQV, ECQV, échange de clef entre trois parties
• Signatures numériques: ECDSA, Signature de Schnorr, EdDSA, ECKCDSA, ECRDSA, ECGDSA
• Chiffrement asymétrique: ECIES
• Chiffrement basé sur l'identité

• 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^[14].
• Courbes elliptiques supersingulières, utilisées pour la cryptographie à base d'isogénies^[15].

Le choix d'une courbe elliptique dépend beaucoup de l'application envisagée. On discute ici certains des paramètres importants concernant les courbes destinées à offrir un groupe dans lequel le calcul du logarithme discret est difficile.

• Le corps de base ${\displaystyle \mathbb {F} _{q}}$ sur lequel est construite la courbe. Dans la plupart des applications cryptographiques, on préfère utiliser ${\displaystyle q=p}$ premier, des attaques efficaces ayant été découvertes dans les corps binaires^[16],[17] et sur des extensions ${\displaystyle q=p^{k}}$ de petit degré^[18],[19].
• La complexité de l'algorithme rho de Pollard : il s'agit d'un algorithme probabiliste, qui calcule un logarithme discret dans un groupe de taille ${\displaystyle \ell }$ en temps espéré ${\displaystyle {\sqrt {\ell \pi /4}}}$^[20]. Cette attaque directe doit être au moins aussi difficile que le niveau de sécurité considéré.
• Le degré de plongement : le problème du logarithme discret sur la courbe, dans un groupe d'ordre ${\displaystyle \ell }$ peut être transféré à un problème dans un corps fini ${\displaystyle \mathbb {F} _{p^{k}}^{\times }}$, ou des méthodes plus efficaces de résolution sont connues. L'entier ${\displaystyle k}$, appelé degré de plongement, doit ainsi être assez large pour compenser ce phénomène, sans quoi une attaque est possible^{[4],[21],[22]}.
• L'existence de transferts additifs : dans certains cas, il est en fait possible de transférer le problème du logarithme discret dans le groupe additif ${\displaystyle \mathbb {F} _{p}}$ où il est très facile de le résoudre. On parle dans ce cas là de transfert additif, qui réduit de beaucoup la sécurité de la courbe^{[23],[24],[25]}. En particulier, les courbes supersingulières ne sont pas adaptées à la cryptographie reposant sur le logarithme discret.
• La taille du discriminant de multiplication complexe : ce nombre est défini comme ${\displaystyle D=(t^{2}-4p)/s^{2}}$ si ${\displaystyle (t^{2}-4p)/s^{2}=1{\bmod {4}}}$, et comme ${\displaystyle D=4(t^{2}-4p)/s^{2}}$ dans les autres cas, avec ${\displaystyle t}$ la trace du Frobenius et ${\displaystyle s}$ le plus grand entier tel que ${\displaystyle s^{2}\mid t^{2}-4p}$. Lorsque ${\displaystyle D}$ est petit, il existe des endomorphismes de multiplication complexe qui peuvent être utilisés pour accélérer légèrement l'algorithme rho.
• La taille des cofacteurs : la présence d'un cofacteur plus grand que 1, mais beaucoup plus petit que l'ordre du groupe, offre des possibilités d'attaque s'il est possible d'obtenir des points d'ordre petit^[26].
• Sécurité des twists : si une courbe admet des twists (quadratiques ou de plus haut degré) qui sont utilisés par le protocole considéré, ou qui peuvent apparaître (par exemple sur une courbe de Montgomery dont on ne retient qu'une coordonnée), alors il faut s'assurer que la courbe twistée offre elle aussi un niveau de sécurité suffisant.

• (en) Ian F. Blake, Gadiel Seroussi et Nigel P. Smart, Elliptic Curves in Cryptography, Cambridge University Press, 1999, 204 p. (ISBN 978-0-521-65374-9, lire en ligne)
• (en) Darrel Hankerson, Alfred J. Menezes et Scott Vanstone, Guide to Elliptic Curve Cryptography, Springer-Verlag, 2004, 312 p. (ISBN 978-0-387-21846-5, lire en ligne)
• (en) Lawrence C. Washington, Elliptic Curves : Number Theory and Cryptography, Chapman & Hall/CRC, 2003, 536 p. (ISBN 978-1-4200-7147-4, lire en ligne)

• Courbe elliptique supersingulière
• Cryptographie sur les courbes hyperelliptiques
• Certicom
• Cryptographie à base de couplages

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

• Portail de la cryptologie