MPHELL  4.0.0
Conversion between Short Weierstrass Curve Model and Twisted Edwards Curves Model

The main idea between those conversion is to go through Montgomery curves, id est make a conversion from Short Weierstrass to Montgomery curves and then to Twisted Edwards Curves.

The Montgomery curves are in bijection with Twisted Edwards Curves, making this step the easiest one.

The Weierstrass curves have an isomorphism over a field K to a Montgomery curve when the Weierstrass curve has the 2 torsion defined over the field K, this isomorphism is determined under some conditions by the choice of a 2 torsion point and a sign choice.

The three main references for this part are:

  • [CS17] Montgomery curves and their arithmetic by Craig Costello and Benjamin Smith published in Journal of Cryptographic Engineering 2017 pages 1-14 viewable at this adress ;
  • [OKS00] Elliptic curves with the Montgomery-form and their cryptographic applications by Katsuyuki Okeya, Hiroyuki Kurumatani, et Kouichi Sakurai published in International Workshop on Public Key Cryptography. Springer, Berlin, Heidelberg, 2000. p. 238-257 viewable at this adress ;
  • [BBL+08] Twisted edwards curves by Daniel. J. Bernstein, Peter Birkner, Marc Joye, Tanja Lange, and Christiane Peters (2008, June) published in International Conference on Cryptology in Africa (pp. 389-405). Springer, Berlin, Heidelberg viewable at this adress .

Conversion between Short Weierstass Curve Model and Montgomery Curves Model

First of all to make this conversion from Short Weierstrass to Mongomery model it is needed to compute a point of order 2: $(\alpha,0)$ such that there exists beta in the field K which verifies:

  1. $ 3 \alpha^2 + a = \beta^2 $

Thus it is possible when there are 3 points of order 2 defined in K that only one of them satisfies this condition, some examples can be found in the vector tests of this software.

We denote the representations:

  1. $ B \times y^2 = x^3 + A \times x^2 + x $ for the Montgomery curve $ M_{A,B}$
  2. $ v^2 = u^3 + a \times u + b $ for the Short Weierstrass curve $W_{a,b}$

Then the choice of $ \alpha $ and $ \beta $ determines the following isomorphism between a Short Weierstrass curve and a Montgomery curve:

  1. $ (u,v) \mapsto (x,y)=((u-\alpha)/\beta,v/\beta) $ for the Montgomery curve $ M_{3 \alpha, 1 /\beta} $

For the reverse isomorphism id est the one from the Montgomery Curve $ M_{A,B}$ to the (unique) corresponding Short Weierstrass curve we have:

  1. $ (x,y) \mapsto (u,v)=((x+A/3)/B,x/B) $ for the Sort Weierstrass curve $ E_{1/B^2(1-A^2/3), (A/(3B^3)(2 A^2/9 -1))} $

It can be easier for the reader to understand this isomorphism to have in mind that

  1. $ (A/3B,1/B) \mapsto (\alpha,\beta) $

and using the fact we have then to solve the followings two equations to find a and b:

  1. $ 3 \alpha^2 + a = \beta^2; $
  2. $ \alpha^3 + a \times \alpha + b = 0. $

More details are in [CS17,§2.4], [OKS00,§4].

Conversion between Twisted Edwards Curve Model and Montgomery Curve Model

We denote the representations:

  1. $ B \times y^2 = x^3 + A \times x^2 + x $ for the Montgomery curve $ M_{A,B}$
  2. $ a u^2 + v^2 = 1 + d \times u^2 v^2 $ for the Twisted Edwards curve $Ed_{a,d}$

For the isomorphism from a Montgomery curve $ M_{A,B}$ to a twisted Edwards curve we use the following isomorphism:

  1. $ (x,y) \mapsto (u,v)=(x/y,(x-1)/(x+1)) $ for the twisted Edwards curve $ Ed_{(A + 2)/B,(A - 2)/B} $

The reverse isomorphism from the twisted Edwards curve $ Ed_{a,d} $ to a Montgomery curve is:

  1. $ (u,v) \mapsto (x,y)=((1+v)/(1-v),(1+v)/((1-v)u)) $ for the Montgomery curve $ M_{2(a + d)/(a-d),4/(a-d)} $.

More details are in [CS17,§2.5], [BBL+08,§3].