Simplify ec_GFp_nistp256_points_mul logic.
Passing in an array of scalars was removed some time ago, but a few
remnants of it remain.
Change-Id: Ia51dcf1f85116ec663e657cc8dbef7f23ffa2edb
Reviewed-on: https://boringssl-review.googlesource.com/13055
Commit-Queue: David Benjamin <davidben@google.com>
Reviewed-by: Adam Langley <agl@google.com>
diff --git a/crypto/ec/p256-64.c b/crypto/ec/p256-64.c
index 38fee45..0f32c2e 100644
--- a/crypto/ec/p256-64.c
+++ b/crypto/ec/p256-64.c
@@ -1427,14 +1427,12 @@
}
/* Interleaved point multiplication using precomputed point multiples: The
- * small point multiples 0*P, 1*P, ..., 17*P are in pre_comp[], the scalars
- * in scalars[]. If g_scalar is non-NULL, we also add this multiple of the
- * generator, using certain (large) precomputed multiples in g_pre_comp.
+ * small point multiples 0*P, 1*P, ..., 17*P are in p_pre_comp, the scalar
+ * in p_scalar, if non-NULL. If g_scalar is non-NULL, we also add this multiple
+ * of the generator, using certain (large) precomputed multiples in g_pre_comp.
* Output point (X, Y, Z) is stored in x_out, y_out, z_out. */
-static void batch_mul(felem x_out, felem y_out, felem z_out,
- const felem_bytearray scalars[],
- const size_t num_points, const u8 *g_scalar,
- const smallfelem pre_comp[][17][3]) {
+static void batch_mul(felem x_out, felem y_out, felem z_out, const u8 *p_scalar,
+ const u8 *g_scalar, const smallfelem p_pre_comp[17][3]) {
felem nq[3], ftmp;
smallfelem tmp[3];
u64 bits;
@@ -1443,12 +1441,12 @@
/* set nq to the point at infinity */
OPENSSL_memset(nq, 0, 3 * sizeof(felem));
- /* Loop over all scalars msb-to-lsb, interleaving additions of multiples
- * of the generator (two in each of the last 32 rounds) and additions of
- * other points multiples (every 5th round). */
+ /* Loop over both scalars msb-to-lsb, interleaving additions of multiples
+ * of the generator (two in each of the last 32 rounds) and additions of p
+ * (every 5th round). */
int skip = 1; /* save two point operations in the first round */
- size_t i = num_points != 0 ? 255 : 31;
+ size_t i = p_scalar != NULL ? 255 : 31;
for (;;) {
/* double */
if (!skip) {
@@ -1487,34 +1485,30 @@
}
/* do other additions every 5 doublings */
- if (num_points != 0 && i % 5 == 0) {
- /* loop over all scalars */
- size_t num;
- for (num = 0; num < num_points; ++num) {
- bits = get_bit(scalars[num], i + 4) << 5;
- bits |= get_bit(scalars[num], i + 3) << 4;
- bits |= get_bit(scalars[num], i + 2) << 3;
- bits |= get_bit(scalars[num], i + 1) << 2;
- bits |= get_bit(scalars[num], i) << 1;
- bits |= get_bit(scalars[num], i - 1);
- ec_GFp_nistp_recode_scalar_bits(&sign, &digit, bits);
+ if (p_scalar != NULL && i % 5 == 0) {
+ bits = get_bit(p_scalar, i + 4) << 5;
+ bits |= get_bit(p_scalar, i + 3) << 4;
+ bits |= get_bit(p_scalar, i + 2) << 3;
+ bits |= get_bit(p_scalar, i + 1) << 2;
+ bits |= get_bit(p_scalar, i) << 1;
+ bits |= get_bit(p_scalar, i - 1);
+ ec_GFp_nistp_recode_scalar_bits(&sign, &digit, bits);
- /* select the point to add or subtract, in constant time. */
- select_point(digit, 17, pre_comp[num], tmp);
- smallfelem_neg(ftmp, tmp[1]); /* (X, -Y, Z) is the negative
- * point */
- copy_small_conditional(ftmp, tmp[1], (((limb)sign) - 1));
- felem_contract(tmp[1], ftmp);
+ /* select the point to add or subtract, in constant time. */
+ select_point(digit, 17, p_pre_comp, tmp);
+ smallfelem_neg(ftmp, tmp[1]); /* (X, -Y, Z) is the negative
+ * point */
+ copy_small_conditional(ftmp, tmp[1], (((limb)sign) - 1));
+ felem_contract(tmp[1], ftmp);
- if (!skip) {
- 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]);
- smallfelem_expand(nq[2], tmp[2]);
- skip = 0;
- }
+ if (!skip) {
+ 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]);
+ smallfelem_expand(nq[2], tmp[2]);
+ skip = 0;
}
}
@@ -1581,31 +1575,17 @@
return 1;
}
-static 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) {
- /* TODO: This function used to take |points| and |scalars| as arrays of
- * |num| elements. The code below should be simplified to work in terms of |p|
- * and |p_scalar|. */
- size_t num = p_ != NULL ? 1 : 0;
- const EC_POINT **points = p_ != NULL ? &p_ : NULL;
- BIGNUM const *const *scalars = p_ != NULL ? &p_scalar_ : NULL;
-
+static 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) {
int ret = 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;
+ felem_bytearray g_secret, p_secret;
+ smallfelem p_pre_comp[17][3];
felem_bytearray tmp;
- size_t num_points = num;
smallfelem x_in, y_in, z_in;
felem x_out, y_out, z_out;
- const EC_POINT *p = NULL;
- const BIGNUM *p_scalar = NULL;
if (ctx == NULL) {
ctx = new_ctx = BN_CTX_new();
@@ -1622,65 +1602,44 @@
goto err;
}
- if (num_points > 0) {
- secrets = OPENSSL_malloc(num_points * sizeof(felem_bytearray));
- pre_comp = OPENSSL_malloc(num_points * sizeof(smallfelem[17][3]));
- if (secrets == NULL || pre_comp == NULL) {
- OPENSSL_PUT_ERROR(EC, ERR_R_MALLOC_FAILURE);
+ if (p != NULL && p_scalar != NULL) {
+ /* We treat NULL scalars as 0, and NULL points as points at infinity, i.e.,
+ * they contribute nothing to the linear combination. */
+ OPENSSL_memset(&p_secret, 0, sizeof(p_secret));
+ OPENSSL_memset(&p_pre_comp, 0, sizeof(p_pre_comp));
+ size_t num_bytes;
+ /* Reduce g_scalar to 0 <= g_scalar < 2^256. */
+ if (BN_num_bits(p_scalar) > 256 || BN_is_negative(p_scalar)) {
+ /* This is an unusual input, and we don't guarantee constant-timeness. */
+ if (!BN_nnmod(tmp_scalar, p_scalar, &group->order, ctx)) {
+ OPENSSL_PUT_ERROR(EC, ERR_R_BN_LIB);
+ goto err;
+ }
+ num_bytes = BN_bn2bin(tmp_scalar, tmp);
+ } else {
+ num_bytes = BN_bn2bin(p_scalar, tmp);
+ }
+ flip_endian(p_secret, tmp, num_bytes);
+ /* Precompute multiples. */
+ if (!BN_to_felem(x_out, &p->X) ||
+ !BN_to_felem(y_out, &p->Y) ||
+ !BN_to_felem(z_out, &p->Z)) {
goto err;
}
-
- /* we treat NULL scalars as 0, and NULL points as points at infinity,
- * i.e., they contribute nothing to the linear combination. */
- OPENSSL_memset(secrets, 0, num_points * sizeof(felem_bytearray));
- OPENSSL_memset(pre_comp, 0, num_points * 17 * 3 * sizeof(smallfelem));
- for (size_t i = 0; i < num_points; ++i) {
- if (i == num) {
- /* we didn't have a valid precomputation, so we pick the generator. */
- p = EC_GROUP_get0_generator(group);
- p_scalar = g_scalar;
+ felem_shrink(p_pre_comp[1][0], x_out);
+ felem_shrink(p_pre_comp[1][1], y_out);
+ felem_shrink(p_pre_comp[1][2], z_out);
+ for (size_t j = 2; j <= 16; ++j) {
+ if (j & 1) {
+ point_add_small(p_pre_comp[j][0], p_pre_comp[j][1],
+ p_pre_comp[j][2], p_pre_comp[1][0],
+ p_pre_comp[1][1], p_pre_comp[1][2],
+ p_pre_comp[j - 1][0], p_pre_comp[j - 1][1],
+ p_pre_comp[j - 1][2]);
} else {
- /* the i^th point */
- p = points[i];
- p_scalar = scalars[i];
- }
- if (p_scalar != NULL && p != NULL) {
- size_t num_bytes;
- /* reduce g_scalar to 0 <= g_scalar < 2^256 */
- if (BN_num_bits(p_scalar) > 256 || BN_is_negative(p_scalar)) {
- /* this is an unusual input, and we don't guarantee
- * constant-timeness. */
- if (!BN_nnmod(tmp_scalar, p_scalar, &group->order, ctx)) {
- OPENSSL_PUT_ERROR(EC, ERR_R_BN_LIB);
- goto err;
- }
- num_bytes = BN_bn2bin(tmp_scalar, tmp);
- } else {
- num_bytes = BN_bn2bin(p_scalar, tmp);
- }
- flip_endian(secrets[i], tmp, num_bytes);
- /* precompute multiples */
- if (!BN_to_felem(x_out, &p->X) ||
- !BN_to_felem(y_out, &p->Y) ||
- !BN_to_felem(z_out, &p->Z)) {
- goto err;
- }
- felem_shrink(pre_comp[i][1][0], x_out);
- felem_shrink(pre_comp[i][1][1], y_out);
- felem_shrink(pre_comp[i][1][2], z_out);
- for (size_t j = 2; j <= 16; ++j) {
- if (j & 1) {
- point_add_small(pre_comp[i][j][0], pre_comp[i][j][1],
- pre_comp[i][j][2], pre_comp[i][1][0],
- pre_comp[i][1][1], pre_comp[i][1][2],
- pre_comp[i][j - 1][0], pre_comp[i][j - 1][1],
- pre_comp[i][j - 1][2]);
- } else {
- point_double_small(pre_comp[i][j][0], pre_comp[i][j][1],
- pre_comp[i][j][2], pre_comp[i][j / 2][0],
- pre_comp[i][j / 2][1], pre_comp[i][j / 2][2]);
- }
- }
+ point_double_small(p_pre_comp[j][0], p_pre_comp[j][1],
+ p_pre_comp[j][2], p_pre_comp[j / 2][0],
+ p_pre_comp[j / 2][1], p_pre_comp[j / 2][2]);
}
}
}
@@ -1703,9 +1662,10 @@
}
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,
- (const smallfelem(*)[17][3])pre_comp);
+ batch_mul(x_out, y_out, z_out,
+ (p != NULL && p_scalar != NULL) ? p_secret : NULL,
+ g_scalar != NULL ? g_secret : NULL,
+ (const smallfelem(*)[3]) &p_pre_comp);
/* reduce the output to its unique minimal representation */
felem_contract(x_in, x_out);
@@ -1722,8 +1682,6 @@
err:
BN_CTX_end(ctx);
BN_CTX_free(new_ctx);
- OPENSSL_free(secrets);
- OPENSSL_free(pre_comp);
return ret;
}
