nisse@lysator.liu.se (Niels Möller) writes:
Daiki Ueno ueno@gnu.org writes:
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.
For ecc_ah_to_a, this code was deleted, but it's still an issue for eddsa_sign. Maybe need special cases for both ed25519 and ed448 for now. Or some logic looking at the high limb of q.
These corner cases are a bit hard to test.
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.
I still think think this makes sense, but it's not clear to me what the usage really is.
Regards, /Niels