diff --git a/src/secp256k1/src/ecmult_impl.h b/src/secp256k1/src/ecmult_impl.h
--- a/src/secp256k1/src/ecmult_impl.h
+++ b/src/secp256k1/src/ecmult_impl.h
@@ -563,53 +563,66 @@
* It has the following guarantees:
* - each wnaf[i] is either 0 or an odd integer between -(1 << w) and (1 << w)
* - the number of words set is always WNAF_SIZE(w)
- * - the returned skew is 0 without endomorphism, or 0 or 1 with endomorphism
+ * - the returned skew is 0 or 1
*/
static int secp256k1_wnaf_fixed(int *wnaf, const secp256k1_scalar *s, int w) {
- int sign = 0;
int skew = 0;
- int pos = 1;
-#ifndef USE_ENDOMORPHISM
- secp256k1_scalar neg_s;
-#endif
+ int pos;
+ int max_pos;
+ int last_w;
const secp256k1_scalar *work = s;
if (secp256k1_scalar_is_zero(s)) {
- while (pos * w < WNAF_BITS) {
+ for (pos = 0; pos < WNAF_SIZE(w); pos++) {
wnaf[pos] = 0;
- ++pos;
}
return 0;
}
if (secp256k1_scalar_is_even(s)) {
-#ifdef USE_ENDOMORPHISM
skew = 1;
-#else
- secp256k1_scalar_negate(&neg_s, s);
- work = &neg_s;
- sign = -1;
-#endif
}
- wnaf[0] = (secp256k1_scalar_get_bits_var(work, 0, w) + skew + sign) ^ sign;
+ wnaf[0] = secp256k1_scalar_get_bits_var(work, 0, w) + skew;
+ /* Compute last window size. Relevant when window size doesn't divide the
+ * number of bits in the scalar */
+ last_w = WNAF_BITS - (WNAF_SIZE(w) - 1) * w;
- while (pos * w < WNAF_BITS) {
- int now = w;
- int val;
- if (now + pos * w > WNAF_BITS) {
- now = WNAF_BITS - pos * w;
+ /* Store the position of the first nonzero word in max_pos to allow
+ * skipping leading zeros when calculating the wnaf. */
+ for (pos = WNAF_SIZE(w) - 1; pos > 0; pos--) {
+ int val = secp256k1_scalar_get_bits_var(work, pos * w, pos == WNAF_SIZE(w)-1 ? last_w : w);
+ if(val != 0) {
+ break;
}
- val = secp256k1_scalar_get_bits_var(work, pos * w, now);
+ wnaf[pos] = 0;
+ }
+ max_pos = pos;
+ pos = 1;
+
+ while (pos <= max_pos) {
+ int val = secp256k1_scalar_get_bits_var(work, pos * w, pos == WNAF_SIZE(w)-1 ? last_w : w);
if ((val & 1) == 0) {
- wnaf[pos - 1] -= ((1 << w) + sign) ^ sign;
- wnaf[pos] = (val + 1 + sign) ^ sign;
+ wnaf[pos - 1] -= (1 << w);
+ wnaf[pos] = (val + 1);
} else {
- wnaf[pos] = (val + sign) ^ sign;
+ wnaf[pos] = val;
+ }
+ /* Set a coefficient to zero if it is 1 or -1 and the proceeding digit
+ * is strictly negative or strictly positive respectively. Only change
+ * coefficients at previous positions because above code assumes that
+ * wnaf[pos - 1] is odd.
+ */
+ if (pos >= 2 && ((wnaf[pos - 1] == 1 && wnaf[pos - 2] < 0) || (wnaf[pos - 1] == -1 && wnaf[pos - 2] > 0))) {
+ if (wnaf[pos - 1] == 1) {
+ wnaf[pos - 2] += 1 << w;
+ } else {
+ wnaf[pos - 2] -= 1 << w;
+ }
+ wnaf[pos - 1] = 0;
}
++pos;
}
- VERIFY_CHECK(pos == WNAF_SIZE(w));
return skew;
}
@@ -665,7 +678,6 @@
secp256k1_ge tmp;
int idx;
-#ifdef USE_ENDOMORPHISM
if (i == 0) {
/* correct for wnaf skew */
int skew = point_state.skew_na;
@@ -674,7 +686,6 @@
secp256k1_gej_add_ge_var(&buckets[0], &buckets[0], &tmp, NULL);
}
}
-#endif
if (n > 0) {
idx = (n - 1)/2;
secp256k1_gej_add_ge_var(&buckets[idx], &buckets[idx], &pt[point_state.input_pos], NULL);
diff --git a/src/secp256k1/src/tests.c b/src/secp256k1/src/tests.c
--- a/src/secp256k1/src/tests.c
+++ b/src/secp256k1/src/tests.c
@@ -3022,8 +3022,7 @@
for (i = WNAF_SIZE(w)-1; i >= 0; --i) {
secp256k1_scalar t;
int v = wnaf[i];
- CHECK(v != 0); /* check nonzero */
- CHECK(v & 1); /* check parity */
+ CHECK(v == 0 || v & 1); /* check parity */
CHECK(v > -(1 << w)); /* check range above */
CHECK(v < (1 << w)); /* check range below */
@@ -3041,7 +3040,20 @@
CHECK(secp256k1_scalar_eq(&x, &num));
}
-void test_fixed_wnaf_zero(int w) {
+/* Checks that the first 8 elements of wnaf are equal to wnaf_expected and the
+ * rest is 0.*/
+void test_fixed_wnaf_small_helper(int *wnaf, int *wnaf_expected, int w) {
+ int i;
+ for (i = WNAF_SIZE(w)-1; i >= 8; --i) {
+ CHECK(wnaf[i] == 0);
+ }
+ for (i = 7; i >= 0; --i) {
+ CHECK(wnaf[i] == wnaf_expected[i]);
+ }
+}
+
+void test_fixed_wnaf_small(void) {
+ int w = 4;
int wnaf[256] = {0};
int i;
int skew;
@@ -3049,12 +3061,49 @@
secp256k1_scalar_set_int(&num, 0);
skew = secp256k1_wnaf_fixed(wnaf, &num, w);
-
for (i = WNAF_SIZE(w)-1; i >= 0; --i) {
int v = wnaf[i];
CHECK(v == 0);
}
CHECK(skew == 0);
+
+ secp256k1_scalar_set_int(&num, 1);
+ skew = secp256k1_wnaf_fixed(wnaf, &num, w);
+ for (i = WNAF_SIZE(w)-1; i >= 1; --i) {
+ int v = wnaf[i];
+ CHECK(v == 0);
+ }
+ CHECK(wnaf[0] == 1);
+ CHECK(skew == 0);
+
+ {
+ int wnaf_expected[8] = { 0xf, 0xf, 0xf, 0xf, 0xf, 0xf, 0xf, 0xf };
+ secp256k1_scalar_set_int(&num, 0xffffffff);
+ skew = secp256k1_wnaf_fixed(wnaf, &num, w);
+ test_fixed_wnaf_small_helper(wnaf, wnaf_expected, w);
+ CHECK(skew == 0);
+ }
+ {
+ int wnaf_expected[8] = { -1, -1, -1, -1, -1, -1, -1, 0xf };
+ secp256k1_scalar_set_int(&num, 0xeeeeeeee);
+ skew = secp256k1_wnaf_fixed(wnaf, &num, w);
+ test_fixed_wnaf_small_helper(wnaf, wnaf_expected, w);
+ CHECK(skew == 1);
+ }
+ {
+ int wnaf_expected[8] = { 1, 0, 1, 0, 1, 0, 1, 0 };
+ secp256k1_scalar_set_int(&num, 0x01010101);
+ skew = secp256k1_wnaf_fixed(wnaf, &num, w);
+ test_fixed_wnaf_small_helper(wnaf, wnaf_expected, w);
+ CHECK(skew == 0);
+ }
+ {
+ int wnaf_expected[8] = { -0xf, 0, 0xf, -0xf, 0, 0xf, 1, 0 };
+ secp256k1_scalar_set_int(&num, 0x01ef1ef1);
+ skew = secp256k1_wnaf_fixed(wnaf, &num, w);
+ test_fixed_wnaf_small_helper(wnaf, wnaf_expected, w);
+ CHECK(skew == 0);
+ }
}
void run_wnaf(void) {
@@ -3068,7 +3117,7 @@
n.d[0] = 2;
test_constant_wnaf(&n, 4);
/* Test 0 */
- test_fixed_wnaf_zero(4);
+ test_fixed_wnaf_small();
/* Random tests */
for (i = 0; i < count; i++) {
random_scalar_order(&n);