[curves] Edwards: recovering x from y

[Nathaniel McCallum]

On Fri, 2015-10-23 at 08:45 -0700, Ron Garret wrote:
> On Oct 23, 2015, at 5:57 AM, Nathaniel McCallum <npmccallum at redhat.co
> m> wrote:
> 
> > Is there a generic way to do this?
> 
> Yes.  It’s just elementary algebra.  An Edwards curve has the form:
> 
> y^2 + x^2 = 1 + d(x^2)(y^2)
> 
> Just solve for x.  The answer turns out to be:
> 
> x = sqrt((y^2 -1) / (d(y^2) - 1))

Argh! So close. I messed up the sign on one of the subtractions.
Thanks! My code is working now.

> > The official Ed25519 code (in python) has a function for this but
> > it
> > depends on some constants and I can't infer what they are doing. In
> > particular, I'd like to recover x from y with Ed448.
> 
> The Ed25519 code is slightly different because Ed25519 is a twisted
> Edwards curve, i.e.
> 
> y^2 +a(x^2) = 1 + d(x^2)(y^2)
> 
> For Ed25519, a = -1 so you end up with d(y^2)+1 instead of d(y^2)-1
> in the denominator.  The rest of the black magic in the Ed25519
> xrecover routine is the modular square root computation.  I think
> that code makes some optimizations based on the value of the field
> modulus (i.e. 2^255-19) so you can’t use that code directly for Ed448
> (but I could be wrong about that).
> 
> You can always check your result by plugging X and Y into the
> original curve equation and see if the two sides are equal.
> 
> rg
>