nisse@lysator.liu.se (Niels Möller) writes:
Wim Lewis wiml@hhhh.org writes:
Now that 3.5.1 is out, is there a chance this could be looked at?
Not sure in which order to do things. Maybe it will be best to first add the square root routines, with tests, and then add functions for converting between points and octet strings (and related utilities, if needed).
I have added sqrt functions on the branch ecc-sqrt (sorry for a forced update since previous attempt). So this is now on top of the changes to the inversion improvements from last year. All the secpxxxr1 curves are supported, but not the gost curves.
Tests pass (I have additional changes to enable randomized tests that I'd like to commit in a few days), except that sqrt(0) fails for the secp224 curve, where the implementation uses the full Tonelli-Shanks algorithm. I'm looking at the algorithm description in Cohen's book (A course in computational algebraic number theory), and it seems to not work for this case.
If we need sqrt(0), it must be handled as a special case. Also, unlike the other square root functions, it seems tricky to make the secp224r1 square root function side-channel silent. But I expect the main use case of point decompression is for public input (secrets in elliptic curve crypto tend to be scalars, not points), right?
Regards, /Niels