[curves] Edwards: recovering x from y
Ron Garret
ron at flownet.com
Fri Oct 23 08:45:01 PDT 2015
On Oct 23, 2015, at 5:57 AM, Nathaniel McCallum <npmccallum at redhat.com> 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))
> 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
More information about the Curves
mailing list