diff options
Diffstat (limited to 'crypto/bn/bntest.c')
-rw-r--r-- | crypto/bn/bntest.c | 288 |
1 files changed, 220 insertions, 68 deletions
diff --git a/crypto/bn/bntest.c b/crypto/bn/bntest.c index 0a97af69c5..91563dd222 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; @@ -122,9 +124,7 @@ int main(int argc, char *argv[]) results = 0; - RAND_seed(rnd_seed, sizeof rnd_seed); /* or BN_rand may fail, and we don't - * even check its return value - * (which we should) */ + RAND_seed(rnd_seed, sizeof rnd_seed); /* or BN_generate_prime may fail */ argc--; argv++; @@ -228,6 +228,14 @@ int main(int argc, char *argv[]) if (!test_exp(out,ctx)) goto err; BIO_flush(out); + 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); @@ -247,21 +255,17 @@ int test_add(BIO *bp) { BIGNUM a,b,c; int i; - int j; BN_init(&a); BN_init(&b); BN_init(&c); - BN_rand(&a,512,0,0); + BN_bntest_rand(&a,512,0,0); for (i=0; i<num0; i++) { - BN_rand(&b,450+i,0,0); + BN_bntest_rand(&b,450+i,0,0); a.neg=rand_neg(); b.neg=rand_neg(); - if (bp == NULL) - for (j=0; j<10000; j++) - BN_add(&c,&a,&b); BN_add(&c,&a,&b); if (bp != NULL) { @@ -295,7 +299,6 @@ int test_sub(BIO *bp) { BIGNUM a,b,c; int i; - int j; BN_init(&a); BN_init(&b); @@ -305,20 +308,17 @@ int test_sub(BIO *bp) { if (i < num1) { - BN_rand(&a,512,0,0); + BN_bntest_rand(&a,512,0,0); BN_copy(&b,&a); if (BN_set_bit(&a,i)==0) return(0); BN_add_word(&b,i); } else { - BN_rand(&b,400+i-num1,0,0); + BN_bntest_rand(&b,400+i-num1,0,0); a.neg=rand_neg(); b.neg=rand_neg(); } - if (bp == NULL) - for (j=0; j<10000; j++) - BN_sub(&c,&a,&b); BN_sub(&c,&a,&b); if (bp != NULL) { @@ -350,7 +350,6 @@ int test_div(BIO *bp, BN_CTX *ctx) { BIGNUM a,b,c,d,e; int i; - int j; BN_init(&a); BN_init(&b); @@ -362,18 +361,15 @@ int test_div(BIO *bp, BN_CTX *ctx) { if (i < num1) { - BN_rand(&a,400,0,0); + BN_bntest_rand(&a,400,0,0); BN_copy(&b,&a); BN_lshift(&a,&a,i); BN_add_word(&a,i); } else - BN_rand(&b,50+3*(i-num1),0,0); + BN_bntest_rand(&b,50+3*(i-num1),0,0); a.neg=rand_neg(); b.neg=rand_neg(); - if (bp == NULL) - for (j=0; j<100; j++) - BN_div(&d,&c,&a,&b,ctx); BN_div(&d,&c,&a,&b,ctx); if (bp != NULL) { @@ -419,7 +415,6 @@ int test_div_recp(BIO *bp, BN_CTX *ctx) BIGNUM a,b,c,d,e; BN_RECP_CTX recp; int i; - int j; BN_RECP_CTX_init(&recp); BN_init(&a); @@ -432,19 +427,16 @@ int test_div_recp(BIO *bp, BN_CTX *ctx) { if (i < num1) { - BN_rand(&a,400,0,0); + BN_bntest_rand(&a,400,0,0); BN_copy(&b,&a); BN_lshift(&a,&a,i); BN_add_word(&a,i); } else - BN_rand(&b,50+3*(i-num1),0,0); + BN_bntest_rand(&b,50+3*(i-num1),0,0); a.neg=rand_neg(); b.neg=rand_neg(); BN_RECP_CTX_set(&recp,&b,ctx); - if (bp == NULL) - for (j=0; j<100; j++) - BN_div_recp(&d,&c,&a,&recp,ctx); BN_div_recp(&d,&c,&a,&recp,ctx); if (bp != NULL) { @@ -495,7 +487,6 @@ int test_mul(BIO *bp) { BIGNUM a,b,c,d,e; int i; - int j; BN_CTX ctx; BN_CTX_init(&ctx); @@ -509,16 +500,13 @@ int test_mul(BIO *bp) { if (i <= num1) { - BN_rand(&a,100,0,0); - BN_rand(&b,100,0,0); + BN_bntest_rand(&a,100,0,0); + BN_bntest_rand(&b,100,0,0); } else - BN_rand(&b,i-num1,0,0); + BN_bntest_rand(&b,i-num1,0,0); a.neg=rand_neg(); b.neg=rand_neg(); - if (bp == NULL) - for (j=0; j<100; j++) - BN_mul(&c,&a,&b,&ctx); BN_mul(&c,&a,&b,&ctx); if (bp != NULL) { @@ -553,7 +541,6 @@ int test_sqr(BIO *bp, BN_CTX *ctx) { BIGNUM a,c,d,e; int i; - int j; BN_init(&a); BN_init(&c); @@ -562,11 +549,8 @@ int test_sqr(BIO *bp, BN_CTX *ctx) for (i=0; i<num0; i++) { - BN_rand(&a,40+i*10,0,0); + BN_bntest_rand(&a,40+i*10,0,0); a.neg=rand_neg(); - if (bp == NULL) - for (j=0; j<100; j++) - BN_sqr(&c,&a,ctx); BN_sqr(&c,&a,ctx); if (bp != NULL) { @@ -600,7 +584,6 @@ int test_mont(BIO *bp, BN_CTX *ctx) BIGNUM a,b,c,d,A,B; BIGNUM n; int i; - int j; BN_MONT_CTX *mont; BN_init(&a); @@ -613,23 +596,23 @@ int test_mont(BIO *bp, BN_CTX *ctx) mont=BN_MONT_CTX_new(); - BN_rand(&a,100,0,0); /**/ - BN_rand(&b,100,0,0); /**/ + BN_bntest_rand(&a,100,0,0); /**/ + BN_bntest_rand(&b,100,0,0); /**/ for (i=0; i<num2; i++) { int bits = (200*(i+1))/num2; if (bits == 0) continue; - BN_rand(&n,bits,0,1); + BN_bntest_rand(&n,bits,0,1); BN_MONT_CTX_set(mont,&n,ctx); + BN_nnmod(&a,&a,&n,ctx); + BN_nnmod(&b,&b,&n,ctx); + BN_to_montgomery(&A,&a,mont,ctx); BN_to_montgomery(&B,&b,mont,ctx); - if (bp == NULL) - for (j=0; j<100; j++) - BN_mod_mul_montgomery(&c,&A,&B,mont,ctx);/**/ BN_mod_mul_montgomery(&c,&A,&B,mont,ctx);/**/ BN_from_montgomery(&A,&c,mont,ctx);/**/ if (bp != NULL) @@ -675,7 +658,6 @@ int test_mod(BIO *bp, BN_CTX *ctx) { BIGNUM *a,*b,*c,*d,*e; int i; - int j; a=BN_new(); b=BN_new(); @@ -683,15 +665,12 @@ int test_mod(BIO *bp, BN_CTX *ctx) d=BN_new(); e=BN_new(); - BN_rand(a,1024,0,0); /**/ + BN_bntest_rand(a,1024,0,0); /**/ for (i=0; i<num0; i++) { - BN_rand(b,450+i*10,0,0); /**/ + BN_bntest_rand(b,450+i*10,0,0); /**/ a->neg=rand_neg(); b->neg=rand_neg(); - if (bp == NULL) - for (j=0; j<100; j++) - BN_mod(c,a,b,ctx);/**/ BN_mod(c,a,b,ctx);/**/ if (bp != NULL) { @@ -732,17 +711,13 @@ int test_mod_mul(BIO *bp, BN_CTX *ctx) d=BN_new(); e=BN_new(); - BN_rand(c,1024,0,0); /**/ + BN_bntest_rand(c,1024,0,0); /**/ for (i=0; i<num0; i++) { - BN_rand(a,475+i*10,0,0); /**/ - BN_rand(b,425+i*11,0,0); /**/ + BN_bntest_rand(a,475+i*10,0,0); /**/ + BN_bntest_rand(b,425+i*11,0,0); /**/ a->neg=rand_neg(); b->neg=rand_neg(); - /* if (bp == NULL) - for (j=0; j<100; j++) - BN_mod_mul(d,a,b,c,ctx);*/ /**/ - if (!BN_mod_mul(e,a,b,c,ctx)) { unsigned long l; @@ -761,6 +736,16 @@ int test_mod_mul(BIO *bp, BN_CTX *ctx) BN_print(bp,b); BIO_puts(bp," % "); BN_print(bp,c); + if ((a->neg ^ 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); @@ -772,6 +757,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; } } @@ -794,11 +780,11 @@ int test_mod_exp(BIO *bp, BN_CTX *ctx) d=BN_new(); e=BN_new(); - BN_rand(c,30,0,1); /* must be odd for montgomery */ + BN_bntest_rand(c,30,0,1); /* must be odd for montgomery */ for (i=0; i<num2; i++) { - BN_rand(a,20+i*5,0,0); /**/ - BN_rand(b,2+i,0,0); /**/ + BN_bntest_rand(a,20+i*5,0,0); /**/ + BN_bntest_rand(b,2+i,0,0); /**/ if (!BN_mod_exp(d,a,b,c,ctx)) return(00); @@ -848,8 +834,8 @@ int test_exp(BIO *bp, BN_CTX *ctx) for (i=0; i<num2; i++) { - BN_rand(a,20+i*5,0,0); /**/ - BN_rand(b,2+i,0,0); /**/ + BN_bntest_rand(a,20+i*5,0,0); /**/ + BN_bntest_rand(b,2+i,0,0); /**/ if (!BN_exp(d,a,b,ctx)) return(00); @@ -884,6 +870,172 @@ 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 (!BN_generate_prime(b, 512, 0, NULL, NULL, genprime_cb, NULL)) goto err; + 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; + if (!BN_sub_word(t, 1)) goto err; + if (!BN_rshift1(t, t)) goto err; + /* r := a^t mod b */ + if (!BN_mod_exp(r, a, t, b, ctx)) goto err; + + 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, ", 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) + { + 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_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 (!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; @@ -899,7 +1051,7 @@ int test_lshift(BIO *bp,BN_CTX *ctx,BIGNUM *a_) else { a=BN_new(); - BN_rand(a,200,0,0); /**/ + BN_bntest_rand(a,200,0,0); /**/ a->neg=rand_neg(); } for (i=0; i<num0; i++) @@ -951,7 +1103,7 @@ int test_lshift1(BIO *bp) b=BN_new(); c=BN_new(); - BN_rand(a,200,0,0); /**/ + BN_bntest_rand(a,200,0,0); /**/ a->neg=rand_neg(); for (i=0; i<num0; i++) { @@ -995,7 +1147,7 @@ int test_rshift(BIO *bp,BN_CTX *ctx) e=BN_new(); BN_one(c); - BN_rand(a,200,0,0); /**/ + BN_bntest_rand(a,200,0,0); /**/ a->neg=rand_neg(); for (i=0; i<num0; i++) { @@ -1038,7 +1190,7 @@ int test_rshift1(BIO *bp) b=BN_new(); c=BN_new(); - BN_rand(a,200,0,0); /**/ + BN_bntest_rand(a,200,0,0); /**/ a->neg=rand_neg(); for (i=0; i<num0; i++) { |