[Cryptography] References for recovering the y coordinate in a montgomery ladder

[Phillip Hallam-Baker]

I have a problem, I am trying to add two RFC7748 aka CurveX25518 points and
it is only working half the time.

The problem here is that the montgomery ladder only uses the X point, the y
point is ignored. And that means that the sign on the y point is also lost.

Since the curve is symmetric about the x axis (y^2 = ...), guessing y is
positive (or even) and drawing a line between the two points is going to
give the correct x if both guesses are right or both are wrong. If one is
right and the other is wrong... oops.


I have found some discussion on the net on recovering the y coordinate from
the Montgomery ladder. But it is kinda icky to refer to random blog posts
in a spec. And not being a number theorist, it is going to take me quite a
while to get familiar with the notation in the original papers.

Can anyone point me to a crib?

Preferably with like working code in Perl or C# :-)


One of the accumulators is sU. The other seems to be (s+1)U. Since all I
need is the sign bit, I could try suck it and see.... but seems icky.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://www.metzdowd.com/pipermail/cryptography/attachments/20191108/81f95216/attachment.htm>