Remove unused code for multiple-point ECC multiplication.

The points are only converted to affine form when there are at least
three points being multiplied (in addition to the generator), but there
never is more than one point, so this is all dead code.

Also, I doubt that the comments "...point at infinity (which normally
shouldn't happen)" in the deleted code are accurate. And, the
projective->affine conversions that were removed from p224-64.c and
p256-64.c didn't seem to properly account for the possibility that any of
those points were at infinity.

Change-Id: I611d42d36dcb7515eabf3abf1857e52ff3b45c92
Reviewed-on: https://boringssl-review.googlesource.com/7100
Reviewed-by: David Benjamin <davidben@google.com>

4 files changed, 14 insertions, 230 deletions

diff --git a/crypto/ec/internal.h b/crypto/ec/internal.h
index 240d24fe..23715f65 100644
--- a/crypto/ec/internal.h
+++ b/crypto/ec/internal.h
@@ -232,15 +232,6 @@ int ec_point_set_Jprojective_coordinates_GFp(const EC_GROUP *group,
                                              const BIGNUM *y, const BIGNUM *z,
                                              BN_CTX *ctx);
 
-void ec_GFp_nistp_points_make_affine_internal(
-    size_t num, void *point_array, size_t felem_size, void *tmp_felems,
-    void (*felem_one)(void *out), int (*felem_is_zero)(const void *in),
-    void (*felem_assign)(void *out, const void *in),
-    void (*felem_square)(void *out, const void *in),
-    void (*felem_mul)(void *out, const void *in1, const void *in2),
-    void (*felem_inv)(void *out, const void *in),
-    void (*felem_contract)(void *out, const void *in));
-
 void ec_GFp_nistp_recode_scalar_bits(uint8_t *sign, uint8_t *digit, uint8_t in);
 
 const EC_METHOD *EC_GFp_nistp224_method(void);
diff --git a/crypto/ec/p224-64.c b/crypto/ec/p224-64.c
index dac20e09..b433a75b 100644
--- a/crypto/ec/p224-64.c
+++ b/crypto/ec/p224-64.c
@@ -242,13 +242,6 @@ static BIGNUM *felem_to_BN(BIGNUM *out, const felem in) {
  * expected to be correct in general - e.g., multiplication with a large scalar
  * will cause an overflow. */
 
-static void felem_one(felem out) {
-  out[0] = 1;
-  out[1] = 0;
-  out[2] = 0;
-  out[3] = 0;
-}
-
 static void felem_assign(felem out, const felem in) {
   out[0] = in[0];
   out[1] = in[1];
@@ -460,18 +453,6 @@ static void felem_reduce(felem out, const widefelem in) {
   out[3] = output[3];
 }
 
-static void felem_square_reduce(felem out, const felem in) {
-  widefelem tmp;
-  felem_square(tmp, in);
-  felem_reduce(out, tmp);
-}
-
-static void felem_mul_reduce(felem out, const felem in1, const felem in2) {
-  widefelem tmp;
-  felem_mul(tmp, in1, in2);
-  felem_reduce(out, tmp);
-}
-
 /* Reduce to unique minimal representation.
  * Requires 0 <= in < 2*p (always call felem_reduce first) */
 static void felem_contract(felem out, const felem in) {
@@ -539,10 +520,6 @@ static limb felem_is_zero(const felem in) {
   return (zero | two224m96p1 | two225m97p2);
 }
 
-static limb felem_is_zero_int(const felem in) {
-  return (int)(felem_is_zero(in) & ((limb)1));
-}
-
 /* Invert a field element */
 /* Computation chain copied from djb's code */
 static void felem_inv(felem out, const felem in) {
@@ -921,7 +898,7 @@ static char get_bit(const felem_bytearray in, unsigned i) {
 static void batch_mul(felem x_out, felem y_out, felem z_out,
                       const felem_bytearray scalars[],
                       const unsigned num_points, const u8 *g_scalar,
-                      const int mixed, const felem pre_comp[][17][3]) {
+                      const felem pre_comp[][17][3]) {
   int i, skip;
   unsigned num;
   unsigned gen_mul = (g_scalar != NULL);
@@ -989,8 +966,8 @@ static void batch_mul(felem x_out, felem y_out, felem z_out,
         copy_conditional(tmp[1], tmp[3], sign);
 
         if (!skip) {
-          point_add(nq[0], nq[1], nq[2], nq[0], nq[1], nq[2], mixed, tmp[0],
-                    tmp[1], tmp[2]);
+          point_add(nq[0], nq[1], nq[2], nq[0], nq[1], nq[2], 0 /* mixed */,
+                    tmp[0], tmp[1], tmp[2]);
         } else {
           memcpy(nq, tmp, 3 * sizeof(felem));
           skip = 0;
@@ -1047,20 +1024,6 @@ int ec_GFp_nistp224_point_get_affine_coordinates(const EC_GROUP *group,
   return 1;
 }
 
-static void make_points_affine(size_t num, felem points[/*num*/][3],
-                               felem tmp_felems[/*num+1*/]) {
-  /* Runs in constant time, unless an input is the point at infinity
-   * (which normally shouldn't happen). */
-  ec_GFp_nistp_points_make_affine_internal(
-      num, points, sizeof(felem), tmp_felems, (void (*)(void *))felem_one,
-      (int (*)(const void *))felem_is_zero_int,
-      (void (*)(void *, const void *))felem_assign,
-      (void (*)(void *, const void *))felem_square_reduce,
-      (void (*)(void *, const void *, const void *))felem_mul_reduce,
-      (void (*)(void *, const void *))felem_inv,
-      (void (*)(void *, const void *))felem_contract);
-}
-
 int ec_GFp_nistp224_points_mul(const EC_GROUP *group, EC_POINT *r,
                                const BIGNUM *g_scalar, const EC_POINT *p_,
                                const BIGNUM *p_scalar_, BN_CTX *ctx) {
@@ -1074,13 +1037,11 @@ int ec_GFp_nistp224_points_mul(const EC_GROUP *group, EC_POINT *r,
   int ret = 0;
   int j;
   unsigned i;
-  int mixed = 0;
   BN_CTX *new_ctx = NULL;
   BIGNUM *x, *y, *z, *tmp_scalar;
   felem_bytearray g_secret;
   felem_bytearray *secrets = NULL;
   felem(*pre_comp)[17][3] = NULL;
-  felem *tmp_felems = NULL;
   felem_bytearray tmp;
   unsigned num_bytes;
   size_t num_points = num;
@@ -1105,19 +1066,10 @@ int ec_GFp_nistp224_points_mul(const EC_GROUP *group, EC_POINT *r,
   }
 
   if (num_points > 0) {
-    if (num_points >= 3) {
-      /* unless we precompute multiples for just one or two points,
-       * converting those into affine form is time well spent  */
-      mixed = 1;
-    }
     secrets = OPENSSL_malloc(num_points * sizeof(felem_bytearray));
     pre_comp = OPENSSL_malloc(num_points * sizeof(felem[17][3]));
-    if (mixed) {
-      tmp_felems = OPENSSL_malloc((num_points * 17 + 1) * sizeof(felem));
-    }
     if (secrets == NULL ||
-        pre_comp == NULL ||
-        (mixed && tmp_felems == NULL)) {
+        pre_comp == NULL) {
       OPENSSL_PUT_ERROR(EC, ERR_R_MALLOC_FAILURE);
       goto err;
     }
@@ -1177,10 +1129,6 @@ int ec_GFp_nistp224_points_mul(const EC_GROUP *group, EC_POINT *r,
         }
       }
     }
-
-    if (mixed) {
-      make_points_affine(num_points * 17, pre_comp[0], tmp_felems);
-    }
   }
 
   if (g_scalar != NULL) {
@@ -1200,7 +1148,7 @@ int ec_GFp_nistp224_points_mul(const EC_GROUP *group, EC_POINT *r,
     flip_endian(g_secret, tmp, num_bytes);
   }
   batch_mul(x_out, y_out, z_out, (const felem_bytearray(*))secrets,
-            num_points, g_scalar != NULL ? g_secret : NULL, mixed,
+            num_points, g_scalar != NULL ? g_secret : NULL,
             (const felem(*)[17][3])pre_comp);
 
   /* reduce the output to its unique minimal representation */
@@ -1220,7 +1168,6 @@ err:
   BN_CTX_free(new_ctx);
   OPENSSL_free(secrets);
   OPENSSL_free(pre_comp);
-  OPENSSL_free(tmp_felems);
   return ret;
 }
 
diff --git a/crypto/ec/p256-64.c b/crypto/ec/p256-64.c
index 629c0c3c..5be9a060 100644
--- a/crypto/ec/p256-64.c
+++ b/crypto/ec/p256-64.c
@@ -134,20 +134,6 @@ static BIGNUM *smallfelem_to_BN(BIGNUM *out, const smallfelem in) {
 
 /* Field operations. */
 
-static void smallfelem_one(smallfelem out) {
-  out[0] = 1;
-  out[1] = 0;
-  out[2] = 0;
-  out[3] = 0;
-}
-
-static void smallfelem_assign(smallfelem out, const smallfelem in) {
-  out[0] = in[0];
-  out[1] = in[1];
-  out[2] = in[2];
-  out[3] = in[3];
-}
-
 static void felem_assign(felem out, const felem in) {
   out[0] = in[0];
   out[1] = in[1];
@@ -779,25 +765,6 @@ static void felem_contract(smallfelem out, const felem in) {
   subtract_u64(&out[3], &carry, result & kPrime[3]);
 }
 
-static void smallfelem_square_contract(smallfelem out, const smallfelem in) {
-  longfelem longtmp;
-  felem tmp;
-
-  smallfelem_square(longtmp, in);
-  felem_reduce(tmp, longtmp);
-  felem_contract(out, tmp);
-}
-
-static void smallfelem_mul_contract(smallfelem out, const smallfelem in1,
-                                    const smallfelem in2) {
-  longfelem longtmp;
-  felem tmp;
-
-  smallfelem_mul(longtmp, in1, in2);
-  felem_reduce(tmp, longtmp);
-  felem_contract(out, tmp);
-}
-
 /* felem_is_zero returns a limb with all bits set if |in| == 0 (mod p) and 0
  * otherwise.
  * On entry:
@@ -834,10 +801,6 @@ static limb smallfelem_is_zero(const smallfelem small) {
   return result;
 }
 
-static int smallfelem_is_zero_int(const smallfelem small) {
-  return (int)(smallfelem_is_zero(small) & ((limb)1));
-}
-
 /* felem_inv calculates |out| = |in|^{-1}
  *
  * Based on Fermat's Little Theorem:
@@ -937,14 +900,6 @@ static void felem_inv(felem out, const felem in) {
   felem_reduce(out, tmp); /* 2^256 - 2^224 + 2^192 + 2^96 - 3 */
 }
 
-static void smallfelem_inv_contract(smallfelem out, const smallfelem in) {
-  felem tmp;
-
-  smallfelem_expand(tmp, in);
-  felem_inv(tmp, tmp);
-  felem_contract(out, tmp);
-}
-
 /* Group operations
  * ----------------
  *
@@ -1484,7 +1439,7 @@ static char get_bit(const felem_bytearray in, int i) {
 static void batch_mul(felem x_out, felem y_out, felem z_out,
                       const felem_bytearray scalars[],
                       const unsigned num_points, const u8 *g_scalar,
-                      const int mixed, const smallfelem pre_comp[][17][3]) {
+                      const smallfelem pre_comp[][17][3]) {
   int i, skip;
   unsigned num, gen_mul = (g_scalar != NULL);
   felem nq[3], ftmp;
@@ -1518,9 +1473,8 @@ static void batch_mul(felem x_out, felem y_out, felem z_out,
       select_point(bits, 16, g_pre_comp[1], tmp);
 
       if (!skip) {
-        /* Arg 1 below is for "mixed" */
-        point_add(nq[0], nq[1], nq[2], nq[0], nq[1], nq[2], 1, tmp[0], tmp[1],
-                  tmp[2]);
+        point_add(nq[0], nq[1], nq[2], nq[0], nq[1], nq[2], 1 /* mixed */,
+                  tmp[0], tmp[1], tmp[2]);
       } else {
         smallfelem_expand(nq[0], tmp[0]);
         smallfelem_expand(nq[1], tmp[1]);
@@ -1535,9 +1489,8 @@ static void batch_mul(felem x_out, felem y_out, felem z_out,
       bits |= get_bit(g_scalar, i);
       /* select the point to add, in constant time */
       select_point(bits, 16, g_pre_comp[0], tmp);
-      /* Arg 1 below is for "mixed" */
-      point_add(nq[0], nq[1], nq[2], nq[0], nq[1], nq[2], 1, tmp[0], tmp[1],
-                tmp[2]);
+      point_add(nq[0], nq[1], nq[2], nq[0], nq[1], nq[2], 1 /* mixed */, tmp[0],
+                tmp[1], tmp[2]);
     }
 
     /* do other additions every 5 doublings */
@@ -1560,8 +1513,8 @@ static void batch_mul(felem x_out, felem y_out, felem z_out,
         felem_contract(tmp[1], ftmp);
 
         if (!skip) {
-          point_add(nq[0], nq[1], nq[2], nq[0], nq[1], nq[2], mixed, tmp[0],
-                    tmp[1], tmp[2]);
+          point_add(nq[0], nq[1], nq[2], nq[0], nq[1], nq[2], 0 /* mixed */,
+                    tmp[0], tmp[1], tmp[2]);
         } else {
           smallfelem_expand(nq[0], tmp[0]);
           smallfelem_expand(nq[1], tmp[1]);
@@ -1622,23 +1575,6 @@ int ec_GFp_nistp256_point_get_affine_coordinates(const EC_GROUP *group,
   return 1;
 }
 
-/* points below is of size |num|, and tmp_smallfelems is of size |num+1| */
-static void make_points_affine(size_t num, smallfelem points[][3],
-                               smallfelem tmp_smallfelems[]) {
-  /* Runs in constant time, unless an input is the point at infinity (which
-   * normally shouldn't happen). */
-  ec_GFp_nistp_points_make_affine_internal(
-      num, points, sizeof(smallfelem), tmp_smallfelems,
-      (void (*)(void *))smallfelem_one,
-      (int (*)(const void *))smallfelem_is_zero_int,
-      (void (*)(void *, const void *))smallfelem_assign,
-      (void (*)(void *, const void *))smallfelem_square_contract,
-      (void (*)(void *, const void *, const void *))smallfelem_mul_contract,
-      (void (*)(void *, const void *))smallfelem_inv_contract,
-      /* nothing to contract */
-      (void (*)(void *, const void *))smallfelem_assign);
-}
-
 int ec_GFp_nistp256_points_mul(const EC_GROUP *group, EC_POINT *r,
                                const BIGNUM *g_scalar, const EC_POINT *p_,
                                const BIGNUM *p_scalar_, BN_CTX *ctx) {
@@ -1651,13 +1587,11 @@ int ec_GFp_nistp256_points_mul(const EC_GROUP *group, EC_POINT *r,
 
   int ret = 0;
   int j;
-  int mixed = 0;
   BN_CTX *new_ctx = NULL;
   BIGNUM *x, *y, *z, *tmp_scalar;
   felem_bytearray g_secret;
   felem_bytearray *secrets = NULL;
   smallfelem(*pre_comp)[17][3] = NULL;
-  smallfelem *tmp_smallfelems = NULL;
   felem_bytearray tmp;
   unsigned i, num_bytes;
   size_t num_points = num;
@@ -1682,19 +1616,9 @@ int ec_GFp_nistp256_points_mul(const EC_GROUP *group, EC_POINT *r,
   }
 
   if (num_points > 0) {
-    if (num_points >= 3) {
-      /* unless we precompute multiples for just one or two points,
-       * converting those into affine form is time well spent */
-      mixed = 1;
-    }
     secrets = OPENSSL_malloc(num_points * sizeof(felem_bytearray));
     pre_comp = OPENSSL_malloc(num_points * sizeof(smallfelem[17][3]));
-    if (mixed) {
-      tmp_smallfelems =
-          OPENSSL_malloc((num_points * 17 + 1) * sizeof(smallfelem));
-    }
-    if (secrets == NULL || pre_comp == NULL ||
-        (mixed && tmp_smallfelems == NULL)) {
+    if (secrets == NULL || pre_comp == NULL) {
       OPENSSL_PUT_ERROR(EC, ERR_R_MALLOC_FAILURE);
       goto err;
     }
@@ -1751,9 +1675,6 @@ int ec_GFp_nistp256_points_mul(const EC_GROUP *group, EC_POINT *r,
         }
       }
     }
-    if (mixed) {
-      make_points_affine(num_points * 17, pre_comp[0], tmp_smallfelems);
-    }
   }
 
   if (g_scalar != NULL) {
@@ -1773,7 +1694,7 @@ int ec_GFp_nistp256_points_mul(const EC_GROUP *group, EC_POINT *r,
     flip_endian(g_secret, tmp, num_bytes);
   }
   batch_mul(x_out, y_out, z_out, (const felem_bytearray(*))secrets,
-            num_points, g_scalar != NULL ? g_secret : NULL, mixed,
+            num_points, g_scalar != NULL ? g_secret : NULL,
             (const smallfelem(*)[17][3])pre_comp);
 
   /* reduce the output to its unique minimal representation */
@@ -1793,7 +1714,6 @@ err:
   BN_CTX_free(new_ctx);
   OPENSSL_free(secrets);
   OPENSSL_free(pre_comp);
-  OPENSSL_free(tmp_smallfelems);
   return ret;
 }
 
diff --git a/crypto/ec/util-64.c b/crypto/ec/util-64.c
index 171b0631..40062712 100644
--- a/crypto/ec/util-64.c
+++ b/crypto/ec/util-64.c
@@ -21,80 +21,6 @@
 
 #include "internal.h"
 
-/* Convert an array of points into affine coordinates. (If the point at
- * infinity is found (Z = 0), it remains unchanged.) This function is
- * essentially an equivalent to EC_POINTs_make_affine(), but works with the
- * internal representation of points as used by ecp_nistp###.c rather than
- * with (BIGNUM-based) EC_POINT data structures. point_array is the
- * input/output buffer ('num' points in projective form, i.e. three
- * coordinates each), based on an internal representation of field elements
- * of size 'felem_size'. tmp_felems needs to point to a temporary array of
- * 'num'+1 field elements for storage of intermediate values. */
-void ec_GFp_nistp_points_make_affine_internal(
-    size_t num, void *point_array, size_t felem_size, void *tmp_felems,
-    void (*felem_one)(void *out), int (*felem_is_zero)(const void *in),
-    void (*felem_assign)(void *out, const void *in),
-    void (*felem_square)(void *out, const void *in),
-    void (*felem_mul)(void *out, const void *in1, const void *in2),
-    void (*felem_inv)(void *out, const void *in),
-    void (*felem_contract)(void *out, const void *in)) {
-  int i = 0;
-
-#define tmp_felem(I) (&((char *)tmp_felems)[(I)*felem_size])
-#define X(I) (&((char *)point_array)[3 * (I)*felem_size])
-#define Y(I) (&((char *)point_array)[(3 * (I) + 1) * felem_size])
-#define Z(I) (&((char *)point_array)[(3 * (I) + 2) * felem_size])
-
-  if (!felem_is_zero(Z(0))) {
-    felem_assign(tmp_felem(0), Z(0));
-  } else {
-    felem_one(tmp_felem(0));
-  }
-
-  for (i = 1; i < (int)num; i++) {
-    if (!felem_is_zero(Z(i))) {
-      felem_mul(tmp_felem(i), tmp_felem(i - 1), Z(i));
-    } else {
-      felem_assign(tmp_felem(i), tmp_felem(i - 1));
-    }
-  }
-  /* Now each tmp_felem(i) is the product of Z(0) .. Z(i), skipping any
-   * zero-valued factors: if Z(i) = 0, we essentially pretend that Z(i) = 1. */
-
-  felem_inv(tmp_felem(num - 1), tmp_felem(num - 1));
-  for (i = num - 1; i >= 0; i--) {
-    if (i > 0) {
-      /* tmp_felem(i-1) is the product of Z(0) .. Z(i-1), tmp_felem(i)
-       * is the inverse of the product of Z(0) .. Z(i). */
-      /* 1/Z(i) */
-      felem_mul(tmp_felem(num), tmp_felem(i - 1), tmp_felem(i));
-    } else {
-      felem_assign(tmp_felem(num), tmp_felem(0)); /* 1/Z(0) */
-    }
-
-    if (!felem_is_zero(Z(i))) {
-      if (i > 0) {
-        /* For next iteration, replace tmp_felem(i-1) by its inverse. */
-        felem_mul(tmp_felem(i - 1), tmp_felem(i), Z(i));
-      }
-
-      /* Convert point (X, Y, Z) into affine form (X/(Z^2), Y/(Z^3), 1). */
-      felem_square(Z(i), tmp_felem(num));    /* 1/(Z^2) */
-      felem_mul(X(i), X(i), Z(i));           /* X/(Z^2) */
-      felem_mul(Z(i), Z(i), tmp_felem(num)); /* 1/(Z^3) */
-      felem_mul(Y(i), Y(i), Z(i));           /* Y/(Z^3) */
-      felem_contract(X(i), X(i));
-      felem_contract(Y(i), Y(i));
-      felem_one(Z(i));
-    } else {
-      if (i > 0) {
-        /* For next iteration, replace tmp_felem(i-1) by its inverse. */
-        felem_assign(tmp_felem(i - 1), tmp_felem(i));
-      }
-    }
-  }
-}
-
 /* This function looks at 5+1 scalar bits (5 current, 1 adjacent less
  * significant bit), and recodes them into a signed digit for use in fast point
  * multiplication: the use of signed rather than unsigned digits means that