From 3837491174ececd6ff1b0dcdda754443f89a7699 Mon Sep 17 00:00:00 2001 From: =?utf8?q?Bodo=20M=C3=B6ller?= Date: Sun, 11 Mar 2001 12:27:24 +0000 Subject: [PATCH] Add functions EC_POINT_mul and EC_GROUP_precompute. The latter does nothing for now, but its existence means that applications can request precomputation when appropriate. --- CHANGES | 6 ++- crypto/ec/ec.h | 6 ++- crypto/ec/ec_err.c | 2 + crypto/ec/ec_mult.c | 62 ++++++++++++++++++++++++++-- crypto/ec/ectest.c | 98 +++++++++++++++++++++++++++++---------------- 5 files changed, 135 insertions(+), 39 deletions(-) diff --git a/CHANGES b/CHANGES index c516fe7087..8ed1b98633 100644 --- a/CHANGES +++ b/CHANGES @@ -4,7 +4,11 @@ Changes between 0.9.6 and 0.9.7 [xx XXX 2000] *) Function EC_POINTs_mul for simultaneous scalar multiplication - of an arbitrary number of elliptic curve points. + of an arbitrary number of elliptic curve points, optionally + including the generator defined for the EC_GROUP. + EC_POINT_mul is a simple wrapper function for the typical case + that the point list has just one item (besides the optional + generator). [Bodo Moeller] *) First EC_METHODs for curves over GF(p): diff --git a/crypto/ec/ec.h b/crypto/ec/ec.h index 084244457d..499c9331dc 100644 --- a/crypto/ec/ec.h +++ b/crypto/ec/ec.h @@ -160,7 +160,9 @@ int EC_POINT_make_affine(const EC_GROUP *, EC_POINT *, BN_CTX *); int EC_POINTs_make_affine(const EC_GROUP *, size_t num, EC_POINT *[], BN_CTX *); -int EC_POINTs_mul(const EC_GROUP *, EC_POINT *r, BIGNUM *, size_t num, EC_POINT *[], BIGNUM *[], BN_CTX *); +int EC_POINTs_mul(const EC_GROUP *, EC_POINT *r, const BIGNUM *, size_t num, const EC_POINT *[], const BIGNUM *[], BN_CTX *); +int EC_POINT_mul(const EC_GROUP *, EC_POINT *r, const BIGNUM *, const EC_POINT *, const BIGNUM *, BN_CTX *); +int EC_GROUP_precompute(EC_GROUP *, BN_CTX *); @@ -193,6 +195,7 @@ void ERR_load_EC_strings(void); #define EC_F_EC_GROUP_GET_EXTRA_DATA 107 #define EC_F_EC_GROUP_GET_ORDER 141 #define EC_F_EC_GROUP_NEW 108 +#define EC_F_EC_GROUP_PRECOMPUTE 142 #define EC_F_EC_GROUP_SET_CURVE_GFP 109 #define EC_F_EC_GROUP_SET_EXTRA_DATA 110 #define EC_F_EC_GROUP_SET_GENERATOR 111 @@ -231,6 +234,7 @@ void ERR_load_EC_strings(void); #define EC_R_POINT_IS_NOT_ON_CURVE 107 #define EC_R_SLOT_FULL 108 #define EC_R_UNDEFINED_GENERATOR 113 +#define EC_R_UNKNOWN_ORDER 114 #ifdef __cplusplus } diff --git a/crypto/ec/ec_err.c b/crypto/ec/ec_err.c index f88501502e..c0573e8330 100644 --- a/crypto/ec/ec_err.c +++ b/crypto/ec/ec_err.c @@ -86,6 +86,7 @@ static ERR_STRING_DATA EC_str_functs[]= {ERR_PACK(0,EC_F_EC_GROUP_GET_EXTRA_DATA,0), "EC_GROUP_get_extra_data"}, {ERR_PACK(0,EC_F_EC_GROUP_GET_ORDER,0), "EC_GROUP_get_order"}, {ERR_PACK(0,EC_F_EC_GROUP_NEW,0), "EC_GROUP_new"}, +{ERR_PACK(0,EC_F_EC_GROUP_PRECOMPUTE,0), "EC_GROUP_precompute"}, {ERR_PACK(0,EC_F_EC_GROUP_SET_CURVE_GFP,0), "EC_GROUP_set_curve_GFp"}, {ERR_PACK(0,EC_F_EC_GROUP_SET_EXTRA_DATA,0), "EC_GROUP_set_extra_data"}, {ERR_PACK(0,EC_F_EC_GROUP_SET_GENERATOR,0), "EC_GROUP_set_generator"}, @@ -127,6 +128,7 @@ static ERR_STRING_DATA EC_str_reasons[]= {EC_R_POINT_IS_NOT_ON_CURVE ,"point is not on curve"}, {EC_R_SLOT_FULL ,"slot full"}, {EC_R_UNDEFINED_GENERATOR ,"undefined generator"}, +{EC_R_UNKNOWN_ORDER ,"unknown order"}, {0,NULL} }; diff --git a/crypto/ec/ec_mult.c b/crypto/ec/ec_mult.c index 01574d8c93..0a749e83d3 100644 --- a/crypto/ec/ec_mult.c +++ b/crypto/ec/ec_mult.c @@ -77,8 +77,8 @@ * scalar*generator * is included in the addition if scalar != NULL */ -int EC_POINTs_mul(const EC_GROUP *group, EC_POINT *r, BIGNUM *scalar, - size_t num, EC_POINT *points[], BIGNUM *scalars[], BN_CTX *ctx) +int EC_POINTs_mul(const EC_GROUP *group, EC_POINT *r, const BIGNUM *scalar, + size_t num, const EC_POINT *points[], const BIGNUM *scalars[], BN_CTX *ctx) { BN_CTX *new_ctx = NULL; EC_POINT *generator = NULL; @@ -228,7 +228,7 @@ int EC_POINTs_mul(const EC_GROUP *group, EC_POINT *r, BIGNUM *scalar, { if (wbits[i] == 0) { - BIGNUM *s; + const BIGNUM *s; s = i < num ? scalars[i] : scalar; @@ -295,3 +295,59 @@ int EC_POINTs_mul(const EC_GROUP *group, EC_POINT *r, BIGNUM *scalar, } return ret; } + + +int EC_POINT_mul(const EC_GROUP *group, EC_POINT *r, const BIGNUM *g_scalar, const EC_POINT *point, const BIGNUM *p_scalar, BN_CTX *ctx) + { + const EC_POINT *points[1]; + const BIGNUM *scalars[1]; + + points[0] = point; + scalars[0] = p_scalar; + + return EC_POINTs_mul(group, r, g_scalar, (point != NULL && p_scalar != NULL), points, scalars, ctx); + } + + +int EC_GROUP_precompute(EC_GROUP *group, BN_CTX *ctx) + { + const EC_POINT *generator; + BN_CTX *new_ctx = NULL; + BIGNUM *order; + int ret = 0; + + generator = EC_GROUP_get0_generator(group); + if (generator == NULL) + { + ECerr(EC_F_EC_GROUP_PRECOMPUTE, EC_R_UNDEFINED_GENERATOR); + return 0; + } + + if (ctx == NULL) + { + ctx = new_ctx = BN_CTX_new(); + if (ctx == NULL) + return 0; + } + + BN_CTX_start(ctx); + order = BN_CTX_get(ctx); + if (order == NULL) goto err; + + if (!EC_GROUP_get_order(group, order, ctx)) return 0; + if (BN_is_zero(order)) + { + ECerr(EC_F_EC_GROUP_PRECOMPUTE, EC_R_UNKNOWN_ORDER); + goto err; + } + + /* TODO */ + + ret = 1; + + err: + BN_CTX_end(ctx); + if (new_ctx != NULL) + BN_CTX_free(new_ctx); + return ret; + } diff --git a/crypto/ec/ectest.c b/crypto/ec/ectest.c index 766a0dbc75..1ccc9ab8c5 100644 --- a/crypto/ec/ectest.c +++ b/crypto/ec/ectest.c @@ -80,8 +80,6 @@ void timings(EC_GROUP *group, int simult, BN_CTX *ctx) int i, j; BIGNUM *s, *s0; EC_POINT *P; - EC_POINT *points[1]; - BIGNUM *scalars[1]; s = BN_new(); s0 = BN_new(); @@ -97,9 +95,6 @@ void timings(EC_GROUP *group, int simult, BN_CTX *ctx) if (P == NULL) ABORT; EC_POINT_copy(P, EC_GROUP_get0_generator(group)); - points[0] = P; - scalars[0] = s0; - clck = clock(); for (i = 0; i < 10; i++) { @@ -110,7 +105,7 @@ void timings(EC_GROUP *group, int simult, BN_CTX *ctx) } for (j = 0; j < 10; j++) { - if (!EC_POINTs_mul(group, P, s, simult != 0, points, scalars, ctx)) ABORT; + if (!EC_POINT_mul(group, P, s, simult ? P : NULL, simult ? s0 : NULL, ctx)) ABORT; } fprintf(stdout, "."); fflush(stdout); @@ -322,12 +317,17 @@ int main(int argc, char *argv[]) if (!BN_hex2bn(&z, "07192B95FFC8DA78631011ED6B24CDD573F977A11E794811")) ABORT; if (0 != BN_cmp(y, z)) ABORT; - fprintf(stdout, "verify group order ... "); + fprintf(stdout, "verify group order ..."); fflush(stdout); if (!EC_GROUP_get_order(group, z, ctx)) ABORT; - if (!EC_POINTs_mul(group, Q, z, 0, NULL, NULL, ctx)) ABORT; + if (!EC_POINT_mul(group, Q, z, NULL, NULL, ctx)) ABORT; + if (!EC_POINT_is_at_infinity(group, Q)) ABORT; + fprintf(stdout, "."); + fflush(stdout); + if (!EC_GROUP_precompute(group, ctx)) ABORT; + if (!EC_POINT_mul(group, Q, z, NULL, NULL, ctx)) ABORT; if (!EC_POINT_is_at_infinity(group, Q)) ABORT; - fprintf(stdout, "ok\n"); + fprintf(stdout, " ok\n"); if (!(P_192 = EC_GROUP_new(EC_GROUP_method_of(group)))) ABORT; if (!EC_GROUP_copy(P_192, group)) ABORT; @@ -357,13 +357,18 @@ int main(int argc, char *argv[]) if (!BN_hex2bn(&z, "BD376388B5F723FB4C22DFE6CD4375A05A07476444D5819985007E34")) ABORT; if (0 != BN_cmp(y, z)) ABORT; - fprintf(stdout, "verify group order ... "); + fprintf(stdout, "verify group order ..."); fflush(stdout); if (!EC_GROUP_get_order(group, z, ctx)) ABORT; - if (!EC_POINTs_mul(group, Q, z, 0, NULL, NULL, ctx)) ABORT; + if (!EC_POINT_mul(group, Q, z, NULL, NULL, ctx)) ABORT; if (!EC_POINT_is_at_infinity(group, Q)) ABORT; - fprintf(stdout, "ok\n"); - + fprintf(stdout, "."); + fflush(stdout); + if (!EC_GROUP_precompute(group, ctx)) ABORT; + if (!EC_POINT_mul(group, Q, z, NULL, NULL, ctx)) ABORT; + if (!EC_POINT_is_at_infinity(group, Q)) ABORT; + fprintf(stdout, " ok\n"); + if (!(P_224 = EC_GROUP_new(EC_GROUP_method_of(group)))) ABORT; if (!EC_GROUP_copy(P_224, group)) ABORT; @@ -393,13 +398,18 @@ int main(int argc, char *argv[]) if (!BN_hex2bn(&z, "4FE342E2FE1A7F9B8EE7EB4A7C0F9E162BCE33576B315ECECBB6406837BF51F5")) ABORT; if (0 != BN_cmp(y, z)) ABORT; - fprintf(stdout, "verify group order ... "); + fprintf(stdout, "verify group order ..."); fflush(stdout); if (!EC_GROUP_get_order(group, z, ctx)) ABORT; - if (!EC_POINTs_mul(group, Q, z, 0, NULL, NULL, ctx)) ABORT; + if (!EC_POINT_mul(group, Q, z, NULL, NULL, ctx)) ABORT; if (!EC_POINT_is_at_infinity(group, Q)) ABORT; - fprintf(stdout, "ok\n"); - + fprintf(stdout, "."); + fflush(stdout); + if (!EC_GROUP_precompute(group, ctx)) ABORT; + if (!EC_POINT_mul(group, Q, z, NULL, NULL, ctx)) ABORT; + if (!EC_POINT_is_at_infinity(group, Q)) ABORT; + fprintf(stdout, " ok\n"); + if (!(P_256 = EC_GROUP_new(EC_GROUP_method_of(group)))) ABORT; if (!EC_GROUP_copy(P_256, group)) ABORT; @@ -434,13 +444,18 @@ int main(int argc, char *argv[]) "7CE9DA3113B5F0B8C00A60B1CE1D7E819D7A431D7C90EA0E5F")) ABORT; if (0 != BN_cmp(y, z)) ABORT; - fprintf(stdout, "verify group order ... "); + fprintf(stdout, "verify group order ..."); fflush(stdout); if (!EC_GROUP_get_order(group, z, ctx)) ABORT; - if (!EC_POINTs_mul(group, Q, z, 0, NULL, NULL, ctx)) ABORT; + if (!EC_POINT_mul(group, Q, z, NULL, NULL, ctx)) ABORT; if (!EC_POINT_is_at_infinity(group, Q)) ABORT; - fprintf(stdout, "ok\n"); - + fprintf(stdout, "."); + fflush(stdout); + if (!EC_GROUP_precompute(group, ctx)) ABORT; + if (!EC_POINT_mul(group, Q, z, NULL, NULL, ctx)) ABORT; + if (!EC_POINT_is_at_infinity(group, Q)) ABORT; + fprintf(stdout, " ok\n"); + if (!(P_384 = EC_GROUP_new(EC_GROUP_method_of(group)))) ABORT; if (!EC_GROUP_copy(P_384, group)) ABORT; @@ -481,12 +496,17 @@ int main(int argc, char *argv[]) "7086A272C24088BE94769FD16650")) ABORT; if (0 != BN_cmp(y, z)) ABORT; - fprintf(stdout, "verify group order ... "); + fprintf(stdout, "verify group order ..."); fflush(stdout); if (!EC_GROUP_get_order(group, z, ctx)) ABORT; - if (!EC_POINTs_mul(group, Q, z, 0, NULL, NULL, ctx)) ABORT; + if (!EC_POINT_mul(group, Q, z, NULL, NULL, ctx)) ABORT; + if (!EC_POINT_is_at_infinity(group, Q)) ABORT; + fprintf(stdout, "."); + fflush(stdout); + if (!EC_GROUP_precompute(group, ctx)) ABORT; + if (!EC_POINT_mul(group, Q, z, NULL, NULL, ctx)) ABORT; if (!EC_POINT_is_at_infinity(group, Q)) ABORT; - fprintf(stdout, "ok\n"); + fprintf(stdout, " ok\n"); if (!(P_521 = EC_GROUP_new(EC_GROUP_method_of(group)))) ABORT; if (!EC_GROUP_copy(P_521, group)) ABORT; @@ -505,17 +525,17 @@ int main(int argc, char *argv[]) if (!EC_POINT_is_at_infinity(group, R)) ABORT; /* R = P + 2Q */ { - EC_POINT *points[2]; - BIGNUM *scalars[2]; + const EC_POINT *points[3]; + const BIGNUM *scalars[3]; if (EC_POINT_is_at_infinity(group, Q)) ABORT; + points[0] = Q; + points[1] = Q; + points[2] = Q; if (!BN_add(y, z, BN_value_one())) ABORT; if (BN_is_odd(y)) ABORT; if (!BN_rshift1(y, y)) ABORT; - - points[0] = Q; - points[1] = Q; scalars[0] = y; /* (group order + 1)/2, so y*Q + y*Q = Q */ scalars[1] = y; @@ -534,20 +554,30 @@ int main(int argc, char *argv[]) if (!BN_pseudo_rand(y, BN_num_bits(y), 0, 0)) ABORT; if (!BN_copy(z, y)) ABORT; z->neg = 1; - - points[0] = Q; - points[1] = Q; scalars[0] = y; - scalars[1] = z; + scalars[1] = z; /* z = -y */ if (!EC_POINTs_mul(group, P, NULL, 2, points, scalars, ctx)) ABORT; if (!EC_POINT_is_at_infinity(group, P)) ABORT; + fprintf(stdout, "."); + fflush(stdout); + + if (!BN_pseudo_rand(x, BN_num_bits(y) - 1, 0, 0)) ABORT; + if (!BN_add(z, x, y)) ABORT; + z->neg = 1; + scalars[0] = x; + scalars[1] = y; + scalars[2] = z; /* z = -(x+y) */ + + if (!EC_POINTs_mul(group, P, NULL, 3, points, scalars, ctx)) ABORT; + if (!EC_POINT_is_at_infinity(group, P)) ABORT; + fprintf(stdout, " ok\n\n"); } -#if 0 +#if 1 timings(P_192, 0, ctx); timings(P_192, 1, ctx); timings(P_224, 0, ctx); -- 2.34.1