Switch wnaf splitting from num-based to scalar-based

sipa · sipa · commit 0b73059709d5 · 2014-11-30T23:38:01.000+01:00
diff --git a/src/ecmult_impl.h b/src/ecmult_impl.h
@@ -9,6 +9,7 @@
 
 #include "num.h"
 #include "group.h"
+#include "scalar.h"
 #include "ecmult.h"
 
 /* optimal for 128-bit and 256-bit exponents. */
@@ -121,38 +122,51 @@ static void secp256k1_ecmult_stop(void) {
  *  with the following guarantees:
  *  - each wnaf[i] is either 0, or an odd integer between -(1<<(w-1) - 1) and (1<<(w-1) - 1)
  *  - two non-zero entries in wnaf are separated by at least w-1 zeroes.
- *  - the index of the highest non-zero entry in wnaf (=return value-1) is at most bits, where
- *    bits is the number of bits necessary to represent the absolute value of the input.
+ *  - the number of set values in wnaf is returned. This number is at most 256, and at most one more
+ *  - than the number of bits in the (absolute value) of the input.
  */
 static int secp256k1_ecmult_wnaf(int *wnaf, const secp256k1_num_t *a, int w) {
-    int ret = 0;
-    int zeroes = 0;
     secp256k1_num_t x;
     secp256k1_num_copy(&x, a);
     int sign = 1;
     if (secp256k1_num_is_neg(&x)) {
         sign = -1;
         secp256k1_num_negate(&x);
     }
-    while (!secp256k1_num_is_zero(&x)) {
-        while (!secp256k1_num_is_odd(&x)) {
-            zeroes++;
-            secp256k1_num_shift(&x, 1);
+    unsigned char cr[32];
+    secp256k1_num_get_bin(cr, 32, &x);
+    secp256k1_scalar_t s;
+    secp256k1_scalar_set_b32(&s, cr, NULL);
+
+    if (secp256k1_scalar_get_bits(&s, 255, 1)) {
+        secp256k1_scalar_negate(&s, &s);
+        sign *= -1;
+    }
+
+    int set_bits = 0;
+    int bit = 0;
+    while (bit < 256) {
+        if (secp256k1_scalar_get_bits(&s, bit, 1) == 0) {
+            bit++;
+            continue;
+        }
+        while (set_bits < bit) {
+            wnaf[set_bits++] = 0;
         }
-        int word = secp256k1_num_shift(&x, w);
-        while (zeroes) {
-            wnaf[ret++] = 0;
-            zeroes--;
+        int now = w;
+        if (bit + now > 256) {
+            now = 256 - bit;
         }
+        int word = secp256k1_scalar_get_bits_var(&s, bit, now);
         if (word & (1 << (w-1))) {
-            secp256k1_num_inc(&x);
-            wnaf[ret++] = sign * (word - (1 << w));
+            secp256k1_scalar_add_bit(&s, bit + w);
+            wnaf[set_bits++] = sign * (word - (1 << w));
         } else {
-            wnaf[ret++] = sign * word;
+            wnaf[set_bits++] = sign * word;
         }
-        zeroes = w-1;
+        bit += now;
     }
-    return ret;
+    return set_bits;
 }
 
 static void secp256k1_ecmult(secp256k1_gej_t *r, const secp256k1_gej_t *a, const secp256k1_num_t *na, const secp256k1_num_t *ng) {
@@ -170,7 +184,7 @@ static void secp256k1_ecmult(secp256k1_gej_t *r, const secp256k1_gej_t *a, const
     if (bits_na_lam > bits) bits = bits_na_lam;
 #else
     /* build wnaf representation for na. */
-    int wnaf_na[257];     int bits_na     = secp256k1_ecmult_wnaf(wnaf_na,     na,      WINDOW_A);
+    int wnaf_na[256];     int bits_na     = secp256k1_ecmult_wnaf(wnaf_na,     na,      WINDOW_A);
     int bits = bits_na;
 #endif
 
diff --git a/src/tests.c b/src/tests.c
@@ -825,8 +825,9 @@ void test_wnaf(const secp256k1_num_t *number, int w) {
     secp256k1_num_t x, two, t;
     secp256k1_num_set_int(&x, 0);
     secp256k1_num_set_int(&two, 2);
-    int wnaf[257];
+    int wnaf[256];
     int bits = secp256k1_ecmult_wnaf(wnaf, number, w);
+    CHECK(bits <= 256);
     int zeroes = -1;
     for (int i=bits-1; i>=0; i--) {
         secp256k1_num_mul(&x, &x, &two);
@@ -844,7 +845,10 @@ void test_wnaf(const secp256k1_num_t *number, int w) {
         secp256k1_num_set_int(&t, v);
         secp256k1_num_add(&x, &x, &t);
     }
-    CHECK(secp256k1_num_eq(&x, number)); /* check that wnaf represents number */
+    secp256k1_num_t xcopy = x, ncopy = *number;
+    secp256k1_num_mod(&xcopy, &secp256k1_ge_consts->order);
+    secp256k1_num_mod(&ncopy, &secp256k1_ge_consts->order);
+    CHECK(secp256k1_num_eq(&xcopy, &ncopy)); /* check that wnaf represents number */
 }
 
 void run_wnaf(void) {
