Discussion:
Montgomery/Edwards curve generation
(too old to reply)
Conrado P. L. Gouvêa
2018-03-20 19:35:10 UTC
Permalink
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
Mike Hamburg
2018-03-20 19:50:08 UTC
Permalink
Hi Conrado,

This looks right to me. Note that if a and d are both square or both nonsquare, then ad = (A^2-4) is square. In that case, you can solve the quadratic x^2+Ax+1=0, so there are additional points on the Montgomery curve where y=0. These points have order 2, and so would be at infinity on the isomorphic Edwards curve. Therefore that Edwards curve can’t be complete. However, there might be an isogenous complete Edwards curve, using the same family of isogenies as Ed448-Goldilocks.

Cheers,
— Mike

Sent from my phone. Please excuse brevity and typos.
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
_______________________________________________
Curves mailing list
https://moderncrypto.org/mailman/listinfo/curves
Conrado P. L. Gouvêa
2018-03-21 13:14:54 UTC
Permalink
Thanks Mike! That was the final piece of the puzzle.

Cheers,

Conrado
Post by Mike Hamburg
Hi Conrado,
This looks right to me. Note that if a and d are both square or both
nonsquare, then ad = (A^2-4) is square. In that case, you can solve the
quadratic x^2+Ax+1=0, so there are additional points on the Montgomery
curve where y=0. These points have order 2, and so would be at infinity on
the isomorphic Edwards curve. Therefore that Edwards curve can’t be
complete. However, there might be an isogenous complete Edwards curve,
using the same family of isogenies as Ed448-Goldilocks.
Cheers,
— Mike
Sent from my phone. Please excuse brevity and typos.
Post by Conrado P. L. Gouvêa
Hi,
I've been studying the process used to generate Montgomery and Edwards
curves.
Post by Conrado P. L. Gouvêa
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.
Post by Conrado P. L. Gouvêa
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).
Post by Conrado P. L. Gouvêa
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.
Post by Conrado P. L. Gouvêa
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.
Post by Conrado P. L. Gouvêa
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).
Post by Conrado P. L. Gouvê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.
Post by Conrado P. L. Gouvêa
(This is how the second curve in the "Curve448" section of RFC 7748 was
generated)
Post by Conrado P. L. Gouvêa
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...
Post by Conrado P. L. Gouvêa
Is this reasoning right?
Thanks!
Conrado
_______________________________________________
Curves mailing list
https://moderncrypto.org/mailman/listinfo/curves
Loading...