From e869d4bd32b896a01106b5195e1f54f1dbdb529e Mon Sep 17 00:00:00 2001 From: =?utf8?q?Bodo=20M=C3=B6ller?= Date: Wed, 7 Mar 2001 20:56:48 +0000 Subject: [PATCH] More method functions. --- crypto/ec/ec.h | 3 +- crypto/ec/ec_err.c | 1 + crypto/ec/ec_lcl.h | 6 +- crypto/ec/ec_lib.c | 2 +- crypto/ec/ecp_smpl.c | 168 +++++++++++++++++++++++++++++++++++++++++-- 5 files changed, 168 insertions(+), 12 deletions(-) diff --git a/crypto/ec/ec.h b/crypto/ec/ec.h index cc0dd788bd..93fde52ffa 100644 --- a/crypto/ec/ec.h +++ b/crypto/ec/ec.h @@ -133,7 +133,7 @@ int EC_POINT_dbl(const EC_GROUP *, EC_POINT *r, const EC_POINT *a, BN_CTX *); int EC_POINT_is_at_infinity(const EC_GROUP *, const EC_POINT *); int EC_POINT_is_on_curve(const EC_GROUP *, const EC_POINT *, BN_CTX *); -int EC_POINT_make_affine(const EC_GROUP *, const EC_POINT *, BN_CTX *); +int EC_POINT_make_affine(const EC_GROUP *, EC_POINT *, BN_CTX *); @@ -150,6 +150,7 @@ int EC_POINT_make_affine(const EC_GROUP *, const EC_POINT *, BN_CTX *); /* Function codes. */ #define EC_F_EC_GFP_SIMPLE_GROUP_SET_GENERATOR 117 +#define EC_F_EC_GFP_SIMPLE_MAKE_AFFINE 118 #define EC_F_EC_GROUP_CLEAR_FREE 103 #define EC_F_EC_GROUP_COPY 102 #define EC_F_EC_GROUP_FREE 104 diff --git a/crypto/ec/ec_err.c b/crypto/ec/ec_err.c index 770bce5373..cd2d79267a 100644 --- a/crypto/ec/ec_err.c +++ b/crypto/ec/ec_err.c @@ -67,6 +67,7 @@ static ERR_STRING_DATA EC_str_functs[]= { {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"}, {ERR_PACK(0,EC_F_EC_GROUP_CLEAR_FREE,0), "EC_GROUP_clear_free"}, {ERR_PACK(0,EC_F_EC_GROUP_COPY,0), "EC_GROUP_copy"}, {ERR_PACK(0,EC_F_EC_GROUP_FREE,0), "EC_GROUP_free"}, diff --git a/crypto/ec/ec_lcl.h b/crypto/ec/ec_lcl.h index 231e8ca179..4bfcc916fd 100644 --- a/crypto/ec/ec_lcl.h +++ b/crypto/ec/ec_lcl.h @@ -99,7 +99,7 @@ struct ec_method_st { /* used by EC_POINT_is_at_infinity, EC_POINT_is_on_curve, EC_POINT_make_affine */ int (*is_at_infinity)(const EC_GROUP *, const EC_POINT *); int (*is_on_curve)(const EC_GROUP *, const EC_POINT *, BN_CTX *); - int (*make_affine)(const EC_GROUP *, const EC_POINT *, BN_CTX *); + int (*make_affine)(const EC_GROUP *, EC_POINT *, BN_CTX *); /* internal functions */ @@ -134,7 +134,7 @@ struct ec_group_st { * or abused for all kinds of fields, not just GF(p).) * For characteristic > 3, the curve is defined * by a Weierstrass equation of the form - * Y^2 = X^3 + a*X + b. + * y^2 = x^3 + a*x + b. */ int a_is_minus3; /* enable optimized point arithmetics for special case */ @@ -197,7 +197,7 @@ int ec_GFp_simple_add(const EC_GROUP *, EC_POINT *r, const EC_POINT *a, const EC int ec_GFp_simple_dbl(const EC_GROUP *, EC_POINT *r, const EC_POINT *a, BN_CTX *); int ec_GFp_simple_is_at_infinity(const EC_GROUP *, const EC_POINT *); int ec_GFp_simple_is_on_curve(const EC_GROUP *, const EC_POINT *, BN_CTX *); -int ec_GFp_simple_make_affine(const EC_GROUP *, const EC_POINT *, BN_CTX *); +int ec_GFp_simple_make_affine(const EC_GROUP *, EC_POINT *, BN_CTX *); int ec_GFp_simple_field_mul(const EC_GROUP *, BIGNUM *r, const BIGNUM *a, const BIGNUM *b, BN_CTX *); int ec_GFp_simple_field_sqr(const EC_GROUP *, BIGNUM *r, const BIGNUM *a, BN_CTX *); diff --git a/crypto/ec/ec_lib.c b/crypto/ec/ec_lib.c index 2056d58cd3..90da84eb7d 100644 --- a/crypto/ec/ec_lib.c +++ b/crypto/ec/ec_lib.c @@ -421,7 +421,7 @@ int EC_POINT_is_on_curve(const EC_GROUP *group, const EC_POINT *point, BN_CTX *c } -int EC_POINT_make_affine(const EC_GROUP *group, const EC_POINT *point, BN_CTX *ctx) +int EC_POINT_make_affine(const EC_GROUP *group, EC_POINT *point, BN_CTX *ctx) { if (group->meth->make_affine == 0) { diff --git a/crypto/ec/ecp_smpl.c b/crypto/ec/ecp_smpl.c index bae752841a..5306efdf15 100644 --- a/crypto/ec/ecp_smpl.c +++ b/crypto/ec/ecp_smpl.c @@ -385,8 +385,8 @@ int ec_GFp_simple_add(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a, con { /* a is the same point as b */ BN_CTX_end(ctx); - ctx = NULL; ret = EC_POINT_dbl(group, r, a, ctx); + ctx = NULL; goto end; } else @@ -491,8 +491,6 @@ int ec_GFp_simple_dbl(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a, BN_ n3 = BN_CTX_get(ctx); if (n3 == NULL) goto err; - /* TODO: optimization for group->a_is_minus3 */ - /* n1 */ if (a->Z_is_one) { @@ -577,12 +575,168 @@ int ec_GFp_simple_is_at_infinity(const EC_GROUP *group, const EC_POINT *point) } -int ec_GFp_simple_is_on_curve(const EC_GROUP *group, const EC_POINT *point, BN_CTX *ctx); -/* TODO */ +int ec_GFp_simple_is_on_curve(const EC_GROUP *group, const EC_POINT *point, BN_CTX *ctx) + { + int (*field_mul)(const EC_GROUP *, BIGNUM *, const BIGNUM *, const BIGNUM *, BN_CTX *); + int (*field_sqr)(const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *); + const BIGNUM *p; + BN_CTX *new_ctx = NULL; + BIGNUM *rh, *tmp1, *tmp2, *Z4, *Z6; + int ret = -1; + if (EC_POINT_is_at_infinity(group, point)) + return 1; + + field_mul = group->meth->field_mul; + field_sqr = group->meth->field_sqr; + p = &group->field; -int ec_GFp_simple_make_affine(const EC_GROUP *group, const EC_POINT *point, BN_CTX *ctx); -/* TODO */ + if (ctx == NULL) + { + ctx = new_ctx = BN_CTX_new(); + if (ctx == NULL) + return 0; + } + BN_CTX_start(ctx); + + rh = BN_CTX_get(ctx); + tmp1 = BN_CTX_get(ctx); + tmp2 = BN_CTX_get(ctx); + Z4 = BN_CTX_get(ctx); + Z6 = BN_CTX_get(ctx); + if (Z6 == NULL) goto err; + + /* We have a curve defined by a Weierstrass equation + * y^2 = x^3 + a*x + b. + * The point to consider is given in Jacobian projective coordinates + * where (X, Y, Z) represents (x, y) = (X/Z^2, Y/Z^3). + * Substituting this and multiplying by Z^6 transforms the above equation into + * Y^2 = X^3 + a*X*Z^4 + b*Z^6. + * To test this, we add up the right-hand side in 'rh'. + */ + + /* rh := X^3 */ + if (!field_sqr(group, rh, &point->X, ctx)) goto err; + if (!field_mul(group, rh, rh, &point->X, ctx)) goto err; + + if (!point->Z_is_one) + { + if (!field_sqr(group, tmp1, &point->Z, ctx)) goto err; + if (!field_sqr(group, Z4, tmp1, ctx)) goto err; + if (!field_mul(group, Z6, Z4, tmp1, ctx)) goto err; + + /* rh := rh + a*X*Z^4 */ + if (!field_mul(group, tmp1, &point->X, Z4, ctx)) goto err; + 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; + if (!BN_mod_sub_quick(rh, rh, tmp2, p)) goto err; + } + else + { + if (!field_mul(group, tmp2, tmp1, &group->a, ctx)) goto err; + if (!BN_mod_add_quick(rh, rh, tmp2, p)) goto err; + } + + /* rh := rh + b*Z^6 */ + if (!field_mul(group, tmp1, &group->b, Z6, ctx)) goto err; + if (!BN_mod_add_quick(rh, rh, tmp1, p)) goto err; + } + else + { + /* point->Z_is_one */ + + /* rh := rh + a*X */ + 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; + if (!BN_mod_sub_quick(rh, rh, tmp2, p)) goto err; + } + else + { + if (!field_mul(group, tmp2, &point->X, &group->a, ctx)) goto err; + if (!BN_mod_add_quick(rh, rh, tmp2, p)) goto err; + } + + /* rh := rh + b */ + if (!BN_mod_add_quick(rh, rh, &group->b, p)) goto err; + } + + /* 'lh' := Y^2 */ + if (!field_sqr(group, tmp1, &point->Y, ctx)) goto err; + + ret = (0 == BN_cmp(tmp1, rh)); + + err: + 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) + { + BN_CTX *new_ctx = NULL; + BIGNUM *Z, *Z_1, *Z_2, *Z_3; + int ret = 0; + + if (point->Z_is_one || EC_POINT_is_at_infinity(group, point)) + return 1; + + if (ctx == NULL) + { + ctx = new_ctx = BN_CTX_new(); + if (ctx == NULL) + return 0; + } + BN_CTX_start(ctx); + + Z = BN_CTX_get(ctx); + Z_1 = BN_CTX_get(ctx); + Z_2 = BN_CTX_get(ctx); + Z_3 = BN_CTX_get(ctx); + if (Z_3 == NULL) goto end; + + /* transform (X, Y, Z) into (X/Z^2, Y/Z^3, 1) */ + + if (group->meth->field_decode) + { + if (!group->meth->field_decode(group, Z, &point->Z, ctx)) goto end; + } + else + Z = &point->Z; + + if (BN_is_one(Z)) + { + point->Z_is_one = 1; + ret = 1; + goto end; + } + + if (!BN_mod_inverse(Z_1, Z, &group->field, ctx)) + { + ECerr(EC_F_EC_GFP_SIMPLE_MAKE_AFFINE, ERR_R_BN_LIB); + goto end; + } + if (!BN_mod_sqr(Z_2, Z_1, &group->field, ctx)) goto end; + if (!BN_mod_mul(Z_3, Z_2, Z_1, &group->field, ctx)) goto end; + + if (!BN_mod_mul(&point->X, &point->X, Z_2, &group->field, ctx)) goto end; + if (!BN_mod_mul(&point->Y, &point->Y, Z_2, &group->field, ctx)) goto end; + if (!BN_set_word(&point->Z, 1)) goto end; + point->Z_is_one = 1; + + ret = 1; + + end: + BN_CTX_end(ctx); + if (new_ctx != NULL) + BN_CTX_free(new_ctx); + return ret; + } int ec_GFp_simple_field_mul(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx) -- 2.25.1