Repository: bitcoin-core/secp256k1
Pull request #405 (2016-07-09 12:26:28)

Make secp256k1_fe_sqrt constant time
The current field element square root algorithm is entirely constant time already, apart from a variable time field element comparison at end (whose time is negligible compared to the exponentiation ladder).

Furthermore, no faster variable time algorithm is known, so we don't lose anything by actually making the algorithm fully constant time. This simplifies some potential future changes in the Schnorr code.


Patch:
diff --git a/src/bench_internal.c b/src/bench_internal.c
index d24ddc2..0809f77 100644
--- a/src/bench_internal.c
+++ b/src/bench_internal.c
@@ -181,12 +181,12 @@ void bench_field_inverse_var(void* arg) {
     }
 }
 
-void bench_field_sqrt_var(void* arg) {
+void bench_field_sqrt(void* arg) {
     int i;
     bench_inv_t *data = (bench_inv_t*)arg;
 
     for (i = 0; i < 20000; i++) {
-        secp256k1_fe_sqrt_var(&data->fe_x, &data->fe_x);
+        secp256k1_fe_sqrt(&data->fe_x, &data->fe_x);
         secp256k1_fe_add(&data->fe_x, &data->fe_y);
     }
 }
@@ -357,7 +357,7 @@ int main(int argc, char **argv) {
     if (have_flag(argc, argv, "field") || have_flag(argc, argv, "mul")) run_benchmark("field_mul", bench_field_mul, bench_setup, NULL, &data, 10, 200000);
     if (have_flag(argc, argv, "field") || have_flag(argc, argv, "inverse")) run_benchmark("field_inverse", bench_field_inverse, bench_setup, NULL, &data, 10, 20000);
     if (have_flag(argc, argv, "field") || have_flag(argc, argv, "inverse")) run_benchmark("field_inverse_var", bench_field_inverse_var, bench_setup, NULL, &data, 10, 20000);
-    if (have_flag(argc, argv, "field") || have_flag(argc, argv, "sqrt")) run_benchmark("field_sqrt_var", bench_field_sqrt_var, bench_setup, NULL, &data, 10, 20000);
+    if (have_flag(argc, argv, "field") || have_flag(argc, argv, "sqrt")) run_benchmark("field_sqrt", bench_field_sqrt, bench_setup, NULL, &data, 10, 20000);
 
     if (have_flag(argc, argv, "group") || have_flag(argc, argv, "double")) run_benchmark("group_double_var", bench_group_double_var, bench_setup, NULL, &data, 10, 200000);
     if (have_flag(argc, argv, "group") || have_flag(argc, argv, "add")) run_benchmark("group_add_var", bench_group_add_var, bench_setup, NULL, &data, 10, 200000);
diff --git a/src/field.h b/src/field.h
index 47d4685..c5ba074 100644
--- a/src/field.h
+++ b/src/field.h
@@ -57,6 +57,9 @@ static int secp256k1_fe_is_zero(const secp256k1_fe *a);
 static int secp256k1_fe_is_odd(const secp256k1_fe *a);
 
 /** Compare two field elements. Requires magnitude-1 inputs. */
+static int secp256k1_fe_equal(const secp256k1_fe *a, const secp256k1_fe *b);
+
+/** Same as secp256k1_fe_equal, but may be variable time. */
 static int secp256k1_fe_equal_var(const secp256k1_fe *a, const secp256k1_fe *b);
 
 /** Compare two field elements. Requires both inputs to be normalized */
@@ -92,7 +95,7 @@ static void secp256k1_fe_sqr(secp256k1_fe *r, const secp256k1_fe *a);
  *  The input's magnitude can be at most 8. The output magnitude is 1 (but not
  *  guaranteed to be normalized). The result in r will always be a square
  *  itself. */
-static int secp256k1_fe_sqrt_var(secp256k1_fe *r, const secp256k1_fe *a);
+static int secp256k1_fe_sqrt(secp256k1_fe *r, const secp256k1_fe *a);
 
 /** Checks whether a field element is a quadratic residue. */
 static int secp256k1_fe_is_quad_var(const secp256k1_fe *a);
diff --git a/src/field_impl.h b/src/field_impl.h
index 00ba6c8..52cd902 100644
--- a/src/field_impl.h
+++ b/src/field_impl.h
@@ -21,6 +21,13 @@
 #error "Please select field implementation"
 #endif
 
+SECP256K1_INLINE static int secp256k1_fe_equal(const secp256k1_fe *a, const secp256k1_fe *b) {
+    secp256k1_fe na;
+    secp256k1_fe_negate(&na, a, 1);
+    secp256k1_fe_add(&na, b);
+    return secp256k1_fe_normalizes_to_zero(&na);
+}
+
 SECP256K1_INLINE static int secp256k1_fe_equal_var(const secp256k1_fe *a, const secp256k1_fe *b) {
     secp256k1_fe na;
     secp256k1_fe_negate(&na, a, 1);
@@ -28,7 +35,7 @@ SECP256K1_INLINE static int secp256k1_fe_equal_var(const secp256k1_fe *a, const
     return secp256k1_fe_normalizes_to_zero_var(&na);
 }
 
-static int secp256k1_fe_sqrt_var(secp256k1_fe *r, const secp256k1_fe *a) {
+static int secp256k1_fe_sqrt(secp256k1_fe *r, const secp256k1_fe *a) {
     /** Given that p is congruent to 3 mod 4, we can compute the square root of
      *  a mod p as the (p+1)/4'th power of a.
      *
@@ -123,7 +130,7 @@ static int secp256k1_fe_sqrt_var(secp256k1_fe *r, const secp256k1_fe *a) {
     /* Check that a square root was actually calculated */
 
     secp256k1_fe_sqr(&t1, r);
-    return secp256k1_fe_equal_var(&t1, a);
+    return secp256k1_fe_equal(&t1, a);
 }
 
 static void secp256k1_fe_inv(secp256k1_fe *r, const secp256k1_fe *a) {
@@ -301,7 +308,7 @@ static int secp256k1_fe_is_quad_var(const secp256k1_fe *a) {
     return secp256k1_num_jacobi(&n, &m) >= 0;
 #else
     secp256k1_fe r;
-    return secp256k1_fe_sqrt_var(&r, a) == 1;
+    return secp256k1_fe_sqrt(&r, a);
 #endif
 }
 
diff --git a/src/group.h b/src/group.h
index 852bb64..d515716 100644
--- a/src/group.h
+++ b/src/group.h
@@ -47,7 +47,7 @@ static void secp256k1_ge_set_xy(secp256k1_ge *r, const secp256k1_fe *x, const se
  *  and a Y coordinate that is a quadratic residue modulo p. The return value
  *  is true iff a coordinate with the given X coordinate exists.
  */
-static int secp256k1_ge_set_xquad_var(secp256k1_ge *r, const secp256k1_fe *x);
+static int secp256k1_ge_set_xquad(secp256k1_ge *r, const secp256k1_fe *x);
 
 /** Set a group element (affine) equal to the point with the given X coordinate, and given oddness
  *  for Y. Return value indicates whether the result is valid. */
diff --git a/src/group_impl.h b/src/group_impl.h
index 616866a..3e9c4c4 100644
--- a/src/group_impl.h
+++ b/src/group_impl.h
@@ -163,7 +163,7 @@ static void secp256k1_ge_clear(secp256k1_ge *r) {
     secp256k1_fe_clear(&r->y);
 }
 
-static int secp256k1_ge_set_xquad_var(secp256k1_ge *r, const secp256k1_fe *x) {
+static int secp256k1_ge_set_xquad(secp256k1_ge *r, const secp256k1_fe *x) {
     secp256k1_fe x2, x3, c;
     r->x = *x;
     secp256k1_fe_sqr(&x2, x);
@@ -171,11 +171,11 @@ static int secp256k1_ge_set_xquad_var(secp256k1_ge *r, const secp256k1_fe *x) {
     r->infinity = 0;
     secp256k1_fe_set_int(&c, 7);
     secp256k1_fe_add(&c, &x3);
-    return secp256k1_fe_sqrt_var(&r->y, &c);
+    return secp256k1_fe_sqrt(&r->y, &c);
 }
 
 static int secp256k1_ge_set_xo_var(secp256k1_ge *r, const secp256k1_fe *x, int odd) {
-    if (!secp256k1_ge_set_xquad_var(r, x)) {
+    if (!secp256k1_ge_set_xquad(r, x)) {
         return 0;
     }
     secp256k1_fe_normalize_var(&r->y);


Test patch:
diff --git a/src/tests.c b/src/tests.c
index bb3014f..b32cb90 100644
--- a/src/tests.c
+++ b/src/tests.c
@@ -1574,7 +1574,7 @@ void random_fe_non_zero(secp256k1_fe *nz) {
 void random_fe_non_square(secp256k1_fe *ns) {
     secp256k1_fe r;
     random_fe_non_zero(ns);
-    if (secp256k1_fe_sqrt_var(&r, ns)) {
+    if (secp256k1_fe_sqrt(&r, ns)) {
         secp256k1_fe_negate(ns, ns, 1);
     }
 }
@@ -1769,7 +1769,7 @@ void run_sqr(void) {
 
 void test_sqrt(const secp256k1_fe *a, const secp256k1_fe *k) {
     secp256k1_fe r1, r2;
-    int v = secp256k1_fe_sqrt_var(&r1, a);
+    int v = secp256k1_fe_sqrt(&r1, a);
     CHECK((v == 0) == (k == NULL));
 
     if (k != NULL) {
@@ -2188,7 +2188,7 @@ void test_group_decompress(const secp256k1_fe* x) {
 
     secp256k1_fe_normalize_var(&fex);
 
-    res_quad = secp256k1_ge_set_xquad_var(&ge_quad, &fex);
+    res_quad = secp256k1_ge_set_xquad(&ge_quad, &fex);
     res_even = secp256k1_ge_set_xo_var(&ge_even, &fex, 0);
     res_odd = secp256k1_ge_set_xo_var(&ge_odd, &fex, 1);