From 156e85578d180313c27e51d0bf186aa8650c49e1 Mon Sep 17 00:00:00 2001 From: =?utf8?q?Bodo=20M=C3=B6ller?= Date: Thu, 8 Mar 2001 20:55:16 +0000 Subject: [PATCH] Implement EC_GFp_mont_method. --- crypto/bn/bn_mont.c | 6 +- crypto/ec/ec.h | 6 ++ crypto/ec/ec_cvt.c | 4 +- crypto/ec/ec_err.c | 6 ++ crypto/ec/ec_lcl.h | 4 -- crypto/ec/ecp_mont.c | 142 ++++++++++++++++++++++++++++++++++++++----- crypto/ec/ecp_nist.c | 12 +--- crypto/ec/ecp_recp.c | 12 +--- crypto/ec/ecp_smpl.c | 21 ++++++- crypto/ec/ectest.c | 9 ++- 10 files changed, 173 insertions(+), 49 deletions(-) diff --git a/crypto/bn/bn_mont.c b/crypto/bn/bn_mont.c index f1765c03ac..82942a4759 100644 --- a/crypto/bn/bn_mont.c +++ b/crypto/bn/bn_mont.c @@ -339,9 +339,9 @@ BN_MONT_CTX *BN_MONT_CTX_copy(BN_MONT_CTX *to, BN_MONT_CTX *from) { if (to == from) return(to); - BN_copy(&(to->RR),&(from->RR)); - BN_copy(&(to->N),&(from->N)); - BN_copy(&(to->Ni),&(from->Ni)); + if (!BN_copy(&(to->RR),&(from->RR))) return NULL; + if (!BN_copy(&(to->N),&(from->N))) return NULL; + if (!BN_copy(&(to->Ni),&(from->Ni))) return NULL; to->ri=from->ri; to->n0=from->n0; return(to); diff --git a/crypto/ec/ec.h b/crypto/ec/ec.h index 16cbf188ec..a9f6c16db4 100644 --- a/crypto/ec/ec.h +++ b/crypto/ec/ec.h @@ -168,6 +168,10 @@ void ERR_load_EC_strings(void); /* Error codes for the EC functions. */ /* Function codes. */ +#define EC_F_EC_GFP_MONT_FIELD_DECODE 133 +#define EC_F_EC_GFP_MONT_FIELD_ENCODE 134 +#define EC_F_EC_GFP_MONT_FIELD_MUL 131 +#define EC_F_EC_GFP_MONT_FIELD_SQR 132 #define EC_F_EC_GFP_SIMPLE_GROUP_SET_CURVE_GFP 100 #define EC_F_EC_GFP_SIMPLE_GROUP_SET_GENERATOR 101 #define EC_F_EC_GFP_SIMPLE_MAKE_AFFINE 102 @@ -199,6 +203,7 @@ void ERR_load_EC_strings(void); #define EC_F_EC_POINT_SET_COMPRESSED_COORDINATES_GFP 125 #define EC_F_EC_POINT_SET_JPROJECTIVE_COORDINATES_GFP 126 #define EC_F_EC_POINT_SET_TO_INFINITY 127 +#define EC_F_GFP_MONT_GROUP_SET_CURVE_GFP 135 /* Reason codes. */ #define EC_R_BUFFER_TOO_SMALL 100 @@ -208,6 +213,7 @@ void ERR_load_EC_strings(void); #define EC_R_INVALID_ENCODING 102 #define EC_R_INVALID_FIELD 103 #define EC_R_INVALID_FORM 104 +#define EC_R_NOT_INITIALIZED 111 #define EC_R_NO_SUCH_EXTRA_DATA 105 #define EC_R_POINT_AT_INFINITY 106 #define EC_R_POINT_IS_NOT_ON_CURVE 107 diff --git a/crypto/ec/ec_cvt.c b/crypto/ec/ec_cvt.c index 361dcc3992..45b0ec33a0 100644 --- a/crypto/ec/ec_cvt.c +++ b/crypto/ec/ec_cvt.c @@ -63,8 +63,8 @@ EC_GROUP *EC_GROUP_new_curve_GFp(const BIGNUM *p, const BIGNUM *a, const BIGNUM /* Finally, this will use EC_GFp_nist_method if 'p' is a special * prime with optimized modular arithmetics (for NIST curves) - * and EC_GFp_mont_method or EC_GFp_recp_method otherwise. */ - meth = EC_GFp_simple_method(); + */ + meth = EC_GFp_mont_method(); ret = EC_GROUP_new(meth); if (ret == NULL) diff --git a/crypto/ec/ec_err.c b/crypto/ec/ec_err.c index 4c03f5cace..6fd74640da 100644 --- a/crypto/ec/ec_err.c +++ b/crypto/ec/ec_err.c @@ -66,6 +66,10 @@ #ifndef OPENSSL_NO_ERR static ERR_STRING_DATA EC_str_functs[]= { +{ERR_PACK(0,EC_F_EC_GFP_MONT_FIELD_DECODE,0), "ec_GFp_mont_field_decode"}, +{ERR_PACK(0,EC_F_EC_GFP_MONT_FIELD_ENCODE,0), "ec_GFp_mont_field_encode"}, +{ERR_PACK(0,EC_F_EC_GFP_MONT_FIELD_MUL,0), "ec_GFp_mont_field_mul"}, +{ERR_PACK(0,EC_F_EC_GFP_MONT_FIELD_SQR,0), "ec_GFp_mont_field_sqr"}, {ERR_PACK(0,EC_F_EC_GFP_SIMPLE_GROUP_SET_CURVE_GFP,0), "ec_GFp_simple_group_set_curve_GFp"}, {ERR_PACK(0,EC_F_EC_GFP_SIMPLE_GROUP_SET_GENERATOR,0), "ec_GFp_simple_group_set_generator"}, {ERR_PACK(0,EC_F_EC_GFP_SIMPLE_MAKE_AFFINE,0), "ec_GFp_simple_make_affine"}, @@ -97,6 +101,7 @@ static ERR_STRING_DATA EC_str_functs[]= {ERR_PACK(0,EC_F_EC_POINT_SET_COMPRESSED_COORDINATES_GFP,0), "EC_POINT_set_compressed_coordinates_GFp"}, {ERR_PACK(0,EC_F_EC_POINT_SET_JPROJECTIVE_COORDINATES_GFP,0), "EC_POINT_set_Jprojective_coordinates_GFp"}, {ERR_PACK(0,EC_F_EC_POINT_SET_TO_INFINITY,0), "EC_POINT_set_to_infinity"}, +{ERR_PACK(0,EC_F_GFP_MONT_GROUP_SET_CURVE_GFP,0), "GFP_MONT_GROUP_SET_CURVE_GFP"}, {0,NULL} }; @@ -109,6 +114,7 @@ static ERR_STRING_DATA EC_str_reasons[]= {EC_R_INVALID_ENCODING ,"invalid encoding"}, {EC_R_INVALID_FIELD ,"invalid field"}, {EC_R_INVALID_FORM ,"invalid form"}, +{EC_R_NOT_INITIALIZED ,"not initialized"}, {EC_R_NO_SUCH_EXTRA_DATA ,"no such extra data"}, {EC_R_POINT_AT_INFINITY ,"point at infinity"}, {EC_R_POINT_IS_NOT_ON_CURVE ,"point is not on curve"}, diff --git a/crypto/ec/ec_lcl.h b/crypto/ec/ec_lcl.h index ad62beb29c..38ce24b06c 100644 --- a/crypto/ec/ec_lcl.h +++ b/crypto/ec/ec_lcl.h @@ -260,8 +260,6 @@ void ec_GFp_recp_group_clear_finish(EC_GROUP *); int ec_GFp_recp_group_copy(EC_GROUP *, const EC_GROUP *); int ec_GFp_recp_field_mul(const EC_GROUP *, BIGNUM *r, const BIGNUM *a, const BIGNUM *b, BN_CTX *); int ec_GFp_recp_field_sqr(const EC_GROUP *, BIGNUM *r, const BIGNUM *a, BN_CTX *); -int ec_GFp_recp_field_encode(const EC_GROUP *, BIGNUM *r, const BIGNUM *a, BN_CTX *); -int ec_GFp_recp_field_decode(const EC_GROUP *, BIGNUM *r, const BIGNUM *a, BN_CTX *); /* method functions in ecp_nist.c */ @@ -272,5 +270,3 @@ void ec_GFp_nist_group_clear_finish(EC_GROUP *); int ec_GFp_nist_group_copy(EC_GROUP *, const EC_GROUP *); int ec_GFp_nist_field_mul(const EC_GROUP *, BIGNUM *r, const BIGNUM *a, const BIGNUM *b, BN_CTX *); int ec_GFp_nist_field_sqr(const EC_GROUP *, BIGNUM *r, const BIGNUM *a, BN_CTX *); -int ec_GFp_nist_field_encode(const EC_GROUP *, BIGNUM *r, const BIGNUM *a, BN_CTX *); -int ec_GFp_nist_field_decode(const EC_GROUP *, BIGNUM *r, const BIGNUM *a, BN_CTX *); diff --git a/crypto/ec/ecp_mont.c b/crypto/ec/ecp_mont.c index 873d142af2..8ba2227404 100644 --- a/crypto/ec/ecp_mont.c +++ b/crypto/ec/ecp_mont.c @@ -53,6 +53,8 @@ * */ +#include + #include "ec_lcl.h" @@ -107,33 +109,141 @@ int ec_GFp_mont_group_init(EC_GROUP *group) } -int ec_GFp_mont_group_set_curve_GFp(EC_GROUP *group, const BIGNUM *p, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx); -/* TODO */ +int ec_GFp_mont_group_set_curve_GFp(EC_GROUP *group, const BIGNUM *p, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx) + { + BN_CTX *new_ctx = NULL; + BN_MONT_CTX *mont = NULL; + int ret = 0; + + if (group->field_data != NULL) + { + BN_MONT_CTX_free(group->field_data); + group->field_data = NULL; + } + + if (ctx == NULL) + { + ctx = new_ctx = BN_CTX_new(); + if (ctx == NULL) + return 0; + } + + mont = BN_MONT_CTX_new(); + if (mont == NULL) goto err; + if (!BN_MONT_CTX_set(mont, p, ctx)) + { + ECerr(EC_F_GFP_MONT_GROUP_SET_CURVE_GFP, ERR_R_BN_LIB); + goto err; + } + + group->field_data = mont; + mont = NULL; + + ret = ec_GFp_simple_group_set_curve_GFp(group, p, a, b, ctx); + + if (!ret) + { + BN_MONT_CTX_free(group->field_data); + group->field_data = NULL; + } + + err: + if (new_ctx != NULL) + BN_CTX_free(new_ctx); + if (mont != NULL) + BN_MONT_CTX_free(mont); + return ret; + } -void ec_GFp_mont_group_finish(EC_GROUP *group); -/* TODO */ +void ec_GFp_mont_group_finish(EC_GROUP *group) + { + if (group->field_data != NULL) + { + BN_MONT_CTX_free(group->field_data); + group->field_data = NULL; + } + ec_GFp_simple_group_finish(group); + } -void ec_GFp_mont_group_clear_finish(EC_GROUP *group); -/* TODO */ +void ec_GFp_mont_group_clear_finish(EC_GROUP *group) + { + if (group->field_data != NULL) + { + BN_MONT_CTX_free(group->field_data); + group->field_data = NULL; + } + ec_GFp_simple_group_clear_finish(group); + } -int ec_GFp_mont_group_copy(EC_GROUP *dest, const EC_GROUP *src); -/* TODO */ +int ec_GFp_mont_group_copy(EC_GROUP *dest, const EC_GROUP *src) + { + if (dest->field_data != NULL) + { + BN_MONT_CTX_free(dest->field_data); + dest->field_data = NULL; + } + + if (!ec_GFp_simple_group_copy(dest, src)) return 0; + + dest->field_data = BN_MONT_CTX_new(); + if (dest->field_data == NULL) return 0; + if (!BN_MONT_CTX_copy(dest->field_data, src->field_data)) + { + BN_MONT_CTX_free(dest->field_data); + dest->field_data = NULL; + return 0; + } + + return 1; + } -int ec_GFp_mont_field_mul(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx); -/* TODO */ +int ec_GFp_mont_field_mul(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx) + { + if (group->field_data == NULL) + { + ECerr(EC_F_EC_GFP_MONT_FIELD_MUL, EC_R_NOT_INITIALIZED); + return 0; + } + return BN_mod_mul_montgomery(r, a, b, group->field_data, ctx); + } -int ec_GFp_mont_field_sqr(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a, BN_CTX *ctx); -/* TODO */ +int ec_GFp_mont_field_sqr(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a, BN_CTX *ctx) + { + if (group->field_data == NULL) + { + ECerr(EC_F_EC_GFP_MONT_FIELD_SQR, EC_R_NOT_INITIALIZED); + return 0; + } + + return BN_mod_mul_montgomery(r, a, a, group->field_data, ctx); + } + + +int ec_GFp_mont_field_encode(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a, BN_CTX *ctx) + { + if (group->field_data == NULL) + { + ECerr(EC_F_EC_GFP_MONT_FIELD_ENCODE, EC_R_NOT_INITIALIZED); + return 0; + } -int ec_GFp_mont_field_encode(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a, BN_CTX *ctx); -/* TODO */ + return BN_to_montgomery(r, a, (BN_MONT_CTX *)group->field_data, ctx); + } -int ec_GFp_mont_field_decode(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a, BN_CTX *ctx); -/* TODO */ +int ec_GFp_mont_field_decode(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a, BN_CTX *ctx) + { + if (group->field_data == NULL) + { + ECerr(EC_F_EC_GFP_MONT_FIELD_DECODE, EC_R_NOT_INITIALIZED); + return 0; + } + + return BN_from_montgomery(r, a, group->field_data, ctx); + } diff --git a/crypto/ec/ecp_nist.c b/crypto/ec/ecp_nist.c index acf2164900..1e3a7dd033 100644 --- a/crypto/ec/ecp_nist.c +++ b/crypto/ec/ecp_nist.c @@ -90,8 +90,8 @@ const EC_METHOD *EC_GFp_nist_method(void) ec_GFp_simple_make_affine, ec_GFp_nist_field_mul, ec_GFp_nist_field_sqr, - ec_GFp_nist_field_encode, - ec_GFp_nist_field_decode }; + 0 /* field_encode */, + 0 /* field_decode */ }; return &ret; } @@ -129,11 +129,3 @@ int ec_GFp_nist_field_mul(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a, con int ec_GFp_nist_field_sqr(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a, BN_CTX *ctx); /* TODO */ - - -int ec_GFp_nist_field_encode(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a, BN_CTX *ctx); -/* TODO */ - - -int ec_GFp_nist_field_decode(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a, BN_CTX *ctx); -/* TODO */ diff --git a/crypto/ec/ecp_recp.c b/crypto/ec/ecp_recp.c index 2419a3058e..c8832de86d 100644 --- a/crypto/ec/ecp_recp.c +++ b/crypto/ec/ecp_recp.c @@ -90,8 +90,8 @@ const EC_METHOD *EC_GFp_recp_method(void) ec_GFp_simple_make_affine, ec_GFp_recp_field_mul, ec_GFp_recp_field_sqr, - ec_GFp_recp_field_encode, - ec_GFp_recp_field_decode }; + 0 /* field_encode */, + 0 /* field_decode */ }; return &ret; } @@ -129,11 +129,3 @@ int ec_GFp_recp_field_mul(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a, con int ec_GFp_recp_field_sqr(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a, BN_CTX *ctx); /* TODO */ - - -int ec_GFp_recp_field_encode(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a, BN_CTX *ctx); -/* TODO */ - - -int ec_GFp_recp_field_decode(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a, BN_CTX *ctx); -/* TODO */ diff --git a/crypto/ec/ecp_smpl.c b/crypto/ec/ecp_smpl.c index a857560bf7..204dafab2a 100644 --- a/crypto/ec/ecp_smpl.c +++ b/crypto/ec/ecp_smpl.c @@ -630,12 +630,29 @@ int ec_GFp_simple_set_compressed_coordinates_GFp(const EC_GROUP *group, EC_POINT } else { - if (!BN_mod_mul(tmp2, &group->a, x, &group->field, ctx)) goto err; + if (group->meth->field_decode) + { + if (!group->meth->field_decode(group, tmp2, &group->a, ctx)) goto err; + if (!BN_mod_mul(tmp2, tmp2, x, &group->field, ctx)) 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 (group->meth->field_decode) + { + if (!group->meth->field_decode(group, tmp2, &group->b, ctx)) goto err; + if (!BN_mod_add_quick(tmp1, tmp1, tmp2, &group->field)) goto err; + } + else + { + if (!BN_mod_add_quick(tmp1, tmp1, &group->b, &group->field)) goto err; + } if (!BN_mod_sqrt(y, tmp1, &group->field, ctx)) { diff --git a/crypto/ec/ectest.c b/crypto/ec/ectest.c index 5425dce01e..28e331b608 100644 --- a/crypto/ec/ectest.c +++ b/crypto/ec/ectest.c @@ -98,8 +98,10 @@ int main(int argc, char *argv[]) if (!BN_hex2bn(&a, "7")) ABORT; if (!BN_hex2bn(&b, "C")) ABORT; - group = EC_GROUP_new_curve_GFp(p, a, b, NULL); + group = EC_GROUP_new(EC_GFp_mont_method()); if (!group) ABORT; + if (!EC_GROUP_set_curve_GFp(group, p, a, b, ctx)) ABORT; + if (!EC_GROUP_get_curve_GFp(group, p, a, b, ctx)) ABORT; fprintf(stdout, "Curve defined by Weierstrass equation\n y^2 = x^3 + a*x + b (mod 0x"); BN_print_fp(stdout, p); @@ -132,8 +134,11 @@ int main(int argc, char *argv[]) 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"); + if (!EC_POINT_get_affine_coordinates_GFp(group, Q, x, y, ctx)) ABORT; + fprintf(stderr, "Point is not on curve: x = 0x"); BN_print_fp(stderr, x); + fprintf(stderr, ", y = 0x"); + BN_print_fp(stderr, y); fprintf(stderr, "\n"); ABORT; } -- 2.34.1