On Thursday, May 23, 2019 1:41:47 PM PDT, Niels Möller wrote:
Wim Lewis wiml@hhhh.org writes:
Point compression is easy enough, but point decompression requires some curve math, potentially dependent on the specific curve, and some of it is redundant with what's already done in ecc_point_set().
I think what's needed is basically a mod p square root. See RFC 6090 for one way to do it.
One motivation for putting this code into Hogweed is that the common curves (P-256, -384, -512) all have primes which allow using a simple shortcut for computing square roots instead of using a general algorithm. If this is true for P-192 and P-224 as well (I haven't checked) then I can safely avoid writing the general algorithm at all. :)
There's already a slot in the curve structure for computing sqrt(u/v), although it's NULL for the non-Edwards curves. My thought was to just fill in this slot for the other curves as well, perhaps with an implementation that's optimized for v==1. Then ecc_point_set_compact() becomes a fairly simple function.
(Btw, it might make sense to adopt the name "compact representation" from that document;
Good thought.
For the details, it's good to have a specific reference to follow. There'a also been a feature request to convert points to and from ANSI x9.62, possibly related? Maybe converting to and from octest strings according to some specification is more useful as an advertised interface, than x coordinate + sign (not ruling out having both).
Indeed, that's my motivation --- I want to be able to work with protocols that use the SEC.1 / X9.62 "ECPoint" format, which can imply the ability to use "compressed" points; converting to and from octet-strings is easy enough by using functions like nettle_mpz_get_str_256(), and only the reconstruction of the y-coordinate requires any non-trivial code.
I'd be happy to contribute the point <--> octet-string functions I'm writing to Hogweed as well. I think that exposing a ecc_point_set_compact() function would be nice to have, even so. But I understand if you'd like to keep the API a little smaller.