[email protected] (Niels Möller) writes:
> Daiki Ueno <[email protected]> writes:
>
>> From 8bc6e735d4b40cbab5e187a28e01b63a04ecd92b Mon Sep 17 00:00:00 2001
>> From: Daiki Ueno <[email protected]>
>> 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 <[email protected]>
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 <[email protected]>
- 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,
--
Daiki Ueno
_______________________________________________
nettle-bugs mailing list
[email protected]
http://lists.lysator.liu.se/mailman/listinfo/nettle-bugs
