I've now merged Daiki's implementation of curve448, and I've done some followup cleanups: Moving and renaming edwards/twisted edwards functions, and using a shared ecc_mul_m function for both curve25519_mul and curve448_mul.
Pending work:
1. Eddsa signatures with curve448. Needs SHAKE support first (Daiki posted patches for this long ago).
2. Renaming of stuff using curve names consistently (recent patches by Dmitry). Preparation for new gost curves.
3. I'm considering changing the struct ecc_point representation to use montgomery representation of the for the individual coordinates, for primes where we use that. Then ecc_a_to_* will (almost?) be redundant. This is inline with also adding other coordinate changes here, if that will be needed for new curves. For the inverse functions, ecc_*_to_a, they're currently repsonsible both for inverting and eliminating the redundant z coordinate, and converting individual coordinates back from montgomery representation, when needed.
4. Adding support for compact representation (patches from Wim Lewis). I have some of the preparations merged on a branch, but I think it will be simpler if (3) is done first.
Regards, /Niels
ср, 25 дек. 2019 г. в 14:01, Niels Möller nisse@lysator.liu.se:
I've now merged Daiki's implementation of curve448, and I've done some followup cleanups: Moving and renaming edwards/twisted edwards functions, and using a shared ecc_mul_m function for both curve25519_mul and curve448_mul.
Great, thank you!
Pending work: 3. I'm considering changing the struct ecc_point representation to use montgomery representation of the for the individual coordinates, for primes where we use that. Then ecc_a_to_* will (almost?) be redundant. This is inline with also adding other coordinate changes here, if that will be needed for new curves. For the inverse functions, ecc_*_to_a, they're currently repsonsible both for inverting and eliminating the redundant z coordinate, and converting individual coordinates back from montgomery representation, when needed.
Great! This can also be a base for Weierstrass-with-Edwards-form curves.
- Adding support for compact representation (patches from Wim Lewis). I have some of the preparations merged on a branch, but I think it will be simpler if (3) is done first.
5. GOST DSA (RFC 5832, RFC 7091)
Code was tested in GnuTLS tree. Patches for Nettle are ready to be posted after patchset 2 (renames) is merged.
6. secp256k1
Code requires support for properly handling of a coefficient in eccdata.c. I have an implementation handling small values fitting into `int` variables. Also this will allow us to merge twisted and untwisted cases in eccdata.c removing code duplication. I have old patches ready which have to be rebased on top of master.
Regards, /Niels
-- Niels Möller. PGP-encrypted email is preferred. Keyid 368C6677. Internet email is subject to wholesale government surveillance.
nettle-bugs mailing list nettle-bugs@lists.lysator.liu.se http://lists.lysator.liu.se/mailman/listinfo/nettle-bugs
-- With best wishes Dmitry
nisse@lysator.liu.se (Niels Möller) writes:
- Eddsa signatures with curve448. Needs SHAKE support first (Daiki posted patches for this long ago).
Done!
- Renaming of stuff using curve names consistently (recent patches by Dmitry). Preparation for new gost curves.
Done! And GOSTDSA with the two easiest GOST curves now on the ecc-cost branch.
- I'm considering changing the struct ecc_point representation to use montgomery representation of the for the individual coordinates, for primes where we use that. Then ecc_a_to_* will (almost?) be redundant.
I still think ecc_a_to_* could be eliminated. They do redc conversions for curves that use that, and some copying of the unit field element.
While looking at this, I also noticed that it seems ecc->g is used only by tests. So this data could be removed from struct ecc_curve.
- Adding support for compact representation (patches from Wim Lewis). I have some of the preparations merged on a branch, but I think it will be simpler if (3) is done first.
I'm thinking that maybe it's reasonalbe to make a release soon, since we have a couple of new features, including ED448, GOSTDSA, SIV-CMAC. If we want to focus on getting a release out, I think both the compact representation change and additional GOST curves should be postponed until after the release. (The ecc_a_to_* cleanup above is also not that important from a release perspective, but I expect it to be fairly easy).
Regards, /Niels
On Sat, Jan 25, 2020 at 4:54 PM Niels Möller nisse@lysator.liu.se wrote:
I'm thinking that maybe it's reasonalbe to make a release soon, since we have a couple of new features, including ED448, GOSTDSA, SIV-CMAC. If we want to focus on getting a release out, I think both the compact representation change and additional GOST curves should be postponed until after the release. (The ecc_a_to_* cleanup above is also not that important from a release perspective, but I expect it to be fairly easy).
A release would be amazing! At this point gnutls bundles so much of nettle, and a release would allow us to have a version which is free of such bundling!
regards, Nikos
nisse@lysator.liu.se (Niels Möller) writes:
- I'm considering changing the struct ecc_point representation to use montgomery representation of the for the individual coordinates, for primes where we use that. Then ecc_a_to_* will (almost?) be redundant.
I still think ecc_a_to_* could be eliminated. They do redc conversions for curves that use that, and some copying of the unit field element.
I noticed an inconsistency here. For curve25519 and curve448, we do sqrt and inversion using powering. If using powering for other curves, as is needed for the sqrt operation with compact representation, it's desirable to do this with inputs and outputs in redc form, for moduli where we use redc.
However, inversion using side-channel silent gcdext, ecc_mod_inv, as is used by all other curves, is unaware of redc. Instead, there's some extra redc processing where it's called in ecc_j_to_a.
If we want to compute v = z^-1 (mod p), but in redc form with v' = vB and z' = zB, then we have
v z = 1 (mod p)
but
v' z' = B^2 (mod p)
So for redc curves we need to compute v' as
v' = (z' / B^2)^-1 (mod p)
Regards, /Niels
nisse@lysator.liu.se (Niels Möller) writes:
If we want to compute v = z^-1 (mod p), but in redc form with v' = vB and z' = zB, then we have
v z = 1 (mod p)
but
v' z' = B^2 (mod p)
So for redc curves we need to compute v' as
v' = (z' / B^2)^-1 (mod p)
I've pushed changes to do this to a new branch invert-with-redc. I think it makes things a bit simpler. I haven't yet looked at any benchmarks, but I'd hope to either see no change or an epsilon improvement.
Regards, /Niels
nettle-bugs@lists.lysator.liu.se
-
Dmitry Eremin-Solenikov -
Nikos Mavrogiannopoulos -
nisse＠lysator.liu.se