Merge bitcoin#741: Remove unnecessary sign variable from wnaf_const

real-or-random · real-or-random · commit 3e5cfc5c73f8 · 2020-07-26T12:21:14.000+02:00
37dba32 Remove unnecessary sign variable from wnaf_const (Jonas Nick) 6bb0b77 Fix test_constant_wnaf for -1 and add a test for it. (Jonas Nick) Pull request description: There currently is a single branch in the `ecmul_const` function that is not being exercised by the tests. This branch is unreachable and therefore I'm suggesting to remove it. For your convenience the paper the wnaf algorithm can be found [here (The Width-w NAF Method Provides Small Memory and Fast Elliptic Scalar Multiplications Secure against Side Channel Attacks)](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.563.1267&rep=rep1&type=pdf). Similarly, unless I'm missing something important, I don't see how their algorithm needs to consider `sign(u[i-1])` unless `d` can be negative - which doesn't make much sense to me either. ACKs for top commit: real-or-random: ACK 37dba32 I verified the correctness of the change and claimed invariant by manual inspection. I tested the code, both with 32bit and 64bit scalars. Tree-SHA512: 9db45f76bd881d00a81923b6d2ae1c3e0f49a82a5d55347f01e1ce4e924d9a3bf55483a0697f25039c327e33edca6796ba3205c068d9f2f99aa5d655e46b15be
diff --git a/src/ecmult_const_impl.h b/src/ecmult_const_impl.h
@@ -105,16 +105,22 @@ static int secp256k1_wnaf_const(int *wnaf, const secp256k1_scalar *scalar, int w
     /* 4 */
     u_last = secp256k1_scalar_shr_int(&s, w);
     do {
-        int sign;
         int even;
 
         /* 4.1 4.4 */
         u = secp256k1_scalar_shr_int(&s, w);
         /* 4.2 */
         even = ((u & 1) == 0);
-        sign = 2 * (u_last > 0) - 1;
-        u += sign * even;
-        u_last -= sign * even * (1 << w);
+        /* In contrast to the original algorithm, u_last is always > 0 and
+         * therefore we do not need to check its sign. In particular, it's easy
+         * to see that u_last is never < 0 because u is never < 0. Moreover,
+         * u_last is never = 0 because u is never even after a loop
+         * iteration. The same holds analogously for the initial value of
+         * u_last (in the first loop iteration). */
+        VERIFY_CHECK(u_last > 0);
+        VERIFY_CHECK((u_last & 1) == 1);
+        u += even;
+        u_last -= even * (1 << w);
 
         /* 4.3, adapted for global sign change */
         wnaf[word++] = u_last * global_sign;
diff --git a/src/tests.c b/src/tests.c
@@ -3234,6 +3234,7 @@ void test_constant_wnaf(const secp256k1_scalar *number, int w) {
     int skew;
     int bits = 256;
     secp256k1_scalar num = *number;
+    secp256k1_scalar scalar_skew;
 
     secp256k1_scalar_set_int(&x, 0);
     secp256k1_scalar_set_int(&shift, 1 << w);
@@ -3264,7 +3265,8 @@ void test_constant_wnaf(const secp256k1_scalar *number, int w) {
         secp256k1_scalar_add(&x, &x, &t);
     }
     /* Skew num because when encoding numbers as odd we use an offset */
-    secp256k1_scalar_cadd_bit(&num, skew == 2, 1);
+    secp256k1_scalar_set_int(&scalar_skew, 1 << (skew == 2));
+    secp256k1_scalar_add(&num, &num, &scalar_skew);
     CHECK(secp256k1_scalar_eq(&x, &num));
 }
 
@@ -3376,13 +3378,32 @@ void run_wnaf(void) {
     int i;
     secp256k1_scalar n = {{0}};
 
+    test_constant_wnaf(&n, 4);
     /* Sanity check: 1 and 2 are the smallest odd and even numbers and should
      *               have easier-to-diagnose failure modes  */
     n.d[0] = 1;
     test_constant_wnaf(&n, 4);
     n.d[0] = 2;
     test_constant_wnaf(&n, 4);
-    /* Test 0 */
+    /* Test -1, because it's a special case in wnaf_const */
+    n = secp256k1_scalar_one;
+    secp256k1_scalar_negate(&n, &n);
+    test_constant_wnaf(&n, 4);
+
+    /* Test -2, which may not lead to overflows in wnaf_const */
+    secp256k1_scalar_add(&n, &secp256k1_scalar_one, &secp256k1_scalar_one);
+    secp256k1_scalar_negate(&n, &n);
+    test_constant_wnaf(&n, 4);
+
+    /* Test (1/2) - 1 = 1/-2 and 1/2 = (1/-2) + 1
+       as corner cases of negation handling in wnaf_const */
+    secp256k1_scalar_inverse(&n, &n);
+    test_constant_wnaf(&n, 4);
+
+    secp256k1_scalar_add(&n, &n, &secp256k1_scalar_one);
+    test_constant_wnaf(&n, 4);
+
+    /* Test 0 for fixed wnaf */
     test_fixed_wnaf_small();
     /* Random tests */
     for (i = 0; i < count; i++) {
