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[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.
Histoire et motivation
modifierKoblitz et Miller
modifierLa 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. 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 qui engendre le groupe par additions successives. Cela est tout à fait analogue à la situation dans les corps finis, où un élément engendre le sous-groupe . Ainsi, toutes les constructions qui s'appuient sur un groupe du type peuvent immédiatement utiliser à la place le groupe 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
modifierIl 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 possède un degré de plongement , tel que le problème du logarithme discret sur la courbe se plonge dans un problème du logarithme discret sur . Ce plongement est donné par l'accouplement de Weil, un élément efficacement calculable qui satisfait notamment . 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é.
Cryptographie à base de couplages
modifierEn 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].
Endomorphismes efficaces : GLV et GLS
modifierSur certaines courbes, il existe en sus de l'opération d'addition entre points un endomorphisme tel que pour un certain . Si est efficacement calculable, par exemple une opération arithmétique simple sur les coordonnées, alors il permet un « raccourci » : au lieu de calculer par une succession d'additions, on l'obtient en un seul coup par application de . En fait, il est possible d'accélérer le calcul d'un multiple arbitraire en décomposant et en calculant 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].
Cryptographie à base d'isogénies
modifierUne 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.
Cryptographie sur courbes hyperelliptiques
modifierPour 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.
Courbes de Montgomery
modifierUne particularité de l'expression est qu'il existe en général, pour une valeur de donnée, deux valeurs de 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 , si on ne se préoccupe pas du signe de . 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 . 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
modifierLe calcul d'un multiple 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.
Attaque en point initial et twists
modifierDans 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 avec secret. Dans des conditions normales, retrouver 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 alors 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 , ce qui force sa cible à travailler sur un twist quadratique de la courbe elliptique, c'est-à-dire une courbe d'équation où 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].
Factorisation par courbes elliptiques
modifierLa 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.
Cryptosystèmes basés sur les courbes elliptiques
modifierDe 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é
Courbes utilisées en cryptographie
modifier- Curve25519, d'équation y2 = x3 + 486662x2 + 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].
Sécurité et choix des courbes
modifierLe 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 sur lequel est construite la courbe. Dans la plupart des applications cryptographiques, on préfère utiliser premier, des attaques efficaces ayant été découvertes dans les corps binaires[16],[17] et sur des extensions 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 en temps espéré [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 peut être transféré à un problème dans un corps fini , ou des méthodes plus efficaces de résolution sont connues. L'entier , 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 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 si , et comme dans les autres cas, avec la trace du Frobenius et le plus grand entier tel que . Lorsque 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.
Notes et références
modifier- (en) Neal Koblitz, « Elliptic curve cryptosystems », Mathematics of Computation, no 48, , p. 203-209 (DOI 10.1090/S0025-5718-1987-0866109-5).
- (en) Victor S. Miller, « Use of elliptic curves in cryptography », Crypto, vol. 218, , p. 417-426 (DOI 10.1007/3-540-39799-X_31).
- (en) Henri Cohen, Gerhard Frey, Roberto Avanzi, Christophe Doche, Tanja Lange, Kim Nguyen et Frederik Vercauteren, Handbook of elliptic and hyperelliptic curve cryptography, Chapman & Hall/CRC, , 848 p. (ISBN 978-1-58488-518-4, OCLC 58546549, lire en ligne)
- (en) A. J. Menezes, T. Okamoto et S. A. Vanstone, « Reducing elliptic curve logarithms to logarithms in a finite field », IEEE Transactions on Information Theory, vol. 39, no 5, , p. 1639–1646 (ISSN 0018-9448, DOI 10.1109/18.259647, lire en ligne, consulté le )
- (en) Dan Boneh, « Pairing-Based Cryptography: Past, Present, and Future », Advances in Cryptology – ASIACRYPT 2012, Springer, Berlin, Heidelberg, lecture Notes in Computer Science, , p. 1–1 (ISBN 9783642349607, DOI 10.1007/978-3-642-34961-4_1, lire en ligne, consulté le )
- (en) Dan Boneh, Ben Lynn et Hovav Shacham, « Short Signatures from the Weil Pairing », Journal of Cryptology, vol. 17, no 4, , p. 297–319 (ISSN 0933-2790 et 1432-1378, DOI 10.1007/s00145-004-0314-9, lire en ligne, consulté le )
- (en) Robert P. Gallant, Robert J. Lambert et Scott A. Vanstone, « Faster Point Multiplication on Elliptic Curves with Efficient Endomorphisms », Advances in Cryptology — CRYPTO 2001, Springer, Berlin, Heidelberg, lecture Notes in Computer Science, , p. 190–200 (ISBN 3540446478, DOI 10.1007/3-540-44647-8_11, lire en ligne, consulté le )
- (en) Steven D. Galbraith, Xibin Lin et Michael Scott, « Endomorphisms for Faster Elliptic Curve Cryptography on a Large Class of Curves », Advances in Cryptology - EUROCRYPT 2009, Springer, Berlin, Heidelberg, lecture Notes in Computer Science, , p. 518–535 (ISBN 9783642010002, DOI 10.1007/978-3-642-01001-9_30, lire en ligne, consulté le )
- (en) Pierrick Gaudry, « An Algorithm for Solving the Discrete Log Problem on Hyperelliptic Curves », Advances in Cryptology — EUROCRYPT 2000, Springer, Berlin, Heidelberg, lecture Notes in Computer Science, , p. 19–34 (ISBN 3540455396, DOI 10.1007/3-540-45539-6_2, lire en ligne, consulté le )
- (en-US) Harold Edwards, « A normal form for elliptic curves », Bulletin of the American Mathematical Society, vol. 44, no 3, , p. 393–422 (ISSN 0273-0979 et 1088-9485, DOI 10.1090/s0273-0979-07-01153-6, lire en ligne, consulté le )
- (en) Daniel J. Bernstein et Tanja Lange, « Faster Addition and Doubling on Elliptic Curves », Advances in Cryptology – ASIACRYPT 2007, Springer, Berlin, Heidelberg, lecture Notes in Computer Science, , p. 29–50 (ISBN 9783540768999, DOI 10.1007/978-3-540-76900-2_3, lire en ligne, consulté le )
- (en) Ingrid Biehl, Bernd Meyer et Volker Müller, « Differential Fault Attacks on Elliptic Curve Cryptosystems », Advances in Cryptology — CRYPTO 2000, Springer, Berlin, Heidelberg, lecture Notes in Computer Science, , p. 131–146 (ISBN 3540445986, DOI 10.1007/3-540-44598-6_8, lire en ligne, consulté le )
- (en) P. A. Fouque, R. Lercier, D. Réal et F. Valette, « Fault Attack on Elliptic Curve Montgomery Ladder Implementation », 2008 5th Workshop on Fault Diagnosis and Tolerance in Cryptography, , p. 92–98 (DOI 10.1109/fdtc.2008.15, lire en ligne, consulté le )
- (en) David Freeman, Michael Scott et Edlyn Teske, « A Taxonomy of Pairing-Friendly Elliptic Curves », Journal of Cryptology, vol. 23, no 2, , p. 224–280 (ISSN 0933-2790 et 1432-1378, DOI 10.1007/s00145-009-9048-z, lire en ligne, consulté le )
- (en) Luca De Feo, David Jao et Jérôme Plût, « Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies », Journal of Mathematical Cryptology, vol. 8, no 3, (ISSN 1862-2984, DOI 10.1515/jmc-2012-0015, lire en ligne, consulté le )
- (en) Erich Wenger et Paul Wolfger, « Solving the Discrete Logarithm of a 113-Bit Koblitz Curve with an FPGA Cluster », Selected Areas in Cryptography -- SAC 2014, Springer, Cham, lecture Notes in Computer Science, , p. 363–379 (ISBN 9783319130507, DOI 10.1007/978-3-319-13051-4_22, lire en ligne, consulté le )
- (en) Erich Wenger et Paul Wolfger, « Harder, better, faster, stronger: elliptic curve discrete logarithm computations on FPGAs », Journal of Cryptographic Engineering, vol. 6, no 4, , p. 287–297 (ISSN 2190-8508 et 2190-8516, DOI 10.1007/s13389-015-0108-z, lire en ligne, consulté le )
- (en) Antoine Joux et Vanessa Vitse, « Elliptic Curve Discrete Logarithm Problem over Small Degree Extension Fields », Journal of Cryptology, vol. 26, no 1, , p. 119–143 (ISSN 0933-2790 et 1432-1378, DOI 10.1007/s00145-011-9116-z, lire en ligne, consulté le )
- (en) Antoine Joux et Vanessa Vitse, « Cover and Decomposition Index Calculus on Elliptic Curves Made Practical », Advances in Cryptology – EUROCRYPT 2012, Springer, Berlin, Heidelberg, lecture Notes in Computer Science, , p. 9–26 (ISBN 9783642290107, DOI 10.1007/978-3-642-29011-4_3, lire en ligne, consulté le )
- (en) Daniel J. Bernstein, Tanja Lange et Peter Schwabe, « On the Correct Use of the Negation Map in the Pollard rho Method », Public Key Cryptography – PKC 2011, Springer, Berlin, Heidelberg, lecture Notes in Computer Science, , p. 128–146 (ISBN 9783642193781, DOI 10.1007/978-3-642-19379-8_8, lire en ligne, consulté le )
- (en) Gerhard Frey et Hans-Georg Rück, « A Remark Concerning m-Divisibility and the Discrete Logarithm in the Divisor Class Group of Curves », Mathematics of Computation, vol. 62, no 206, , p. 865–874 (DOI 10.2307/2153546, lire en ligne, consulté le )
- (ru) I. A. Semaev, « О вычислении логарифмов на эллиптических кривых », Дискретная математика, vol. 8, no 1, , p. 65–71 (DOI 10.4213/dm516, lire en ligne, consulté le )
- (en-US) I. Semaev, « Evaluation of discrete logarithms in a group of 𝑝-torsion points of an elliptic curve in characteristic 𝑝 », Mathematics of Computation of the American Mathematical Society, vol. 67, no 221, , p. 353–356 (ISSN 0025-5718 et 1088-6842, DOI 10.1090/s0025-5718-98-00887-4, lire en ligne, consulté le )
- (en) Satoh, Takakazu et Kiyomichi Araki, « Fermat quotients and the polynomial time discrete log algorithm for anomalous elliptic curves », Rikkyo Daigaku sugaku zasshi 47, no. 1, , p. 81-92
- (en) N. P. Smart, « The Discrete Logarithm Problem on Elliptic Curves of Trace One », Journal of Cryptology, vol. 12, no 3, , p. 193–196 (ISSN 0933-2790 et 1432-1378, DOI 10.1007/s001459900052, lire en ligne, consulté le )
- (en) Chae Hoon Lim et Pil Joong Lee, « A key recovery attack on discrete log-based schemes using a prime order subgroup », Advances in Cryptology — CRYPTO '97, Springer, Berlin, Heidelberg, lecture Notes in Computer Science, , p. 249–263 (ISBN 9783540633846, DOI 10.1007/bfb0052240, lire en ligne, consulté le )
Voir aussi
modifierBibliographie
modifier- (en) Ian F. Blake, Gadiel Seroussi et Nigel P. Smart, Elliptic Curves in Cryptography, Cambridge University Press, , 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, , 312 p. (ISBN 978-0-387-21846-5, lire en ligne)
- (en) Lawrence C. Washington, Elliptic Curves : Number Theory and Cryptography, Chapman & Hall/CRC, , 536 p. (ISBN 978-1-4200-7147-4, lire en ligne)
Articles connexes
modifier- Courbe elliptique supersingulière
- Cryptographie sur les courbes hyperelliptiques
- Certicom
- Cryptographie à base de couplages
Liens externes
modifier- « Chiffrer avec des courbes elliptiques », sur bibmath.net
- (en) ECC a gentle introduction