I'm looking at implementing elliptic curve point compression a la SEC1 (admittedly, mostly to reduce the number of "feature not supported" code paths in a library, but it seems like a somewhat useful ability). Nettle/Hogweed already implements it internally for curve25519, but I want to implement it for the "secp" curves as well.
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(). So I was thinking about moving this functionality into Hogweed as a function along the lines of ecc_point_set_compressed(), which would take, instead of a y-coordinate, an int containing the sign/parity of the y-coordinate.
So my question for the list and for the maintainers is, is this a reasonable API to add to Hogweed? Is there interest in including it in Hogweed if I were to take the time to turn it into a tidy patch?
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. (Btw, it might make sense to adopt the name "compact representation" from that document; the name "point compression" was probably invented to make the good old math sound more technical and impressive in patent filings).
So I was thinking about moving this functionality into Hogweed as a function along the lines of ecc_point_set_compressed(), which would take, instead of a y-coordinate, an int containing the sign/parity of the y-coordinate.
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).
So my question for the list and for the maintainers is, is this a reasonable API to add to Hogweed? Is there interest in including it in Hogweed if I were to take the time to turn it into a tidy patch?
It could make sense. Do you have any concrete use cases?
Regards, /Niels
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.
On Thursday, May 23, 2019 3:54:08 PM PDT, Wim Lewis wrote:
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. :)
Ah, sadly P-224 is an exception.
This document does have optimized square root algorithms for each of the curves, including P-224:
https://apps.nsa.gov/iaarchive/library/ia-guidance/ia-solutions-for-classifi...
and also references a paper by djb on efficiently computing square roots in "annoying" prime fields such as P-224's.
On Thu, May 23, 2019 at 6:54 PM Wim Lewis wiml@hhhh.org wrote:
On Thursday, May 23, 2019 1:41:47 PM PDT, Niels Möller wrote:
...
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).
Related, one sharp edge with SEC.1 is, the the private key has the same length as order of the curve. That means, for example, a secp160 private key is 21 bytes instead of 20 bytes.
I've seen bug reports because of the difference.
The private key length was supposed to change to order of base point in a future version of SEC, but I did not see the change in SEC-2.
Also, I have a copy of x9.62 if you need something copied. I don't have a copy of P1363, though.
Jeff
I've pushed some work-in-progress to a git repository here: https://git.lysator.liu.se/wiml/nettle
There's more to be done, but I would appreciate any comments or feedback people might have. This is all the time I have available to put into it right now, but I hope to return to it before too long.
The changes add two new public functions: - ecc_point_set_compact() which is like ecc_point_set but accepts a point in compact form (X and Y's parity/sign rather than X and Y) - ecc_point_set_from_octets() which interprets a point converted to an octet string by the rules set out in X9.62 and SEC.1, including compressed, uncompressed, and hybrid points
I'm not terribly happy with the name ecc_point_set_compact(); does anyone have a suggestion for a better name?
Internals:
Decompression works for P-256, P-384, and P-521, but it still needs sqrt implementations for P-192 and P-224. P-224 will be much more complex than the others (the c^((p-3)/4) shortcut doesn't apply), but there's a paper by djb on computing square roots in it.
I added a second slot to the `ecc_modulo` struct to contain a sqrt(u) implementation (as opposed to the existing sqrt(u/v) implementation). The slot, and the typedef that describes functions in that slot, need better names.
I've pushed a few more changes to that repository; decompression now works for P-192 and P-224 as well.
I think this is done --- Niels, can you consider this a pull/review request, or would you rather I send a patch (or git-bundle) to the list?
The tests have almost but not quite 100% branch coverage. The few uncovered branches are either cases which I think are allowed by other functions' specification but not by their current implementation, or things that I think are mathematically impossible but can't trivially prove.
On Wed, May 29, 2019 at 01:25:08AM -0700, Wim Lewis wrote:
I've pushed some work-in-progress to a git repository here: https://git.lysator.liu.se/wiml/nettle
There's more to be done, but I would appreciate any comments or feedback people might have. This is all the time I have available to put into it right now, but I hope to return to it before too long.
The changes add two new public functions:
- ecc_point_set_compact() which is like ecc_point_set but accepts a point
in compact form (X and Y's parity/sign rather than X and Y)
- ecc_point_set_from_octets() which interprets a point converted to an
octet string by the rules set out in X9.62 and SEC.1, including compressed, uncompressed, and hybrid points
I'm not terribly happy with the name ecc_point_set_compact(); does anyone have a suggestion for a better name?
Internals:
Decompression works for P-256, P-384, and P-521, but it still needs sqrt implementations for P-192 and P-224. P-224 will be much more complex than the others (the c^((p-3)/4) shortcut doesn't apply), but there's a paper by djb on computing square roots in it.
I added a second slot to the `ecc_modulo` struct to contain a sqrt(u) implementation (as opposed to the existing sqrt(u/v) implementation). The slot, and the typedef that describes functions in that slot, need better names.
Now that 3.5.1 is out, is there a chance this could be looked at?
On Wed, May 29, 2019 at 01:25:08AM -0700, Wim Lewis wrote:
I've pushed some work-in-progress to a git repository here: https://git.lysator.liu.se/wiml/nettle
On Thursday, June 6, 2019 11:41:49 PM PDT, Wim Lewis wrote:
I've pushed a few more changes to that repository; decompression now works for P-192 and P-224 as well.
I think this is done --- Niels, can you consider this a pull/review request, or would you rather I send a patch (or git-bundle) to the list?
The tests have almost but not quite 100% branch coverage. The few uncovered branches are either cases which I think are allowed by other functions' specification but not by their current implementation, or things that I think are mathematically impossible but can't trivially prove.
Wim Lewis wiml@hhhh.org writes:
Now that 3.5.1 is out, is there a chance this could be looked at?
I'd like to have a closer look soon.
On Wed, May 29, 2019 at 01:25:08AM -0700, Wim Lewis wrote:
I've pushed some work-in-progress to a git repository here: https://git.lysator.liu.se/wiml/nettle
Is this still the place for the latest version?
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).
One general questions on the setting: Do you expect any of the new functions will be used for secret data (in contrast to public keys or signatures)? If so, we need to be particularly careful with side-channel leaks.
things that I think are mathematically impossible but can't trivially prove.
I would consider adding asserts for such conditions, to ensure that the library fails promptly and in a controlled fashion in case assumptions turn out to be wrong.
Regards, /Niels
nisse@lysator.liu.se (Niels Möller) writes:
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've now pushed some preparatory changes to the branch ecc-sqrt.
Regards, /Niels
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
nettle-bugs@lists.lysator.liu.se
-
Jeffrey Walton -
nisse＠lysator.liu.se -
Wim Lewis