bntest.c

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

				fprintf(stderr,"GF(2^m) modular inversion test failed!\n");
				goto err;
				}
			}
		}
	ret = 1;
  err:
	BN_free(a);
	BN_free(b[0]);
	BN_free(b[1]);
	BN_free(c);
	BN_free(d);
	return ret;
	}

int test_gf2m_mod_div(BIO *bp,BN_CTX *ctx)
	{
	BIGNUM *a,*b[2],*c,*d,*e,*f;
	int i, j, ret = 0;
	unsigned int p0[] = {163,7,6,3,0};
	unsigned int p1[] = {193,15,0};

	a=BN_new();
	b[0]=BN_new();
	b[1]=BN_new();
	c=BN_new();
	d=BN_new();
	e=BN_new();
	f=BN_new();

	BN_GF2m_arr2poly(p0, b[0]);
	BN_GF2m_arr2poly(p1, b[1]);

	for (i=0; i<num0; i++)
		{
		BN_bntest_rand(a, 512, 0, 0); 
		BN_bntest_rand(c, 512, 0, 0);
		for (j=0; j < 2; j++)
			{
			BN_GF2m_mod_div(d, a, c, b[j], ctx);
			BN_GF2m_mod_mul(e, d, c, b[j], ctx);
			BN_GF2m_mod_div(f, a, e, b[j], ctx);
#if 0 /* make test uses ouput in bc but bc can't handle GF(2^m) arithmetic */
			if (bp != NULL)
				{
				if (!results)
					{
					BN_print(bp,a);
					BIO_puts(bp, " = ");
					BN_print(bp,c);
					BIO_puts(bp," * ");
					BN_print(bp,d);
					BIO_puts(bp, " % ");
					BN_print(bp,b[j]);
					BIO_puts(bp,"\n");
					}
				}
#endif
			/* Test that ((a/c)*c)/a = 1. */
			if(!BN_is_one(f))
				{
				fprintf(stderr,"GF(2^m) modular division test failed!\n");
				goto err;
				}
			}
		}
	ret = 1;
  err:
	BN_free(a);
	BN_free(b[0]);
	BN_free(b[1]);
	BN_free(c);
	BN_free(d);
	BN_free(e);
	BN_free(f);
	return ret;
	}

int test_gf2m_mod_exp(BIO *bp,BN_CTX *ctx)
	{
	BIGNUM *a,*b[2],*c,*d,*e,*f;
	int i, j, ret = 0;
	unsigned int p0[] = {163,7,6,3,0};
	unsigned int p1[] = {193,15,0};

	a=BN_new();
	b[0]=BN_new();
	b[1]=BN_new();
	c=BN_new();
	d=BN_new();
	e=BN_new();
	f=BN_new();

	BN_GF2m_arr2poly(p0, b[0]);
	BN_GF2m_arr2poly(p1, b[1]);

	for (i=0; i<num0; i++)
		{
		BN_bntest_rand(a, 512, 0, 0);
		BN_bntest_rand(c, 512, 0, 0);
		BN_bntest_rand(d, 512, 0, 0);
		for (j=0; j < 2; j++)
			{
			BN_GF2m_mod_exp(e, a, c, b[j], ctx);
			BN_GF2m_mod_exp(f, a, d, b[j], ctx);
			BN_GF2m_mod_mul(e, e, f, b[j], ctx);
			BN_add(f, c, d);
			BN_GF2m_mod_exp(f, a, f, b[j], ctx);
#if 0 /* make test uses ouput in bc but bc can't handle GF(2^m) arithmetic */
			if (bp != NULL)
				{
				if (!results)
					{
					BN_print(bp,a);
					BIO_puts(bp, " ^ (");
					BN_print(bp,c);
					BIO_puts(bp," + ");
					BN_print(bp,d);
					BIO_puts(bp, ") = ");
					BN_print(bp,e);
					BIO_puts(bp, "; - ");
					BN_print(bp,f);
					BIO_puts(bp, " % ");
					BN_print(bp,b[j]);
					BIO_puts(bp,"\n");
					}
				}
#endif
			BN_GF2m_add(f, e, f);
			/* Test that a^(c+d)=a^c*a^d. */
			if(!BN_is_zero(f))
				{
				fprintf(stderr,"GF(2^m) modular exponentiation test failed!\n");
				goto err;
				}
			}
		}
	ret = 1;
  err:
	BN_free(a);
	BN_free(b[0]);
	BN_free(b[1]);
	BN_free(c);
	BN_free(d);
	BN_free(e);
	BN_free(f);
	return ret;
	}

int test_gf2m_mod_sqrt(BIO *bp,BN_CTX *ctx)
	{
	BIGNUM *a,*b[2],*c,*d,*e,*f;
	int i, j, ret = 0;
	unsigned int p0[] = {163,7,6,3,0};
	unsigned int p1[] = {193,15,0};

	a=BN_new();
	b[0]=BN_new();
	b[1]=BN_new();
	c=BN_new();
	d=BN_new();
	e=BN_new();
	f=BN_new();

	BN_GF2m_arr2poly(p0, b[0]);
	BN_GF2m_arr2poly(p1, b[1]);

	for (i=0; i<num0; i++)
		{
		BN_bntest_rand(a, 512, 0, 0);
		for (j=0; j < 2; j++)
			{
			BN_GF2m_mod(c, a, b[j]);
			BN_GF2m_mod_sqrt(d, a, b[j], ctx);
			BN_GF2m_mod_sqr(e, d, b[j], ctx);
#if 0 /* make test uses ouput in bc but bc can't handle GF(2^m) arithmetic */
			if (bp != NULL)
				{
				if (!results)
					{
					BN_print(bp,d);
					BIO_puts(bp, " ^ 2 - ");
					BN_print(bp,a);
					BIO_puts(bp,"\n");
					}
				}
#endif
			BN_GF2m_add(f, c, e);
			/* Test that d^2 = a, where d = sqrt(a). */
			if(!BN_is_zero(f))
				{
				fprintf(stderr,"GF(2^m) modular square root test failed!\n");
				goto err;
				}
			}
		}
	ret = 1;
  err:
	BN_free(a);
	BN_free(b[0]);
	BN_free(b[1]);
	BN_free(c);
	BN_free(d);
	BN_free(e);
	BN_free(f);
	return ret;
	}

int test_gf2m_mod_solve_quad(BIO *bp,BN_CTX *ctx)
	{
	BIGNUM *a,*b[2],*c,*d,*e;
	int i, j, s = 0, t, ret = 0;
	unsigned int p0[] = {163,7,6,3,0};
	unsigned int p1[] = {193,15,0};

	a=BN_new();
	b[0]=BN_new();
	b[1]=BN_new();
	c=BN_new();
	d=BN_new();
	e=BN_new();

	BN_GF2m_arr2poly(p0, b[0]);
	BN_GF2m_arr2poly(p1, b[1]);

	for (i=0; i<num0; i++)
		{
		BN_bntest_rand(a, 512, 0, 0);
		for (j=0; j < 2; j++)
			{
			t = BN_GF2m_mod_solve_quad(c, a, b[j], ctx);
			if (t)
				{
				s++;
				BN_GF2m_mod_sqr(d, c, b[j], ctx);
				BN_GF2m_add(d, c, d);
				BN_GF2m_mod(e, a, b[j]);
#if 0 /* make test uses ouput in bc but bc can't handle GF(2^m) arithmetic */
				if (bp != NULL)
					{
					if (!results)
						{
						BN_print(bp,c);
						BIO_puts(bp, " is root of z^2 + z = ");
						BN_print(bp,a);
						BIO_puts(bp, " % ");
						BN_print(bp,b[j]);
						BIO_puts(bp, "\n");
						}
					}
#endif
				BN_GF2m_add(e, e, d);
				/* Test that solution of quadratic c satisfies c^2 + c = a. */
				if(!BN_is_zero(e))
					{
					fprintf(stderr,"GF(2^m) modular solve quadratic test failed!\n");
					goto err;
					}

				}
			else 
				{
#if 0 /* make test uses ouput in bc but bc can't handle GF(2^m) arithmetic */
				if (bp != NULL)
					{
					if (!results)
						{
						BIO_puts(bp, "There are no roots of z^2 + z = ");
						BN_print(bp,a);
						BIO_puts(bp, " % ");
						BN_print(bp,b[j]);
						BIO_puts(bp, "\n");
						}
					}
#endif
				}
			}
		}
	if (s == 0)
		{	
		fprintf(stderr,"All %i tests of GF(2^m) modular solve quadratic resulted in no roots;\n", num0);
		fprintf(stderr,"this is very unlikely and probably indicates an error.\n");
		goto err;
		}
	ret = 1;
  err:
	BN_free(a);
	BN_free(b[0]);
	BN_free(b[1]);
	BN_free(c);
	BN_free(d);
	BN_free(e);
	return ret;
	}

static int genprime_cb(int p, int n, BN_GENCB *arg)
	{
	char c='*';

	if (p == 0) c='.';
	if (p == 1) c='+';
	if (p == 2) c='*';
	if (p == 3) c='\n';
	putc(c, stderr);
	fflush(stderr);
	return 1;
	}

int test_kron(BIO *bp, BN_CTX *ctx)
	{
	BN_GENCB cb;
	BIGNUM *a,*b,*r,*t;
	int i;
	int legendre, kronecker;
	int ret = 0;

	a = BN_new();
	b = BN_new();
	r = BN_new();
	t = BN_new();
	if (a == NULL || b == NULL || r == NULL || t == NULL) goto err;

	BN_GENCB_set(&cb, genprime_cb, NULL);
	
	/* We test BN_kronecker(a, b, ctx) just for  b  odd (Jacobi symbol).
	 * In this case we know that if  b  is prime, then BN_kronecker(a, b, ctx)
	 * is congruent to $a^{(b-1)/2}$, modulo $b$ (Legendre symbol).
	 * So we generate a random prime  b  and compare these values
	 * for a number of random  a's.  (That is, we run the Solovay-Strassen
	 * primality test to confirm that  b  is prime, except that we
	 * don't want to test whether  b  is prime but whether BN_kronecker
	 * works.) */

	if (!BN_generate_prime_ex(b, 512, 0, NULL, NULL, &cb)) goto err;
	b->neg = rand_neg();
	putc('\n', stderr);

	for (i = 0; i < num0; i++)
		{
		if (!BN_bntest_rand(a, 512, 0, 0)) goto err;
		a->neg = rand_neg();

		/* t := (|b|-1)/2  (note that b is odd) */
		if (!BN_copy(t, b)) goto err;
		t->neg = 0;
		if (!BN_sub_word(t, 1)) goto err;
		if (!BN_rshift1(t, t)) goto err;
		/* r := a^t mod b */
		b->neg=0;
		
		if (!BN_mod_exp_recp(r, a, t, b, ctx)) goto err;
		b->neg=1;

		if (BN_is_word(r, 1))
			legendre = 1;
		else if (BN_is_zero(r))
			legendre = 0;
		else
			{
			if (!BN_add_word(r, 1)) goto err;
			if (0 != BN_ucmp(r, b))
				{
				fprintf(stderr, "Legendre symbol computation failed\n");
				goto err;
				}
			legendre = -1;
			}
		
		kronecker = BN_kronecker(a, b, ctx);
		if (kronecker < -1) goto err;
		/* we actually need BN_kronecker(a, |b|) */
		if (a->neg && b->neg)
			kronecker = -kronecker;
		
		if (legendre != kronecker)
			{
			fprintf(stderr, "legendre != kronecker; a = ");
			BN_print_fp(stderr, a);
			fprintf(stderr, ", b = ");
			BN_print_fp(stderr, b);
			fprintf(stderr, "\n");
			goto err;
			}

		putc('.', stderr);
		fflush(stderr);
		}

	putc('\n', stderr);
	fflush(stderr);
	ret = 1;
 err:
	if (a != NULL) BN_free(a);
	if (b != NULL) BN_free(b);
	if (r != NULL) BN_free(r);
	if (t != NULL) BN_free(t);
	return ret;
	}

int test_sqrt(BIO *bp, BN_CTX *ctx)
	{
	BN_GENCB cb;
	BIGNUM *a,*p,*r;
	int i, j;
	int ret = 0;

	a = BN_new();
	p = BN_new();
	r = BN_new();
	if (a == NULL || p == NULL || r == NULL) goto err;

	BN_GENCB_set(&cb, genprime_cb, NULL);

	for (i = 0; i < 16; i++)
		{
		if (i < 8)
			{
			unsigned primes[8] = { 2, 3, 5, 7, 11, 13, 17, 19 };
			
			if (!BN_set_word(p, primes[i])) goto err;
			}
		else
			{
			if (!BN_set_word(a, 32)) goto err;
			if (!BN_set_word(r, 2*i + 1)) goto err;
		
			if (!BN_generate_prime_ex(p, 256, 0, a, r, &cb)) goto err;
			putc('\n', stderr);
			}
		p->neg = rand_neg();

		for (j = 0; j < num2; j++)
			{
			/* construct 'a' such that it is a square modulo p,
			 * but in general not a proper square and not reduced modulo p */
			if (!BN_bntest_rand(r, 256, 0, 3)) goto err;
			if (!BN_nnmod(r, r, p, ctx)) goto err;
			if (!BN_mod_sqr(r, r, p, ctx)) goto err;
			if (!BN_bntest_rand(a, 256, 0, 3)) goto err;
			if (!BN_nnmod(a, a, p, ctx)) goto err;
			if (!BN_mod_sqr(a, a, p, ctx)) goto err;
			if (!BN_mul(a, a, r, ctx)) goto err;
			if (rand_neg())
				if (!BN_sub(a, a, p)) goto err;

			if (!BN_mod_sqrt(r, a, p, ctx)) goto err;
			if (!BN_mod_sqr(r, r, p, ctx)) goto err;

			if (!BN_nnmod(a, a, p, ctx)) goto err;

			if (BN_cmp(a, r) != 0)
				{
				fprintf(stderr, "BN_mod_sqrt failed: a = ");
				BN_print_fp(stderr, a);
				fprintf(stderr, ", r = ");
				BN_print_fp(stderr, r);
				fprintf(stderr, ", p = ");
				BN_print_fp(stderr, p);
				fprintf(stderr, "\n");
				goto err;
				}

			putc('.', stderr);
			fflush(stderr);
			}
		
		putc('\n', stderr);
		fflush(stderr);
		}
	ret = 1;
 err:
	if (a != NULL) BN_free(a);
	if (p != NULL) BN_free(p);
	if (r != NULL) BN_free(r);
	return ret;
	}

int test_lshift(BIO *bp,BN_CTX *ctx,BIGNUM *a_)
	{
	BIGNUM *a,*b,*c,*d;
	int i;

	b=BN_new();
	c=BN_new();
	d=BN_new();
	BN_one(c);

	if(a_)
	    a=a_;
	else
	    {
	    a=BN_new();
	    BN_bntest_rand(a,200,0,0); /**/
	    a->neg=rand_neg();
	    }
	for (i=0; i<num0; i++)
		{
		BN_lshift(b,a,i+1);
		BN_add(c,c,c);
		if (bp != NULL)
			{
			if (!results)
				{
				BN_print(bp,a);
				BIO_puts(bp," * ");
				BN_print(bp,c);
				BIO_puts(bp," - ");
				}
			BN_print(bp,b);
			BIO_puts(bp,"\n");
			}
		BN_mul(d,a,c,ctx);
		BN_sub(d,d,b);
		if(!BN_is_zero(d))
		    {
		    fprintf(stderr,"Left shift test failed!\n");
		    fprintf(stderr,"a=");
		    BN_print_fp(stderr,a);
		    fprintf(stderr,"\nb=");
		    BN_print_fp(stderr,b);
		    fprintf(stderr,"\nc=");
		    BN_print_fp(stderr,c);
		    fprintf(stderr,"\nd=");
		    BN_print_fp(stderr,d);
		    fprintf(stderr,"\n");
		    return 0;
		    }
		}
	BN_free(a);
	BN_free(b);
	BN_free(c);
	BN_free(d);
	return(1);
	}

int test_lshift1(BIO *bp)
	{
	BIGNUM *a,*b,*c;
	int i;

	a=BN_new();
	b=BN_new();
	c=BN_new();

	BN_bntest_rand(a,200,0,0); /**/
	a->neg=rand_neg();
	for (i=0; i<num0; i++)
		{
		BN_lshift1(b,a);
		if (bp != NULL)
			{
			if (!results)
				{
				BN_print(bp,a);
				BIO_puts(bp," * 2");
				BIO_puts(bp," - ");
				}
			BN_print(bp,b);
			BIO_puts(bp,"\n");
			}
		BN_add(c,a,a);
		BN_sub(a,b,c);
		if(!BN_is_zero(a))
		    {
		    fprintf(stderr,"Left shift one test failed!\n");
		    return 0;
		    }
		
		BN_copy(a,b);
		}
	BN_free(a);
	BN_free(b);
	BN_free(c);
	return(1);
	}

int test_rshift(BIO *bp,BN_CTX *ctx)
	{
	BIGNUM *a,*b,*c,*d,*e;
	int i;

	a=BN_new();
	b=BN_new();
	c=BN_new();
	d=BN_new();
	e=BN_new();
	BN_one(c);

	BN_bntest_rand(a,200,0,0); /**/
	a->neg=rand_neg();
	for (i=0; i<num0; i++)
		{
		BN_rshift(b,a,i+1);
		BN_add(c,c,c);
		if (bp != NULL)
			{
			if (!results)
				{
				BN_print(bp,a);
				BIO_puts(bp," / ");
				BN_print(bp,c);
				BIO_puts(bp," - ");
				}
			BN_print(bp,b);
			BIO_puts(bp,"\n");
			}
		BN_div(d,e,a,c,ctx);
		BN_sub(d,d,b);
		if(!BN_is_zero(d))
		    {
		    fprintf(stderr,"Right shift test failed!\n");
		    return 0;
		    }
		}
	BN_free(a);
	BN_free(b);
	BN_free(c);
	BN_free(d);
	BN_free(e);
	return(1);
	}

int test_rshift1(BIO *bp)
	{
	BIGNUM *a,*b,*c;
	int i;

	a=BN_new();
	b=BN_new();
	c=BN_new();

	BN_bntest_rand(a,200,0,0); /**/
	a->neg=rand_neg();
	for (i=0; i<num0; i++)
		{
		BN_rshift1(b,a);
		if (bp != NULL)
			{
			if (!results)
				{
				BN_print(bp,a);
				BIO_puts(bp," / 2");
				BIO_puts(bp," - ");
				}
			BN_print(bp,b);
			BIO_puts(bp,"\n");
			}
		BN_sub(c,a,b);
		BN_sub(c,c,b);
		if(!BN_is_zero(c) && !BN_abs_is_word(c, 1))
		    {
		    fprintf(stderr,"Right shift one test failed!\n");
		    return 0;
		    }
		BN_copy(a,b);
		}
	BN_free(a);
	BN_free(b);
	BN_free(c);
	return(1);
	}

int rand_neg(void)
	{
	static unsigned int neg=0;
	static int sign[8]={0,0,0,1,1,0,1,1};

	return(sign[(neg++)%8]);
	}