diff options
author | Geoff Thorpe <geoff@openssl.org> | 2004-07-16 03:24:19 +0000 |
---|---|---|
committer | Geoff Thorpe <geoff@openssl.org> | 2004-07-16 03:24:19 +0000 |
commit | 7f5b4dd1e8596f7043a7da76b3e2f6675db8cd87 (patch) | |
tree | c5a0286007cf0acbd9bd4e112caac3beb7618d23 /crypto/ec | |
parent | 5906e8d5fee7b97223f221200702fa1a30436e2d (diff) |
Using Horner's algorithm to evaluate the ec polynomial
(suggested by Adam Young <ayoung@cigital.com>)
Submitted by: Nils Larsch
Diffstat (limited to 'crypto/ec')
-rw-r--r-- | crypto/ec/ec2_smpl.c | 49 | ||||
-rw-r--r-- | crypto/ec/ecp_smpl.c | 53 |
2 files changed, 41 insertions, 61 deletions
diff --git a/crypto/ec/ec2_smpl.c b/crypto/ec/ec2_smpl.c index d34e97d676..34c3a953a5 100644 --- a/crypto/ec/ec2_smpl.c +++ b/crypto/ec/ec2_smpl.c @@ -805,13 +805,18 @@ int ec_GF2m_simple_is_at_infinity(const EC_GROUP *group, const EC_POINT *point) */ int ec_GF2m_simple_is_on_curve(const EC_GROUP *group, const EC_POINT *point, BN_CTX *ctx) { - BN_CTX *new_ctx = NULL; - BIGNUM *rh, *lh, *tmp1; int ret = -1; + BN_CTX *new_ctx = NULL; + BIGNUM *lh, *y2; + int (*field_mul)(const EC_GROUP *, BIGNUM *, const BIGNUM *, const BIGNUM *, BN_CTX *); + int (*field_sqr)(const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *); if (EC_POINT_is_at_infinity(group, point)) return 1; - + + field_mul = group->meth->field_mul; + field_sqr = group->meth->field_sqr; + /* only support affine coordinates */ if (!point->Z_is_one) goto err; @@ -823,37 +828,23 @@ int ec_GF2m_simple_is_on_curve(const EC_GROUP *group, const EC_POINT *point, BN_ } BN_CTX_start(ctx); - rh = BN_CTX_get(ctx); + y2 = BN_CTX_get(ctx); lh = BN_CTX_get(ctx); - tmp1 = BN_CTX_get(ctx); - if (tmp1 == NULL) goto err; + if (lh == NULL) goto err; /* We have a curve defined by a Weierstrass equation * y^2 + x*y = x^3 + a*x^2 + b. - * To test this, we add up the right-hand side in 'rh' - * and the left-hand side in 'lh'. + * <=> x^3 + a*x^2 + x*y + b + y^2 = 0 + * <=> ((x + a) * x + y ) * x + b + y^2 = 0 */ - - /* rh := X^3 */ - if (!group->meth->field_sqr(group, tmp1, &point->X, ctx)) goto err; - if (!group->meth->field_mul(group, rh, tmp1, &point->X, ctx)) goto err; - - /* rh := rh + a*X^2 */ - if (!group->meth->field_mul(group, tmp1, tmp1, &group->a, ctx)) goto err; - if (!BN_GF2m_add(rh, rh, tmp1)) goto err; - - /* rh := rh + b */ - if (!BN_GF2m_add(rh, rh, &group->b)) goto err; - - /* lh := Y^2 */ - if (!group->meth->field_sqr(group, lh, &point->Y, ctx)) goto err; - - /* lh := lh + x*y */ - if (!group->meth->field_mul(group, tmp1, &point->X, &point->Y, ctx)) goto err; - if (!BN_GF2m_add(lh, lh, tmp1)) goto err; - - ret = (0 == BN_GF2m_cmp(lh, rh)); - + if (!BN_GF2m_add(lh, &point->X, &group->a)) goto err; + if (!field_mul(group, lh, lh, &point->X, ctx)) goto err; + if (!BN_GF2m_add(lh, lh, &point->Y)) goto err; + if (!field_mul(group, lh, lh, &point->X, ctx)) goto err; + if (!BN_GF2m_add(lh, lh, &group->b)) goto err; + if (!field_sqr(group, y2, &point->Y, ctx)) goto err; + if (!BN_GF2m_add(lh, lh, y2)) goto err; + ret = BN_is_zero(lh); err: if (ctx) BN_CTX_end(ctx); if (new_ctx) BN_CTX_free(new_ctx); diff --git a/crypto/ec/ecp_smpl.c b/crypto/ec/ecp_smpl.c index 87ebf7b89e..1c0052c5ca 100644 --- a/crypto/ec/ecp_smpl.c +++ b/crypto/ec/ecp_smpl.c @@ -1301,7 +1301,7 @@ int ec_GFp_simple_is_on_curve(const EC_GROUP *group, const EC_POINT *point, BN_C 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; + BIGNUM *rh, *tmp, *Z4, *Z6; int ret = -1; if (EC_POINT_is_at_infinity(group, point)) @@ -1320,8 +1320,7 @@ int ec_GFp_simple_is_on_curve(const EC_GROUP *group, const EC_POINT *point, BN_C BN_CTX_start(ctx); rh = BN_CTX_get(ctx); - tmp1 = BN_CTX_get(ctx); - tmp2 = BN_CTX_get(ctx); + tmp = BN_CTX_get(ctx); Z4 = BN_CTX_get(ctx); Z6 = BN_CTX_get(ctx); if (Z6 == NULL) goto err; @@ -1335,59 +1334,49 @@ int ec_GFp_simple_is_on_curve(const EC_GROUP *group, const EC_POINT *point, BN_C * To test this, we add up the right-hand side in 'rh'. */ - /* rh := X^3 */ + /* rh := X^2 */ 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; + if (!field_sqr(group, tmp, &point->Z, ctx)) goto err; + if (!field_sqr(group, Z4, tmp, ctx)) goto err; + if (!field_mul(group, Z6, Z4, tmp, ctx)) goto err; - /* rh := rh + a*X*Z^4 */ - if (!field_mul(group, tmp1, &point->X, Z4, ctx)) goto err; + /* rh := (rh + a*Z^4)*X */ 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; + if (!BN_mod_lshift1_quick(tmp, Z4, p)) goto err; + if (!BN_mod_add_quick(tmp, tmp, Z4, p)) goto err; + if (!BN_mod_sub_quick(rh, rh, tmp, p)) goto err; + if (!field_mul(group, rh, rh, &point->X, ctx)) 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; + if (!field_mul(group, tmp, Z4, &group->a, ctx)) goto err; + if (!BN_mod_add_quick(rh, rh, tmp, p)) goto err; + if (!field_mul(group, rh, rh, &point->X, ctx)) 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; + if (!field_mul(group, tmp, &group->b, Z6, ctx)) goto err; + if (!BN_mod_add_quick(rh, rh, tmp, 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 + a)*X */ + if (!BN_mod_add_quick(rh, rh, &group->a, p)) goto err; + if (!field_mul(group, rh, rh, &point->X, ctx)) 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; + if (!field_sqr(group, tmp, &point->Y, ctx)) goto err; - ret = (0 == BN_cmp(tmp1, rh)); + ret = (0 == BN_ucmp(tmp, rh)); err: BN_CTX_end(ctx); |