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/ec2_smpl.c | |
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/ec2_smpl.c')
-rw-r--r-- | crypto/ec/ec2_smpl.c | 49 |
1 files changed, 20 insertions, 29 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); |