Hello,
чт, 5 дек. 2019 г. в 00:18, Niels Möller nisse@lysator.liu.se:
dbaryshkov@gmail.com writes:
From: Dmitry Eremin-Solenikov dbaryshkov@gmail.com
Use jacobian/harmonized representation in ecc_point structure.
Can you explain what benefit you see from this?
Well, I've had two particular GOST curves in mind. They are defined in Weierstrass form, but have birationally equal Edwards curves that can be used for point addition. Converting to/from Edwards form during each operation doesn't look like a good solution.
E.g., ecc_point_mul takes a const struct ecc_point as input, and calls ecc->mul, which for the standard weierstrass curves is ecc_mul_a. This one is a loop including a call to ecc_add_jja, which assumes that the z coordinate is one.
(ecc_mul_a also calls ecc_a_to_j, which appears to write a z = 1 coordinate, in montgomery representation if appropriate. Even though the z coordinate is not used in this case. Maybe no callers of ecc_a_to_j needs the z coordiante? Needs some investigation. Reading the code a few years after it was written I wish I had been more thorough with documenting details input and output assumptions).
Doing ecc_point_mul starting with a point represented as (X, Y, Z) where Z is arbitrary will be slower, since it needs to take one more coordinate into account in the point addition.
It could be useful to work exclusively with jacobian or homogeneous coordinates if you want to make a series of operations on points, and only convert back to affine at the very end. But I'd like to see a clear use case before trying to optimize for that.
diff --git a/ecc-a-to-j.c b/ecc-a-to-j.c index 9fb0d2b80c41..895502e0fe20 100644 --- a/ecc-a-to-j.c +++ b/ecc-a-to-j.c @@ -40,11 +40,12 @@
void ecc_a_to_j (const struct ecc_curve *ecc,
mp_limb_t *r, const mp_limb_t *p)
mp_limb_t *r, const mpz_t x, const mpz_t y){ if (ecc->use_redc) {
mpn_copyd (r + ecc->p.size, p, 2*ecc->p.size);
mpz_limbs_copy (r + ecc->p.size, x, ecc->p.size);mpz_limbs_copy (r + 2 * ecc->p.size, y, ecc->p.size);I don't think we should use the mpz_t type in internal ecc functions. mpz_limbs_copy is not side-channnel silent, since organization of storage inside mpz_t is different depending on the leading bits.
Hmm, I don't see how mpz_t internal representation can be a threat. Also this function becomes less internal now, as it is called only from ecc_point_set().
If you wish, I can change a_to_j to copy available limbs and zero-fill rest of limbs instead of using mpz_t/mpz_limbs_copy().