Courbe de Montgomery

En mathématiques, la courbe de Montgomery est une forme de courbe elliptique, introduite par Peter L. Montgomery en 1987^[1]. Si une courbe elliptique peut en général être présentée sous forme de Weierstrass, la forme de Montgomery permet d’accélérer les opérations d'addition sur la courbe dans les corps finis, ce qui est un avantage dans de nombreuses applications de cryptographie^[2],[3] et de factorisation^[4]. Les courbes de Montgomery sont également en équivalence birationnelle avec les courbes d'Edwards.

Définition

Une courbe de Montgomery d'équation ${\textstyle {\frac {1}{4}}y^{2}=x^{3}+2{,}5x^{2}+x}$ sur le corps ${\displaystyle \mathbb {R} }$.

Une courbe de Montgomery sur un corps K de caractéristique différente de 2 est définie par l'équation

${\displaystyle M_{A,B}:By^{2}=x^{3}+Ax^{2}+x}$

pour certain A ∈ K ∖ {−2, 2}, B ∈ K ∖ {0}, avec B(A² − 4) ≠ 0. Si les corps finis sont le lieu naturel des applications cryptographiques, la même équation est utilisée pour l'algorithme de Lenstra sur l'anneau ${\displaystyle \mathbb {Z} /(n)}$, et on peut également considérer la courbe sur le corps des rationnels ${\displaystyle \mathbb {Q} }$.

Arithmétique sur les courbes de Montgomery

L'introduction des courbes de Montgomery est motivée par l'existence d'un algorithme d'addition de points plus efficace que sur une courbe elliptique générale. Cet algorithme, découvert par Montgomery et qui porte aujourd'hui son nom, peut être vu comme un cas particulier d'addition sur la surface de Kummer correspondante.

Surface de Kummer et coordonnées de Montgomery

On se place déjà en coordonnées projectives : ${\displaystyle \mathbb {P} ^{2}K=\{(X:Y:Z)\mid (X,Y,Z)\in K\setminus (0,0,0)\}/\sim }$ avec ${\displaystyle (X:Y:Z)\sim (X':Y':Z')}$ si et seulement s'il existe ${\displaystyle \lambda \in K^{\times }}$ tel que ${\displaystyle X'=\lambda X,Y'=\lambda Y,Z'=\lambda Z}$ . L'idée de Montgomery et d'ensuite oublier la coordonnée ${\displaystyle Y}$, et d'écrire la loi de groupe uniquement en termes de ${\displaystyle X}$ et ${\displaystyle Z}$^{[note 1]}.

Dans les applications où seule la coordonnée ${\displaystyle x=X/Z}$ est utilisée, telle que l'échange de clé de Diffie-Hellman sur courbes elliptiques, cette information est suffisante : c'est pourquoi une courbe de Montgomery telle que Curve25519 peut tout à fait être utilisée dans ce contexte.

Échelle de Montgomery

Supposons que ${\displaystyle P_{n}=[n]P=(X_{n}:Z_{n})}$et ${\displaystyle P_{m}=[m]P=(X_{m}:Z_{m})}$avec ${\displaystyle n\neq m}$, alors on a directement

${\displaystyle {\begin{aligned}X_{m+n}&=Z_{m-n}((X_{m}-Z_{m})(X_{n}+Z_{n})+(X_{m}+Z_{m})(X_{n}-Z_{n}))^{2}\\Z_{m+n}&=X_{m-n}((X_{m}-Z_{m})(X_{n}+Z_{n})-(X_{m}+Z_{m})(X_{n}-Z_{n}))^{2}\end{aligned}}}$

c'est-à-dire trois multiplications et deux mises au carré dans ${\displaystyle K}$, les opérations d'addition et soustraction d'éléments de corps étant négligeables. Une formule pour le doublement (correspondant à ${\displaystyle m=n}$) est également aisément obtenue :

${\displaystyle {\begin{aligned}X_{2n}&=(X_{n}+Z_{n})^{2}(X_{n}-Z_{n})^{2}\\Z_{2n}&=(4X_{n}Z_{n})((X_{n}-Z_{n})^{2}+((A+2)/4)(4X_{n}Z_{n}))\end{aligned}}}$

où on a préalablement calculé ${\displaystyle 4X_{n}Z_{n}=(X_{n}+Z_{n})^{2}-(X_{n}-Z_{n})^{2}}$

Annexes

Notes

1. La courbe quotient l'automorphisme ${\displaystyle Y\mapsto -Y}$ est appelée courbe (ou plus généralement, surface) de Kummer. La loi résultante n'est pas à proprement parler une loi de groupe, mais elle suffit pour les applications cryptographiques considérées.

Références

1. (en) Peter L. Montgomery, « Speeding the Pollard and elliptic curve methods of factorization », Mathematics of Computation, vol. 48, n^o 177,‎ 1987, p. 243–264 (ISSN 0025-5718 et 1088-6842, DOI 10.1090/S0025-5718-1987-0866113-7, lire en ligne, consulté le 7 août 2018)
2. (en) Joost Renes et Benjamin Smith, « qDSA: Small and Secure Digital Signatures with Curve-Based Diffie–Hellman Key Pairs », dans Advances in Cryptology – ASIACRYPT 2017, Springer International Publishing, 2017 (ISBN 9783319706962, DOI 10.1007/978-3-319-70697-9_10, lire en ligne), p. 273–302
3. (en) Katsuyuki Okeya, Hiroyuki Kurumatani et Kouichi Sakurai, « Elliptic Curves with the Montgomery-Form and Their Cryptographic Applications », dans Public Key Cryptography, Springer Berlin Heidelberg, 2000 (ISBN 9783540669678, DOI 10.1007/978-3-540-46588-1_17, lire en ligne), p. 238–257
4. Montgomery 1987.

Bibliographie

• (en) Peter L. Montgomery, « Speeding the Pollard and Elliptic Curve Methods of Factorization », Mathematics of Computation, vol. 48, n^o 177,‎ 1987, p. 243–264 (DOI 10.2307/2007888, JSTOR 2007888)
• Daniel J. Bernstein, Peter Birkner, Marc Joye, Tanja Lange et Christiane Peters, Twisted Edwards Curves, Springer-Verlag Berlin Heidelberg, 2008, 414 p. (ISBN 978-3-540-68159-5, lire en ligne)
• Wouter Castryck, Steven Galbraith et Reza Rezaeian Farashahi, « Efficient Arithmetic on Elliptic Curves using a Mixed Edwards-Montgomery Representation », IACR Cryptology, vol. 2008,‎ 2008 (lire en ligne)

• Portail des mathématiques
• Portail de la cryptologie