nisse@lysator.liu.se (Niels Möller) writes:
Daiki Ueno ueno@gnu.org writes:
From 8bc6e735d4b40cbab5e187a28e01b63a04ecd92b Mon Sep 17 00:00:00 2001 From: Daiki Ueno dueno@redhat.com Date: Fri, 23 Jun 2017 17:26:18 +0200 Subject: [PATCH 2/4] Implement Curve448 primitives
This patch adds the necessary primitives for "curve448", defined in RFC 7748. Those primitives are namely: addition, doubling, scalar multiplication of the generator or an arbitrary point, inversion, and square root.
At last, I've now merged this onto the curve448 branch.
That's a great news, thank you Niels!
I see you've made some chenges to the needed scratch space, if I understand it correctly, you need to allow h_to_a_itch larger than mul_itch or mul_g_itch. You increase the value of ECC_ECDSA_SIGN_ITCH and add a new ECC_ECDSA_KEYGEN_ITCH. Can you comment on that?
The only reason ECDSA is affected at all by curve448, is that we have tests for ecdsa over the curve25519 and curve448, even though that's not the way these curves are intended to be used. Maybe that should just be deleted.
Indeed, I agree to remove the tests and affected parts in the library.
Performance for the scalar multiplication primitives seem to be slower than secp384 and slightly faster than secp521, and looking at point addition, it's slower than secp521. I hope that will be improved a quite a bit with an optimized mod operation for the curve448 prime.
While the interface is similar to curve25519, the implementation is slightly different. For curve25519, the Pippenger tables are generated through the coordinates on the Montgomery curve. On the other hand, the tables for curve448 are directly generated from the coordinates on the corresponding Edwards curve ("edwards448").
This is no longer the case, since the handling curve 25519 was changed early on, based on your patches back then.
Thank you. By the way, one thing I realized in my past rebase attempts is that, this commit doing the final reduction of a value by mod q seems to be incorrect for curve448 and should probably be reverted:
commit 6cf6abd68eb3d6c8c8e5ab217be734f9c537037f Author: Daiki Ueno dueno@redhat.com Date: Sat Aug 5 09:43:47 2017 +0200
ecc-eh-to-a, eddsa-sign: Parameterize hard-coded value
This allows the same code to be reused in curve448 and Ed448.
Signed-off-by: Daiki Ueno dueno@redhat.com
- shift = 252 - GMP_NUMB_BITS * (ecc->p.size - 1); + shift = ecc->q.bit_size - 1 - GMP_NUMB_BITS * (ecc->p.size - 1); cy = mpn_submul_1 (r, ecc->q.m, ecc->p.size, r[ecc->p.size-1] >> shift);
For curve25519, q is defined as:
2^252 + 0x14def9dea2f79cd65812631a5cf5d3ed
whose bit pattern starts with 0x1000, so r - q * (r>>252) should work.
On the other hand, for curve448, q is defined as:
2^446 - 0x8335dc163bb124b65129c96fde933d8d723a70aadc873d6d54a7bb0d
whose bit pattern starts with 0xFFFF. In that case the formula (r - q * (r>>445)) could be incorrect due to the accumulated errors by multiplication (i.e. q * 0x7FFF...).
Therefore, I suggest using r - q * (r>>446) instead, though it would introduce another hard-coded value.
Regards,