Some changes for bn_gf2m.c: better error checking plus some minor

optimizations.

Submitted by: Nils Larsch

1 files changed, 48 insertions, 30 deletions

diff --git a/crypto/bn/bn_gf2m.c b/crypto/bn/bn_gf2m.c
index 0bb4f9b251..1cdad7473b 100644
--- a/crypto/bn/bn_gf2m.c
+++ b/crypto/bn/bn_gf2m.c
@@ -323,8 +323,12 @@ int BN_GF2m_mod_arr(BIGNUM *r, const BIGNUM *a, const unsigned int p[])
 	int n, dN, d0, d1;
 	BN_ULONG zz, *z;
 	
-	/* Since the algorithm does reduction in the r value, if a != r, copy the
-	 * contents of a into r so we can do reduction in r. 
+	if (!p[0])
+		/* reduction mod 1 => return 0 */
+		return BN_zero(r);
+
+	/* Since the algorithm does reduction in the r value, if a != r, copy
+	 * the contents of a into r so we can do reduction in r. 
 	 */
 	if (a != r)
 		{
@@ -345,7 +349,7 @@ int BN_GF2m_mod_arr(BIGNUM *r, const BIGNUM *a, const unsigned int p[])
 		if (z[j] == 0) { j--; continue; }
 		z[j] = 0;
 
-		for (k = 1; p[k] > 0; k++)
+		for (k = 1; p[k] != 0; k++)
 			{
 			/* reducing component t^p[k] */
 			n = p[0] - p[k];
@@ -375,7 +379,7 @@ int BN_GF2m_mod_arr(BIGNUM *r, const BIGNUM *a, const unsigned int p[])
 		if (d0) z[dN] = (z[dN] << d1) >> d1; /* clear up the top d1 bits */
 		z[0] ^= zz; /* reduction t^0 component */
 
-		for (k = 1; p[k] > 0; k++)
+		for (k = 1; p[k] != 0; k++)
 			{
 			BN_ULONG tmp_ulong;
 
@@ -408,7 +412,8 @@ int	BN_GF2m_mod(BIGNUM *r, const BIGNUM *a, const BIGNUM *p)
 	const int max = BN_num_bits(p);
 	unsigned int *arr=NULL, ret = 0;
 	if ((arr = (unsigned int *)OPENSSL_malloc(sizeof(unsigned int) * max)) == NULL) goto err;
-	if (BN_GF2m_poly2arr(p, arr, max) > max)
+	ret = BN_GF2m_poly2arr(p, arr, max);
+	if (!ret || ret > max)
 		{
 		BNerr(BN_F_BN_GF2M_MOD,BN_R_INVALID_LENGTH);
 		goto err;
@@ -459,9 +464,9 @@ int	BN_GF2m_mod_mul_arr(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const unsig
 		}
 
 	bn_correct_top(s);
-	BN_GF2m_mod_arr(r, s, p);
+	if (BN_GF2m_mod_arr(r, s, p))
+		ret = 1;
 	bn_check_top(r);
-	ret = 1;
 
   err:
 	BN_CTX_end(ctx);
@@ -481,7 +486,8 @@ int	BN_GF2m_mod_mul(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *p
 	const int max = BN_num_bits(p);
 	unsigned int *arr=NULL, ret = 0;
 	if ((arr = (unsigned int *)OPENSSL_malloc(sizeof(unsigned int) * max)) == NULL) goto err;
-	if (BN_GF2m_poly2arr(p, arr, max) > max)
+	ret = BN_GF2m_poly2arr(p, arr, max);
+	if (!ret || ret > max)
 		{
 		BNerr(BN_F_BN_GF2M_MOD_MUL,BN_R_INVALID_LENGTH);
 		goto err;
@@ -531,7 +537,8 @@ int	BN_GF2m_mod_sqr(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx)
 	const int max = BN_num_bits(p);
 	unsigned int *arr=NULL, ret = 0;
 	if ((arr = (unsigned int *)OPENSSL_malloc(sizeof(unsigned int) * max)) == NULL) goto err;
-	if (BN_GF2m_poly2arr(p, arr, max) > max)
+	ret = BN_GF2m_poly2arr(p, arr, max);
+	if (!ret || ret > max)
 		{
 		BNerr(BN_F_BN_GF2M_MOD_SQR,BN_R_INVALID_LENGTH);
 		goto err;
@@ -567,10 +574,6 @@ int BN_GF2m_mod_inv(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx)
 	if (!BN_GF2m_mod(u, a, p)) goto err;
 	if (!BN_copy(v, p)) goto err;
 
-	u->neg = 0; /* Need to set u->neg = 0 because BN_is_one(u) checks
-	             * the neg flag of the bignum.
-	             */
-
 	if (BN_is_zero(u)) goto err;
 
 	while (1)
@@ -585,7 +588,7 @@ int BN_GF2m_mod_inv(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx)
 			if (!BN_rshift1(b, b)) goto err;
 			}
 
-		if (BN_is_one(u)) break;
+		if (BN_abs_is_word(u, 1)) break;
 
 		if (BN_num_bits(u) < BN_num_bits(v))
 			{
@@ -679,10 +682,6 @@ int BN_GF2m_mod_div(BIGNUM *r, const BIGNUM *y, const BIGNUM *x, const BIGNUM *p
 	if (!BN_copy(b, p)) goto err;
 	if (!BN_zero(v)) goto err;
 	
-	a->neg = 0; /* Need to set a->neg = 0 because BN_is_one(a) checks
-	             * the neg flag of the bignum.
-	             */
-
 	while (!BN_is_odd(a))
 		{
 		if (!BN_rshift1(a, a)) goto err;
@@ -703,7 +702,7 @@ int BN_GF2m_mod_div(BIGNUM *r, const BIGNUM *y, const BIGNUM *x, const BIGNUM *p
 				if (!BN_rshift1(v, v)) goto err;
 				} while (!BN_is_odd(b));
 			}
-		else if (BN_is_one(a))
+		else if (BN_abs_is_word(a, 1))
 			break;
 		else
 			{
@@ -763,9 +762,10 @@ int	BN_GF2m_mod_exp_arr(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const unsig
 	BIGNUM *u;
 	
 	if (BN_is_zero(b))
-		{
 		return(BN_one(r));
-		}
+
+	if (BN_abs_is_word(b, 1))
+		return (BN_copy(r, a) != NULL);
 	
 
 	BN_CTX_start(ctx);
@@ -804,7 +804,8 @@ int BN_GF2m_mod_exp(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *p
 	const int max = BN_num_bits(p);
 	unsigned int *arr=NULL, ret = 0;
 	if ((arr = (unsigned int *)OPENSSL_malloc(sizeof(unsigned int) * max)) == NULL) goto err;
-	if (BN_GF2m_poly2arr(p, arr, max) > max)
+	ret = BN_GF2m_poly2arr(p, arr, max);
+	if (!ret || ret > max)
 		{
 		BNerr(BN_F_BN_GF2M_MOD_EXP,BN_R_INVALID_LENGTH);
 		goto err;
@@ -824,6 +825,10 @@ int	BN_GF2m_mod_sqrt_arr(BIGNUM *r, const BIGNUM *a, const unsigned int p[], BN_
 	{
 	int ret = 0;
 	BIGNUM *u;
+
+	if (!p[0])
+		/* reduction mod 1 => return 0 */
+		return BN_zero(r);
 	
 	BN_CTX_start(ctx);
 	if ((u = BN_CTX_get(ctx)) == NULL) goto err;
@@ -850,7 +855,8 @@ int BN_GF2m_mod_sqrt(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx)
 	const int max = BN_num_bits(p);
 	unsigned int *arr=NULL, ret = 0;
 	if ((arr = (unsigned int *)OPENSSL_malloc(sizeof(unsigned int) * max)) == NULL) goto err;
-	if (BN_GF2m_poly2arr(p, arr, max) > max)
+	ret = BN_GF2m_poly2arr(p, arr, max);
+	if (!ret || ret > max)
 		{
 		BNerr(BN_F_BN_GF2M_MOD_EXP,BN_R_INVALID_LENGTH);
 		goto err;
@@ -870,7 +876,11 @@ int BN_GF2m_mod_solve_quad_arr(BIGNUM *r, const BIGNUM *a_, const unsigned int p
 	int ret = 0, count = 0;
 	unsigned int j;
 	BIGNUM *a, *z, *rho, *w, *w2, *tmp;
-	
+
+	if (!p[0])
+		/* reduction mod 1 => return 0 */
+		return BN_zero(r);
+
 	BN_CTX_start(ctx);
 	a = BN_CTX_get(ctx);
 	z = BN_CTX_get(ctx);
@@ -951,7 +961,8 @@ int BN_GF2m_mod_solve_quad(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, BN_CTX *
 	const int max = BN_num_bits(p);
 	unsigned int *arr=NULL, ret = 0;
 	if ((arr = (unsigned int *)OPENSSL_malloc(sizeof(unsigned int) * max)) == NULL) goto err;
-	if (BN_GF2m_poly2arr(p, arr, max) > max)
+	ret = BN_GF2m_poly2arr(p, arr, max);
+	if (!ret || ret > max)
 		{
 		BNerr(BN_F_BN_GF2M_MOD_SOLVE_QUAD,BN_R_INVALID_LENGTH);
 		goto err;
@@ -963,21 +974,28 @@ int BN_GF2m_mod_solve_quad(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, BN_CTX *
 	return ret;
 	}
 
-/* Convert the bit-string representation of a polynomial a into an array
+/* Convert the bit-string representation of a polynomial
+ * ( \sum_{i=0}^n a_i * x^i , where a_0 is *not* zero) into an array
  * of integers corresponding to the bits with non-zero coefficient.
  * Up to max elements of the array will be filled.  Return value is total
  * number of coefficients that would be extracted if array was large enough.
  */
 int BN_GF2m_poly2arr(const BIGNUM *a, unsigned int p[], int max)
 	{
-	int i, j, k;
+	int i, j, k = 0;
 	BN_ULONG mask;
 
-	for (k = 0; k < max; k++) p[k] = 0;
-	k = 0;
+	if (BN_is_zero(a) || !BN_is_bit_set(a, 0))
+		/* a_0 == 0 => return error (the unsigned int array
+		 * must be terminated by 0)
+		 */
+		return 0;
 
 	for (i = a->top - 1; i >= 0; i--)
 		{
+		if (!a->d[i])
+			/* skip word if a->d[i] == 0 */
+			continue;
 		mask = BN_TBIT;
 		for (j = BN_BITS2 - 1; j >= 0; j--)
 			{
@@ -1001,7 +1019,7 @@ int BN_GF2m_arr2poly(const unsigned int p[], BIGNUM *a)
 	int i;
 
 	BN_zero(a);
-	for (i = 0; p[i] > 0; i++)
+	for (i = 0; p[i] != 0; i++)
 		{
 		BN_set_bit(a, p[i]);
 		}