1 /* crypto/bn/bntest.c */
2 /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
3 * All rights reserved.
4 *
5 * This package is an SSL implementation written
6 * by Eric Young (eay@cryptsoft.com).
7 * The implementation was written so as to conform with Netscapes SSL.
8 *
9 * This library is free for commercial and non-commercial use as long as
10 * the following conditions are aheared to. The following conditions
11 * apply to all code found in this distribution, be it the RC4, RSA,
12 * lhash, DES, etc., code; not just the SSL code. The SSL documentation
13 * included with this distribution is covered by the same copyright terms
14 * except that the holder is Tim Hudson (tjh@cryptsoft.com).
15 *
16 * Copyright remains Eric Young's, and as such any Copyright notices in
17 * the code are not to be removed.
18 * If this package is used in a product, Eric Young should be given attribution
19 * as the author of the parts of the library used.
20 * This can be in the form of a textual message at program startup or
21 * in documentation (online or textual) provided with the package.
22 *
23 * Redistribution and use in source and binary forms, with or without
24 * modification, are permitted provided that the following conditions
25 * are met:
26 * 1. Redistributions of source code must retain the copyright
27 * notice, this list of conditions and the following disclaimer.
28 * 2. Redistributions in binary form must reproduce the above copyright
29 * notice, this list of conditions and the following disclaimer in the
30 * documentation and/or other materials provided with the distribution.
31 * 3. All advertising materials mentioning features or use of this software
32 * must display the following acknowledgement:
33 * "This product includes cryptographic software written by
34 * Eric Young (eay@cryptsoft.com)"
35 * The word 'cryptographic' can be left out if the rouines from the library
36 * being used are not cryptographic related :-).
37 * 4. If you include any Windows specific code (or a derivative thereof) from
38 * the apps directory (application code) you must include an acknowledgement:
39 * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)"
40 *
41 * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND
42 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
43 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
44 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
45 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
46 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
47 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
48 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
49 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
50 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
51 * SUCH DAMAGE.
52 *
53 * The licence and distribution terms for any publically available version or
54 * derivative of this code cannot be changed. i.e. this code cannot simply be
55 * copied and put under another distribution licence
56 * [including the GNU Public Licence.]
57 */
58
59 #include <stdio.h>
60 #include <stdlib.h>
61 #include <string.h>
62
63 #include "e_os.h"
64
65 #include <openssl/bio.h>
66 #include <openssl/bn.h>
67 #include <openssl/rand.h>
68 #include <openssl/x509.h>
69 #include <openssl/err.h>
70
71 const int num0 = 100; /* number of tests */
72 const int num1 = 50; /* additional tests for some functions */
73 const int num2 = 5; /* number of tests for slow functions */
74
75 int test_add(BIO *bp);
76 int test_sub(BIO *bp);
77 int test_lshift1(BIO *bp);
78 int test_lshift(BIO *bp,BN_CTX *ctx,BIGNUM *a_);
79 int test_rshift1(BIO *bp);
80 int test_rshift(BIO *bp,BN_CTX *ctx);
81 int test_div(BIO *bp,BN_CTX *ctx);
82 int test_div_recp(BIO *bp,BN_CTX *ctx);
83 int test_mul(BIO *bp);
84 int test_sqr(BIO *bp,BN_CTX *ctx);
85 int test_mont(BIO *bp,BN_CTX *ctx);
86 int test_mod(BIO *bp,BN_CTX *ctx);
87 int test_mod_mul(BIO *bp,BN_CTX *ctx);
88 int test_mod_exp(BIO *bp,BN_CTX *ctx);
89 int test_mod_exp_mont_consttime(BIO *bp,BN_CTX *ctx);
90 int test_exp(BIO *bp,BN_CTX *ctx);
91 int test_kron(BIO *bp,BN_CTX *ctx);
92 int test_sqrt(BIO *bp,BN_CTX *ctx);
93 int rand_neg(void);
94 static int results=0;
95
96 static unsigned char lst[]="\xC6\x4F\x43\x04\x2A\xEA\xCA\x6E\x58\x36\x80\x5B\xE8\xC9"
97 "\x9B\x04\x5D\x48\x36\xC2\xFD\x16\xC9\x64\xF0";
98
99 static const char rnd_seed[] = "string to make the random number generator think it has entropy";
100
message(BIO * out,char * m)101 static void message(BIO *out, char *m)
102 {
103 fprintf(stderr, "test %s\n", m);
104 BIO_puts(out, "print \"test ");
105 BIO_puts(out, m);
106 BIO_puts(out, "\\n\"\n");
107 }
108
main(int argc,char * argv[])109 int main(int argc, char *argv[])
110 {
111 BN_CTX *ctx;
112 BIO *out;
113 char *outfile=NULL;
114
115 results = 0;
116
117 RAND_seed(rnd_seed, sizeof rnd_seed); /* or BN_generate_prime may fail */
118
119 argc--;
120 argv++;
121 while (argc >= 1)
122 {
123 if (strcmp(*argv,"-results") == 0)
124 results=1;
125 else if (strcmp(*argv,"-out") == 0)
126 {
127 if (--argc < 1) break;
128 outfile= *(++argv);
129 }
130 argc--;
131 argv++;
132 }
133
134
135 ctx=BN_CTX_new();
136 if (ctx == NULL) EXIT(1);
137
138 out=BIO_new(BIO_s_file());
139 if (out == NULL) EXIT(1);
140 if (outfile == NULL)
141 {
142 BIO_set_fp(out,stdout,BIO_NOCLOSE);
143 }
144 else
145 {
146 if (!BIO_write_filename(out,outfile))
147 {
148 perror(outfile);
149 EXIT(1);
150 }
151 }
152
153 if (!results)
154 BIO_puts(out,"obase=16\nibase=16\n");
155
156 message(out,"BN_add");
157 if (!test_add(out)) goto err;
158 BIO_flush(out);
159
160 message(out,"BN_sub");
161 if (!test_sub(out)) goto err;
162 BIO_flush(out);
163
164 message(out,"BN_lshift1");
165 if (!test_lshift1(out)) goto err;
166 BIO_flush(out);
167
168 message(out,"BN_lshift (fixed)");
169 if (!test_lshift(out,ctx,BN_bin2bn(lst,sizeof(lst)-1,NULL)))
170 goto err;
171 BIO_flush(out);
172
173 message(out,"BN_lshift");
174 if (!test_lshift(out,ctx,NULL)) goto err;
175 BIO_flush(out);
176
177 message(out,"BN_rshift1");
178 if (!test_rshift1(out)) goto err;
179 BIO_flush(out);
180
181 message(out,"BN_rshift");
182 if (!test_rshift(out,ctx)) goto err;
183 BIO_flush(out);
184
185 message(out,"BN_sqr");
186 if (!test_sqr(out,ctx)) goto err;
187 BIO_flush(out);
188
189 message(out,"BN_mul");
190 if (!test_mul(out)) goto err;
191 BIO_flush(out);
192
193 message(out,"BN_div");
194 if (!test_div(out,ctx)) goto err;
195 BIO_flush(out);
196
197 message(out,"BN_div_recp");
198 if (!test_div_recp(out,ctx)) goto err;
199 BIO_flush(out);
200
201 message(out,"BN_mod");
202 if (!test_mod(out,ctx)) goto err;
203 BIO_flush(out);
204
205 message(out,"BN_mod_mul");
206 if (!test_mod_mul(out,ctx)) goto err;
207 BIO_flush(out);
208
209 message(out,"BN_mont");
210 if (!test_mont(out,ctx)) goto err;
211 BIO_flush(out);
212
213 message(out,"BN_mod_exp");
214 if (!test_mod_exp(out,ctx)) goto err;
215 BIO_flush(out);
216
217 message(out,"BN_mod_exp_mont_consttime");
218 if (!test_mod_exp_mont_consttime(out,ctx)) goto err;
219 BIO_flush(out);
220
221 message(out,"BN_exp");
222 if (!test_exp(out,ctx)) goto err;
223 BIO_flush(out);
224
225 message(out,"BN_kronecker");
226 if (!test_kron(out,ctx)) goto err;
227 BIO_flush(out);
228
229 message(out,"BN_mod_sqrt");
230 if (!test_sqrt(out,ctx)) goto err;
231 BIO_flush(out);
232
233 BN_CTX_free(ctx);
234 BIO_free(out);
235
236 /**/
237 EXIT(0);
238 err:
239 BIO_puts(out,"1\n"); /* make sure the Perl script fed by bc notices
240 * the failure, see test_bn in test/Makefile */
241 BIO_flush(out);
242 ERR_load_crypto_strings();
243 ERR_print_errors_fp(stderr);
244 EXIT(1);
245 return(1);
246 }
247
test_add(BIO * bp)248 int test_add(BIO *bp)
249 {
250 BIGNUM a,b,c;
251 int i;
252
253 BN_init(&a);
254 BN_init(&b);
255 BN_init(&c);
256
257 BN_bntest_rand(&a,512,0,0);
258 for (i=0; i<num0; i++)
259 {
260 BN_bntest_rand(&b,450+i,0,0);
261 a.neg=rand_neg();
262 b.neg=rand_neg();
263 BN_add(&c,&a,&b);
264 if (bp != NULL)
265 {
266 if (!results)
267 {
268 BN_print(bp,&a);
269 BIO_puts(bp," + ");
270 BN_print(bp,&b);
271 BIO_puts(bp," - ");
272 }
273 BN_print(bp,&c);
274 BIO_puts(bp,"\n");
275 }
276 a.neg=!a.neg;
277 b.neg=!b.neg;
278 BN_add(&c,&c,&b);
279 BN_add(&c,&c,&a);
280 if(!BN_is_zero(&c))
281 {
282 fprintf(stderr,"Add test failed!\n");
283 return 0;
284 }
285 }
286 BN_free(&a);
287 BN_free(&b);
288 BN_free(&c);
289 return(1);
290 }
291
test_sub(BIO * bp)292 int test_sub(BIO *bp)
293 {
294 BIGNUM a,b,c;
295 int i;
296
297 BN_init(&a);
298 BN_init(&b);
299 BN_init(&c);
300
301 for (i=0; i<num0+num1; i++)
302 {
303 if (i < num1)
304 {
305 BN_bntest_rand(&a,512,0,0);
306 BN_copy(&b,&a);
307 if (BN_set_bit(&a,i)==0) return(0);
308 BN_add_word(&b,i);
309 }
310 else
311 {
312 BN_bntest_rand(&b,400+i-num1,0,0);
313 a.neg=rand_neg();
314 b.neg=rand_neg();
315 }
316 BN_sub(&c,&a,&b);
317 if (bp != NULL)
318 {
319 if (!results)
320 {
321 BN_print(bp,&a);
322 BIO_puts(bp," - ");
323 BN_print(bp,&b);
324 BIO_puts(bp," - ");
325 }
326 BN_print(bp,&c);
327 BIO_puts(bp,"\n");
328 }
329 BN_add(&c,&c,&b);
330 BN_sub(&c,&c,&a);
331 if(!BN_is_zero(&c))
332 {
333 fprintf(stderr,"Subtract test failed!\n");
334 return 0;
335 }
336 }
337 BN_free(&a);
338 BN_free(&b);
339 BN_free(&c);
340 return(1);
341 }
342
test_div(BIO * bp,BN_CTX * ctx)343 int test_div(BIO *bp, BN_CTX *ctx)
344 {
345 BIGNUM a,b,c,d,e;
346 int i;
347
348 BN_init(&a);
349 BN_init(&b);
350 BN_init(&c);
351 BN_init(&d);
352 BN_init(&e);
353
354 for (i=0; i<num0+num1; i++)
355 {
356 if (i < num1)
357 {
358 BN_bntest_rand(&a,400,0,0);
359 BN_copy(&b,&a);
360 BN_lshift(&a,&a,i);
361 BN_add_word(&a,i);
362 }
363 else
364 BN_bntest_rand(&b,50+3*(i-num1),0,0);
365 a.neg=rand_neg();
366 b.neg=rand_neg();
367 BN_div(&d,&c,&a,&b,ctx);
368 if (bp != NULL)
369 {
370 if (!results)
371 {
372 BN_print(bp,&a);
373 BIO_puts(bp," / ");
374 BN_print(bp,&b);
375 BIO_puts(bp," - ");
376 }
377 BN_print(bp,&d);
378 BIO_puts(bp,"\n");
379
380 if (!results)
381 {
382 BN_print(bp,&a);
383 BIO_puts(bp," % ");
384 BN_print(bp,&b);
385 BIO_puts(bp," - ");
386 }
387 BN_print(bp,&c);
388 BIO_puts(bp,"\n");
389 }
390 BN_mul(&e,&d,&b,ctx);
391 BN_add(&d,&e,&c);
392 BN_sub(&d,&d,&a);
393 if(!BN_is_zero(&d))
394 {
395 fprintf(stderr,"Division test failed!\n");
396 return 0;
397 }
398 }
399 BN_free(&a);
400 BN_free(&b);
401 BN_free(&c);
402 BN_free(&d);
403 BN_free(&e);
404 return(1);
405 }
406
test_div_recp(BIO * bp,BN_CTX * ctx)407 int test_div_recp(BIO *bp, BN_CTX *ctx)
408 {
409 BIGNUM a,b,c,d,e;
410 BN_RECP_CTX recp;
411 int i;
412
413 BN_RECP_CTX_init(&recp);
414 BN_init(&a);
415 BN_init(&b);
416 BN_init(&c);
417 BN_init(&d);
418 BN_init(&e);
419
420 for (i=0; i<num0+num1; i++)
421 {
422 if (i < num1)
423 {
424 BN_bntest_rand(&a,400,0,0);
425 BN_copy(&b,&a);
426 BN_lshift(&a,&a,i);
427 BN_add_word(&a,i);
428 }
429 else
430 BN_bntest_rand(&b,50+3*(i-num1),0,0);
431 a.neg=rand_neg();
432 b.neg=rand_neg();
433 BN_RECP_CTX_set(&recp,&b,ctx);
434 BN_div_recp(&d,&c,&a,&recp,ctx);
435 if (bp != NULL)
436 {
437 if (!results)
438 {
439 BN_print(bp,&a);
440 BIO_puts(bp," / ");
441 BN_print(bp,&b);
442 BIO_puts(bp," - ");
443 }
444 BN_print(bp,&d);
445 BIO_puts(bp,"\n");
446
447 if (!results)
448 {
449 BN_print(bp,&a);
450 BIO_puts(bp," % ");
451 BN_print(bp,&b);
452 BIO_puts(bp," - ");
453 }
454 BN_print(bp,&c);
455 BIO_puts(bp,"\n");
456 }
457 BN_mul(&e,&d,&b,ctx);
458 BN_add(&d,&e,&c);
459 BN_sub(&d,&d,&a);
460 if(!BN_is_zero(&d))
461 {
462 fprintf(stderr,"Reciprocal division test failed!\n");
463 fprintf(stderr,"a=");
464 BN_print_fp(stderr,&a);
465 fprintf(stderr,"\nb=");
466 BN_print_fp(stderr,&b);
467 fprintf(stderr,"\n");
468 return 0;
469 }
470 }
471 BN_free(&a);
472 BN_free(&b);
473 BN_free(&c);
474 BN_free(&d);
475 BN_free(&e);
476 BN_RECP_CTX_free(&recp);
477 return(1);
478 }
479
test_mul(BIO * bp)480 int test_mul(BIO *bp)
481 {
482 BIGNUM a,b,c,d,e;
483 int i;
484 BN_CTX *ctx;
485
486 ctx = BN_CTX_new();
487 if (ctx == NULL) EXIT(1);
488
489 BN_init(&a);
490 BN_init(&b);
491 BN_init(&c);
492 BN_init(&d);
493 BN_init(&e);
494
495 for (i=0; i<num0+num1; i++)
496 {
497 if (i <= num1)
498 {
499 BN_bntest_rand(&a,100,0,0);
500 BN_bntest_rand(&b,100,0,0);
501 }
502 else
503 BN_bntest_rand(&b,i-num1,0,0);
504 a.neg=rand_neg();
505 b.neg=rand_neg();
506 BN_mul(&c,&a,&b,ctx);
507 if (bp != NULL)
508 {
509 if (!results)
510 {
511 BN_print(bp,&a);
512 BIO_puts(bp," * ");
513 BN_print(bp,&b);
514 BIO_puts(bp," - ");
515 }
516 BN_print(bp,&c);
517 BIO_puts(bp,"\n");
518 }
519 BN_div(&d,&e,&c,&a,ctx);
520 BN_sub(&d,&d,&b);
521 if(!BN_is_zero(&d) || !BN_is_zero(&e))
522 {
523 fprintf(stderr,"Multiplication test failed!\n");
524 return 0;
525 }
526 }
527 BN_free(&a);
528 BN_free(&b);
529 BN_free(&c);
530 BN_free(&d);
531 BN_free(&e);
532 BN_CTX_free(ctx);
533 return(1);
534 }
535
test_sqr(BIO * bp,BN_CTX * ctx)536 int test_sqr(BIO *bp, BN_CTX *ctx)
537 {
538 BIGNUM a,c,d,e;
539 int i;
540
541 BN_init(&a);
542 BN_init(&c);
543 BN_init(&d);
544 BN_init(&e);
545
546 for (i=0; i<num0; i++)
547 {
548 BN_bntest_rand(&a,40+i*10,0,0);
549 a.neg=rand_neg();
550 BN_sqr(&c,&a,ctx);
551 if (bp != NULL)
552 {
553 if (!results)
554 {
555 BN_print(bp,&a);
556 BIO_puts(bp," * ");
557 BN_print(bp,&a);
558 BIO_puts(bp," - ");
559 }
560 BN_print(bp,&c);
561 BIO_puts(bp,"\n");
562 }
563 BN_div(&d,&e,&c,&a,ctx);
564 BN_sub(&d,&d,&a);
565 if(!BN_is_zero(&d) || !BN_is_zero(&e))
566 {
567 fprintf(stderr,"Square test failed!\n");
568 return 0;
569 }
570 }
571 BN_free(&a);
572 BN_free(&c);
573 BN_free(&d);
574 BN_free(&e);
575 return(1);
576 }
577
test_mont(BIO * bp,BN_CTX * ctx)578 int test_mont(BIO *bp, BN_CTX *ctx)
579 {
580 BIGNUM a,b,c,d,A,B;
581 BIGNUM n;
582 int i;
583 BN_MONT_CTX *mont;
584
585 BN_init(&a);
586 BN_init(&b);
587 BN_init(&c);
588 BN_init(&d);
589 BN_init(&A);
590 BN_init(&B);
591 BN_init(&n);
592
593 mont=BN_MONT_CTX_new();
594
595 BN_bntest_rand(&a,100,0,0); /**/
596 BN_bntest_rand(&b,100,0,0); /**/
597 for (i=0; i<num2; i++)
598 {
599 int bits = (200*(i+1))/num2;
600
601 if (bits == 0)
602 continue;
603 BN_bntest_rand(&n,bits,0,1);
604 BN_MONT_CTX_set(mont,&n,ctx);
605
606 BN_nnmod(&a,&a,&n,ctx);
607 BN_nnmod(&b,&b,&n,ctx);
608
609 BN_to_montgomery(&A,&a,mont,ctx);
610 BN_to_montgomery(&B,&b,mont,ctx);
611
612 BN_mod_mul_montgomery(&c,&A,&B,mont,ctx);/**/
613 BN_from_montgomery(&A,&c,mont,ctx);/**/
614 if (bp != NULL)
615 {
616 if (!results)
617 {
618 #ifdef undef
619 fprintf(stderr,"%d * %d %% %d\n",
620 BN_num_bits(&a),
621 BN_num_bits(&b),
622 BN_num_bits(mont->N));
623 #endif
624 BN_print(bp,&a);
625 BIO_puts(bp," * ");
626 BN_print(bp,&b);
627 BIO_puts(bp," % ");
628 BN_print(bp,&(mont->N));
629 BIO_puts(bp," - ");
630 }
631 BN_print(bp,&A);
632 BIO_puts(bp,"\n");
633 }
634 BN_mod_mul(&d,&a,&b,&n,ctx);
635 BN_sub(&d,&d,&A);
636 if(!BN_is_zero(&d))
637 {
638 fprintf(stderr,"Montgomery multiplication test failed!\n");
639 return 0;
640 }
641 }
642 BN_MONT_CTX_free(mont);
643 BN_free(&a);
644 BN_free(&b);
645 BN_free(&c);
646 BN_free(&d);
647 BN_free(&A);
648 BN_free(&B);
649 BN_free(&n);
650 return(1);
651 }
652
test_mod(BIO * bp,BN_CTX * ctx)653 int test_mod(BIO *bp, BN_CTX *ctx)
654 {
655 BIGNUM *a,*b,*c,*d,*e;
656 int i;
657
658 a=BN_new();
659 b=BN_new();
660 c=BN_new();
661 d=BN_new();
662 e=BN_new();
663
664 BN_bntest_rand(a,1024,0,0); /**/
665 for (i=0; i<num0; i++)
666 {
667 BN_bntest_rand(b,450+i*10,0,0); /**/
668 a->neg=rand_neg();
669 b->neg=rand_neg();
670 BN_mod(c,a,b,ctx);/**/
671 if (bp != NULL)
672 {
673 if (!results)
674 {
675 BN_print(bp,a);
676 BIO_puts(bp," % ");
677 BN_print(bp,b);
678 BIO_puts(bp," - ");
679 }
680 BN_print(bp,c);
681 BIO_puts(bp,"\n");
682 }
683 BN_div(d,e,a,b,ctx);
684 BN_sub(e,e,c);
685 if(!BN_is_zero(e))
686 {
687 fprintf(stderr,"Modulo test failed!\n");
688 return 0;
689 }
690 }
691 BN_free(a);
692 BN_free(b);
693 BN_free(c);
694 BN_free(d);
695 BN_free(e);
696 return(1);
697 }
698
test_mod_mul(BIO * bp,BN_CTX * ctx)699 int test_mod_mul(BIO *bp, BN_CTX *ctx)
700 {
701 BIGNUM *a,*b,*c,*d,*e;
702 int i,j;
703
704 a=BN_new();
705 b=BN_new();
706 c=BN_new();
707 d=BN_new();
708 e=BN_new();
709
710 for (j=0; j<3; j++) {
711 BN_bntest_rand(c,1024,0,0); /**/
712 for (i=0; i<num0; i++)
713 {
714 BN_bntest_rand(a,475+i*10,0,0); /**/
715 BN_bntest_rand(b,425+i*11,0,0); /**/
716 a->neg=rand_neg();
717 b->neg=rand_neg();
718 if (!BN_mod_mul(e,a,b,c,ctx))
719 {
720 unsigned long l;
721
722 while ((l=ERR_get_error()))
723 fprintf(stderr,"ERROR:%s\n",
724 ERR_error_string(l,NULL));
725 EXIT(1);
726 }
727 if (bp != NULL)
728 {
729 if (!results)
730 {
731 BN_print(bp,a);
732 BIO_puts(bp," * ");
733 BN_print(bp,b);
734 BIO_puts(bp," % ");
735 BN_print(bp,c);
736 if ((a->neg ^ b->neg) && !BN_is_zero(e))
737 {
738 /* If (a*b) % c is negative, c must be added
739 * in order to obtain the normalized remainder
740 * (new with OpenSSL 0.9.7, previous versions of
741 * BN_mod_mul could generate negative results)
742 */
743 BIO_puts(bp," + ");
744 BN_print(bp,c);
745 }
746 BIO_puts(bp," - ");
747 }
748 BN_print(bp,e);
749 BIO_puts(bp,"\n");
750 }
751 BN_mul(d,a,b,ctx);
752 BN_sub(d,d,e);
753 BN_div(a,b,d,c,ctx);
754 if(!BN_is_zero(b))
755 {
756 fprintf(stderr,"Modulo multiply test failed!\n");
757 ERR_print_errors_fp(stderr);
758 return 0;
759 }
760 }
761 }
762 BN_free(a);
763 BN_free(b);
764 BN_free(c);
765 BN_free(d);
766 BN_free(e);
767 return(1);
768 }
769
test_mod_exp(BIO * bp,BN_CTX * ctx)770 int test_mod_exp(BIO *bp, BN_CTX *ctx)
771 {
772 BIGNUM *a,*b,*c,*d,*e;
773 int i;
774
775 a=BN_new();
776 b=BN_new();
777 c=BN_new();
778 d=BN_new();
779 e=BN_new();
780
781 BN_bntest_rand(c,30,0,1); /* must be odd for montgomery */
782 for (i=0; i<num2; i++)
783 {
784 BN_bntest_rand(a,20+i*5,0,0); /**/
785 BN_bntest_rand(b,2+i,0,0); /**/
786
787 if (!BN_mod_exp(d,a,b,c,ctx))
788 return(0);
789
790 if (bp != NULL)
791 {
792 if (!results)
793 {
794 BN_print(bp,a);
795 BIO_puts(bp," ^ ");
796 BN_print(bp,b);
797 BIO_puts(bp," % ");
798 BN_print(bp,c);
799 BIO_puts(bp," - ");
800 }
801 BN_print(bp,d);
802 BIO_puts(bp,"\n");
803 }
804 BN_exp(e,a,b,ctx);
805 BN_sub(e,e,d);
806 BN_div(a,b,e,c,ctx);
807 if(!BN_is_zero(b))
808 {
809 fprintf(stderr,"Modulo exponentiation test failed!\n");
810 return 0;
811 }
812 }
813 BN_free(a);
814 BN_free(b);
815 BN_free(c);
816 BN_free(d);
817 BN_free(e);
818 return(1);
819 }
820
test_mod_exp_mont_consttime(BIO * bp,BN_CTX * ctx)821 int test_mod_exp_mont_consttime(BIO *bp, BN_CTX *ctx)
822 {
823 BIGNUM *a,*b,*c,*d,*e;
824 int i;
825
826 a=BN_new();
827 b=BN_new();
828 c=BN_new();
829 d=BN_new();
830 e=BN_new();
831
832 BN_bntest_rand(c,30,0,1); /* must be odd for montgomery */
833 for (i=0; i<num2; i++)
834 {
835 BN_bntest_rand(a,20+i*5,0,0); /**/
836 BN_bntest_rand(b,2+i,0,0); /**/
837
838 if (!BN_mod_exp_mont_consttime(d,a,b,c,ctx,NULL))
839 return(00);
840
841 if (bp != NULL)
842 {
843 if (!results)
844 {
845 BN_print(bp,a);
846 BIO_puts(bp," ^ ");
847 BN_print(bp,b);
848 BIO_puts(bp," % ");
849 BN_print(bp,c);
850 BIO_puts(bp," - ");
851 }
852 BN_print(bp,d);
853 BIO_puts(bp,"\n");
854 }
855 BN_exp(e,a,b,ctx);
856 BN_sub(e,e,d);
857 BN_div(a,b,e,c,ctx);
858 if(!BN_is_zero(b))
859 {
860 fprintf(stderr,"Modulo exponentiation test failed!\n");
861 return 0;
862 }
863 }
864 BN_free(a);
865 BN_free(b);
866 BN_free(c);
867 BN_free(d);
868 BN_free(e);
869 return(1);
870 }
871
test_exp(BIO * bp,BN_CTX * ctx)872 int test_exp(BIO *bp, BN_CTX *ctx)
873 {
874 BIGNUM *a,*b,*d,*e,*one;
875 int i;
876
877 a=BN_new();
878 b=BN_new();
879 d=BN_new();
880 e=BN_new();
881 one=BN_new();
882 BN_one(one);
883
884 for (i=0; i<num2; i++)
885 {
886 BN_bntest_rand(a,20+i*5,0,0); /**/
887 BN_bntest_rand(b,2+i,0,0); /**/
888
889 if (!BN_exp(d,a,b,ctx))
890 return(0);
891
892 if (bp != NULL)
893 {
894 if (!results)
895 {
896 BN_print(bp,a);
897 BIO_puts(bp," ^ ");
898 BN_print(bp,b);
899 BIO_puts(bp," - ");
900 }
901 BN_print(bp,d);
902 BIO_puts(bp,"\n");
903 }
904 BN_one(e);
905 for( ; !BN_is_zero(b) ; BN_sub(b,b,one))
906 BN_mul(e,e,a,ctx);
907 BN_sub(e,e,d);
908 if(!BN_is_zero(e))
909 {
910 fprintf(stderr,"Exponentiation test failed!\n");
911 return 0;
912 }
913 }
914 BN_free(a);
915 BN_free(b);
916 BN_free(d);
917 BN_free(e);
918 BN_free(one);
919 return(1);
920 }
921
genprime_cb(int p,int n,void * arg)922 static void genprime_cb(int p, int n, void *arg)
923 {
924 char c='*';
925
926 if (p == 0) c='.';
927 if (p == 1) c='+';
928 if (p == 2) c='*';
929 if (p == 3) c='\n';
930 putc(c, stderr);
931 fflush(stderr);
932 (void)n;
933 (void)arg;
934 }
935
test_kron(BIO * bp,BN_CTX * ctx)936 int test_kron(BIO *bp, BN_CTX *ctx)
937 {
938 BIGNUM *a,*b,*r,*t;
939 int i;
940 int legendre, kronecker;
941 int ret = 0;
942
943 a = BN_new();
944 b = BN_new();
945 r = BN_new();
946 t = BN_new();
947 if (a == NULL || b == NULL || r == NULL || t == NULL) goto err;
948
949 /* We test BN_kronecker(a, b, ctx) just for b odd (Jacobi symbol).
950 * In this case we know that if b is prime, then BN_kronecker(a, b, ctx)
951 * is congruent to $a^{(b-1)/2}$, modulo $b$ (Legendre symbol).
952 * So we generate a random prime b and compare these values
953 * for a number of random a's. (That is, we run the Solovay-Strassen
954 * primality test to confirm that b is prime, except that we
955 * don't want to test whether b is prime but whether BN_kronecker
956 * works.) */
957
958 if (!BN_generate_prime(b, 512, 0, NULL, NULL, genprime_cb, NULL)) goto err;
959 b->neg = rand_neg();
960 putc('\n', stderr);
961
962 for (i = 0; i < num0; i++)
963 {
964 if (!BN_bntest_rand(a, 512, 0, 0)) goto err;
965 a->neg = rand_neg();
966
967 /* t := (|b|-1)/2 (note that b is odd) */
968 if (!BN_copy(t, b)) goto err;
969 t->neg = 0;
970 if (!BN_sub_word(t, 1)) goto err;
971 if (!BN_rshift1(t, t)) goto err;
972 /* r := a^t mod b */
973 b->neg=0;
974
975 if (!BN_mod_exp_recp(r, a, t, b, ctx)) goto err;
976 b->neg=1;
977
978 if (BN_is_word(r, 1))
979 legendre = 1;
980 else if (BN_is_zero(r))
981 legendre = 0;
982 else
983 {
984 if (!BN_add_word(r, 1)) goto err;
985 if (0 != BN_ucmp(r, b))
986 {
987 fprintf(stderr, "Legendre symbol computation failed\n");
988 goto err;
989 }
990 legendre = -1;
991 }
992
993 kronecker = BN_kronecker(a, b, ctx);
994 if (kronecker < -1) goto err;
995 /* we actually need BN_kronecker(a, |b|) */
996 if (a->neg && b->neg)
997 kronecker = -kronecker;
998
999 if (legendre != kronecker)
1000 {
1001 fprintf(stderr, "legendre != kronecker; a = ");
1002 BN_print_fp(stderr, a);
1003 fprintf(stderr, ", b = ");
1004 BN_print_fp(stderr, b);
1005 fprintf(stderr, "\n");
1006 goto err;
1007 }
1008
1009 putc('.', stderr);
1010 fflush(stderr);
1011 }
1012
1013 putc('\n', stderr);
1014 fflush(stderr);
1015 ret = 1;
1016 err:
1017 if (a != NULL) BN_free(a);
1018 if (b != NULL) BN_free(b);
1019 if (r != NULL) BN_free(r);
1020 if (t != NULL) BN_free(t);
1021 return ret;
1022 }
1023
test_sqrt(BIO * bp,BN_CTX * ctx)1024 int test_sqrt(BIO *bp, BN_CTX *ctx)
1025 {
1026 BIGNUM *a,*p,*r;
1027 int i, j;
1028 int ret = 0;
1029
1030 a = BN_new();
1031 p = BN_new();
1032 r = BN_new();
1033 if (a == NULL || p == NULL || r == NULL) goto err;
1034
1035 for (i = 0; i < 16; i++)
1036 {
1037 if (i < 8)
1038 {
1039 unsigned primes[8] = { 2, 3, 5, 7, 11, 13, 17, 19 };
1040
1041 if (!BN_set_word(p, primes[i])) goto err;
1042 }
1043 else
1044 {
1045 if (!BN_set_word(a, 32)) goto err;
1046 if (!BN_set_word(r, 2*i + 1)) goto err;
1047
1048 if (!BN_generate_prime(p, 256, 0, a, r, genprime_cb, NULL)) goto err;
1049 putc('\n', stderr);
1050 }
1051 p->neg = rand_neg();
1052
1053 for (j = 0; j < num2; j++)
1054 {
1055 /* construct 'a' such that it is a square modulo p,
1056 * but in general not a proper square and not reduced modulo p */
1057 if (!BN_bntest_rand(r, 256, 0, 3)) goto err;
1058 if (!BN_nnmod(r, r, p, ctx)) goto err;
1059 if (!BN_mod_sqr(r, r, p, ctx)) goto err;
1060 if (!BN_bntest_rand(a, 256, 0, 3)) goto err;
1061 if (!BN_nnmod(a, a, p, ctx)) goto err;
1062 if (!BN_mod_sqr(a, a, p, ctx)) goto err;
1063 if (!BN_mul(a, a, r, ctx)) goto err;
1064 if (rand_neg())
1065 if (!BN_sub(a, a, p)) goto err;
1066
1067 if (!BN_mod_sqrt(r, a, p, ctx)) goto err;
1068 if (!BN_mod_sqr(r, r, p, ctx)) goto err;
1069
1070 if (!BN_nnmod(a, a, p, ctx)) goto err;
1071
1072 if (BN_cmp(a, r) != 0)
1073 {
1074 fprintf(stderr, "BN_mod_sqrt failed: a = ");
1075 BN_print_fp(stderr, a);
1076 fprintf(stderr, ", r = ");
1077 BN_print_fp(stderr, r);
1078 fprintf(stderr, ", p = ");
1079 BN_print_fp(stderr, p);
1080 fprintf(stderr, "\n");
1081 goto err;
1082 }
1083
1084 putc('.', stderr);
1085 fflush(stderr);
1086 }
1087
1088 putc('\n', stderr);
1089 fflush(stderr);
1090 }
1091 ret = 1;
1092 err:
1093 if (a != NULL) BN_free(a);
1094 if (p != NULL) BN_free(p);
1095 if (r != NULL) BN_free(r);
1096 return ret;
1097 }
1098
test_lshift(BIO * bp,BN_CTX * ctx,BIGNUM * a_)1099 int test_lshift(BIO *bp,BN_CTX *ctx,BIGNUM *a_)
1100 {
1101 BIGNUM *a,*b,*c,*d;
1102 int i;
1103
1104 b=BN_new();
1105 c=BN_new();
1106 d=BN_new();
1107 BN_one(c);
1108
1109 if(a_)
1110 a=a_;
1111 else
1112 {
1113 a=BN_new();
1114 BN_bntest_rand(a,200,0,0); /**/
1115 a->neg=rand_neg();
1116 }
1117 for (i=0; i<num0; i++)
1118 {
1119 BN_lshift(b,a,i+1);
1120 BN_add(c,c,c);
1121 if (bp != NULL)
1122 {
1123 if (!results)
1124 {
1125 BN_print(bp,a);
1126 BIO_puts(bp," * ");
1127 BN_print(bp,c);
1128 BIO_puts(bp," - ");
1129 }
1130 BN_print(bp,b);
1131 BIO_puts(bp,"\n");
1132 }
1133 BN_mul(d,a,c,ctx);
1134 BN_sub(d,d,b);
1135 if(!BN_is_zero(d))
1136 {
1137 fprintf(stderr,"Left shift test failed!\n");
1138 fprintf(stderr,"a=");
1139 BN_print_fp(stderr,a);
1140 fprintf(stderr,"\nb=");
1141 BN_print_fp(stderr,b);
1142 fprintf(stderr,"\nc=");
1143 BN_print_fp(stderr,c);
1144 fprintf(stderr,"\nd=");
1145 BN_print_fp(stderr,d);
1146 fprintf(stderr,"\n");
1147 return 0;
1148 }
1149 }
1150 BN_free(a);
1151 BN_free(b);
1152 BN_free(c);
1153 BN_free(d);
1154 return(1);
1155 }
1156
test_lshift1(BIO * bp)1157 int test_lshift1(BIO *bp)
1158 {
1159 BIGNUM *a,*b,*c;
1160 int i;
1161
1162 a=BN_new();
1163 b=BN_new();
1164 c=BN_new();
1165
1166 BN_bntest_rand(a,200,0,0); /**/
1167 a->neg=rand_neg();
1168 for (i=0; i<num0; i++)
1169 {
1170 BN_lshift1(b,a);
1171 if (bp != NULL)
1172 {
1173 if (!results)
1174 {
1175 BN_print(bp,a);
1176 BIO_puts(bp," * 2");
1177 BIO_puts(bp," - ");
1178 }
1179 BN_print(bp,b);
1180 BIO_puts(bp,"\n");
1181 }
1182 BN_add(c,a,a);
1183 BN_sub(a,b,c);
1184 if(!BN_is_zero(a))
1185 {
1186 fprintf(stderr,"Left shift one test failed!\n");
1187 return 0;
1188 }
1189
1190 BN_copy(a,b);
1191 }
1192 BN_free(a);
1193 BN_free(b);
1194 BN_free(c);
1195 return(1);
1196 }
1197
test_rshift(BIO * bp,BN_CTX * ctx)1198 int test_rshift(BIO *bp,BN_CTX *ctx)
1199 {
1200 BIGNUM *a,*b,*c,*d,*e;
1201 int i;
1202
1203 a=BN_new();
1204 b=BN_new();
1205 c=BN_new();
1206 d=BN_new();
1207 e=BN_new();
1208 BN_one(c);
1209
1210 BN_bntest_rand(a,200,0,0); /**/
1211 a->neg=rand_neg();
1212 for (i=0; i<num0; i++)
1213 {
1214 BN_rshift(b,a,i+1);
1215 BN_add(c,c,c);
1216 if (bp != NULL)
1217 {
1218 if (!results)
1219 {
1220 BN_print(bp,a);
1221 BIO_puts(bp," / ");
1222 BN_print(bp,c);
1223 BIO_puts(bp," - ");
1224 }
1225 BN_print(bp,b);
1226 BIO_puts(bp,"\n");
1227 }
1228 BN_div(d,e,a,c,ctx);
1229 BN_sub(d,d,b);
1230 if(!BN_is_zero(d))
1231 {
1232 fprintf(stderr,"Right shift test failed!\n");
1233 return 0;
1234 }
1235 }
1236 BN_free(a);
1237 BN_free(b);
1238 BN_free(c);
1239 BN_free(d);
1240 BN_free(e);
1241 return(1);
1242 }
1243
test_rshift1(BIO * bp)1244 int test_rshift1(BIO *bp)
1245 {
1246 BIGNUM *a,*b,*c;
1247 int i;
1248
1249 a=BN_new();
1250 b=BN_new();
1251 c=BN_new();
1252
1253 BN_bntest_rand(a,200,0,0); /**/
1254 a->neg=rand_neg();
1255 for (i=0; i<num0; i++)
1256 {
1257 BN_rshift1(b,a);
1258 if (bp != NULL)
1259 {
1260 if (!results)
1261 {
1262 BN_print(bp,a);
1263 BIO_puts(bp," / 2");
1264 BIO_puts(bp," - ");
1265 }
1266 BN_print(bp,b);
1267 BIO_puts(bp,"\n");
1268 }
1269 BN_sub(c,a,b);
1270 BN_sub(c,c,b);
1271 if(!BN_is_zero(c) && !BN_abs_is_word(c, 1))
1272 {
1273 fprintf(stderr,"Right shift one test failed!\n");
1274 return 0;
1275 }
1276 BN_copy(a,b);
1277 }
1278 BN_free(a);
1279 BN_free(b);
1280 BN_free(c);
1281 return(1);
1282 }
1283
rand_neg(void)1284 int rand_neg(void)
1285 {
1286 static unsigned int neg=0;
1287 static int sign[8]={0,0,0,1,1,0,1,1};
1288
1289 return(sign[(neg++)%8]);
1290 }
1291