Point conversion between Twisted Edwards and Montgomery curves

1.6k Views Asked by At

With the great help of Birational Equvalence of Twisted Edwards and Montgomery curves I know how to convert twisted Edwards curves into their birationally equivalent Montgomery counterparts where I can almost arbitrarily choose the curve coefficient B.

Again, say I have a source curve which is the twisted Edwards curve Ed25519:

$$ax^2 + y^2 = 1 + dx^2 y^2 \quad \text{where} \quad a = -1,\ \ d = \frac{-121665}{121666} \quad\text{over the finite field}\quad F_{2^{255}-19}$$

And I'm interested in the birationally equivalent Montgomery curve Curve25519:

$$By^2 = x^3 + A\,x^2 + x\quad\text{where}\quad A=486662,\ \ B = 1 \quad\text{over the finite field}\quad \mathbb{F}_{2^{255}-19}$$

I first calculate $A, B$ according to Bernstein et. al:

$$p = 2^{255}-19$$ $$A = 2\frac{a+d}{a-d} = 486662 \mod p$$ $$B = \frac{4}{a-d} = -486664 \neq 1 \mod p$$

My target $B$ is 1, so I determine a scaling factor:

$$s = \sqrt{B^{-1}} \mod p =$$ $$= \pm \small 16416487832636737118837039172820900612695230415163812779824790760673067034857$$

Now I want to convert a point from Ed25519 to Curve25519. For this I choose the generator point $G$ of Ed25519:

$$G = \small(15112221349535400772501151409588531511454012693041857206046113283949847762202, 46316835694926478169428394003475163141307993866256225615783033603165251855960)$$

And first calculate the coordinates of the equivalent Montgomery point of the original (unscaled) curve (i.e. $B = -486664$):

$$u = \frac{1 + y}{1-y} = 9 \mod p$$ $$v = \frac{1 + y}{(1 - y) x} = \small 46155036877857898950720737868668298259344786430663990124372813544693780678454 \mod p$$

Then I apply the scaling factor. This is where I run into a problem: There are two choices as the result of the square root operation which gave me $s$. The negative and positive root of the inverted $B$. Depending on which one I chose, I either get:

$$v_1 = \frac{v}{s_p} = \small 14781619447589544791020593568409986887264606134616475288964881837755586237401 \mod p$$

or

$$v_2 = \frac{v}{s_n} = 43114425171068552920764898935933967039370386198203806730763910166200978582548 \mod p$$

Both do fulfill the Curve25519 equation. How can I choose the correct one? In my case the generator $G$ of Curve25519 would be $(u, v_2)$.

Note that for this particular example (Ed25519 to Curve25519), Wikipedia gives a formula that explains the point conversion, but still doesn't answer how to determine the sign of the result of the square root. For this particular example I just know which scaling factor is currect, but I don't want just to solve this for these particular curves, but eventually be able to do the calculations for arbitrary curves. Therefore I'm looking for a generic solution.

1

There are 1 best solutions below

2
On BEST ANSWER

Both signs of $s$ are equally usable, but one has to make the choice first and then stick with that for consistency. Doing Montgomery elliptic curve arithmetic with the signs of all incoming $Y$ coordinates flipped produces correspondingly flipped outputs, so that is just an automorphism. Accordingly, both candidates for $G$ that you have considered are suitable as generator. If one of these is claimed to be the correct transformation result, this just reveals which $s$ the authors have used; they could as well have used the opposite sign.