diff --git a/src/secp256k1/src/ecmult_const_impl.h b/src/secp256k1/src/ecmult_const_impl.h --- a/src/secp256k1/src/ecmult_const_impl.h +++ b/src/secp256k1/src/ecmult_const_impl.h @@ -15,8 +15,10 @@ /* This is like `ECMULT_TABLE_GET_GE` but is constant time */ #define ECMULT_CONST_TABLE_GET_GE(r,pre,n,w) do { \ int m; \ - int abs_n = (n) * (((n) > 0) * 2 - 1); \ - int idx_n = abs_n / 2; \ + /* Extract the sign-bit for a constant time absolute-value. */ \ + int mask = (n) >> (sizeof(n) * CHAR_BIT - 1); \ + int abs_n = ((n) + mask) ^ mask; \ + int idx_n = abs_n >> 1; \ secp256k1_fe neg_y; \ VERIFY_CHECK(((n) & 1) == 1); \ VERIFY_CHECK((n) >= -((1 << ((w)-1)) - 1)); \ @@ -172,6 +174,7 @@ for (i = 0; i < ECMULT_TABLE_SIZE(WINDOW_A); i++) { secp256k1_ge_mul_lambda(&pre_a_lam[i], &pre_a[i]); } + } #endif @@ -195,7 +198,7 @@ int n; int j; for (j = 0; j < WINDOW_A - 1; ++j) { - secp256k1_gej_double_nonzero(r, r, NULL); + secp256k1_gej_double_nonzero(r, r); } n = wnaf_1[i]; diff --git a/src/secp256k1/src/group.h b/src/secp256k1/src/group.h --- a/src/secp256k1/src/group.h +++ b/src/secp256k1/src/group.h @@ -95,14 +95,13 @@ /** Check whether a group element's y coordinate is a quadratic residue. */ static int secp256k1_gej_has_quad_y_var(const secp256k1_gej *a); -/** Set r equal to the double of a. If rzr is not-NULL, r->z = a->z * *rzr (where infinity means an implicit z = 0). - * a may not be zero. Constant time. */ -static void secp256k1_gej_double_nonzero(secp256k1_gej *r, const secp256k1_gej *a, secp256k1_fe *rzr); +/** Set r equal to the double of a, a cannot be infinity. Constant time. */ +static void secp256k1_gej_double_nonzero(secp256k1_gej *r, const secp256k1_gej *a); -/** Set r equal to the double of a. If rzr is not-NULL, r->z = a->z * *rzr (where infinity means an implicit z = 0). */ +/** Set r equal to the double of a. If rzr is not-NULL this sets *rzr such that r->z == a->z * *rzr (where infinity means an implicit z = 0). */ static void secp256k1_gej_double_var(secp256k1_gej *r, const secp256k1_gej *a, secp256k1_fe *rzr); -/** Set r equal to the sum of a and b. If rzr is non-NULL, r->z = a->z * *rzr (a cannot be infinity in that case). */ +/** Set r equal to the sum of a and b. If rzr is non-NULL this sets *rzr such that r->z == a->z * *rzr (a cannot be infinity in that case). */ static void secp256k1_gej_add_var(secp256k1_gej *r, const secp256k1_gej *a, const secp256k1_gej *b, secp256k1_fe *rzr); /** Set r equal to the sum of a and b (with b given in affine coordinates, and not infinity). */ @@ -110,7 +109,7 @@ /** Set r equal to the sum of a and b (with b given in affine coordinates). This is more efficient than secp256k1_gej_add_var. It is identical to secp256k1_gej_add_ge but without constant-time - 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). */ + guarantee, and b is allowed to be infinity. If rzr is non-NULL this sets *rzr such that r->z == a->z * *rzr (a cannot be infinity in that case). */ static void secp256k1_gej_add_ge_var(secp256k1_gej *r, const secp256k1_gej *a, const secp256k1_ge *b, secp256k1_fe *rzr); /** Set r equal to the sum of a and b (with the inverse of b's Z coordinate passed as bzinv). */ diff --git a/src/secp256k1/src/group_impl.h b/src/secp256k1/src/group_impl.h --- a/src/secp256k1/src/group_impl.h +++ b/src/secp256k1/src/group_impl.h @@ -303,7 +303,7 @@ return secp256k1_fe_equal_var(&y2, &x3); } -static void secp256k1_gej_double_var(secp256k1_gej *r, const secp256k1_gej *a, secp256k1_fe *rzr) { +static SECP256K1_INLINE void secp256k1_gej_double_nonzero(secp256k1_gej *r, const secp256k1_gej *a) { /* Operations: 3 mul, 4 sqr, 0 normalize, 12 mul_int/add/negate. * * Note that there is an implementation described at @@ -312,29 +312,9 @@ * mainly because it requires more normalizations. */ secp256k1_fe t1,t2,t3,t4; - /** For secp256k1, 2Q is infinity if and only if Q is infinity. This is because if 2Q = infinity, - * Q must equal -Q, or that Q.y == -(Q.y), or Q.y is 0. For a point on y^2 = x^3 + 7 to have - * y=0, x^3 must be -7 mod p. However, -7 has no cube root mod p. - * - * Having said this, if this function receives a point on a sextic twist, e.g. by - * a fault attack, it is possible for y to be 0. This happens for y^2 = x^3 + 6, - * since -6 does have a cube root mod p. For this point, this function will not set - * the infinity flag even though the point doubles to infinity, and the result - * point will be gibberish (z = 0 but infinity = 0). - */ - r->infinity = a->infinity; - if (r->infinity) { - if (rzr != NULL) { - secp256k1_fe_set_int(rzr, 1); - } - return; - } - if (rzr != NULL) { - *rzr = a->y; - secp256k1_fe_normalize_weak(rzr); - secp256k1_fe_mul_int(rzr, 2); - } + VERIFY_CHECK(!secp256k1_gej_is_infinity(a)); + r->infinity = 0; secp256k1_fe_mul(&r->z, &a->z, &a->y); secp256k1_fe_mul_int(&r->z, 2); /* Z' = 2*Y*Z (2) */ @@ -358,9 +338,32 @@ secp256k1_fe_add(&r->y, &t2); /* Y' = 36*X^3*Y^2 - 27*X^6 - 8*Y^4 (4) */ } -static SECP256K1_INLINE void secp256k1_gej_double_nonzero(secp256k1_gej *r, const secp256k1_gej *a, secp256k1_fe *rzr) { - VERIFY_CHECK(!secp256k1_gej_is_infinity(a)); - secp256k1_gej_double_var(r, a, rzr); +static void secp256k1_gej_double_var(secp256k1_gej *r, const secp256k1_gej *a, secp256k1_fe *rzr) { + /** For secp256k1, 2Q is infinity if and only if Q is infinity. This is because if 2Q = infinity, + * Q must equal -Q, or that Q.y == -(Q.y), or Q.y is 0. For a point on y^2 = x^3 + 7 to have + * y=0, x^3 must be -7 mod p. However, -7 has no cube root mod p. + * + * Having said this, if this function receives a point on a sextic twist, e.g. by + * a fault attack, it is possible for y to be 0. This happens for y^2 = x^3 + 6, + * since -6 does have a cube root mod p. For this point, this function will not set + * the infinity flag even though the point doubles to infinity, and the result + * point will be gibberish (z = 0 but infinity = 0). + */ + if (a->infinity) { + r->infinity = 1; + if (rzr != NULL) { + secp256k1_fe_set_int(rzr, 1); + } + return; + } + + if (rzr != NULL) { + *rzr = a->y; + secp256k1_fe_normalize_weak(rzr); + secp256k1_fe_mul_int(rzr, 2); + } + + secp256k1_gej_double_nonzero(r, a); } static void secp256k1_gej_add_var(secp256k1_gej *r, const secp256k1_gej *a, const secp256k1_gej *b, secp256k1_fe *rzr) { diff --git a/src/secp256k1/src/tests_exhaustive.c b/src/secp256k1/src/tests_exhaustive.c --- a/src/secp256k1/src/tests_exhaustive.c +++ b/src/secp256k1/src/tests_exhaustive.c @@ -142,7 +142,7 @@ for (i = 0; i < order; i++) { secp256k1_gej tmp; if (i > 0) { - secp256k1_gej_double_nonzero(&tmp, &groupj[i], NULL); + secp256k1_gej_double_nonzero(&tmp, &groupj[i]); ge_equals_gej(&group[(2 * i) % order], &tmp); } secp256k1_gej_double_var(&tmp, &groupj[i], NULL); diff --git a/src/secp256k1/src/util.h b/src/secp256k1/src/util.h --- a/src/secp256k1/src/util.h +++ b/src/secp256k1/src/util.h @@ -14,6 +14,7 @@ #include #include #include +#include typedef struct { void (*fn)(const char *text, void* data);