From bb62a8b0c57c88ec189389f07250dee9c87d0681 Mon Sep 17 00:00:00 2001 From: =?utf8?q?Bodo=20M=C3=B6ller?= Date: Thu, 8 Mar 2001 19:14:52 +0000 Subject: [PATCH] More method functions for elliptic curves, and an ectest.c that actually tests something. --- CHANGES | 4 +- config | 2 +- crypto/ec/ec.h | 21 +- crypto/ec/ec_err.c | 5 + crypto/ec/ec_lcl.h | 24 +- crypto/ec/ec_lib.c | 39 +-- crypto/ec/ecp_mont.c | 7 +- crypto/ec/ecp_nist.c | 7 +- crypto/ec/ecp_recp.c | 7 +- crypto/ec/ecp_smpl.c | 562 ++++++++++++++++++++++++++++++++----------- crypto/ec/ectest.c | 149 +++++++++++- 11 files changed, 649 insertions(+), 178 deletions(-) diff --git a/CHANGES b/CHANGES index b3a6f2f40f..1391c8f11e 100644 --- a/CHANGES +++ b/CHANGES @@ -3,8 +3,8 @@ Changes between 0.9.6 and 0.9.7 [xx XXX 2000] - *) Replace rdtsc with _emit statements for VC++ version 5. - [Jeremy Cooper ] + *) Replace rdtsc with _emit statements for VC++ version 5. + [Jeremy Cooper ] *) Hide BN_CTX structure details in bn_lcl.h instead of publishing them in . Also further increase BN_CTX_NUM to 24. diff --git a/config b/config index a6411528af..2d363d80ef 100755 --- a/config +++ b/config @@ -557,7 +557,7 @@ case "$GUESSOS" in i386-*) options="$options 386" ;; esac -for i in bf cast des dh dsa hmac md2 md5 mdc2 rc2 rc4 rc5 ripemd rsa sha +for i in bf cast des dh dsa ec hmac md2 md5 mdc2 rc2 rc4 rc5 ripemd rsa sha do if [ ! -d crypto/$i ] then diff --git a/crypto/ec/ec.h b/crypto/ec/ec.h index 0f0b9e08a5..16cbf188ec 100644 --- a/crypto/ec/ec.h +++ b/crypto/ec/ec.h @@ -56,6 +56,10 @@ #ifndef HEADER_EC_H #define HEADER_EC_H +#ifdef OPENSSL_NO_EC +#error Elliptic curves are disabled. +#endif + #include #include @@ -64,7 +68,6 @@ extern "C" { #endif - typedef enum { /* values as defined in X9.62 (ECDSA) and elsewhere */ POINT_CONVERSION_COMPRESSED = 2, @@ -81,7 +84,7 @@ typedef struct ec_group_st -- field definition -- curve coefficients -- optional generator with associated information (order, cofactor) - -- optional Lim/Lee precomputation table + -- optional extra data (Lim/Lee precomputation table) */ EC_GROUP; @@ -103,19 +106,20 @@ EC_GROUP *EC_GROUP_new(const EC_METHOD *); * Otherwise we would declare * int EC_GROUP_set_curve(EC_GROUP *, .....); */ -int EC_GROUP_set_curve_GFp(EC_GROUP *, const BIGNUM *p, const BIGNUM *a, const BIGNUM *b, BN_CTX *); void EC_GROUP_free(EC_GROUP *); void EC_GROUP_clear_free(EC_GROUP *); int EC_GROUP_copy(EC_GROUP *, const EC_GROUP*); +int EC_GROUP_set_curve_GFp(EC_GROUP *, const BIGNUM *p, const BIGNUM *a, const BIGNUM *b, BN_CTX *); +int EC_GROUP_get_curve_GFp(EC_GROUP *, BIGNUM *p, BIGNUM *a, BIGNUM *b, BN_CTX *); /* EC_GROUP_new_GFp() calls EC_GROUP_new() and EC_GROUP_set_GFp() * after choosing an appropriate EC_METHOD */ EC_GROUP *EC_GROUP_new_curve_GFp(const BIGNUM *p, const BIGNUM *a, const BIGNUM *b, BN_CTX *); int EC_GROUP_set_generator(EC_GROUP *, const EC_POINT *generator, const BIGNUM *order, const BIGNUM *cofactor); - -/* TODO: 'set' and 'get' functions for EC_GROUPs */ - +EC_POINT *EC_group_get0_generator(EC_GROUP *); +int EC_GROUP_get_order(EC_GROUP *, BIGNUM *order, BN_CTX *); +int EC_GROUP_get_cofactor(EC_GROUP *, BIGNUM *cofactor, BN_CTX *); EC_POINT *EC_POINT_new(const EC_GROUP *); void EC_POINT_free(EC_POINT *); @@ -170,7 +174,10 @@ void ERR_load_EC_strings(void); #define EC_F_EC_GFP_SIMPLE_OCT2POINT 103 #define EC_F_EC_GFP_SIMPLE_POINT2OCT 104 #define EC_F_EC_GFP_SIMPLE_POINT_GET_AFFINE_COORDINATES_GFP 105 +#define EC_F_EC_GFP_SIMPLE_POINT_SET_AFFINE_COORDINATES_GFP 128 +#define EC_F_EC_GFP_SIMPLE_SET_COMPRESSED_COORDINATES_GFP 129 #define EC_F_EC_GROUP_COPY 106 +#define EC_F_EC_GROUP_GET_CURVE_GFP 130 #define EC_F_EC_GROUP_GET_EXTRA_DATA 107 #define EC_F_EC_GROUP_NEW 108 #define EC_F_EC_GROUP_SET_CURVE_GFP 109 @@ -196,6 +203,8 @@ void ERR_load_EC_strings(void); /* Reason codes. */ #define EC_R_BUFFER_TOO_SMALL 100 #define EC_R_INCOMPATIBLE_OBJECTS 101 +#define EC_R_INVALID_COMPRESSED_POINT 110 +#define EC_R_INVALID_COMPRESSION_BIT 109 #define EC_R_INVALID_ENCODING 102 #define EC_R_INVALID_FIELD 103 #define EC_R_INVALID_FORM 104 diff --git a/crypto/ec/ec_err.c b/crypto/ec/ec_err.c index 90b7ddc314..4c03f5cace 100644 --- a/crypto/ec/ec_err.c +++ b/crypto/ec/ec_err.c @@ -72,7 +72,10 @@ static ERR_STRING_DATA EC_str_functs[]= {ERR_PACK(0,EC_F_EC_GFP_SIMPLE_OCT2POINT,0), "ec_GFp_simple_oct2point"}, {ERR_PACK(0,EC_F_EC_GFP_SIMPLE_POINT2OCT,0), "ec_GFp_simple_point2oct"}, {ERR_PACK(0,EC_F_EC_GFP_SIMPLE_POINT_GET_AFFINE_COORDINATES_GFP,0), "ec_GFp_simple_point_get_affine_coordinates_GFp"}, +{ERR_PACK(0,EC_F_EC_GFP_SIMPLE_POINT_SET_AFFINE_COORDINATES_GFP,0), "ec_GFp_simple_point_set_affine_coordinates_GFp"}, +{ERR_PACK(0,EC_F_EC_GFP_SIMPLE_SET_COMPRESSED_COORDINATES_GFP,0), "ec_GFp_simple_set_compressed_coordinates_GFp"}, {ERR_PACK(0,EC_F_EC_GROUP_COPY,0), "EC_GROUP_copy"}, +{ERR_PACK(0,EC_F_EC_GROUP_GET_CURVE_GFP,0), "EC_GROUP_get_curve_GFp"}, {ERR_PACK(0,EC_F_EC_GROUP_GET_EXTRA_DATA,0), "EC_GROUP_get_extra_data"}, {ERR_PACK(0,EC_F_EC_GROUP_NEW,0), "EC_GROUP_new"}, {ERR_PACK(0,EC_F_EC_GROUP_SET_CURVE_GFP,0), "EC_GROUP_set_curve_GFp"}, @@ -101,6 +104,8 @@ static ERR_STRING_DATA EC_str_reasons[]= { {EC_R_BUFFER_TOO_SMALL ,"buffer too small"}, {EC_R_INCOMPATIBLE_OBJECTS ,"incompatible objects"}, +{EC_R_INVALID_COMPRESSED_POINT ,"invalid compressed point"}, +{EC_R_INVALID_COMPRESSION_BIT ,"invalid compression bit"}, {EC_R_INVALID_ENCODING ,"invalid encoding"}, {EC_R_INVALID_FIELD ,"invalid field"}, {EC_R_INVALID_FORM ,"invalid form"}, diff --git a/crypto/ec/ec_lcl.h b/crypto/ec/ec_lcl.h index 15007d83c7..ad62beb29c 100644 --- a/crypto/ec/ec_lcl.h +++ b/crypto/ec/ec_lcl.h @@ -63,19 +63,24 @@ * so all this may change in future versions. */ struct ec_method_st { - /* used by EC_GROUP_new, EC_GROUP_set_curve_GFp, EC_GROUP_free, EC_GROUP_clear_free, EC_GROUP_copy: */ + /* used by EC_GROUP_new, EC_GROUP_free, EC_GROUP_clear_free, EC_GROUP_copy: */ int (*group_init)(EC_GROUP *); - int (*group_set_curve_GFp)(EC_GROUP *, const BIGNUM *p, const BIGNUM *a, const BIGNUM *b, BN_CTX *); void (*group_finish)(EC_GROUP *); void (*group_clear_finish)(EC_GROUP *); int (*group_copy)(EC_GROUP *, const EC_GROUP *); - /* used by EC_GROUP_set_generator: */ + /* used by EC_GROUP_set_curve_GFp and EC_GROUP_get_curve_GFp: */ + int (*group_set_curve_GFp)(EC_GROUP *, const BIGNUM *p, const BIGNUM *a, const BIGNUM *b, BN_CTX *); + int (*group_get_curve_GFp)(EC_GROUP *, BIGNUM *p, BIGNUM *a, BIGNUM *b, BN_CTX *); + + /* used by EC_GROUP_set_generator, EC_group_get0_generator, + * EC_GROUP_get_order, EC_GROUP_get_cofactor: + */ int (*group_set_generator)(EC_GROUP *, const EC_POINT *generator, const BIGNUM *order, const BIGNUM *cofactor); - - /* TODO: 'set' and 'get' functions for EC_GROUPs */ - + EC_POINT *(*group_get0_generator)(EC_GROUP *); + int (*group_get_order)(EC_GROUP *, BIGNUM *order, BN_CTX *); + int (*group_get_cofactor)(EC_GROUP *, BIGNUM *cofactor, BN_CTX *); /* used by EC_POINT_new, EC_POINT_free, EC_POINT_clear_free, EC_POINT_copy: */ int (*point_init)(EC_POINT *); @@ -195,13 +200,16 @@ struct ec_point_st { /* method functions in ecp_smpl.c */ int ec_GFp_simple_group_init(EC_GROUP *); -int ec_GFp_simple_group_set_curve_GFp(EC_GROUP *, const BIGNUM *p, const BIGNUM *a, const BIGNUM *b, BN_CTX *); void ec_GFp_simple_group_finish(EC_GROUP *); void ec_GFp_simple_group_clear_finish(EC_GROUP *); int ec_GFp_simple_group_copy(EC_GROUP *, const EC_GROUP *); +int ec_GFp_simple_group_set_curve_GFp(EC_GROUP *, const BIGNUM *p, const BIGNUM *a, const BIGNUM *b, BN_CTX *); +int ec_GFp_simple_group_get_curve_GFp(EC_GROUP *, BIGNUM *p, BIGNUM *a, BIGNUM *b, BN_CTX *); int ec_GFp_simple_group_set_generator(EC_GROUP *, const EC_POINT *generator, const BIGNUM *order, const BIGNUM *cofactor); -/* TODO: 'set' and 'get' functions for EC_GROUPs */ +EC_POINT *ec_GFp_simple_group_get0_generator(EC_GROUP *); +int ec_GFp_simple_group_get_order(EC_GROUP *, BIGNUM *order, BN_CTX *); +int ec_GFp_simple_group_get_cofactor(EC_GROUP *, BIGNUM *cofactor, BN_CTX *); int ec_GFp_simple_point_init(EC_POINT *); void ec_GFp_simple_point_finish(EC_POINT *); void ec_GFp_simple_point_clear_finish(EC_POINT *); diff --git a/crypto/ec/ec_lib.c b/crypto/ec/ec_lib.c index bef62961e1..6aaacb343f 100644 --- a/crypto/ec/ec_lib.c +++ b/crypto/ec/ec_lib.c @@ -56,9 +56,12 @@ #include #include +#include #include "ec_lcl.h" +static const char EC_version[] = "EC" OPENSSL_VERSION_PTEXT; + /* functions for EC_GROUP objects */ @@ -101,17 +104,6 @@ EC_GROUP *EC_GROUP_new(const EC_METHOD *meth) } -int EC_GROUP_set_curve_GFp(EC_GROUP *group, const BIGNUM *p, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx) - { - if (group->meth->group_set_curve_GFp == 0) - { - ECerr(EC_F_EC_GROUP_SET_CURVE_GFP, ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED); - return 0; - } - return group->meth->group_set_curve_GFp(group, p, a, b, ctx); - } - - void EC_GROUP_free(EC_GROUP *group) { if (group->meth->group_finish != 0) @@ -171,6 +163,28 @@ int EC_GROUP_copy(EC_GROUP *dest, const EC_GROUP *src) } +int EC_GROUP_set_curve_GFp(EC_GROUP *group, const BIGNUM *p, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx) + { + if (group->meth->group_set_curve_GFp == 0) + { + ECerr(EC_F_EC_GROUP_SET_CURVE_GFP, ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED); + return 0; + } + return group->meth->group_set_curve_GFp(group, p, a, b, ctx); + } + + +int EC_GROUP_get_curve_GFp(EC_GROUP *group, BIGNUM *p, BIGNUM *a, BIGNUM *b, BN_CTX *ctx) + { + if (group->meth->group_get_curve_GFp == 0) + { + ECerr(EC_F_EC_GROUP_GET_CURVE_GFP, ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED); + return 0; + } + return group->meth->group_get_curve_GFp(group, p, a, b, ctx); + } + + int EC_GROUP_set_generator(EC_GROUP *group, const EC_POINT *generator, const BIGNUM *order, const BIGNUM *cofactor) { if (group->meth->group_set_generator == 0) @@ -182,9 +196,6 @@ int EC_GROUP_set_generator(EC_GROUP *group, const EC_POINT *generator, const BIG } -/* TODO: 'set' and 'get' functions for EC_GROUPs */ - - /* this has 'package' visibility */ int EC_GROUP_set_extra_data(EC_GROUP *group, void *extra_data, void *(*extra_data_dup_func)(void *), void (*extra_data_free_func)(void *), void (*extra_data_clear_free_func)(void *)) diff --git a/crypto/ec/ecp_mont.c b/crypto/ec/ecp_mont.c index 5db65ae419..873d142af2 100644 --- a/crypto/ec/ecp_mont.c +++ b/crypto/ec/ecp_mont.c @@ -60,12 +60,15 @@ const EC_METHOD *EC_GFp_mont_method(void) { static const EC_METHOD ret = { ec_GFp_mont_group_init, - ec_GFp_mont_group_set_curve_GFp, ec_GFp_mont_group_finish, ec_GFp_mont_group_clear_finish, ec_GFp_mont_group_copy, + ec_GFp_mont_group_set_curve_GFp, + ec_GFp_simple_group_get_curve_GFp, ec_GFp_simple_group_set_generator, - /* TODO: 'set' and 'get' functions for EC_GROUPs */ + ec_GFp_simple_group_get0_generator, + ec_GFp_simple_group_get_order, + ec_GFp_simple_group_get_cofactor, ec_GFp_simple_point_init, ec_GFp_simple_point_finish, ec_GFp_simple_point_clear_finish, diff --git a/crypto/ec/ecp_nist.c b/crypto/ec/ecp_nist.c index 089e2c610f..acf2164900 100644 --- a/crypto/ec/ecp_nist.c +++ b/crypto/ec/ecp_nist.c @@ -60,12 +60,15 @@ const EC_METHOD *EC_GFp_nist_method(void) { static const EC_METHOD ret = { ec_GFp_nist_group_init, - ec_GFp_nist_group_set_curve_GFp, ec_GFp_nist_group_finish, ec_GFp_nist_group_clear_finish, ec_GFp_nist_group_copy, + ec_GFp_nist_group_set_curve_GFp, + ec_GFp_simple_group_get_curve_GFp, ec_GFp_simple_group_set_generator, - /* TODO: 'set' and 'get' functions for EC_GROUPs */ + ec_GFp_simple_group_get0_generator, + ec_GFp_simple_group_get_order, + ec_GFp_simple_group_get_cofactor, ec_GFp_simple_point_init, ec_GFp_simple_point_finish, ec_GFp_simple_point_clear_finish, diff --git a/crypto/ec/ecp_recp.c b/crypto/ec/ecp_recp.c index 8afdca1fa7..2419a3058e 100644 --- a/crypto/ec/ecp_recp.c +++ b/crypto/ec/ecp_recp.c @@ -60,12 +60,15 @@ const EC_METHOD *EC_GFp_recp_method(void) { static const EC_METHOD ret = { ec_GFp_recp_group_init, - ec_GFp_recp_group_set_curve_GFp, ec_GFp_recp_group_finish, ec_GFp_recp_group_clear_finish, ec_GFp_recp_group_copy, + ec_GFp_recp_group_set_curve_GFp, + ec_GFp_simple_group_get_curve_GFp, ec_GFp_simple_group_set_generator, - /* TODO: 'set' and 'get' functions for EC_GROUPs */ + ec_GFp_simple_group_get0_generator, + ec_GFp_simple_group_get_order, + ec_GFp_simple_group_get_cofactor, ec_GFp_simple_point_init, ec_GFp_simple_point_finish, ec_GFp_simple_point_clear_finish, diff --git a/crypto/ec/ecp_smpl.c b/crypto/ec/ecp_smpl.c index d6c3f635e5..a857560bf7 100644 --- a/crypto/ec/ecp_smpl.c +++ b/crypto/ec/ecp_smpl.c @@ -64,12 +64,15 @@ const EC_METHOD *EC_GFp_simple_method(void) { static const EC_METHOD ret = { ec_GFp_simple_group_init, - ec_GFp_simple_group_set_curve_GFp, ec_GFp_simple_group_finish, ec_GFp_simple_group_clear_finish, ec_GFp_simple_group_copy, + ec_GFp_simple_group_set_curve_GFp, + ec_GFp_simple_group_get_curve_GFp, ec_GFp_simple_group_set_generator, - /* TODO: 'set' and 'get' functions for EC_GROUPs */ + ec_GFp_simple_group_get0_generator, + ec_GFp_simple_group_get_order, + ec_GFp_simple_group_get_cofactor, ec_GFp_simple_point_init, ec_GFp_simple_point_finish, ec_GFp_simple_point_clear_finish, @@ -111,6 +114,67 @@ int ec_GFp_simple_group_init(EC_GROUP *group) } +void ec_GFp_simple_group_finish(EC_GROUP *group) + { + BN_free(&group->field); + BN_free(&group->a); + BN_free(&group->b); + if (group->generator != NULL) + EC_POINT_free(group->generator); + BN_free(&group->order); + BN_free(&group->cofactor); + } + + +void ec_GFp_simple_group_clear_finish(EC_GROUP *group) + { + BN_clear_free(&group->field); + BN_clear_free(&group->a); + BN_clear_free(&group->b); + if (group->generator != NULL) + { + EC_POINT_clear_free(group->generator); + group->generator = NULL; + } + BN_clear_free(&group->order); + BN_clear_free(&group->cofactor); + } + + +int ec_GFp_simple_group_copy(EC_GROUP *dest, const EC_GROUP *src) + { + if (!BN_copy(&dest->field, &src->field)) return 0; + if (!BN_copy(&dest->a, &src->a)) return 0; + if (!BN_copy(&dest->b, &src->b)) return 0; + + dest->a_is_minus3 = src->a_is_minus3; + + if (src->generator != NULL) + { + if (dest->generator == NULL) + { + dest->generator = EC_POINT_new(dest); + if (dest->generator == NULL) return 0; + } + if (!EC_POINT_copy(dest->generator, src->generator)) return 0; + } + else + { + /* src->generator == NULL */ + if (dest->generator != NULL) + { + EC_POINT_clear_free(dest->generator); + dest->generator = NULL; + } + } + + if (!BN_copy(&dest->order, &src->order)) return 0; + if (!BN_copy(&dest->cofactor, &src->cofactor)) return 0; + + return 1; + } + + int ec_GFp_simple_group_set_curve_GFp(EC_GROUP *group, const BIGNUM *p, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx) { @@ -166,67 +230,58 @@ int ec_GFp_simple_group_set_curve_GFp(EC_GROUP *group, } -void ec_GFp_simple_group_finish(EC_GROUP *group) - { - BN_free(&group->field); - BN_free(&group->a); - BN_free(&group->b); - if (group->generator != NULL) - EC_POINT_free(group->generator); - BN_free(&group->order); - BN_free(&group->cofactor); - } - - -void ec_GFp_simple_group_clear_finish(EC_GROUP *group) +int ec_GFp_simple_group_get_curve_GFp(EC_GROUP *group, BIGNUM *p, BIGNUM *a, BIGNUM *b, BN_CTX *ctx) { - BN_clear_free(&group->field); - BN_clear_free(&group->a); - BN_clear_free(&group->b); - if (group->generator != NULL) + int ret = 0; + BN_CTX *new_ctx = NULL; + + if (p != NULL) { - EC_POINT_clear_free(group->generator); - group->generator = NULL; + if (!BN_copy(p, &group->field)) return 0; } - BN_clear_free(&group->order); - BN_clear_free(&group->cofactor); - } - -int ec_GFp_simple_group_copy(EC_GROUP *dest, const EC_GROUP *src) - { - if (!BN_copy(&dest->field, &src->field)) return 0; - if (!BN_copy(&dest->a, &src->a)) return 0; - if (!BN_copy(&dest->b, &src->b)) return 0; - - dest->a_is_minus3 = src->a_is_minus3; - - if (src->generator != NULL) + if (a != NULL || b != NULL) { - if (dest->generator == NULL) + if (group->meth->field_decode) { - dest->generator = EC_POINT_new(dest); - if (dest->generator == NULL) return 0; + if (ctx == NULL) + { + ctx = new_ctx = BN_CTX_new(); + if (ctx == NULL) + return 0; + } + if (a != NULL) + { + if (!group->meth->field_decode(group, a, &group->a, ctx)) goto err; + } + if (b != NULL) + { + if (!group->meth->field_decode(group, b, &group->b, ctx)) goto err; + } } - if (!EC_POINT_copy(dest->generator, src->generator)) return 0; - } - else - { - /* src->generator == NULL */ - if (dest->generator != NULL) + else { - EC_POINT_clear_free(dest->generator); - dest->generator = NULL; + if (a != NULL) + { + if (!BN_copy(a, &group->a)) goto err; + } + if (b != NULL) + { + if (!BN_copy(b, &group->b)) goto err; + } } } - - if (!BN_copy(&dest->order, &src->order)) return 0; - if (!BN_copy(&dest->cofactor, &src->cofactor)) return 0; - - return 1; + + ret = 1; + + err: + if (new_ctx) + BN_CTX_free(new_ctx); + return ret; } + int ec_GFp_simple_group_set_generator(EC_GROUP *group, const EC_POINT *generator, const BIGNUM *order, const BIGNUM *cofactor) { @@ -257,7 +312,28 @@ int ec_GFp_simple_group_set_generator(EC_GROUP *group, const EC_POINT *generator } -/* TODO: 'set' and 'get' functions for EC_GROUPs */ +EC_POINT *ec_GFp_simple_group_get0_generator(EC_GROUP *group) + { + return group->generator; + } + + +int ec_GFp_simple_group_get_order(EC_GROUP *group, BIGNUM *order, BN_CTX *ctx) + { + if (!BN_copy(order, &group->order)) + return 0; + + return !BN_is_zero(&group->order); + } + + +int ec_GFp_simple_group_get_cofactor(EC_GROUP *group, BIGNUM *cofactor, BN_CTX *ctx) + { + if (!BN_copy(cofactor, &group->cofactor)) + return 0; + + return !BN_is_zero(&group->cofactor); + } int ec_GFp_simple_point_init(EC_POINT *point) @@ -307,26 +383,65 @@ int ec_GFp_simple_point_set_to_infinity(const EC_GROUP *group, EC_POINT *point) int ec_GFp_simple_set_Jprojective_coordinates_GFp(const EC_GROUP *group, EC_POINT *point, - const BIGNUM *x, const BIGNUM *y, const BIGNUM *z, BN_CTX *ctx); -/* TODO */ + const BIGNUM *x, const BIGNUM *y, const BIGNUM *z, BN_CTX *ctx) + { + BN_CTX *new_ctx = NULL; + int ret = 0; + + if (ctx == NULL) + { + ctx = new_ctx = BN_CTX_new(); + if (ctx == NULL) + return 0; + } + if (x != NULL) + { + if (!BN_nnmod(&point->X, x, &group->field, ctx)) goto err; + if (group->meth->field_encode) + { + if (!group->meth->field_encode(group, &point->X, &point->X, ctx)) goto err; + } + } + + if (y != NULL) + { + if (!BN_nnmod(&point->Y, y, &group->field, ctx)) goto err; + if (group->meth->field_encode) + { + if (!group->meth->field_encode(group, &point->Y, &point->Y, ctx)) goto err; + } + } + + if (z != NULL) + { + int Z_is_one; -int ec_GFp_simple_get_Jprojective_coordinates_GFp(const EC_GROUP *group, const EC_POINT *point, - BIGNUM *x, BIGNUM *y, BIGNUM *z, BN_CTX *ctx); -/* TODO */ + if (!BN_nnmod(&point->Z, z, &group->field, ctx)) goto err; + Z_is_one = BN_is_one(&point->Z); + if (group->meth->field_encode) + { + if (!group->meth->field_encode(group, &point->Z, &point->Z, ctx)) goto err; + } + point->Z_is_one = Z_is_one; + } + + ret = 1; + + err: + if (new_ctx != NULL) + BN_CTX_free(new_ctx); + return ret; + } -int ec_GFp_simple_point_set_affine_coordinates_GFp(const EC_GROUP *group, EC_POINT *point, - const BIGNUM *x, const BIGNUM *y, BN_CTX *ctx) +int ec_GFp_simple_get_Jprojective_coordinates_GFp(const EC_GROUP *group, const EC_POINT *point, + BIGNUM *x, BIGNUM *y, BIGNUM *z, BN_CTX *ctx) { BN_CTX *new_ctx = NULL; int ret = 0; - - if (!BN_copy(&point->X, x)) goto err; - if (!BN_copy(&point->Y, y)) goto err; - if (!BN_one(&point->Z)) goto err; - - if (group->meth->field_encode) + + if (group->meth->field_decode != 0) { if (ctx == NULL) { @@ -334,14 +449,38 @@ int ec_GFp_simple_point_set_affine_coordinates_GFp(const EC_GROUP *group, EC_POI if (ctx == NULL) return 0; } - - if (!group->meth->field_encode(group, &point->X, &point->X, ctx)) goto err; - if (!group->meth->field_encode(group, &point->Y, &point->Y, ctx)) goto err; - if (!group->meth->field_encode(group, &point->Z, &point->Z, ctx)) goto err; - } - point->Z_is_one = 1; + if (x != NULL) + { + if (!group->meth->field_decode(group, x, &point->X, ctx)) goto err; + } + if (y != NULL) + { + if (!group->meth->field_decode(group, y, &point->Y, ctx)) goto err; + } + if (z != NULL) + { + if (!group->meth->field_decode(group, z, &point->Z, ctx)) goto err; + } + } + else + { + if (x != NULL) + { + if (!BN_copy(x, &point->X)) goto err; + } + if (y != NULL) + { + if (!BN_copy(y, &point->Y)) goto err; + } + if (z != NULL) + { + if (!BN_copy(z, &point->Z)) goto err; + } + } + ret = 1; + err: if (new_ctx != NULL) BN_CTX_free(new_ctx); @@ -349,6 +488,20 @@ int ec_GFp_simple_point_set_affine_coordinates_GFp(const EC_GROUP *group, EC_POI } +int ec_GFp_simple_point_set_affine_coordinates_GFp(const EC_GROUP *group, EC_POINT *point, + const BIGNUM *x, const BIGNUM *y, BN_CTX *ctx) + { + if (x == NULL || y == NULL) + { + /* unlike for projective coordinates, we do not tolerate this */ + ECerr(EC_F_EC_GFP_SIMPLE_POINT_SET_AFFINE_COORDINATES_GFP, ERR_R_PASSED_NULL_PARAMETER); + return 0; + } + + return EC_POINT_set_Jprojective_coordinates_GFp(group, point, x, y, BN_value_one(), ctx); + } + + int ec_GFp_simple_point_get_affine_coordinates_GFp(const EC_GROUP *group, const EC_POINT *point, BIGNUM *x, BIGNUM *y, BN_CTX *ctx) { @@ -438,8 +591,93 @@ int ec_GFp_simple_point_get_affine_coordinates_GFp(const EC_GROUP *group, const int ec_GFp_simple_set_compressed_coordinates_GFp(const EC_GROUP *group, EC_POINT *point, - const BIGNUM *x, int y_bit, BN_CTX *); -/* TODO */ + const BIGNUM *x, int y_bit, BN_CTX *ctx) + { + BN_CTX *new_ctx = NULL; + BIGNUM *tmp1, *tmp2, *y; + int ret = 0; + + if (ctx == NULL) + { + ctx = new_ctx = BN_CTX_new(); + if (ctx == NULL) + return 0; + } + + y_bit = (y_bit != 0); + + BN_CTX_start(ctx); + tmp1 = BN_CTX_get(ctx); + tmp2 = BN_CTX_get(ctx); + y = BN_CTX_get(ctx); + if (y == NULL) goto err; + + /* Recover y. We have a Weierstrass equation + * y^2 = x^3 + a*x + b, + * so y is one of the square roots of x^3 + a*x + b. + */ + + /* tmp1 := x^3 */ + if (!BN_mod_sqr(tmp2, x, &group->field, ctx)) goto err; + if (!BN_mod_mul(tmp1, tmp2, x, &group->field, ctx)) goto err; + + /* tmp1 := tmp1 + a*x */ + if (group->a_is_minus3) + { + if (!BN_mod_lshift1_quick(tmp2, x, &group->field)) goto err; + if (!BN_mod_add_quick(tmp2, tmp2, x, &group->field)) goto err; + if (!BN_mod_sub_quick(tmp1, tmp1, tmp2, &group->field)) goto err; + } + else + { + if (!BN_mod_mul(tmp2, &group->a, x, &group->field, ctx)) goto err; + if (!BN_mod_add_quick(tmp1, tmp1, tmp2, &group->field)) goto err; + } + + /* tmp1 := tmp1 + b */ + if (!BN_mod_add_quick(tmp1, tmp1, &group->b, &group->field)) goto err; + + if (!BN_mod_sqrt(y, tmp1, &group->field, ctx)) + { + ECerr(EC_F_EC_GFP_SIMPLE_SET_COMPRESSED_COORDINATES_GFP, ERR_R_BN_LIB); + goto err; + } + /* If tmp1 is not a square (i.e. there is no point on the curve with + * our x), then y now is a nonsense value too */ + + if (y_bit != BN_is_odd(y)) + { + if (BN_is_zero(y)) + { + int kron; + + kron = BN_kronecker(x, &group->field, ctx); + if (kron == -2) goto err; + + if (kron == 1) + ECerr(EC_F_EC_GFP_SIMPLE_SET_COMPRESSED_COORDINATES_GFP, EC_R_INVALID_COMPRESSION_BIT); + else + ECerr(EC_F_EC_GFP_SIMPLE_SET_COMPRESSED_COORDINATES_GFP, EC_R_INVALID_COMPRESSED_POINT); + goto err; + } + if (!BN_usub(y, &group->field, y)) goto err; + } + if (y_bit != BN_is_odd(y)) + { + ECerr(EC_F_EC_GFP_SIMPLE_SET_COMPRESSED_COORDINATES_GFP, ERR_R_INTERNAL_ERROR); + goto err; + } + + if (!EC_POINT_set_affine_coordinates_GFp(group, point, x, y, ctx)) goto err; + + ret = 1; + + err: + BN_CTX_end(ctx); + if (new_ctx != NULL) + BN_CTX_free(new_ctx); + return ret; + } size_t ec_GFp_simple_point2oct(const EC_GROUP *group, const EC_POINT *point, point_conversion_form_t form, @@ -638,7 +876,11 @@ int ec_GFp_simple_oct2point(const EC_GROUP *group, EC_POINT *point, goto err; } - if (form != POINT_CONVERSION_COMPRESSED) + if (form == POINT_CONVERSION_COMPRESSED) + { + if (!EC_POINT_set_compressed_coordinates_GFp(group, point, x, y_bit, ctx)) goto err; + } + else { if (!BN_bin2bn(buf + 1 + field_len, field_len, y)) goto err; if (BN_ucmp(y, &group->field) >= 0) @@ -654,65 +896,10 @@ int ec_GFp_simple_oct2point(const EC_GROUP *group, EC_POINT *point, goto err; } } - } - if (form == POINT_CONVERSION_COMPRESSED) - { - /* Recover y. We have a Weierstrass equation - * y^2 = x^3 + a*x + b, - * so y is one of the square roots of x^3 + a*x + b. - */ - - BIGNUM *tmp1, *tmp2; - - tmp1 = BN_CTX_get(ctx); - tmp2 = BN_CTX_get(ctx); - if (tmp2 == NULL) goto err; - - /* tmp1 := x^3 */ - if (!BN_mod_sqr(tmp2, x, &group->field, ctx)) goto err; - if (!BN_mod_mul(tmp1, tmp2, x, &group->field, ctx)) goto err; - - /* tmp1 := tmp1 + a*x */ - if (group->a_is_minus3) - { - if (!BN_mod_lshift1_quick(tmp2, x, &group->field)) goto err; - if (!BN_mod_add_quick(tmp2, tmp2, x, &group->field)) goto err; - if (!BN_mod_sub_quick(tmp1, tmp1, tmp2, &group->field)) goto err; - } - else - { - if (!BN_mod_mul(tmp2, &group->a, x, &group->field, ctx)) goto err; - if (!BN_mod_add_quick(tmp1, tmp1, tmp2, &group->field)) goto err; - } - - /* tmp1 := tmp1 + b */ - if (!BN_mod_add_quick(tmp1, tmp1, &group->b, &group->field)) goto err; - - if (!BN_mod_sqrt(y, tmp1, &group->field, ctx)) - { - ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, ERR_R_BN_LIB); - goto err; - } - - if (y_bit != BN_is_odd(y)) - { - if (BN_is_zero(y)) - { - ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING); - goto err; - } - if (!BN_usub(y, &group->field, y)) goto err; - } - if (y_bit != BN_is_odd(y)) - { - ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, ERR_R_INTERNAL_ERROR); - goto err; - } + if (!EC_POINT_set_affine_coordinates_GFp(group, point, x, y, ctx)) goto err; } - if (!EC_POINT_set_affine_coordinates_GFp(group, point, x, y, ctx)) goto err; - if (!EC_POINT_is_on_curve(group, point, ctx)) /* test required by X9.62 */ { ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_POINT_IS_NOT_ON_CURVE); @@ -1010,8 +1197,14 @@ int ec_GFp_simple_dbl(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a, BN_ } -int ec_GFp_simple_invert(const EC_GROUP *group, EC_POINT *point, BN_CTX *ctx); -/* TODO */ +int ec_GFp_simple_invert(const EC_GROUP *group, EC_POINT *point, BN_CTX *ctx) + { + if (EC_POINT_is_at_infinity(group, point) || BN_is_zero(&point->Y)) + /* point is its own inverse */ + return 1; + + return BN_usub(&point->Y, &group->field, &point->Y); + } int ec_GFp_simple_is_at_infinity(const EC_GROUP *group, const EC_POINT *point) @@ -1072,7 +1265,7 @@ int ec_GFp_simple_is_on_curve(const EC_GROUP *group, const EC_POINT *point, BN_C /* rh := rh + a*X*Z^4 */ if (!field_mul(group, tmp1, &point->X, Z4, ctx)) goto err; - if (&group->a_is_minus3) + if (group->a_is_minus3) { if (!BN_mod_lshift1_quick(tmp2, tmp1, p)) goto err; if (!BN_mod_add_quick(tmp2, tmp2, tmp1, p)) goto err; @@ -1093,7 +1286,7 @@ int ec_GFp_simple_is_on_curve(const EC_GROUP *group, const EC_POINT *point, BN_C /* point->Z_is_one */ /* rh := rh + a*X */ - if (&group->a_is_minus3) + if (group->a_is_minus3) { if (!BN_mod_lshift1_quick(tmp2, &point->X, p)) goto err; if (!BN_mod_add_quick(tmp2, tmp2, &point->X, p)) goto err; @@ -1122,8 +1315,107 @@ int ec_GFp_simple_is_on_curve(const EC_GROUP *group, const EC_POINT *point, BN_C } -int ec_GFp_simple_cmp(const EC_GROUP *, const EC_POINT *a, const EC_POINT *b, BN_CTX *); -/* TODO */ +int ec_GFp_simple_cmp(const EC_GROUP *group, const EC_POINT *a, const EC_POINT *b, BN_CTX *ctx) + { + /* return values: + * -1 error + * 0 equal (in affine coordinates) + * 1 not equal + */ + + int (*field_mul)(const EC_GROUP *, BIGNUM *, const BIGNUM *, const BIGNUM *, BN_CTX *); + int (*field_sqr)(const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *); + BN_CTX *new_ctx = NULL; + BIGNUM *tmp1, *tmp2, *Za23, *Zb23; + const BIGNUM *tmp1_, *tmp2_; + int ret = -1; + + if (EC_POINT_is_at_infinity(group, a)) + { + return EC_POINT_is_at_infinity(group, b) ? 0 : 1; + } + + if (a->Z_is_one && b->Z_is_one) + { + return ((BN_cmp(&a->X, &b->X) == 0) && BN_cmp(&a->Y, &b->Y) == 0) ? 0 : 1; + } + + field_mul = group->meth->field_mul; + field_sqr = group->meth->field_sqr; + + if (ctx == NULL) + { + ctx = new_ctx = BN_CTX_new(); + if (ctx == NULL) + return -1; + } + + BN_CTX_start(ctx); + tmp1 = BN_CTX_get(ctx); + tmp2 = BN_CTX_get(ctx); + Za23 = BN_CTX_get(ctx); + Zb23 = BN_CTX_get(ctx); + if (Zb23 == NULL) goto end; + + /* We have to decide whether + * (X_a/Z_a^2, Y_a/Z_a^3) = (X_b/Z_b^2, Y_b/Z_b^3), + * or equivalently, whether + * (X_a*Z_b^2, Y_a*Z_b^3) = (X_b*Z_a^2, Y_b*Z_a^3). + */ + + if (!b->Z_is_one) + { + if (!field_sqr(group, Zb23, &b->Z, ctx)) goto end; + if (!field_mul(group, tmp1, &a->X, Zb23, ctx)) goto end; + tmp1_ = tmp1; + } + else + tmp1_ = &a->X; + if (!a->Z_is_one) + { + if (!field_sqr(group, Za23, &a->Z, ctx)) goto end; + if (!field_mul(group, tmp2, &b->X, Za23, ctx)) goto end; + tmp2_ = tmp2; + } + else + tmp2_ = &b->X; + + /* compare X_a*Z_b^2 with X_b*Z_a^2 */ + if (BN_cmp(tmp1_, tmp2_) != 0) + { + ret = 1; /* points differ */ + goto end; + } + + + if (!b->Z_is_one) + { + if (!field_mul(group, Zb23, Zb23, &b->Z, ctx)) goto end; + if (!field_mul(group, tmp1, &a->Y, Zb23, ctx)) goto end; + } + if (!a->Z_is_one) + { + if (!field_mul(group, Za23, Za23, &a->Z, ctx)) goto end; + if (!field_mul(group, tmp2, &b->Y, Za23, ctx)) goto end; + } + /* tmp1_ and tmp2_ are still ok */ + + /* compare Y_a*Z_b^3 with Y_b*Z_a^3 */ + if (BN_cmp(tmp1_, tmp2_) != 0) + { + ret = 1; /* points differ */ + goto end; + } + + /* points are equal */ + ret = 0; + + end: + BN_CTX_end(ctx); + if (new_ctx != NULL) + BN_CTX_free(new_ctx); + return ret; + } int ec_GFp_simple_make_affine(const EC_GROUP *group, EC_POINT *point, BN_CTX *ctx) diff --git a/crypto/ec/ectest.c b/crypto/ec/ectest.c index f557480f44..5425dce01e 100644 --- a/crypto/ec/ectest.c +++ b/crypto/ec/ectest.c @@ -1,4 +1,3 @@ -/* TODO */ /* crypto/ec/ectest.c */ /* ==================================================================== * Copyright (c) 1998-2001 The OpenSSL Project. All rights reserved. @@ -57,26 +56,164 @@ #include #include + +#ifdef OPENSSL_NO_EC +int main(int argc, char * argv[]) { puts("Elliptic curves are disabled."); return 0; } +#else + + #include #include - #define ABORT do { \ - fprintf(stderr, "%s:%d: Error\n", __FILE__, __LINE__); \ + fprintf(stderr, "%s:%d: ABORT\n", __FILE__, __LINE__); \ ERR_print_errors_fp(stderr); \ exit(1); \ } while (0) int main(int argc, char *argv[]) { + BN_CTX *ctx = NULL; + BIGNUM *p, *a, *b; EC_GROUP *group; - + EC_POINT *P, *Q, *R; + BIGNUM *x, *y, *z; + unsigned char buf[100]; + size_t i, len; + + CRYPTO_mem_ctrl(CRYPTO_MEM_CHECK_ON); ERR_load_crypto_strings(); -#if 0 - group = EC_GROUP_new(NULL); +#if 0 /* optional */ + ctx = BN_CTX_new(); + if (!ctx) ABORT; +#endif + + p = BN_new(); + a = BN_new(); + b = BN_new(); + if (!p || !a || !b) ABORT; + + if (!BN_hex2bn(&p, "D")) ABORT; + if (!BN_hex2bn(&a, "7")) ABORT; + if (!BN_hex2bn(&b, "C")) ABORT; + + group = EC_GROUP_new_curve_GFp(p, a, b, NULL); if (!group) ABORT; + + fprintf(stdout, "Curve defined by Weierstrass equation\n y^2 = x^3 + a*x + b (mod 0x"); + BN_print_fp(stdout, p); + fprintf(stdout, ")\n a = 0x"); + BN_print_fp(stdout, a); + fprintf(stdout, "\n b = 0x"); + BN_print_fp(stdout, b); + fprintf(stdout, "\n"); + + P = EC_POINT_new(group); + Q = EC_POINT_new(group); + R = EC_POINT_new(group); + if (!P || !Q || !R) ABORT; + + if (!EC_POINT_set_to_infinity(group, P)) ABORT; + if (!EC_POINT_is_at_infinity(group, P)) ABORT; + + buf[0] = 0; + if (!EC_POINT_oct2point(group, Q, buf, 1, ctx)) ABORT; + + if (!EC_POINT_add(group, P, P, Q, ctx)) ABORT; + if (!EC_POINT_is_at_infinity(group, P)) ABORT; + + x = BN_new(); + y = BN_new(); + z = BN_new(); + if (!x || !y || !z) ABORT; + + if (!BN_hex2bn(&x, "C")) ABORT; + if (!EC_POINT_set_compressed_coordinates_GFp(group, Q, x, 1, ctx)) ABORT; + if (!EC_POINT_is_on_curve(group, Q, ctx)) + { + fprintf(stderr, "Point is not on curve, x = 0x"); + BN_print_fp(stderr, x); + fprintf(stderr, "\n"); + ABORT; + } + + fprintf(stdout, "A cyclic subgroup:\n"); + do + { + if (EC_POINT_is_at_infinity(group, P)) + fprintf(stdout, " point at infinity\n"); + else + { + if (!EC_POINT_get_affine_coordinates_GFp(group, P, x, y, ctx)) ABORT; + + fprintf(stdout, " x = 0x"); + BN_print_fp(stdout, x); + fprintf(stdout, ", y = 0x"); + BN_print_fp(stdout, y); + fprintf(stdout, "\n"); + } + + if (!EC_POINT_copy(R, P)) ABORT; + if (!EC_POINT_add(group, P, P, Q, ctx)) ABORT; + +#if 0 /* optional */ + if (!EC_POINT_make_affine(group, P, ctx)) ABORT; #endif + } + while (!EC_POINT_is_at_infinity(group, P)); + + if (!EC_POINT_add(group, P, Q, R, ctx)) ABORT; + if (!EC_POINT_is_at_infinity(group, P)) ABORT; + len = EC_POINT_point2oct(group, Q, POINT_CONVERSION_COMPRESSED, buf, sizeof buf, ctx); + if (len == 0) ABORT; + if (!EC_POINT_oct2point(group, P, buf, len, ctx)) ABORT; + if (0 != EC_POINT_cmp(group, P, Q, ctx)) ABORT; + fprintf(stdout, "Generator as octect string, compressed form:\n "); + for (i = 0; i < len; i++) fprintf(stdout, "%02X", buf[i]); + + len = EC_POINT_point2oct(group, Q, POINT_CONVERSION_UNCOMPRESSED, buf, sizeof buf, ctx); + if (len == 0) ABORT; + if (!EC_POINT_oct2point(group, P, buf, len, ctx)) ABORT; + if (0 != EC_POINT_cmp(group, P, Q, ctx)) ABORT; + fprintf(stdout, "\nGenerator as octect string, uncompressed form:\n "); + for (i = 0; i < len; i++) fprintf(stdout, "%02X", buf[i]); + + len = EC_POINT_point2oct(group, Q, POINT_CONVERSION_HYBRID, buf, sizeof buf, ctx); + if (len == 0) ABORT; + if (!EC_POINT_oct2point(group, P, buf, len, ctx)) ABORT; + if (0 != EC_POINT_cmp(group, P, Q, ctx)) ABORT; + fprintf(stdout, "\nGenerator as octect string, hybrid form:\n "); + for (i = 0; i < len; i++) fprintf(stdout, "%02X", buf[i]); + + if (!EC_POINT_get_Jprojective_coordinates_GFp(group, R, x, y, z, ctx)) ABORT; + fprintf(stdout, "\nA representation of the inverse of that generator in\nJacobian projective coordinates:\n X = 0x"); + BN_print_fp(stdout, x); + fprintf(stdout, ", Y = 0x"); + BN_print_fp(stdout, y); + fprintf(stdout, ", Z = 0x"); + BN_print_fp(stdout, z); + fprintf(stdout, "\n"); + + if (!EC_POINT_invert(group, P, ctx)) ABORT; + if (0 != EC_POINT_cmp(group, P, R, ctx)) ABORT; + + /* ... */ + + if (ctx) + BN_CTX_free(ctx); + BN_free(p); BN_free(a); BN_free(b); + EC_GROUP_free(group); + EC_POINT_free(P); + EC_POINT_free(Q); + EC_POINT_free(R); + BN_free(x); BN_free(y); BN_free(z); + + ERR_free_strings(); + ERR_remove_state(0); + CRYPTO_mem_leaks_fp(stderr); + return 0; } +#endif -- 2.34.1