Daiki Ueno <u...@gnu.org> writes: > 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 <du...@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 <du...@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...).
Good catch! Right, this needs a bit more analysis. Fur curve25519, the subtraction can underflow (unlikely), which is addressed with the conditional addition a few lines down. > Therefore, I suggest using r - q * (r>>446) instead, though it would > introduce another hard-coded value. But for curve448, that subtraction will never underflow, instead it will sometimes produce a non-canonical result, r >= q. So correcting the shift isn't enough. On the other hand, this code should perhaps be deleted altogether, I think h_to_a with flags == 2 is used only for ecdsa. It might make sense to instead add a function pointer to struct ecc_modulo to do canonical reduction; that's needed in a few different places, not only here. 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
