bn_gf2m.c

mediastreamer2是开源的网络传输媒体流的库

 * This function calls down to the BN_GF2m_mod_sqr_arr implementation; this wrapper
 * function is only provided for convenience; for best performance, use the 
 * BN_GF2m_mod_sqr_arr function.
 */
int	BN_GF2m_mod_sqr(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx)
	{
	int ret = 0;
	const int max = BN_num_bits(p);
	unsigned int *arr=NULL;

	bn_check_top(a);
	bn_check_top(p);
	if ((arr = (unsigned int *)OPENSSL_malloc(sizeof(unsigned int) * max)) == NULL) goto err;
	ret = BN_GF2m_poly2arr(p, arr, max);
	if (!ret || ret > max)
		{
		BNerr(BN_F_BN_GF2M_MOD_SQR,BN_R_INVALID_LENGTH);
		goto err;
		}
	ret = BN_GF2m_mod_sqr_arr(r, a, arr, ctx);
	bn_check_top(r);
err:
	if (arr) OPENSSL_free(arr);
	return ret;
	}


/* Invert a, reduce modulo p, and store the result in r. r could be a. 
 * Uses Modified Almost Inverse Algorithm (Algorithm 10) from
 *     Hankerson, D., Hernandez, J.L., and Menezes, A.  "Software Implementation
 *     of Elliptic Curve Cryptography Over Binary Fields".
 */
int BN_GF2m_mod_inv(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx)
	{
	BIGNUM *b, *c, *u, *v, *tmp;
	int ret = 0;

	bn_check_top(a);
	bn_check_top(p);

	BN_CTX_start(ctx);
	
	b = BN_CTX_get(ctx);
	c = BN_CTX_get(ctx);
	u = BN_CTX_get(ctx);
	v = BN_CTX_get(ctx);
	if (v == NULL) goto err;

	if (!BN_one(b)) goto err;
	if (!BN_GF2m_mod(u, a, p)) goto err;
	if (!BN_copy(v, p)) goto err;

	if (BN_is_zero(u)) goto err;

	while (1)
		{
		while (!BN_is_odd(u))
			{
			if (!BN_rshift1(u, u)) goto err;
			if (BN_is_odd(b))
				{
				if (!BN_GF2m_add(b, b, p)) goto err;
				}
			if (!BN_rshift1(b, b)) goto err;
			}

		if (BN_abs_is_word(u, 1)) break;

		if (BN_num_bits(u) < BN_num_bits(v))
			{
			tmp = u; u = v; v = tmp;
			tmp = b; b = c; c = tmp;
			}
		
		if (!BN_GF2m_add(u, u, v)) goto err;
		if (!BN_GF2m_add(b, b, c)) goto err;
		}


	if (!BN_copy(r, b)) goto err;
	bn_check_top(r);
	ret = 1;

err:
  	BN_CTX_end(ctx);
	return ret;
	}

/* Invert xx, reduce modulo p, and store the result in r. r could be xx. 
 *
 * This function calls down to the BN_GF2m_mod_inv implementation; this wrapper
 * function is only provided for convenience; for best performance, use the 
 * BN_GF2m_mod_inv function.
 */
int BN_GF2m_mod_inv_arr(BIGNUM *r, const BIGNUM *xx, const unsigned int p[], BN_CTX *ctx)
	{
	BIGNUM *field;
	int ret = 0;

	bn_check_top(xx);
	BN_CTX_start(ctx);
	if ((field = BN_CTX_get(ctx)) == NULL) goto err;
	if (!BN_GF2m_arr2poly(p, field)) goto err;
	
	ret = BN_GF2m_mod_inv(r, xx, field, ctx);
	bn_check_top(r);

err:
	BN_CTX_end(ctx);
	return ret;
	}


#ifndef OPENSSL_SUN_GF2M_DIV
/* Divide y by x, reduce modulo p, and store the result in r. r could be x 
 * or y, x could equal y.
 */
int BN_GF2m_mod_div(BIGNUM *r, const BIGNUM *y, const BIGNUM *x, const BIGNUM *p, BN_CTX *ctx)
	{
	BIGNUM *xinv = NULL;
	int ret = 0;

	bn_check_top(y);
	bn_check_top(x);
	bn_check_top(p);

	BN_CTX_start(ctx);
	xinv = BN_CTX_get(ctx);
	if (xinv == NULL) goto err;
	
	if (!BN_GF2m_mod_inv(xinv, x, p, ctx)) goto err;
	if (!BN_GF2m_mod_mul(r, y, xinv, p, ctx)) goto err;
	bn_check_top(r);
	ret = 1;

err:
	BN_CTX_end(ctx);
	return ret;
	}
#else
/* Divide y by x, reduce modulo p, and store the result in r. r could be x 
 * or y, x could equal y.
 * Uses algorithm Modular_Division_GF(2^m) from 
 *     Chang-Shantz, S.  "From Euclid's GCD to Montgomery Multiplication to 
 *     the Great Divide".
 */
int BN_GF2m_mod_div(BIGNUM *r, const BIGNUM *y, const BIGNUM *x, const BIGNUM *p, BN_CTX *ctx)
	{
	BIGNUM *a, *b, *u, *v;
	int ret = 0;

	bn_check_top(y);
	bn_check_top(x);
	bn_check_top(p);

	BN_CTX_start(ctx);
	
	a = BN_CTX_get(ctx);
	b = BN_CTX_get(ctx);
	u = BN_CTX_get(ctx);
	v = BN_CTX_get(ctx);
	if (v == NULL) goto err;

	/* reduce x and y mod p */
	if (!BN_GF2m_mod(u, y, p)) goto err;
	if (!BN_GF2m_mod(a, x, p)) goto err;
	if (!BN_copy(b, p)) goto err;
	
	while (!BN_is_odd(a))
		{
		if (!BN_rshift1(a, a)) goto err;
		if (BN_is_odd(u)) if (!BN_GF2m_add(u, u, p)) goto err;
		if (!BN_rshift1(u, u)) goto err;
		}

	do
		{
		if (BN_GF2m_cmp(b, a) > 0)
			{
			if (!BN_GF2m_add(b, b, a)) goto err;
			if (!BN_GF2m_add(v, v, u)) goto err;
			do
				{
				if (!BN_rshift1(b, b)) goto err;
				if (BN_is_odd(v)) if (!BN_GF2m_add(v, v, p)) goto err;
				if (!BN_rshift1(v, v)) goto err;
				} while (!BN_is_odd(b));
			}
		else if (BN_abs_is_word(a, 1))
			break;
		else
			{
			if (!BN_GF2m_add(a, a, b)) goto err;
			if (!BN_GF2m_add(u, u, v)) goto err;
			do
				{
				if (!BN_rshift1(a, a)) goto err;
				if (BN_is_odd(u)) if (!BN_GF2m_add(u, u, p)) goto err;
				if (!BN_rshift1(u, u)) goto err;
				} while (!BN_is_odd(a));
			}
		} while (1);

	if (!BN_copy(r, u)) goto err;
	bn_check_top(r);
	ret = 1;

err:
  	BN_CTX_end(ctx);
	return ret;
	}
#endif

/* Divide yy by xx, reduce modulo p, and store the result in r. r could be xx 
 * or yy, xx could equal yy.
 *
 * This function calls down to the BN_GF2m_mod_div implementation; this wrapper
 * function is only provided for convenience; for best performance, use the 
 * BN_GF2m_mod_div function.
 */
int BN_GF2m_mod_div_arr(BIGNUM *r, const BIGNUM *yy, const BIGNUM *xx, const unsigned int p[], BN_CTX *ctx)
	{
	BIGNUM *field;
	int ret = 0;

	bn_check_top(yy);
	bn_check_top(xx);

	BN_CTX_start(ctx);
	if ((field = BN_CTX_get(ctx)) == NULL) goto err;
	if (!BN_GF2m_arr2poly(p, field)) goto err;
	
	ret = BN_GF2m_mod_div(r, yy, xx, field, ctx);
	bn_check_top(r);

err:
	BN_CTX_end(ctx);
	return ret;
	}


/* Compute the bth power of a, reduce modulo p, and store
 * the result in r.  r could be a.
 * Uses simple square-and-multiply algorithm A.5.1 from IEEE P1363.
 */
int	BN_GF2m_mod_exp_arr(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const unsigned int p[], BN_CTX *ctx)
	{
	int ret = 0, i, n;
	BIGNUM *u;

	bn_check_top(a);
	bn_check_top(b);

	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);
	if ((u = BN_CTX_get(ctx)) == NULL) goto err;
	
	if (!BN_GF2m_mod_arr(u, a, p)) goto err;
	
	n = BN_num_bits(b) - 1;
	for (i = n - 1; i >= 0; i--)
		{
		if (!BN_GF2m_mod_sqr_arr(u, u, p, ctx)) goto err;
		if (BN_is_bit_set(b, i))
			{
			if (!BN_GF2m_mod_mul_arr(u, u, a, p, ctx)) goto err;
			}
		}
	if (!BN_copy(r, u)) goto err;
	bn_check_top(r);
	ret = 1;
err:
	BN_CTX_end(ctx);
	return ret;
	}

/* Compute the bth power of a, reduce modulo p, and store
 * the result in r.  r could be a.
 *
 * This function calls down to the BN_GF2m_mod_exp_arr implementation; this wrapper
 * function is only provided for convenience; for best performance, use the 
 * BN_GF2m_mod_exp_arr function.
 */
int BN_GF2m_mod_exp(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *p, BN_CTX *ctx)
	{
	int ret = 0;
	const int max = BN_num_bits(p);
	unsigned int *arr=NULL;
	bn_check_top(a);
	bn_check_top(b);
	bn_check_top(p);
	if ((arr = (unsigned int *)OPENSSL_malloc(sizeof(unsigned int) * max)) == NULL) goto err;
	ret = BN_GF2m_poly2arr(p, arr, max);
	if (!ret || ret > max)
		{
		BNerr(BN_F_BN_GF2M_MOD_EXP,BN_R_INVALID_LENGTH);
		goto err;
		}
	ret = BN_GF2m_mod_exp_arr(r, a, b, arr, ctx);
	bn_check_top(r);
err:
	if (arr) OPENSSL_free(arr);
	return ret;
	}

/* Compute the square root of a, reduce modulo p, and store
 * the result in r.  r could be a.
 * Uses exponentiation as in algorithm A.4.1 from IEEE P1363.
 */
int	BN_GF2m_mod_sqrt_arr(BIGNUM *r, const BIGNUM *a, const unsigned int p[], BN_CTX *ctx)
	{
	int ret = 0;
	BIGNUM *u;

	bn_check_top(a);

	if (!p[0])
		{
		/* reduction mod 1 => return 0 */
		BN_zero(r);
		return 1;
		}

	BN_CTX_start(ctx);
	if ((u = BN_CTX_get(ctx)) == NULL) goto err;
	
	if (!BN_set_bit(u, p[0] - 1)) goto err;
	ret = BN_GF2m_mod_exp_arr(r, a, u, p, ctx);
	bn_check_top(r);

err:
	BN_CTX_end(ctx);
	return ret;
	}

/* Compute the square root of a, reduce modulo p, and store
 * the result in r.  r could be a.
 *
 * This function calls down to the BN_GF2m_mod_sqrt_arr implementation; this wrapper
 * function is only provided for convenience; for best performance, use the 
 * BN_GF2m_mod_sqrt_arr function.
 */
int BN_GF2m_mod_sqrt(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx)
	{
	int ret = 0;
	const int max = BN_num_bits(p);
	unsigned int *arr=NULL;
	bn_check_top(a);
	bn_check_top(p);
	if ((arr = (unsigned int *)OPENSSL_malloc(sizeof(unsigned int) * max)) == NULL) goto err;
	ret = BN_GF2m_poly2arr(p, arr, max);
	if (!ret || ret > max)
		{
		BNerr(BN_F_BN_GF2M_MOD_SQRT,BN_R_INVALID_LENGTH);
		goto err;
		}
	ret = BN_GF2m_mod_sqrt_arr(r, a, arr, ctx);
	bn_check_top(r);
err:
	if (arr) OPENSSL_free(arr);
	return ret;
	}

/* Find r such that r^2 + r = a mod p.  r could be a. If no r exists returns 0.
 * Uses algorithms A.4.7 and A.4.6 from IEEE P1363.
 */
int BN_GF2m_mod_solve_quad_arr(BIGNUM *r, const BIGNUM *a_, const unsigned int p[], BN_CTX *ctx)
	{
	int ret = 0, count = 0;
	unsigned int j;
	BIGNUM *a, *z, *rho, *w, *w2, *tmp;

	bn_check_top(a_);

	if (!p[0])
		{
		/* reduction mod 1 => return 0 */
		BN_zero(r);
		return 1;
		}

	BN_CTX_start(ctx);
	a = BN_CTX_get(ctx);
	z = BN_CTX_get(ctx);
	w = BN_CTX_get(ctx);
	if (w == NULL) goto err;

	if (!BN_GF2m_mod_arr(a, a_, p)) goto err;
	
	if (BN_is_zero(a))
		{
		BN_zero(r);
		ret = 1;
		goto err;
		}

	if (p[0] & 0x1) /* m is odd */
		{
		/* compute half-trace of a */
		if (!BN_copy(z, a)) goto err;
		for (j = 1; j <= (p[0] - 1) / 2; j++)
			{
			if (!BN_GF2m_mod_sqr_arr(z, z, p, ctx)) goto err;
			if (!BN_GF2m_mod_sqr_arr(z, z, p, ctx)) goto err;
			if (!BN_GF2m_add(z, z, a)) goto err;
			}
		
		}
	else /* m is even */
		{
		rho = BN_CTX_get(ctx);
		w2 = BN_CTX_get(ctx);
		tmp = BN_CTX_get(ctx);
		if (tmp == NULL) goto err;
		do
			{
			if (!BN_rand(rho, p[0], 0, 0)) goto err;
			if (!BN_GF2m_mod_arr(rho, rho, p)) goto err;
			BN_zero(z);
			if (!BN_copy(w, rho)) goto err;
			for (j = 1; j <= p[0] - 1; j++)
				{
				if (!BN_GF2m_mod_sqr_arr(z, z, p, ctx)) goto err;
				if (!BN_GF2m_mod_sqr_arr(w2, w, p, ctx)) goto err;
				if (!BN_GF2m_mod_mul_arr(tmp, w2, a, p, ctx)) goto err;
				if (!BN_GF2m_add(z, z, tmp)) goto err;
				if (!BN_GF2m_add(w, w2, rho)) goto err;
				}
			count++;
			} while (BN_is_zero(w) && (count < MAX_ITERATIONS));
		if (BN_is_zero(w))
			{
			BNerr(BN_F_BN_GF2M_MOD_SOLVE_QUAD_ARR,BN_R_TOO_MANY_ITERATIONS);
			goto err;
			}
		}
	
	if (!BN_GF2m_mod_sqr_arr(w, z, p, ctx)) goto err;
	if (!BN_GF2m_add(w, z, w)) goto err;
	if (BN_GF2m_cmp(w, a))
		{
		BNerr(BN_F_BN_GF2M_MOD_SOLVE_QUAD_ARR, BN_R_NO_SOLUTION);
		goto err;
		}

	if (!BN_copy(r, z)) goto err;
	bn_check_top(r);

	ret = 1;

err:
	BN_CTX_end(ctx);
	return ret;
	}

/* Find r such that r^2 + r = a mod p.  r could be a. If no r exists returns 0.
 *
 * This function calls down to the BN_GF2m_mod_solve_quad_arr implementation; this wrapper
 * function is only provided for convenience; for best performance, use the 
 * BN_GF2m_mod_solve_quad_arr function.
 */
int BN_GF2m_mod_solve_quad(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx)
	{
	int ret = 0;
	const int max = BN_num_bits(p);
	unsigned int *arr=NULL;
	bn_check_top(a);
	bn_check_top(p);
	if ((arr = (unsigned int *)OPENSSL_malloc(sizeof(unsigned int) *
						max)) == NULL) goto err;
	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;
		}
	ret = BN_GF2m_mod_solve_quad_arr(r, a, arr, ctx);
	bn_check_top(r);
err:
	if (arr) OPENSSL_free(arr);
	return ret;
	}

/* 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 = 0;
	BN_ULONG mask;

	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--)
			{
			if (a->d[i] & mask) 
				{
				if (k < max) p[k] = BN_BITS2 * i + j;
				k++;
				}
			mask >>= 1;
			}
		}

	return k;
	}

/* Convert the coefficient array representation of a polynomial to a 
 * bit-string.  The array must be terminated by 0.
 */
int BN_GF2m_arr2poly(const unsigned int p[], BIGNUM *a)
	{
	int i;

	bn_check_top(a);
	BN_zero(a);
	for (i = 0; p[i] != 0; i++)
		{
		BN_set_bit(a, p[i]);
		}
	BN_set_bit(a, 0);
	bn_check_top(a);

	return 1;
	}