Conrado P. L. Gouvêa

2018-03-20 19:35:10 UTC

Hi,

I've been studying the process used to generate Montgomery and Edwards

curves.

Generating Montgomery seems fairly straightforward. Pick B = 1 for speed

and select a suitable A that generates a curve / twist curve with

near-prime order. Only values such that (A-2) % 4 == 0 are considered, also

for speed.

Now suppose you want to create an Edwards curve E(a,d) from a certain

Montgomery M(A,B=1) curve found. The default mapping is to set a = (A + 2)

and d = (A - 2).

The first problem is: from what I understand, in order for the formulas to

be complete, "a" needs to be square and "d" needs to be nonsquare.

The second problem is: "a" is usually 1 or -1 for speed reasons.

Reading about it, I've kind of deduced that the following is the approach

taken, but I'd like to verify if this is correct.

If "a" is square and "d" nonsquare, you're almost done. Use the mapping

(x', y') -> (x*sqrt(a), y) and get the curve E(1,d/a) which is isomorphic

(birationally equivalent?) to E(a,d). If your prime is 1 modulo 4 then -1

is square, so you can target "a" == -1 which is faster. Use the mapping

(x', y') -> (-x*(sqrt(a)/sqrt(-1)), y) and get the curve E(-1, -d/a).

(This is how edwards25519 was generated)

If "a" is nonsquare and "d" square, you can use the mapping (x', y') -> (x,

1/y) and get the curve E(d, a). Then follow the previous procedure to get a

new "a" = 1 or "a" = -1.

(This is how the second curve in the "Curve448" section of RFC 7748 was

generated)

Now if "a" and "d" are both square or nonsquare, it seems you can't do

anything, though I haven't seen this explicitly mentioned anywhere...

Is this reasoning right?

Thanks!

Conrado

I've been studying the process used to generate Montgomery and Edwards

curves.

Generating Montgomery seems fairly straightforward. Pick B = 1 for speed

and select a suitable A that generates a curve / twist curve with

near-prime order. Only values such that (A-2) % 4 == 0 are considered, also

for speed.

Now suppose you want to create an Edwards curve E(a,d) from a certain

Montgomery M(A,B=1) curve found. The default mapping is to set a = (A + 2)

and d = (A - 2).

The first problem is: from what I understand, in order for the formulas to

be complete, "a" needs to be square and "d" needs to be nonsquare.

The second problem is: "a" is usually 1 or -1 for speed reasons.

Reading about it, I've kind of deduced that the following is the approach

taken, but I'd like to verify if this is correct.

If "a" is square and "d" nonsquare, you're almost done. Use the mapping

(x', y') -> (x*sqrt(a), y) and get the curve E(1,d/a) which is isomorphic

(birationally equivalent?) to E(a,d). If your prime is 1 modulo 4 then -1

is square, so you can target "a" == -1 which is faster. Use the mapping

(x', y') -> (-x*(sqrt(a)/sqrt(-1)), y) and get the curve E(-1, -d/a).

(This is how edwards25519 was generated)

If "a" is nonsquare and "d" square, you can use the mapping (x', y') -> (x,

1/y) and get the curve E(d, a). Then follow the previous procedure to get a

new "a" = 1 or "a" = -1.

(This is how the second curve in the "Curve448" section of RFC 7748 was

generated)

Now if "a" and "d" are both square or nonsquare, it seems you can't do

anything, though I haven't seen this explicitly mentioned anywhere...

Is this reasoning right?

Thanks!

Conrado