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