On Thursday, May 23, 2019 1:41:47 PM PDT, Niels Möller wrote:
Wim Lewis <[email protected]> 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.
_______________________________________________
nettle-bugs mailing list
[email protected]
http://lists.lysator.liu.se/mailman/listinfo/nettle-bugs
