Changeset View
Changeset View
Standalone View
Standalone View
src/secp256k1/src/ecmult_const_impl.h
Show First 20 Lines • Show All 42 Lines • ▼ Show 20 Lines | |||||
* - the number of words set is always WNAF_SIZE(w) + 1 | * - the number of words set is always WNAF_SIZE(w) + 1 | ||||
* | * | ||||
* Adapted from `The Width-w NAF Method Provides Small Memory and Fast Elliptic Scalar | * Adapted from `The Width-w NAF Method Provides Small Memory and Fast Elliptic Scalar | ||||
* Multiplications Secure against Side Channel Attacks`, Okeya and Tagaki. M. Joye (Ed.) | * Multiplications Secure against Side Channel Attacks`, Okeya and Tagaki. M. Joye (Ed.) | ||||
* CT-RSA 2003, LNCS 2612, pp. 328-443, 2003. Springer-Verlagy Berlin Heidelberg 2003 | * CT-RSA 2003, LNCS 2612, pp. 328-443, 2003. Springer-Verlagy Berlin Heidelberg 2003 | ||||
* | * | ||||
* Numbers reference steps of `Algorithm SPA-resistant Width-w NAF with Odd Scalar` on pp. 335 | * Numbers reference steps of `Algorithm SPA-resistant Width-w NAF with Odd Scalar` on pp. 335 | ||||
*/ | */ | ||||
static int secp256k1_wnaf_const(int *wnaf, secp256k1_scalar s, int w) { | static int secp256k1_wnaf_const(int *wnaf, secp256k1_scalar s, int w, int size) { | ||||
int global_sign; | int global_sign; | ||||
int skew = 0; | int skew = 0; | ||||
int word = 0; | int word = 0; | ||||
/* 1 2 3 */ | /* 1 2 3 */ | ||||
int u_last; | int u_last; | ||||
int u; | int u; | ||||
int flip; | int flip; | ||||
int bit; | int bit; | ||||
secp256k1_scalar neg_s; | secp256k1_scalar neg_s; | ||||
int not_neg_one; | int not_neg_one; | ||||
/* Note that we cannot handle even numbers by negating them to be odd, as is | /* Note that we cannot handle even numbers by negating them to be odd, as is | ||||
* done in other implementations, since if our scalars were specified to have | * done in other implementations, since if our scalars were specified to have | ||||
* width < 256 for performance reasons, their negations would have width 256 | * width < 256 for performance reasons, their negations would have width 256 | ||||
* and we'd lose any performance benefit. Instead, we use a technique from | * and we'd lose any performance benefit. Instead, we use a technique from | ||||
* Section 4.2 of the Okeya/Tagaki paper, which is to add either 1 (for even) | * Section 4.2 of the Okeya/Tagaki paper, which is to add either 1 (for even) | ||||
* or 2 (for odd) to the number we are encoding, returning a skew value indicating | * or 2 (for odd) to the number we are encoding, returning a skew value indicating | ||||
* this, and having the caller compensate after doing the multiplication. */ | * this, and having the caller compensate after doing the multiplication. | ||||
* | |||||
/* Negative numbers will be negated to keep their bit representation below the maximum width */ | * In fact, we _do_ want to negate numbers to minimize their bit-lengths (and in | ||||
* particular, to ensure that the outputs from the endomorphism-split fit into | |||||
* 128 bits). If we negate, the parity of our number flips, inverting which of | |||||
* {1, 2} we want to add to the scalar when ensuring that it's odd. Further | |||||
* complicating things, -1 interacts badly with `secp256k1_scalar_cadd_bit` and | |||||
* we need to special-case it in this logic. */ | |||||
flip = secp256k1_scalar_is_high(&s); | flip = secp256k1_scalar_is_high(&s); | ||||
/* We add 1 to even numbers, 2 to odd ones, noting that negation flips parity */ | /* We add 1 to even numbers, 2 to odd ones, noting that negation flips parity */ | ||||
bit = flip ^ !secp256k1_scalar_is_even(&s); | bit = flip ^ !secp256k1_scalar_is_even(&s); | ||||
/* We check for negative one, since adding 2 to it will cause an overflow */ | /* We check for negative one, since adding 2 to it will cause an overflow */ | ||||
secp256k1_scalar_negate(&neg_s, &s); | secp256k1_scalar_negate(&neg_s, &s); | ||||
not_neg_one = !secp256k1_scalar_is_one(&neg_s); | not_neg_one = !secp256k1_scalar_is_one(&neg_s); | ||||
secp256k1_scalar_cadd_bit(&s, bit, not_neg_one); | secp256k1_scalar_cadd_bit(&s, bit, not_neg_one); | ||||
/* If we had negative one, flip == 1, s.d[0] == 0, bit == 1, so caller expects | /* If we had negative one, flip == 1, s.d[0] == 0, bit == 1, so caller expects | ||||
* that we added two to it and flipped it. In fact for -1 these operations are | * that we added two to it and flipped it. In fact for -1 these operations are | ||||
* identical. We only flipped, but since skewing is required (in the sense that | * identical. We only flipped, but since skewing is required (in the sense that | ||||
* the skew must be 1 or 2, never zero) and flipping is not, we need to change | * the skew must be 1 or 2, never zero) and flipping is not, we need to change | ||||
* our flags to claim that we only skewed. */ | * our flags to claim that we only skewed. */ | ||||
global_sign = secp256k1_scalar_cond_negate(&s, flip); | global_sign = secp256k1_scalar_cond_negate(&s, flip); | ||||
global_sign *= not_neg_one * 2 - 1; | global_sign *= not_neg_one * 2 - 1; | ||||
skew = 1 << bit; | skew = 1 << bit; | ||||
/* 4 */ | /* 4 */ | ||||
u_last = secp256k1_scalar_shr_int(&s, w); | u_last = secp256k1_scalar_shr_int(&s, w); | ||||
while (word * w < WNAF_BITS) { | while (word * w < size) { | ||||
int sign; | int sign; | ||||
int even; | int even; | ||||
/* 4.1 4.4 */ | /* 4.1 4.4 */ | ||||
u = secp256k1_scalar_shr_int(&s, w); | u = secp256k1_scalar_shr_int(&s, w); | ||||
/* 4.2 */ | /* 4.2 */ | ||||
even = ((u & 1) == 0); | even = ((u & 1) == 0); | ||||
sign = 2 * (u_last > 0) - 1; | sign = 2 * (u_last > 0) - 1; | ||||
u += sign * even; | u += sign * even; | ||||
u_last -= sign * even * (1 << w); | u_last -= sign * even * (1 << w); | ||||
/* 4.3, adapted for global sign change */ | /* 4.3, adapted for global sign change */ | ||||
wnaf[word++] = u_last * global_sign; | wnaf[word++] = u_last * global_sign; | ||||
u_last = u; | u_last = u; | ||||
} | } | ||||
wnaf[word] = u * global_sign; | wnaf[word] = u * global_sign; | ||||
VERIFY_CHECK(secp256k1_scalar_is_zero(&s)); | VERIFY_CHECK(secp256k1_scalar_is_zero(&s)); | ||||
VERIFY_CHECK(word == WNAF_SIZE(w)); | VERIFY_CHECK(word == WNAF_SIZE_BITS(size, w)); | ||||
return skew; | return skew; | ||||
} | } | ||||
static void secp256k1_ecmult_const(secp256k1_gej *r, const secp256k1_ge *a, const secp256k1_scalar *scalar, int size) { | |||||
static void secp256k1_ecmult_const(secp256k1_gej *r, const secp256k1_ge *a, const secp256k1_scalar *scalar) { | |||||
secp256k1_ge pre_a[ECMULT_TABLE_SIZE(WINDOW_A)]; | secp256k1_ge pre_a[ECMULT_TABLE_SIZE(WINDOW_A)]; | ||||
secp256k1_ge tmpa; | secp256k1_ge tmpa; | ||||
secp256k1_fe Z; | secp256k1_fe Z; | ||||
int skew_1; | int skew_1; | ||||
int wnaf_1[1 + WNAF_SIZE(WINDOW_A - 1)]; | |||||
#ifdef USE_ENDOMORPHISM | #ifdef USE_ENDOMORPHISM | ||||
secp256k1_ge pre_a_lam[ECMULT_TABLE_SIZE(WINDOW_A)]; | secp256k1_ge pre_a_lam[ECMULT_TABLE_SIZE(WINDOW_A)]; | ||||
int wnaf_lam[1 + WNAF_SIZE(WINDOW_A - 1)]; | int wnaf_lam[1 + WNAF_SIZE(WINDOW_A - 1)]; | ||||
int skew_lam; | int skew_lam; | ||||
secp256k1_scalar q_1, q_lam; | secp256k1_scalar q_1, q_lam; | ||||
#endif | #endif | ||||
int wnaf_1[1 + WNAF_SIZE(WINDOW_A - 1)]; | |||||
int i; | int i; | ||||
secp256k1_scalar sc = *scalar; | secp256k1_scalar sc = *scalar; | ||||
/* build wnaf representation for q. */ | /* build wnaf representation for q. */ | ||||
int rsize = size; | |||||
#ifdef USE_ENDOMORPHISM | #ifdef USE_ENDOMORPHISM | ||||
if (size > 128) { | |||||
rsize = 128; | |||||
/* split q into q_1 and q_lam (where q = q_1 + q_lam*lambda, and q_1 and q_lam are ~128 bit) */ | /* split q into q_1 and q_lam (where q = q_1 + q_lam*lambda, and q_1 and q_lam are ~128 bit) */ | ||||
secp256k1_scalar_split_lambda(&q_1, &q_lam, &sc); | secp256k1_scalar_split_lambda(&q_1, &q_lam, &sc); | ||||
skew_1 = secp256k1_wnaf_const(wnaf_1, q_1, WINDOW_A - 1); | skew_1 = secp256k1_wnaf_const(wnaf_1, q_1, WINDOW_A - 1, 128); | ||||
skew_lam = secp256k1_wnaf_const(wnaf_lam, q_lam, WINDOW_A - 1); | skew_lam = secp256k1_wnaf_const(wnaf_lam, q_lam, WINDOW_A - 1, 128); | ||||
#else | } else | ||||
skew_1 = secp256k1_wnaf_const(wnaf_1, sc, WINDOW_A - 1); | #endif | ||||
{ | |||||
skew_1 = secp256k1_wnaf_const(wnaf_1, sc, WINDOW_A - 1, size); | |||||
#ifdef USE_ENDOMORPHISM | |||||
skew_lam = 0; | |||||
#endif | #endif | ||||
} | |||||
/* Calculate odd multiples of a. | /* Calculate odd multiples of a. | ||||
* All multiples are brought to the same Z 'denominator', which is stored | * All multiples are brought to the same Z 'denominator', which is stored | ||||
* in Z. Due to secp256k1' isomorphism we can do all operations pretending | * in Z. Due to secp256k1' isomorphism we can do all operations pretending | ||||
* that the Z coordinate was 1, use affine addition formulae, and correct | * that the Z coordinate was 1, use affine addition formulae, and correct | ||||
* the Z coordinate of the result once at the end. | * the Z coordinate of the result once at the end. | ||||
*/ | */ | ||||
secp256k1_gej_set_ge(r, a); | secp256k1_gej_set_ge(r, a); | ||||
secp256k1_ecmult_odd_multiples_table_globalz_windowa(pre_a, &Z, r); | secp256k1_ecmult_odd_multiples_table_globalz_windowa(pre_a, &Z, r); | ||||
for (i = 0; i < ECMULT_TABLE_SIZE(WINDOW_A); i++) { | for (i = 0; i < ECMULT_TABLE_SIZE(WINDOW_A); i++) { | ||||
secp256k1_fe_normalize_weak(&pre_a[i].y); | secp256k1_fe_normalize_weak(&pre_a[i].y); | ||||
} | } | ||||
#ifdef USE_ENDOMORPHISM | #ifdef USE_ENDOMORPHISM | ||||
if (size > 128) { | |||||
for (i = 0; i < ECMULT_TABLE_SIZE(WINDOW_A); i++) { | for (i = 0; i < ECMULT_TABLE_SIZE(WINDOW_A); i++) { | ||||
secp256k1_ge_mul_lambda(&pre_a_lam[i], &pre_a[i]); | secp256k1_ge_mul_lambda(&pre_a_lam[i], &pre_a[i]); | ||||
} | } | ||||
} | |||||
#endif | #endif | ||||
/* first loop iteration (separated out so we can directly set r, rather | /* first loop iteration (separated out so we can directly set r, rather | ||||
* than having it start at infinity, get doubled several times, then have | * than having it start at infinity, get doubled several times, then have | ||||
* its new value added to it) */ | * its new value added to it) */ | ||||
i = wnaf_1[WNAF_SIZE(WINDOW_A - 1)]; | i = wnaf_1[WNAF_SIZE_BITS(rsize, WINDOW_A - 1)]; | ||||
VERIFY_CHECK(i != 0); | VERIFY_CHECK(i != 0); | ||||
ECMULT_CONST_TABLE_GET_GE(&tmpa, pre_a, i, WINDOW_A); | ECMULT_CONST_TABLE_GET_GE(&tmpa, pre_a, i, WINDOW_A); | ||||
secp256k1_gej_set_ge(r, &tmpa); | secp256k1_gej_set_ge(r, &tmpa); | ||||
#ifdef USE_ENDOMORPHISM | #ifdef USE_ENDOMORPHISM | ||||
i = wnaf_lam[WNAF_SIZE(WINDOW_A - 1)]; | if (size > 128) { | ||||
i = wnaf_lam[WNAF_SIZE_BITS(rsize, WINDOW_A - 1)]; | |||||
VERIFY_CHECK(i != 0); | VERIFY_CHECK(i != 0); | ||||
ECMULT_CONST_TABLE_GET_GE(&tmpa, pre_a_lam, i, WINDOW_A); | ECMULT_CONST_TABLE_GET_GE(&tmpa, pre_a_lam, i, WINDOW_A); | ||||
secp256k1_gej_add_ge(r, r, &tmpa); | secp256k1_gej_add_ge(r, r, &tmpa); | ||||
} | |||||
#endif | #endif | ||||
/* remaining loop iterations */ | /* remaining loop iterations */ | ||||
for (i = WNAF_SIZE(WINDOW_A - 1) - 1; i >= 0; i--) { | for (i = WNAF_SIZE_BITS(rsize, WINDOW_A - 1) - 1; i >= 0; i--) { | ||||
int n; | int n; | ||||
int j; | int j; | ||||
for (j = 0; j < WINDOW_A - 1; ++j) { | for (j = 0; j < WINDOW_A - 1; ++j) { | ||||
secp256k1_gej_double_nonzero(r, r, NULL); | secp256k1_gej_double_nonzero(r, r, NULL); | ||||
} | } | ||||
n = wnaf_1[i]; | n = wnaf_1[i]; | ||||
ECMULT_CONST_TABLE_GET_GE(&tmpa, pre_a, n, WINDOW_A); | ECMULT_CONST_TABLE_GET_GE(&tmpa, pre_a, n, WINDOW_A); | ||||
VERIFY_CHECK(n != 0); | VERIFY_CHECK(n != 0); | ||||
secp256k1_gej_add_ge(r, r, &tmpa); | secp256k1_gej_add_ge(r, r, &tmpa); | ||||
#ifdef USE_ENDOMORPHISM | #ifdef USE_ENDOMORPHISM | ||||
if (size > 128) { | |||||
n = wnaf_lam[i]; | n = wnaf_lam[i]; | ||||
ECMULT_CONST_TABLE_GET_GE(&tmpa, pre_a_lam, n, WINDOW_A); | ECMULT_CONST_TABLE_GET_GE(&tmpa, pre_a_lam, n, WINDOW_A); | ||||
VERIFY_CHECK(n != 0); | VERIFY_CHECK(n != 0); | ||||
secp256k1_gej_add_ge(r, r, &tmpa); | secp256k1_gej_add_ge(r, r, &tmpa); | ||||
} | |||||
#endif | #endif | ||||
} | } | ||||
secp256k1_fe_mul(&r->z, &r->z, &Z); | secp256k1_fe_mul(&r->z, &r->z, &Z); | ||||
{ | { | ||||
/* Correct for wNAF skew */ | /* Correct for wNAF skew */ | ||||
secp256k1_ge correction = *a; | secp256k1_ge correction = *a; | ||||
secp256k1_ge_storage correction_1_stor; | secp256k1_ge_storage correction_1_stor; | ||||
#ifdef USE_ENDOMORPHISM | #ifdef USE_ENDOMORPHISM | ||||
secp256k1_ge_storage correction_lam_stor; | secp256k1_ge_storage correction_lam_stor; | ||||
#endif | #endif | ||||
secp256k1_ge_storage a2_stor; | secp256k1_ge_storage a2_stor; | ||||
secp256k1_gej tmpj; | secp256k1_gej tmpj; | ||||
secp256k1_gej_set_ge(&tmpj, &correction); | secp256k1_gej_set_ge(&tmpj, &correction); | ||||
secp256k1_gej_double_var(&tmpj, &tmpj, NULL); | secp256k1_gej_double_var(&tmpj, &tmpj, NULL); | ||||
secp256k1_ge_set_gej(&correction, &tmpj); | secp256k1_ge_set_gej(&correction, &tmpj); | ||||
secp256k1_ge_to_storage(&correction_1_stor, a); | secp256k1_ge_to_storage(&correction_1_stor, a); | ||||
#ifdef USE_ENDOMORPHISM | #ifdef USE_ENDOMORPHISM | ||||
if (size > 128) { | |||||
secp256k1_ge_to_storage(&correction_lam_stor, a); | secp256k1_ge_to_storage(&correction_lam_stor, a); | ||||
} | |||||
#endif | #endif | ||||
secp256k1_ge_to_storage(&a2_stor, &correction); | secp256k1_ge_to_storage(&a2_stor, &correction); | ||||
/* For odd numbers this is 2a (so replace it), for even ones a (so no-op) */ | /* For odd numbers this is 2a (so replace it), for even ones a (so no-op) */ | ||||
secp256k1_ge_storage_cmov(&correction_1_stor, &a2_stor, skew_1 == 2); | secp256k1_ge_storage_cmov(&correction_1_stor, &a2_stor, skew_1 == 2); | ||||
#ifdef USE_ENDOMORPHISM | #ifdef USE_ENDOMORPHISM | ||||
if (size > 128) { | |||||
secp256k1_ge_storage_cmov(&correction_lam_stor, &a2_stor, skew_lam == 2); | secp256k1_ge_storage_cmov(&correction_lam_stor, &a2_stor, skew_lam == 2); | ||||
} | |||||
#endif | #endif | ||||
/* Apply the correction */ | /* Apply the correction */ | ||||
secp256k1_ge_from_storage(&correction, &correction_1_stor); | secp256k1_ge_from_storage(&correction, &correction_1_stor); | ||||
secp256k1_ge_neg(&correction, &correction); | secp256k1_ge_neg(&correction, &correction); | ||||
secp256k1_gej_add_ge(r, r, &correction); | secp256k1_gej_add_ge(r, r, &correction); | ||||
#ifdef USE_ENDOMORPHISM | #ifdef USE_ENDOMORPHISM | ||||
if (size > 128) { | |||||
secp256k1_ge_from_storage(&correction, &correction_lam_stor); | secp256k1_ge_from_storage(&correction, &correction_lam_stor); | ||||
secp256k1_ge_neg(&correction, &correction); | secp256k1_ge_neg(&correction, &correction); | ||||
secp256k1_ge_mul_lambda(&correction, &correction); | secp256k1_ge_mul_lambda(&correction, &correction); | ||||
secp256k1_gej_add_ge(r, r, &correction); | secp256k1_gej_add_ge(r, r, &correction); | ||||
} | |||||
#endif | #endif | ||||
} | } | ||||
} | } | ||||
#endif /* SECP256K1_ECMULT_CONST_IMPL_H */ | #endif /* SECP256K1_ECMULT_CONST_IMPL_H */ |