Split two helpers out of ec_wNAF_mul()

As its name indicates, the first, ec_compute_odd_multiples(), fills
point, 3 * point, 5 * point, ..., (2 * len - 1) * point into row[].
In fact, it first computes doubled = 2 * point and then goes on to
set row[i] = row[i - 1] + doubled. That's straightforward enough. One
change here is that this helper allocates row[i] on the fly rather
than preallocating the entire array of points up front.

The second piece is the actual precomputation, ec_wNAF_precompute().
It first computes the wNAF digits of the two scalars n and m (in this
order for now) with appropriate window size and length. Then the above
mentioned val[] array is allocated and populated with odd multiples
of point and generator. Finally, all points in val[] are made affine
in a single step, which means we only need one modular inversion, and
this then allows us to take fast paths in all the computations in the
one remaining loop in ec_wNAF_mul().

ok jsing

1 files changed, 119 insertions, 92 deletions

diff --git a/src/lib/libcrypto/ec/ec_mult.c b/src/lib/libcrypto/ec/ec_mult.c
index 43fab4b83c..9a695a2fb6 100644
--- a/src/lib/libcrypto/ec/ec_mult.c
+++ b/src/lib/libcrypto/ec/ec_mult.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: ec_mult.c,v 1.41 2024/11/22 00:54:42 tb Exp $ */
+/* $OpenBSD: ec_mult.c,v 1.42 2024/11/22 14:59:40 tb Exp $ */
 /*
  * Originally written by Bodo Moeller and Nils Larsch for the OpenSSL project.
  */
@@ -219,6 +219,113 @@ compute_wNAF(const BIGNUM *scalar, int w, size_t *ret_len)
                   (b) >=   20 ? 2 : \
                   1))
 
+static int
+ec_compute_odd_multiples(const EC_GROUP *group, const EC_POINT *point,
+    EC_POINT **row, size_t len, BN_CTX *ctx)
+{
+        EC_POINT *doubled = NULL;
+        size_t i;
+        int ret = 0;
+
+        if (len < 1)
+                goto err;
+
+        if ((row[0] = EC_POINT_dup(point, group)) == NULL)
+                goto err;
+
+        if ((doubled = EC_POINT_new(group)) == NULL)
+                goto err;
+        if (!EC_POINT_dbl(group, doubled, point, ctx))
+                goto err;
+        for (i = 1; i < len; i++) {
+                if ((row[i] = EC_POINT_new(group)) == NULL)
+                        goto err;
+                if (!EC_POINT_add(group, row[i], row[i - 1], doubled, ctx))
+                        goto err;
+        }
+
+        ret = 1;
+
+ err:
+        EC_POINT_free(doubled);
+
+        return ret;
+}
+
+/*
+ * This computes the wNAF representation of m and n and uses the window size to
+ * precompute the two rows of odd multiples of point and generator. On success,
+ * out_val owns the out_val_len points in the two rows.
+ *
+ * XXX - the only reason we need a single array is to be able to pass it to
+ * EC_POINTs_make_affine(). Consider writing a suitable variant that doesn't
+ * require such grotesque gymnastics.
+ */
+
+static int
+ec_wNAF_precompute(const EC_GROUP *group, const BIGNUM *m, const EC_POINT *point,
+    const BIGNUM *n, signed char *wNAF[2], size_t wNAF_len[2], EC_POINT **row[2],
+    EC_POINT ***out_val, size_t *out_val_len, BN_CTX *ctx)
+{
+        EC_POINT **val = NULL;
+        size_t val_len = 0;
+        const EC_POINT *generator;
+        size_t wsize[2] = { 0 };
+        size_t i, len0, len1;
+        int ret = 0;
+
+        *out_val = NULL;
+        *out_val_len = 0;
+
+        if ((generator = EC_GROUP_get0_generator(group)) == NULL) {
+                ECerror(EC_R_UNDEFINED_GENERATOR);
+                goto err;
+        }
+
+        wsize[0] = EC_window_bits_for_scalar_size(BN_num_bits(n));
+        if ((wNAF[0] = compute_wNAF(n, wsize[0], &wNAF_len[0])) == NULL)
+                goto err;
+
+        wsize[1] = EC_window_bits_for_scalar_size(BN_num_bits(m));
+        if ((wNAF[1] = compute_wNAF(m, wsize[1], &wNAF_len[1])) == NULL)
+                goto err;
+
+        len0 = 1 << (wsize[0] - 1);
+        len1 = 1 << (wsize[1] - 1);
+
+        if ((val = calloc(len0 + len1, sizeof(*val))) == NULL) {
+                ECerror(ERR_R_MALLOC_FAILURE);
+                goto err;
+        }
+        val_len = len0 + len1;
+
+        row[0] = &val[0];
+        row[1] = &val[len0];
+
+        if (!ec_compute_odd_multiples(group, point, row[0], len0, ctx))
+                goto err;
+        if (!ec_compute_odd_multiples(group, generator, row[1], len1, ctx))
+                goto err;
+
+        if (!EC_POINTs_make_affine(group, val_len, val, ctx))
+                goto err;
+
+        *out_val = val;
+        val = NULL;
+
+        *out_val_len = val_len;
+        val_len = 0;
+
+        ret = 1;
+
+ err:
+        for (i = 0; i < val_len; i++)
+                EC_POINT_free(val[i]);
+        free(val);
+
+        return ret;
+}
+
 /*
  * Compute r = generator * m + point * n in non-constant time.
  */
@@ -229,17 +336,13 @@ ec_wNAF_mul(const EC_GROUP *group, EC_POINT *r, const BIGNUM *m,
 {
         signed char *wNAF[2] = { 0 };
         size_t wNAF_len[2] = { 0 };
-        size_t wsize[2] = { 0 };
-        const EC_POINT *generator = NULL;
-        EC_POINT *tmp = NULL;
         EC_POINT **row[2] = { 0 };
-        size_t i, j;
+        EC_POINT **val = NULL;
+        size_t val_len = 0;
+        size_t i;
         int k;
         int r_is_inverted = 0;
         size_t max_len = 0;
-        size_t num_val;
-        EC_POINT **val = NULL;  /* precomputation */
-        EC_POINT **v;
         int ret = 0;
 
         if (m == NULL || n == NULL) {
@@ -251,86 +354,13 @@ ec_wNAF_mul(const EC_GROUP *group, EC_POINT *r, const BIGNUM *m,
                 goto err;
         }
 
-        if ((generator = EC_GROUP_get0_generator(group)) == NULL) {
-                ECerror(EC_R_UNDEFINED_GENERATOR);
+        if (!ec_wNAF_precompute(group, m, point, n, wNAF, wNAF_len, row,
+            &val, &val_len, ctx))
                 goto err;
-        }
 
-        /* num_val will be the total number of temporarily precomputed points */
-        num_val = 0;
-
-        for (i = 0; i < 2; i++) {
-                size_t bits;
-
-                bits = i < 1 ? BN_num_bits(n) : BN_num_bits(m);
-                wsize[i] = EC_window_bits_for_scalar_size(bits);
-                num_val += (size_t) 1 << (wsize[i] - 1);
-                wNAF[i] = compute_wNAF(i < 1 ? n : m, wsize[i], &wNAF_len[i]);
-                if (wNAF[i] == NULL)
-                        goto err;
-                if (wNAF_len[i] > max_len)
-                        max_len = wNAF_len[i];
-        }
-
-        /*
-         * All points we precompute now go into a single array 'val'.
-         * 'val_sub[i]' is a pointer to the subarray for the i-th point, or
-         * to a subarray of 'pre_comp->points' if we already have
-         * precomputation.
-         */
-        val = reallocarray(NULL, (num_val + 1), sizeof val[0]);
-        if (val == NULL) {
-                ECerror(ERR_R_MALLOC_FAILURE);
-                goto err;
-        }
-        val[num_val] = NULL;    /* pivot element */
-
-        /* allocate points for precomputation */
-        v = val;
-        for (i = 0; i < 2; i++) {
-                row[i] = v;
-                for (j = 0; j < ((size_t) 1 << (wsize[i] - 1)); j++) {
-                        *v = EC_POINT_new(group);
-                        if (*v == NULL)
-                                goto err;
-                        v++;
-                }
-        }
-        if (!(v == val + num_val)) {
-                ECerror(ERR_R_INTERNAL_ERROR);
-                goto err;
-        }
-        if (!(tmp = EC_POINT_new(group)))
-                goto err;
-
-        /*
-         * prepare precomputed values:
-         *  row[i][0] :=     points[i]
-         *  row[i][1] := 3 * points[i]
-         *  row[i][2] := 5 * points[i]
-         *  ...
-         */
-        for (i = 0; i < 2; i++) {
-                if (i < 1) {
-                        if (!EC_POINT_copy(row[i][0], point))
-                                goto err;
-                } else {
-                        if (!EC_POINT_copy(row[i][0], generator))
-                                goto err;
-                }
-
-                if (wsize[i] > 1) {
-                        if (!EC_POINT_dbl(group, tmp, row[i][0], ctx))
-                                goto err;
-                        for (j = 1; j < ((size_t) 1 << (wsize[i] - 1)); j++) {
-                                if (!EC_POINT_add(group, row[i][j], row[i][j - 1], tmp, ctx))
-                                        goto err;
-                        }
-                }
-        }
-
-        if (!EC_POINTs_make_affine(group, num_val, val, ctx))
-                goto err;
+        max_len = wNAF_len[0];
+        if (wNAF_len[1] > max_len)
+                max_len = wNAF_len[1];
 
         /*
          * Set r to the neutral element. Scan through the wNAF representations
@@ -381,14 +411,11 @@ ec_wNAF_mul(const EC_GROUP *group, EC_POINT *r, const BIGNUM *m,
         ret = 1;
 
  err:
-        EC_POINT_free(tmp);
         free(wNAF[0]);
         free(wNAF[1]);
-        if (val != NULL) {
-                for (v = val; *v != NULL; v++)
-                        EC_POINT_free(*v);
-                free(val);
-        }
+        for (i = 0; i < val_len; i++)
+                EC_POINT_free(val[i]);
+        free(val);
 
         return ret;
 }