Skip to content

Commit 2d5a186

Browse files
peterdettmansipa
peterdettman
authored and
sipa
committed
Apply effective-affine trick to precomp
1 parent 4f9791a commit 2d5a186

File tree

6 files changed

+53
-20
lines changed

6 files changed

+53
-20
lines changed

‎src/bench_internal.c‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -220,7 +220,7 @@ void bench_group_add_affine_var(void* arg) {
220220
bench_inv_t *data = (bench_inv_t*)arg;
221221

222222
for (i = 0; i < 200000; i++) {
223-
secp256k1_gej_add_ge_var(&data->gej_x, &data->gej_x, &data->ge_y);
223+
secp256k1_gej_add_ge_var(&data->gej_x, &data->gej_x, &data->ge_y, NULL);
224224
}
225225
}
226226

‎src/ecmult_gen_impl.h‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -40,7 +40,7 @@ static void secp256k1_ecmult_gen_context_build(secp256k1_ecmult_gen_context_t *c
4040
VERIFY_CHECK(secp256k1_ge_set_xo_var(&nums_ge, &nums_x, 0));
4141
secp256k1_gej_set_ge(&nums_gej, &nums_ge);
4242
/* Add G to make the bits in x uniformly distributed. */
43-
secp256k1_gej_add_ge_var(&nums_gej, &nums_gej, &secp256k1_ge_const_g);
43+
secp256k1_gej_add_ge_var(&nums_gej, &nums_gej, &secp256k1_ge_const_g, NULL);
4444
}
4545

4646
/* compute prec. */

‎src/ecmult_impl.h‎

Lines changed: 29 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -30,19 +30,41 @@
3030
/** Fill a table 'prej' with precomputed odd multiples of a. Prej will contain
3131
* the values [1*a,3*a,...,(2*n-1)*a], so it space for n values. zr[0] will
3232
* contain prej[0].z / a.z. The other zr[i] values = prej[i].z / prej[i-1].z.
33+
* Prej's Z values are undefined, except for the last value.
3334
*/
3435
static void secp256k1_ecmult_odd_multiples_table(int n, secp256k1_gej_t *prej, secp256k1_fe_t *zr, const secp256k1_gej_t *a) {
3536
secp256k1_gej_t d;
37+
secp256k1_ge_t a_ge, d_ge;
3638
int i;
3739

3840
VERIFY_CHECK(!a->infinity);
3941

40-
prej[0] = *a;
41-
secp256k1_gej_double_var(&d, &prej[0], NULL);
42-
secp256k1_fe_set_int(zr, 1);
42+
secp256k1_gej_double_var(&d, a, NULL);
43+
44+
/*
45+
* Perform the additions on an isomorphism where 'd' is affine: drop the z coordinate
46+
* of 'd', and scale the 1P starting value's x/y coordinates without changing its z.
47+
*/
48+
d_ge.x = d.x;
49+
d_ge.y = d.y;
50+
d_ge.infinity = 0;
51+
52+
secp256k1_ge_set_gej_zinv(&a_ge, a, &d.z);
53+
prej[0].x = a_ge.x;
54+
prej[0].y = a_ge.y;
55+
prej[0].z = a->z;
56+
prej[0].infinity = 0;
57+
58+
zr[0] = d.z;
4359
for (i = 1; i < n; i++) {
44-
secp256k1_gej_add_var(&prej[i], &prej[i-1], &d, &zr[i]);
60+
secp256k1_gej_add_ge_var(&prej[i], &prej[i-1], &d_ge, &zr[i]);
4561
}
62+
63+
/*
64+
* Each point in 'prej' has a z coordinate too small by a factor of 'd.z'. Only
65+
* the final point's z coordinate is actually used though, so just update that.
66+
*/
67+
secp256k1_fe_mul(&prej[n-1].z, &prej[n-1].z, &d.z);
4668
}
4769

4870
/** Fill a table 'pre' with precomputed odd multiples of a.
@@ -319,11 +341,11 @@ static void secp256k1_ecmult(const secp256k1_ecmult_context_t *ctx, secp256k1_ge
319341
#ifdef USE_ENDOMORPHISM
320342
if (i < bits_na_1 && (n = wnaf_na_1[i])) {
321343
ECMULT_TABLE_GET_GE(&tmpa, pre_a, n, WINDOW_A);
322-
secp256k1_gej_add_ge_var(r, r, &tmpa);
344+
secp256k1_gej_add_ge_var(r, r, &tmpa, NULL);
323345
}
324346
if (i < bits_na_lam && (n = wnaf_na_lam[i])) {
325347
ECMULT_TABLE_GET_GE(&tmpa, pre_a_lam, n, WINDOW_A);
326-
secp256k1_gej_add_ge_var(r, r, &tmpa);
348+
secp256k1_gej_add_ge_var(r, r, &tmpa, NULL);
327349
}
328350
if (i < bits_ng_1 && (n = wnaf_ng_1[i])) {
329351
ECMULT_TABLE_GET_GE_STORAGE(&tmpa, *ctx->pre_g, n, WINDOW_G);
@@ -336,7 +358,7 @@ static void secp256k1_ecmult(const secp256k1_ecmult_context_t *ctx, secp256k1_ge
336358
#else
337359
if (i < bits_na && (n = wnaf_na[i])) {
338360
ECMULT_TABLE_GET_GE(&tmpa, pre_a, n, WINDOW_A);
339-
secp256k1_gej_add_ge_var(r, r, &tmpa);
361+
secp256k1_gej_add_ge_var(r, r, &tmpa, NULL);
340362
}
341363
if (i < bits_ng && (n = wnaf_ng[i])) {
342364
ECMULT_TABLE_GET_GE_STORAGE(&tmpa, *ctx->pre_g, n, WINDOW_G);

‎src/group.h‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -103,8 +103,8 @@ static void secp256k1_gej_add_ge(secp256k1_gej_t *r, const secp256k1_gej_t *a, c
103103

104104
/** Set r equal to the sum of a and b (with b given in affine coordinates). This is more efficient
105105
than secp256k1_gej_add_var. It is identical to secp256k1_gej_add_ge but without constant-time
106-
guarantee, and b is allowed to be infinity. */
107-
static void secp256k1_gej_add_ge_var(secp256k1_gej_t *r, const secp256k1_gej_t *a, const secp256k1_ge_t *b);
106+
guarantee, and b is allowed to be infinity. If rzr is non-NULL, r->z = a->z * *rzr (a cannot be infinity in that case). */
107+
static void secp256k1_gej_add_ge_var(secp256k1_gej_t *r, const secp256k1_gej_t *a, const secp256k1_ge_t *b, secp256k1_fe_t *rzr);
108108

109109
/** Set r equal to the sum of a and b (with the inverse of b's Z coordinate passed as bzinv). */
110110
static void secp256k1_gej_add_zinv_var(secp256k1_gej_t *r, const secp256k1_gej_t *a, const secp256k1_ge_t *b, const secp256k1_fe_t *bzinv);

‎src/group_impl.h‎

Lines changed: 14 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -354,17 +354,18 @@ static void secp256k1_gej_add_var(secp256k1_gej_t *r, const secp256k1_gej_t *a,
354354
secp256k1_fe_add(&r->y, &h3);
355355
}
356356

357-
static void secp256k1_gej_add_ge_var(secp256k1_gej_t *r, const secp256k1_gej_t *a, const secp256k1_ge_t *b) {
357+
static void secp256k1_gej_add_ge_var(secp256k1_gej_t *r, const secp256k1_gej_t *a, const secp256k1_ge_t *b, secp256k1_fe_t *rzr) {
358358
/* 8 mul, 3 sqr, 4 normalize, 12 mul_int/add/negate */
359359
secp256k1_fe_t z12, u1, u2, s1, s2, h, i, i2, h2, h3, t;
360360
if (a->infinity) {
361-
r->infinity = b->infinity;
362-
r->x = b->x;
363-
r->y = b->y;
364-
secp256k1_fe_set_int(&r->z, 1);
361+
VERIFY_CHECK(rzr == NULL);
362+
secp256k1_gej_set_ge(r, b);
365363
return;
366364
}
367365
if (b->infinity) {
366+
if (rzr) {
367+
secp256k1_fe_set_int(rzr, 1);
368+
}
368369
*r = *a;
369370
return;
370371
}
@@ -379,16 +380,22 @@ static void secp256k1_gej_add_ge_var(secp256k1_gej_t *r, const secp256k1_gej_t *
379380
secp256k1_fe_negate(&i, &s1, 1); secp256k1_fe_add(&i, &s2);
380381
if (secp256k1_fe_normalizes_to_zero_var(&h)) {
381382
if (secp256k1_fe_normalizes_to_zero_var(&i)) {
382-
secp256k1_gej_double_var(r, a, NULL);
383+
secp256k1_gej_double_var(r, a, rzr);
383384
} else {
385+
if (rzr) {
386+
secp256k1_fe_set_int(rzr, 0);
387+
}
384388
r->infinity = 1;
385389
}
386390
return;
387391
}
388392
secp256k1_fe_sqr(&i2, &i);
389393
secp256k1_fe_sqr(&h2, &h);
390394
secp256k1_fe_mul(&h3, &h, &h2);
391-
r->z = a->z; secp256k1_fe_mul(&r->z, &r->z, &h);
395+
if (rzr) {
396+
*rzr = h;
397+
}
398+
secp256k1_fe_mul(&r->z, &a->z, &h);
392399
secp256k1_fe_mul(&t, &u1, &h2);
393400
r->x = t; secp256k1_fe_mul_int(&r->x, 2); secp256k1_fe_add(&r->x, &h3); secp256k1_fe_negate(&r->x, &r->x, 3); secp256k1_fe_add(&r->x, &i2);
394401
secp256k1_fe_negate(&r->y, &r->x, 5); secp256k1_fe_add(&r->y, &t); secp256k1_fe_mul(&r->y, &r->y, &i);

‎src/tests.c‎

Lines changed: 6 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1035,9 +1035,13 @@ void test_ge(void) {
10351035
}
10361036
secp256k1_ge_set_gej_var(&ref, &refj);
10371037

1038-
/* Test gej + ge (var). */
1039-
secp256k1_gej_add_ge_var(&resj, &gej[i1], &ge[i2]);
1038+
/* Test gej + ge with Z ratio result (var). */
1039+
secp256k1_gej_add_ge_var(&resj, &gej[i1], &ge[i2], secp256k1_gej_is_infinity(&gej[i1]) ? NULL : &zr);
10401040
ge_equals_gej(&ref, &resj);
1041+
if (!secp256k1_gej_is_infinity(&gej[i1]) && !secp256k1_gej_is_infinity(&resj)) {
1042+
secp256k1_fe_t zrz; secp256k1_fe_mul(&zrz, &zr, &gej[i1].z);
1043+
CHECK(secp256k1_fe_equal_var(&zrz, &resj.z));
1044+
}
10411045

10421046
/* Test gej + ge (var, with additional Z factor). */
10431047
{

0 commit comments

Comments
 (0)