[curves] Montgomery/Edwards curve generation

[Conrado P. L. Gouvêa]

Thanks Mike! That was the final piece of the puzzle.

Cheers,

Conrado

On Tue, Mar 20, 2018 at 4:50 PM, Mike Hamburg <mike at shiftleft.org> wrote:

> 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.
>
> > On Mar 20, 2018, at 12:35, Conrado P. L. Gouvêa <conradoplg at gmail.com>
> wrote:
> >
> > 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
> > Curves at moderncrypto.org
> > https://moderncrypto.org/mailman/listinfo/curves
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://moderncrypto.org/mail-archive/curves/attachments/20180321/8eb9d518/attachment.html>