summaryrefslogtreecommitdiff
path: root/src/lib/libcrypto/bn/bntest.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/lib/libcrypto/bn/bntest.c')
-rw-r--r--src/lib/libcrypto/bn/bntest.c261
1 files changed, 215 insertions, 46 deletions
diff --git a/src/lib/libcrypto/bn/bntest.c b/src/lib/libcrypto/bn/bntest.c
index af0c2629e8..443cf420e5 100644
--- a/src/lib/libcrypto/bn/bntest.c
+++ b/src/lib/libcrypto/bn/bntest.c
@@ -60,7 +60,7 @@
60#include <stdlib.h> 60#include <stdlib.h>
61#include <string.h> 61#include <string.h>
62 62
63#include "openssl/e_os.h" 63#include "e_os.h"
64 64
65#include <openssl/bio.h> 65#include <openssl/bio.h>
66#include <openssl/bn.h> 66#include <openssl/bn.h>
@@ -68,7 +68,7 @@
68#include <openssl/x509.h> 68#include <openssl/x509.h>
69#include <openssl/err.h> 69#include <openssl/err.h>
70 70
71#ifdef WINDOWS 71#ifdef OPENSSL_SYS_WINDOWS
72#include "../bio/bss_file.c" 72#include "../bio/bss_file.c"
73#endif 73#endif
74 74
@@ -91,10 +91,12 @@ int test_mod(BIO *bp,BN_CTX *ctx);
91int test_mod_mul(BIO *bp,BN_CTX *ctx); 91int test_mod_mul(BIO *bp,BN_CTX *ctx);
92int test_mod_exp(BIO *bp,BN_CTX *ctx); 92int test_mod_exp(BIO *bp,BN_CTX *ctx);
93int test_exp(BIO *bp,BN_CTX *ctx); 93int test_exp(BIO *bp,BN_CTX *ctx);
94int test_kron(BIO *bp,BN_CTX *ctx);
95int test_sqrt(BIO *bp,BN_CTX *ctx);
94int rand_neg(void); 96int rand_neg(void);
95static int results=0; 97static int results=0;
96 98
97#ifdef NO_STDIO 99#ifdef OPENSSL_NO_STDIO
98#define APPS_WIN16 100#define APPS_WIN16
99#include "bss_file.c" 101#include "bss_file.c"
100#endif 102#endif
@@ -224,6 +226,14 @@ int main(int argc, char *argv[])
224 if (!test_exp(out,ctx)) goto err; 226 if (!test_exp(out,ctx)) goto err;
225 BIO_flush(out); 227 BIO_flush(out);
226 228
229 message(out,"BN_kronecker");
230 if (!test_kron(out,ctx)) goto err;
231 BIO_flush(out);
232
233 message(out,"BN_mod_sqrt");
234 if (!test_sqrt(out,ctx)) goto err;
235 BIO_flush(out);
236
227 BN_CTX_free(ctx); 237 BN_CTX_free(ctx);
228 BIO_free(out); 238 BIO_free(out);
229 239
@@ -243,7 +253,6 @@ int test_add(BIO *bp)
243 { 253 {
244 BIGNUM a,b,c; 254 BIGNUM a,b,c;
245 int i; 255 int i;
246 int j;
247 256
248 BN_init(&a); 257 BN_init(&a);
249 BN_init(&b); 258 BN_init(&b);
@@ -255,9 +264,6 @@ int test_add(BIO *bp)
255 BN_bntest_rand(&b,450+i,0,0); 264 BN_bntest_rand(&b,450+i,0,0);
256 a.neg=rand_neg(); 265 a.neg=rand_neg();
257 b.neg=rand_neg(); 266 b.neg=rand_neg();
258 if (bp == NULL)
259 for (j=0; j<10000; j++)
260 BN_add(&c,&a,&b);
261 BN_add(&c,&a,&b); 267 BN_add(&c,&a,&b);
262 if (bp != NULL) 268 if (bp != NULL)
263 { 269 {
@@ -291,7 +297,6 @@ int test_sub(BIO *bp)
291 { 297 {
292 BIGNUM a,b,c; 298 BIGNUM a,b,c;
293 int i; 299 int i;
294 int j;
295 300
296 BN_init(&a); 301 BN_init(&a);
297 BN_init(&b); 302 BN_init(&b);
@@ -312,9 +317,6 @@ int test_sub(BIO *bp)
312 a.neg=rand_neg(); 317 a.neg=rand_neg();
313 b.neg=rand_neg(); 318 b.neg=rand_neg();
314 } 319 }
315 if (bp == NULL)
316 for (j=0; j<10000; j++)
317 BN_sub(&c,&a,&b);
318 BN_sub(&c,&a,&b); 320 BN_sub(&c,&a,&b);
319 if (bp != NULL) 321 if (bp != NULL)
320 { 322 {
@@ -346,7 +348,6 @@ int test_div(BIO *bp, BN_CTX *ctx)
346 { 348 {
347 BIGNUM a,b,c,d,e; 349 BIGNUM a,b,c,d,e;
348 int i; 350 int i;
349 int j;
350 351
351 BN_init(&a); 352 BN_init(&a);
352 BN_init(&b); 353 BN_init(&b);
@@ -367,9 +368,6 @@ int test_div(BIO *bp, BN_CTX *ctx)
367 BN_bntest_rand(&b,50+3*(i-num1),0,0); 368 BN_bntest_rand(&b,50+3*(i-num1),0,0);
368 a.neg=rand_neg(); 369 a.neg=rand_neg();
369 b.neg=rand_neg(); 370 b.neg=rand_neg();
370 if (bp == NULL)
371 for (j=0; j<100; j++)
372 BN_div(&d,&c,&a,&b,ctx);
373 BN_div(&d,&c,&a,&b,ctx); 371 BN_div(&d,&c,&a,&b,ctx);
374 if (bp != NULL) 372 if (bp != NULL)
375 { 373 {
@@ -415,7 +413,6 @@ int test_div_recp(BIO *bp, BN_CTX *ctx)
415 BIGNUM a,b,c,d,e; 413 BIGNUM a,b,c,d,e;
416 BN_RECP_CTX recp; 414 BN_RECP_CTX recp;
417 int i; 415 int i;
418 int j;
419 416
420 BN_RECP_CTX_init(&recp); 417 BN_RECP_CTX_init(&recp);
421 BN_init(&a); 418 BN_init(&a);
@@ -438,9 +435,6 @@ int test_div_recp(BIO *bp, BN_CTX *ctx)
438 a.neg=rand_neg(); 435 a.neg=rand_neg();
439 b.neg=rand_neg(); 436 b.neg=rand_neg();
440 BN_RECP_CTX_set(&recp,&b,ctx); 437 BN_RECP_CTX_set(&recp,&b,ctx);
441 if (bp == NULL)
442 for (j=0; j<100; j++)
443 BN_div_recp(&d,&c,&a,&recp,ctx);
444 BN_div_recp(&d,&c,&a,&recp,ctx); 438 BN_div_recp(&d,&c,&a,&recp,ctx);
445 if (bp != NULL) 439 if (bp != NULL)
446 { 440 {
@@ -491,10 +485,11 @@ int test_mul(BIO *bp)
491 { 485 {
492 BIGNUM a,b,c,d,e; 486 BIGNUM a,b,c,d,e;
493 int i; 487 int i;
494 int j; 488 BN_CTX *ctx;
495 BN_CTX ctx;
496 489
497 BN_CTX_init(&ctx); 490 ctx = BN_CTX_new();
491 if (ctx == NULL) exit(1);
492
498 BN_init(&a); 493 BN_init(&a);
499 BN_init(&b); 494 BN_init(&b);
500 BN_init(&c); 495 BN_init(&c);
@@ -512,10 +507,7 @@ int test_mul(BIO *bp)
512 BN_bntest_rand(&b,i-num1,0,0); 507 BN_bntest_rand(&b,i-num1,0,0);
513 a.neg=rand_neg(); 508 a.neg=rand_neg();
514 b.neg=rand_neg(); 509 b.neg=rand_neg();
515 if (bp == NULL) 510 BN_mul(&c,&a,&b,ctx);
516 for (j=0; j<100; j++)
517 BN_mul(&c,&a,&b,&ctx);
518 BN_mul(&c,&a,&b,&ctx);
519 if (bp != NULL) 511 if (bp != NULL)
520 { 512 {
521 if (!results) 513 if (!results)
@@ -528,7 +520,7 @@ int test_mul(BIO *bp)
528 BN_print(bp,&c); 520 BN_print(bp,&c);
529 BIO_puts(bp,"\n"); 521 BIO_puts(bp,"\n");
530 } 522 }
531 BN_div(&d,&e,&c,&a,&ctx); 523 BN_div(&d,&e,&c,&a,ctx);
532 BN_sub(&d,&d,&b); 524 BN_sub(&d,&d,&b);
533 if(!BN_is_zero(&d) || !BN_is_zero(&e)) 525 if(!BN_is_zero(&d) || !BN_is_zero(&e))
534 { 526 {
@@ -541,7 +533,7 @@ int test_mul(BIO *bp)
541 BN_free(&c); 533 BN_free(&c);
542 BN_free(&d); 534 BN_free(&d);
543 BN_free(&e); 535 BN_free(&e);
544 BN_CTX_free(&ctx); 536 BN_CTX_free(ctx);
545 return(1); 537 return(1);
546 } 538 }
547 539
@@ -549,7 +541,6 @@ int test_sqr(BIO *bp, BN_CTX *ctx)
549 { 541 {
550 BIGNUM a,c,d,e; 542 BIGNUM a,c,d,e;
551 int i; 543 int i;
552 int j;
553 544
554 BN_init(&a); 545 BN_init(&a);
555 BN_init(&c); 546 BN_init(&c);
@@ -560,9 +551,6 @@ int test_sqr(BIO *bp, BN_CTX *ctx)
560 { 551 {
561 BN_bntest_rand(&a,40+i*10,0,0); 552 BN_bntest_rand(&a,40+i*10,0,0);
562 a.neg=rand_neg(); 553 a.neg=rand_neg();
563 if (bp == NULL)
564 for (j=0; j<100; j++)
565 BN_sqr(&c,&a,ctx);
566 BN_sqr(&c,&a,ctx); 554 BN_sqr(&c,&a,ctx);
567 if (bp != NULL) 555 if (bp != NULL)
568 { 556 {
@@ -596,7 +584,6 @@ int test_mont(BIO *bp, BN_CTX *ctx)
596 BIGNUM a,b,c,d,A,B; 584 BIGNUM a,b,c,d,A,B;
597 BIGNUM n; 585 BIGNUM n;
598 int i; 586 int i;
599 int j;
600 BN_MONT_CTX *mont; 587 BN_MONT_CTX *mont;
601 588
602 BN_init(&a); 589 BN_init(&a);
@@ -620,12 +607,12 @@ int test_mont(BIO *bp, BN_CTX *ctx)
620 BN_bntest_rand(&n,bits,0,1); 607 BN_bntest_rand(&n,bits,0,1);
621 BN_MONT_CTX_set(mont,&n,ctx); 608 BN_MONT_CTX_set(mont,&n,ctx);
622 609
610 BN_nnmod(&a,&a,&n,ctx);
611 BN_nnmod(&b,&b,&n,ctx);
612
623 BN_to_montgomery(&A,&a,mont,ctx); 613 BN_to_montgomery(&A,&a,mont,ctx);
624 BN_to_montgomery(&B,&b,mont,ctx); 614 BN_to_montgomery(&B,&b,mont,ctx);
625 615
626 if (bp == NULL)
627 for (j=0; j<100; j++)
628 BN_mod_mul_montgomery(&c,&A,&B,mont,ctx);/**/
629 BN_mod_mul_montgomery(&c,&A,&B,mont,ctx);/**/ 616 BN_mod_mul_montgomery(&c,&A,&B,mont,ctx);/**/
630 BN_from_montgomery(&A,&c,mont,ctx);/**/ 617 BN_from_montgomery(&A,&c,mont,ctx);/**/
631 if (bp != NULL) 618 if (bp != NULL)
@@ -671,7 +658,6 @@ int test_mod(BIO *bp, BN_CTX *ctx)
671 { 658 {
672 BIGNUM *a,*b,*c,*d,*e; 659 BIGNUM *a,*b,*c,*d,*e;
673 int i; 660 int i;
674 int j;
675 661
676 a=BN_new(); 662 a=BN_new();
677 b=BN_new(); 663 b=BN_new();
@@ -685,9 +671,6 @@ int test_mod(BIO *bp, BN_CTX *ctx)
685 BN_bntest_rand(b,450+i*10,0,0); /**/ 671 BN_bntest_rand(b,450+i*10,0,0); /**/
686 a->neg=rand_neg(); 672 a->neg=rand_neg();
687 b->neg=rand_neg(); 673 b->neg=rand_neg();
688 if (bp == NULL)
689 for (j=0; j<100; j++)
690 BN_mod(c,a,b,ctx);/**/
691 BN_mod(c,a,b,ctx);/**/ 674 BN_mod(c,a,b,ctx);/**/
692 if (bp != NULL) 675 if (bp != NULL)
693 { 676 {
@@ -720,7 +703,7 @@ int test_mod(BIO *bp, BN_CTX *ctx)
720int test_mod_mul(BIO *bp, BN_CTX *ctx) 703int test_mod_mul(BIO *bp, BN_CTX *ctx)
721 { 704 {
722 BIGNUM *a,*b,*c,*d,*e; 705 BIGNUM *a,*b,*c,*d,*e;
723 int i; 706 int i,j;
724 707
725 a=BN_new(); 708 a=BN_new();
726 b=BN_new(); 709 b=BN_new();
@@ -728,6 +711,7 @@ int test_mod_mul(BIO *bp, BN_CTX *ctx)
728 d=BN_new(); 711 d=BN_new();
729 e=BN_new(); 712 e=BN_new();
730 713
714 for (j=0; j<3; j++) {
731 BN_bntest_rand(c,1024,0,0); /**/ 715 BN_bntest_rand(c,1024,0,0); /**/
732 for (i=0; i<num0; i++) 716 for (i=0; i<num0; i++)
733 { 717 {
@@ -735,10 +719,6 @@ int test_mod_mul(BIO *bp, BN_CTX *ctx)
735 BN_bntest_rand(b,425+i*11,0,0); /**/ 719 BN_bntest_rand(b,425+i*11,0,0); /**/
736 a->neg=rand_neg(); 720 a->neg=rand_neg();
737 b->neg=rand_neg(); 721 b->neg=rand_neg();
738 /* if (bp == NULL)
739 for (j=0; j<100; j++)
740 BN_mod_mul(d,a,b,c,ctx);*/ /**/
741
742 if (!BN_mod_mul(e,a,b,c,ctx)) 722 if (!BN_mod_mul(e,a,b,c,ctx))
743 { 723 {
744 unsigned long l; 724 unsigned long l;
@@ -757,6 +737,16 @@ int test_mod_mul(BIO *bp, BN_CTX *ctx)
757 BN_print(bp,b); 737 BN_print(bp,b);
758 BIO_puts(bp," % "); 738 BIO_puts(bp," % ");
759 BN_print(bp,c); 739 BN_print(bp,c);
740 if ((a->neg ^ b->neg) && !BN_is_zero(e))
741 {
742 /* If (a*b) % c is negative, c must be added
743 * in order to obtain the normalized remainder
744 * (new with OpenSSL 0.9.7, previous versions of
745 * BN_mod_mul could generate negative results)
746 */
747 BIO_puts(bp," + ");
748 BN_print(bp,c);
749 }
760 BIO_puts(bp," - "); 750 BIO_puts(bp," - ");
761 } 751 }
762 BN_print(bp,e); 752 BN_print(bp,e);
@@ -768,9 +758,11 @@ int test_mod_mul(BIO *bp, BN_CTX *ctx)
768 if(!BN_is_zero(b)) 758 if(!BN_is_zero(b))
769 { 759 {
770 fprintf(stderr,"Modulo multiply test failed!\n"); 760 fprintf(stderr,"Modulo multiply test failed!\n");
761 ERR_print_errors_fp(stderr);
771 return 0; 762 return 0;
772 } 763 }
773 } 764 }
765 }
774 BN_free(a); 766 BN_free(a);
775 BN_free(b); 767 BN_free(b);
776 BN_free(c); 768 BN_free(c);
@@ -880,6 +872,183 @@ int test_exp(BIO *bp, BN_CTX *ctx)
880 return(1); 872 return(1);
881 } 873 }
882 874
875static void genprime_cb(int p, int n, void *arg)
876 {
877 char c='*';
878
879 if (p == 0) c='.';
880 if (p == 1) c='+';
881 if (p == 2) c='*';
882 if (p == 3) c='\n';
883 putc(c, stderr);
884 fflush(stderr);
885 (void)n;
886 (void)arg;
887 }
888
889int test_kron(BIO *bp, BN_CTX *ctx)
890 {
891 BIGNUM *a,*b,*r,*t;
892 int i;
893 int legendre, kronecker;
894 int ret = 0;
895
896 a = BN_new();
897 b = BN_new();
898 r = BN_new();
899 t = BN_new();
900 if (a == NULL || b == NULL || r == NULL || t == NULL) goto err;
901
902 /* We test BN_kronecker(a, b, ctx) just for b odd (Jacobi symbol).
903 * In this case we know that if b is prime, then BN_kronecker(a, b, ctx)
904 * is congruent to $a^{(b-1)/2}$, modulo $b$ (Legendre symbol).
905 * So we generate a random prime b and compare these values
906 * for a number of random a's. (That is, we run the Solovay-Strassen
907 * primality test to confirm that b is prime, except that we
908 * don't want to test whether b is prime but whether BN_kronecker
909 * works.) */
910
911 if (!BN_generate_prime(b, 512, 0, NULL, NULL, genprime_cb, NULL)) goto err;
912 b->neg = rand_neg();
913 putc('\n', stderr);
914
915 for (i = 0; i < num0; i++)
916 {
917 if (!BN_bntest_rand(a, 512, 0, 0)) goto err;
918 a->neg = rand_neg();
919
920 /* t := (|b|-1)/2 (note that b is odd) */
921 if (!BN_copy(t, b)) goto err;
922 t->neg = 0;
923 if (!BN_sub_word(t, 1)) goto err;
924 if (!BN_rshift1(t, t)) goto err;
925 /* r := a^t mod b */
926 b->neg=0;
927
928 if (!BN_mod_exp_recp(r, a, t, b, ctx)) goto err; /* XXX should be BN_mod_exp_recp, but ..._recp triggers a bug that must be fixed */
929 b->neg=1;
930
931 if (BN_is_word(r, 1))
932 legendre = 1;
933 else if (BN_is_zero(r))
934 legendre = 0;
935 else
936 {
937 if (!BN_add_word(r, 1)) goto err;
938 if (0 != BN_ucmp(r, b))
939 {
940 fprintf(stderr, "Legendre symbol computation failed\n");
941 goto err;
942 }
943 legendre = -1;
944 }
945
946 kronecker = BN_kronecker(a, b, ctx);
947 if (kronecker < -1) goto err;
948 /* we actually need BN_kronecker(a, |b|) */
949 if (a->neg && b->neg)
950 kronecker = -kronecker;
951
952 if (legendre != kronecker)
953 {
954 fprintf(stderr, "legendre != kronecker; a = ");
955 BN_print_fp(stderr, a);
956 fprintf(stderr, ", b = ");
957 BN_print_fp(stderr, b);
958 fprintf(stderr, "\n");
959 goto err;
960 }
961
962 putc('.', stderr);
963 fflush(stderr);
964 }
965
966 putc('\n', stderr);
967 fflush(stderr);
968 ret = 1;
969 err:
970 if (a != NULL) BN_free(a);
971 if (b != NULL) BN_free(b);
972 if (r != NULL) BN_free(r);
973 if (t != NULL) BN_free(t);
974 return ret;
975 }
976
977int test_sqrt(BIO *bp, BN_CTX *ctx)
978 {
979 BIGNUM *a,*p,*r;
980 int i, j;
981 int ret = 0;
982
983 a = BN_new();
984 p = BN_new();
985 r = BN_new();
986 if (a == NULL || p == NULL || r == NULL) goto err;
987
988 for (i = 0; i < 16; i++)
989 {
990 if (i < 8)
991 {
992 unsigned primes[8] = { 2, 3, 5, 7, 11, 13, 17, 19 };
993
994 if (!BN_set_word(p, primes[i])) goto err;
995 }
996 else
997 {
998 if (!BN_set_word(a, 32)) goto err;
999 if (!BN_set_word(r, 2*i + 1)) goto err;
1000
1001 if (!BN_generate_prime(p, 256, 0, a, r, genprime_cb, NULL)) goto err;
1002 putc('\n', stderr);
1003 }
1004 p->neg = rand_neg();
1005
1006 for (j = 0; j < num2; j++)
1007 {
1008 /* construct 'a' such that it is a square modulo p,
1009 * but in general not a proper square and not reduced modulo p */
1010 if (!BN_bntest_rand(r, 256, 0, 3)) goto err;
1011 if (!BN_nnmod(r, r, p, ctx)) goto err;
1012 if (!BN_mod_sqr(r, r, p, ctx)) goto err;
1013 if (!BN_bntest_rand(a, 256, 0, 3)) goto err;
1014 if (!BN_nnmod(a, a, p, ctx)) goto err;
1015 if (!BN_mod_sqr(a, a, p, ctx)) goto err;
1016 if (!BN_mul(a, a, r, ctx)) goto err;
1017 if (rand_neg())
1018 if (!BN_sub(a, a, p)) goto err;
1019
1020 if (!BN_mod_sqrt(r, a, p, ctx)) goto err;
1021 if (!BN_mod_sqr(r, r, p, ctx)) goto err;
1022
1023 if (!BN_nnmod(a, a, p, ctx)) goto err;
1024
1025 if (BN_cmp(a, r) != 0)
1026 {
1027 fprintf(stderr, "BN_mod_sqrt failed: a = ");
1028 BN_print_fp(stderr, a);
1029 fprintf(stderr, ", r = ");
1030 BN_print_fp(stderr, r);
1031 fprintf(stderr, ", p = ");
1032 BN_print_fp(stderr, p);
1033 fprintf(stderr, "\n");
1034 goto err;
1035 }
1036
1037 putc('.', stderr);
1038 fflush(stderr);
1039 }
1040
1041 putc('\n', stderr);
1042 fflush(stderr);
1043 }
1044 ret = 1;
1045 err:
1046 if (a != NULL) BN_free(a);
1047 if (p != NULL) BN_free(p);
1048 if (r != NULL) BN_free(r);
1049 return ret;
1050 }
1051
883int test_lshift(BIO *bp,BN_CTX *ctx,BIGNUM *a_) 1052int test_lshift(BIO *bp,BN_CTX *ctx,BIGNUM *a_)
884 { 1053 {
885 BIGNUM *a,*b,*c,*d; 1054 BIGNUM *a,*b,*c,*d;
@@ -1052,7 +1221,7 @@ int test_rshift1(BIO *bp)
1052 } 1221 }
1053 BN_sub(c,a,b); 1222 BN_sub(c,a,b);
1054 BN_sub(c,c,b); 1223 BN_sub(c,c,b);
1055 if(!BN_is_zero(c) && !BN_is_one(c)) 1224 if(!BN_is_zero(c) && !BN_abs_is_word(c, 1))
1056 { 1225 {
1057 fprintf(stderr,"Right shift one test failed!\n"); 1226 fprintf(stderr,"Right shift one test failed!\n");
1058 return 0; 1227 return 0;
generated by cgit v1.2.3-55-g6feb (git 2.39.1) at 2025-04-26 14:35:23 +0000