Using Horner's algorithm to evaluate the ec polynomial

(suggested by Adam Young <ayoung@cigital.com>)

Submitted by: Nils Larsch

1 files changed, 21 insertions, 32 deletions

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);