diff options
Diffstat (limited to 'crypto/ec/p256-64.c')
| -rw-r--r-- | crypto/ec/p256-64.c | 205 |
1 files changed, 71 insertions, 134 deletions
diff --git a/crypto/ec/p256-64.c b/crypto/ec/p256-64.c index b94e226e..c4259b62 100644 --- a/crypto/ec/p256-64.c +++ b/crypto/ec/p256-64.c @@ -27,7 +27,6 @@ #include <openssl/ec.h> #include <openssl/err.h> #include <openssl/mem.h> -#include <openssl/obj.h> #include <string.h> @@ -94,8 +93,8 @@ static void smallfelem_to_bin32(u8 out[32], const smallfelem in) { } /* To preserve endianness when using BN_bn2bin and BN_bin2bn. */ -static void flip_endian(u8 *out, const u8 *in, unsigned len) { - unsigned i; +static void flip_endian(u8 *out, const u8 *in, size_t len) { + size_t i; for (i = 0; i < len; ++i) { out[i] = in[len - 1 - i]; } @@ -111,7 +110,7 @@ static int BN_to_felem(felem out, const BIGNUM *bn) { felem_bytearray b_out; /* BN_bn2bin eats leading zeroes */ memset(b_out, 0, sizeof(b_out)); - unsigned num_bytes = BN_num_bytes(bn); + size_t num_bytes = BN_num_bytes(bn); if (num_bytes > sizeof(b_out)) { OPENSSL_PUT_ERROR(EC, EC_R_BIGNUM_OUT_OF_RANGE); return 0; @@ -134,20 +133,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]; @@ -343,8 +328,7 @@ static void felem_shrink(smallfelem out, const felem in) { * conditionally subtract kPrime if tmp[3] is large enough. */ high = tmp[3] >> 64; /* As tmp[3] < 2^65, high is either 1 or 0 */ - high <<= 63; - high >>= 63; + high = ~(high - 1); /* high is: * all ones if the high word of tmp[3] is 1 * all zeros if the high word of tmp[3] if 0 */ @@ -735,7 +719,7 @@ static void felem_contract(smallfelem out, const felem in) { * each u64, from most-significant to least significant. For each one, if * all words so far have been equal (m is all ones) then a non-equal * result is the answer. Otherwise we continue. */ - unsigned i; + size_t i; for (i = 3; i < 4; i--) { u64 equal; uint128_t a = ((uint128_t)kPrime[i]) - out[i]; @@ -779,25 +763,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 +799,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: @@ -849,7 +810,7 @@ static void felem_inv(felem out, const felem in) { /* each e_I will hold |in|^{2^I - 1} */ felem e2, e4, e8, e16, e32, e64; longfelem tmp; - unsigned i; + size_t i; felem_square(tmp, in); felem_reduce(ftmp, tmp); /* 2^1 */ @@ -937,14 +898,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 * ---------------- * @@ -1055,7 +1008,7 @@ static void point_double_small(smallfelem x_out, smallfelem y_out, /* copy_conditional copies in to out iff mask is all ones. */ static void copy_conditional(felem out, const felem in, limb mask) { - unsigned i; + size_t i; for (i = 0; i < NLIMBS; ++i) { const limb tmp = mask & (in[i] ^ out[i]); out[i] ^= tmp; @@ -1064,7 +1017,7 @@ static void copy_conditional(felem out, const felem in, limb mask) { /* copy_small_conditional copies in to out iff mask is all ones. */ static void copy_small_conditional(felem out, const smallfelem in, limb mask) { - unsigned i; + size_t i; const u64 mask64 = mask; for (i = 0; i < NLIMBS; ++i) { out[i] = ((limb)(in[i] & mask64)) | (out[i] & ~mask); @@ -1448,12 +1401,13 @@ static const smallfelem g_pre_comp[2][16][3] = { /* select_point selects the |idx|th point from a precomputation table and * copies it to out. */ -static void select_point(const u64 idx, unsigned int size, - const smallfelem pre_comp[16][3], smallfelem out[3]) { - unsigned i, j; +static void select_point(const u64 idx, size_t size, + const smallfelem pre_comp[/*size*/][3], + smallfelem out[3]) { u64 *outlimbs = &out[0][0]; memset(outlimbs, 0, 3 * sizeof(smallfelem)); + size_t i; for (i = 0; i < size; i++) { const u64 *inlimbs = (const u64 *)&pre_comp[i][0][0]; u64 mask = i ^ idx; @@ -1462,6 +1416,7 @@ static void select_point(const u64 idx, unsigned int size, mask |= mask >> 1; mask &= 1; mask--; + size_t j; for (j = 0; j < NLIMBS * 3; j++) { outlimbs[j] |= inlimbs[j] & mask; } @@ -1483,10 +1438,8 @@ static char get_bit(const felem_bytearray in, int i) { * 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 unsigned num_points, const u8 *g_scalar, - const int mixed, const smallfelem pre_comp[][17][3]) { - int i, skip; - unsigned num, gen_mul = (g_scalar != NULL); + const size_t num_points, const u8 *g_scalar, + const smallfelem pre_comp[][17][3]) { felem nq[3], ftmp; smallfelem tmp[3]; u64 bits; @@ -1499,16 +1452,16 @@ static void batch_mul(felem x_out, felem y_out, felem z_out, * of the generator (two in each of the last 32 rounds) and additions of * other points multiples (every 5th round). */ - skip = 1; /* save two point operations in the first - * round */ - for (i = (num_points ? 255 : 31); i >= 0; --i) { + int skip = 1; /* save two point operations in the first round */ + size_t i = num_points != 0 ? 255 : 31; + for (;;) { /* double */ if (!skip) { point_double(nq[0], nq[1], nq[2], nq[0], nq[1], nq[2]); } /* add multiples of the generator */ - if (gen_mul && i <= 31) { + if (g_scalar != NULL && i <= 31) { /* first, look 32 bits upwards */ bits = get_bit(g_scalar, i + 224) << 3; bits |= get_bit(g_scalar, i + 160) << 2; @@ -1518,9 +1471,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,14 +1487,14 @@ 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 */ - if (num_points && (i % 5 == 0)) { + 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; @@ -1560,8 +1512,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]); @@ -1570,6 +1522,11 @@ static void batch_mul(felem x_out, felem y_out, felem z_out, } } } + + if (i == 0) { + break; + } + --i; } felem_assign(x_out, nq[0]); felem_assign(y_out, nq[1]); @@ -1583,10 +1540,10 @@ static void batch_mul(felem x_out, felem y_out, felem z_out, /* Takes the Jacobian coordinates (X, Y, Z) of a point and returns (X', Y') = * (X/Z^2, Y/Z^3). */ -int ec_GFp_nistp256_point_get_affine_coordinates(const EC_GROUP *group, - const EC_POINT *point, - BIGNUM *x, BIGNUM *y, - BN_CTX *ctx) { +static int ec_GFp_nistp256_point_get_affine_coordinates(const EC_GROUP *group, + const EC_POINT *point, + BIGNUM *x, BIGNUM *y, + BN_CTX *ctx) { felem z1, z2, x_in, y_in; smallfelem x_out, y_out; longfelem tmp; @@ -1603,45 +1560,38 @@ int ec_GFp_nistp256_point_get_affine_coordinates(const EC_GROUP *group, felem_inv(z2, z1); felem_square(tmp, z2); felem_reduce(z1, tmp); - felem_mul(tmp, x_in, z1); - felem_reduce(x_in, tmp); - felem_contract(x_out, x_in); - if (x != NULL && !smallfelem_to_BN(x, x_out)) { - OPENSSL_PUT_ERROR(EC, ERR_R_BN_LIB); - return 0; + + if (x != NULL) { + felem_mul(tmp, x_in, z1); + felem_reduce(x_in, tmp); + felem_contract(x_out, x_in); + if (!smallfelem_to_BN(x, x_out)) { + OPENSSL_PUT_ERROR(EC, ERR_R_BN_LIB); + return 0; + } } - felem_mul(tmp, z1, z2); - felem_reduce(z1, tmp); - felem_mul(tmp, y_in, z1); - felem_reduce(y_in, tmp); - felem_contract(y_out, y_in); - if (y != NULL && !smallfelem_to_BN(y, y_out)) { - OPENSSL_PUT_ERROR(EC, ERR_R_BN_LIB); - return 0; + + if (y != NULL) { + felem_mul(tmp, z1, z2); + felem_reduce(z1, tmp); + felem_mul(tmp, y_in, z1); + felem_reduce(y_in, tmp); + felem_contract(y_out, y_in); + if (!smallfelem_to_BN(y, y_out)) { + OPENSSL_PUT_ERROR(EC, ERR_R_BN_LIB); + return 0; + } } - 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); + return 1; } -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) { +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|. */ @@ -1650,16 +1600,12 @@ int ec_GFp_nistp256_points_mul(const EC_GROUP *group, EC_POINT *r, BIGNUM const *const *scalars = p_ != NULL ? &p_scalar_ : NULL; 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; smallfelem x_in, y_in, z_in; felem x_out, y_out, z_out; @@ -1682,19 +1628,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; } @@ -1703,6 +1639,7 @@ int ec_GFp_nistp256_points_mul(const EC_GROUP *group, EC_POINT *r, * i.e., they contribute nothing to the linear combination. */ memset(secrets, 0, num_points * sizeof(felem_bytearray)); memset(pre_comp, 0, num_points * 17 * 3 * sizeof(smallfelem)); + size_t i; for (i = 0; i < num_points; ++i) { if (i == num) { /* we didn't have a valid precomputation, so we pick the generator. */ @@ -1714,6 +1651,7 @@ int ec_GFp_nistp256_points_mul(const EC_GROUP *group, EC_POINT *r, 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 @@ -1736,6 +1674,7 @@ int ec_GFp_nistp256_points_mul(const EC_GROUP *group, EC_POINT *r, 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); + size_t j; for (j = 2; j <= 16; ++j) { if (j & 1) { point_add_small(pre_comp[i][j][0], pre_comp[i][j][1], @@ -1751,12 +1690,11 @@ 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) { + size_t num_bytes; + memset(g_secret, 0, sizeof(g_secret)); /* reduce g_scalar to 0 <= g_scalar < 2^256 */ if (BN_num_bits(g_scalar) > 256 || BN_is_negative(g_scalar)) { @@ -1773,7 +1711,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 +1731,6 @@ err: BN_CTX_free(new_ctx); OPENSSL_free(secrets); OPENSSL_free(pre_comp); - OPENSSL_free(tmp_smallfelems); return ret; } @@ -1807,7 +1744,7 @@ const EC_METHOD *EC_GFp_nistp256_method(void) { ec_GFp_nistp256_points_mul, 0 /* check_pub_key_order */, ec_GFp_simple_field_mul, ec_GFp_simple_field_sqr, - 0 /* field_encode */, 0 /* field_decode */, 0 /* field_set_to_one */ + 0 /* field_encode */, 0 /* field_decode */, }; return &ret; |