Daiki Ueno ueno@gnu.org writes:
This patch series implements the Curve448 Diffie-Hellman protocol (RFC 7748) and the Ed448 signature scheme (RFC 8032). Although I tried to make it as close as possible to the Curve25519 and Ed25519 implementations, I had to add a few special cases, namely:
Thanks a lot for this work. I've started by applying the first 4 easy patches (currently on the master-updates branch).
- for Curve448, eccdata directly calculates points on the Edwards curve instead of the equivalent Montgomery curve
It would be nice to do it the same way. Are Montgomery computations the same, regardless of twist/no-twist?
- untwisted versions of ecc_add_eh* and ecc_dup_eh are added
Just a note that the twisted versions should at some point be updated to use more effficient formulas.
- the point decoding for Ed448 uses a different formula to recover u and v
Does it have to be done differently? I'll have to read up to find out. Efficient sqrt is going to be tailored for this prime to be most efficient.
Also, optimized implementation of modular reduction is currently missing, which is beyond my expertise. I would appreciate any suggestions regarding that.
If we do Euclidean reduction, we should use the property that
2^448 = 2^224 + 1 (mod)
And we'd need to use this twice to reduce a 896-bit product to 448 bits. On 64-bit machines, we'll get some shifting since 224 isn't a multiple of 64.
Redc might be slightly more efficient than the above reduction. Due to the structure, it might also work nicely to do a "half redc", reducing from both ends, and they might share the shift. I'll have to think through the details. But unlikely to be a big win over Euclidean.
Regards, /Niels