4
$\begingroup$

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.

$\endgroup$

1 Answer 1

5
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Thank you for clearing this up. So this means if I want consistent conversion I have to look at the $G_M \rightarrow G_E$ conversion and check which one of the two scaling factors produces the mapping I desire and then use this scaling factor consistently, correct? Your comments have made me leap forward in understanding this topic very much and I thank you thourougly for it. $\endgroup$ Commented Aug 10, 2015 at 20:38
  • 1
    $\begingroup$ I find myself saying yes incredibly often here :-) In this case, you prefer one of the choices over the other because it is then consistent not only with itself but with other people's usage. Nevertheless, any choice works, as long as you stick to it thereafter. $\endgroup$
    – ccorn
    Commented Aug 10, 2015 at 20:51

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .