4
$\begingroup$

I'm trying to understand the birational equivalence between Twisted Edwards and Montgomery curves and try to calculate some examples. In particular, as an example, I'm looking at the Ed25519 Twisted Edwards curve:

$$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}$$

This curve, according to Wikipedia, is birationally equivalent to the 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}$$

In Eurocrypt 2008, Daniel Bernstein et. al in their paper "Twisted Edwards Curves" (pg. 401) state that for a given Twisted Edwards Curve with parameters $a, d$ the birationally equivalent Montgomery curve is given by

$$A = 2\frac{a+d}{a-d} \quad\text{and}\quad B = \frac{4}{a-d}$$

When I try to calculate this, the calculation for $A$ works out, but the one for $B$ does not:

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

What is the mistake I'm making here and how would one convert from Twisted Edwards curve parameters to Montgomery and vice versa?

$\endgroup$

1 Answer 1

4
$\begingroup$

The only relevant aspect is that $\left(\frac{B}{p}\right)=+1$. Then you can find a scale factor $s\in\mathbb{F}_p^\times$ for the substitution $y=sY$ that makes the new $B' = Bs^2\equiv1\pmod{p}$.

$\endgroup$
2
  • $\begingroup$ Let me try to apply it to my example: B = -486664 which is a QR mod p. I can find a value s as you describe: $s = 16416487832636737118837039172820900612695230415163812779824790760673067034857$ and $B s^2 = 1 \mod p$ Now that I have the scale factor, what exactly do I do with it? Does it mean that the Montgomery curves with $B = 1$ and with $B = -486664$ are bijective to one another? If so, can I just always set $B = 1$ once I know that $\frac{4}{a-d}$ is a QR over p when I'm only interested in one birationally equivalent curve (and not necessarily a specific one)? $\endgroup$ Commented Aug 10, 2015 at 8:34
  • 1
    $\begingroup$ Oops, forgot to invert, your $s$ is correct. Yes, there is the bijection $y=sY$. And yes, if $B$ is a QR, then any QR will do as well, and if $B$ is a non-QR, any non-QR will do as well. $\endgroup$
    – ccorn
    Commented Aug 10, 2015 at 8:55

You must log in to answer this question.

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