X-Git-Url: https://git.openssl.org/gitweb/?p=openssl.git;a=blobdiff_plain;f=crypto%2Fbn%2Fbntest.c;h=3c0c95feb609028db2c687341d3b743b1ea2399e;hp=cec21646da6a4ed32db6a9b028f075b957751917;hb=b2993bdea10ed0c1344ce8b9fa9ddacfe681e822;hpb=f07fb9b24be9ae2d21647257d830da565561df3b diff --git a/crypto/bn/bntest.c b/crypto/bn/bntest.c index cec21646da..3c0c95feb6 100644 --- a/crypto/bn/bntest.c +++ b/crypto/bn/bntest.c @@ -91,6 +91,8 @@ int test_mod(BIO *bp,BN_CTX *ctx); int test_mod_mul(BIO *bp,BN_CTX *ctx); int test_mod_exp(BIO *bp,BN_CTX *ctx); int test_exp(BIO *bp,BN_CTX *ctx); +int test_kron(BIO *bp,BN_CTX *ctx); +int test_sqrt(BIO *bp,BN_CTX *ctx); int rand_neg(void); static int results=0; @@ -104,10 +106,10 @@ static unsigned char lst[]="\xC6\x4F\x43\x04\x2A\xEA\xCA\x6E\x58\x36\x80\x5B\xE8 static const char rnd_seed[] = "string to make the random number generator think it has entropy"; -void message(BIO *out, char *m) +static void message(BIO *out, char *m) { fprintf(stderr, "test %s\n", m); -#if defined(linux) || defined(FreeBSD) /* can we use GNU bc features? */ +#if defined(linux) || defined(__FreeBSD__) /* can we use GNU bc features? */ BIO_puts(out, "print \"test "); BIO_puts(out, m); BIO_puts(out, "\\n\"\n"); @@ -163,70 +165,80 @@ int main(int argc, char *argv[]) if (!results) BIO_puts(out,"obase=16\nibase=16\n"); +#if 0 message(out,"BN_add"); if (!test_add(out)) goto err; - fflush(stdout); + BIO_flush(out); message(out,"BN_sub"); if (!test_sub(out)) goto err; - fflush(stdout); + BIO_flush(out); message(out,"BN_lshift1"); if (!test_lshift1(out)) goto err; - fflush(stdout); + BIO_flush(out); message(out,"BN_lshift (fixed)"); if (!test_lshift(out,ctx,BN_bin2bn(lst,sizeof(lst)-1,NULL))) goto err; - fflush(stdout); + BIO_flush(out); message(out,"BN_lshift"); if (!test_lshift(out,ctx,NULL)) goto err; - fflush(stdout); + BIO_flush(out); message(out,"BN_rshift1"); if (!test_rshift1(out)) goto err; - fflush(stdout); + BIO_flush(out); message(out,"BN_rshift"); if (!test_rshift(out,ctx)) goto err; - fflush(stdout); + BIO_flush(out); message(out,"BN_sqr"); if (!test_sqr(out,ctx)) goto err; - fflush(stdout); + BIO_flush(out); message(out,"BN_mul"); if (!test_mul(out)) goto err; - fflush(stdout); + BIO_flush(out); message(out,"BN_div"); if (!test_div(out,ctx)) goto err; - fflush(stdout); + BIO_flush(out); message(out,"BN_div_recp"); if (!test_div_recp(out,ctx)) goto err; - fflush(stdout); + BIO_flush(out); message(out,"BN_mod"); if (!test_mod(out,ctx)) goto err; - fflush(stdout); + BIO_flush(out); message(out,"BN_mod_mul"); if (!test_mod_mul(out,ctx)) goto err; - fflush(stdout); + BIO_flush(out); message(out,"BN_mont"); if (!test_mont(out,ctx)) goto err; - fflush(stdout); + BIO_flush(out); message(out,"BN_mod_exp"); if (!test_mod_exp(out,ctx)) goto err; - fflush(stdout); + BIO_flush(out); message(out,"BN_exp"); if (!test_exp(out,ctx)) goto err; - fflush(stdout); + BIO_flush(out); +#endif + + message(out,"BN_kronecker"); + if (!test_kron(out,ctx)) goto err; + BIO_flush(out); + + message(out,"BN_mod_sqrt"); + if (!test_sqrt(out,ctx)) goto err; + BIO_flush(out); BN_CTX_free(ctx); BIO_free(out); @@ -234,7 +246,9 @@ int main(int argc, char *argv[]) /**/ exit(0); err: - BIO_puts(out,"1\n"); /* make sure bc fails if we are piping to it */ + BIO_puts(out,"1\n"); /* make sure the Perl script fed by bc notices + * the failure, see test_bn in test/Makefile.ssl*/ + BIO_flush(out); ERR_load_crypto_strings(); ERR_print_errors_fp(stderr); exit(1); @@ -505,7 +519,7 @@ int test_mul(BIO *bp) for (i=0; ineg ^ b->neg) && !BN_is_zero(e)) + { + /* If (a*b) % c is negative, c must be added + * in order to obtain the normalized remainder + * (new with OpenSSL 0.9.7, previous versions of + * BN_mod_mul could generate negative results) + */ + BIO_puts(bp," + "); + BN_print(bp,c); + } BIO_puts(bp," - "); } BN_print(bp,e); @@ -770,6 +797,7 @@ int test_mod_mul(BIO *bp, BN_CTX *ctx) if(!BN_is_zero(b)) { fprintf(stderr,"Modulo multiply test failed!\n"); + ERR_print_errors_fp(stderr); return 0; } } @@ -882,6 +910,186 @@ int test_exp(BIO *bp, BN_CTX *ctx) return(1); } +static void genprime_cb(int p, int n, void *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); + (void)n; + (void)arg; + } + +int test_kron(BIO *bp, BN_CTX *ctx) + { + 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; + + /* 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 0 + if (!BN_generate_prime(b, 512, 0, NULL, NULL, genprime_cb, NULL)) goto err; +#else + if (!BN_set_word(b,65537)) goto err; +#endif + putc('\n', stderr); + + for (i = 0; i < num0; i++) + { +#if 0 + if (!BN_rand(a, 512, 0, 0)) goto err; + a->neg = rand_neg(); +#else + if (!BN_bin2bn("\x01\xff\xff\xff\xff", 5, a)) goto err; +#endif + + /* t := (b-1)/2 (note that b is odd) */ + if (!BN_copy(t, b)) goto err; + if (!BN_sub_word(t, 1)) goto err; + if (!BN_rshift1(t, t)) goto err; + /* r := a^t mod b */ +#if 0 + if (!BN_mod_exp(r, a, t, b, ctx)) goto err; +#elif 0 + if (!BN_mod_exp_recp(r, a, t, b, ctx)) goto err; +#else + if (!BN_mod_exp_simple(r, a, t, b, ctx)) goto err; +#endif + + 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_cmp(r, b)) + { + fprintf(stderr, "Legendre symbol computation failed\n"); + goto err; + } + legendre = -1; + } + + kronecker = BN_kronecker(a, b, ctx); + if (kronecker < -1) goto err; + + if (legendre != kronecker) + { + fprintf(stderr, "legendre != kronecker; a = "); + BN_print_fp(stderr, a); + fprintf(stderr, ", a = "); + 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) + { + 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; + + 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(p, 256, 0, a, r, genprime_cb, NULL)) goto err; + putc('\n', stderr); + } + + 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_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_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 (!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;