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 * Copyright 2002 Sun Microsystems, Inc. ALL RIGHTS RESERVED.
60 *
61 * Portions of the attached software ("Contribution") are developed by
62 * SUN MICROSYSTEMS, INC., and are contributed to the OpenSSL project.
63 *
64 * The Contribution is licensed pursuant to the Eric Young open source
65 * license provided above.
66 *
67 * The binary polynomial arithmetic software is originally written by
68 * Sheueling Chang Shantz and Douglas Stebila of Sun Microsystems Laboratories.
69 *
70 */
71
72 /* Until the key-gen callbacks are modified to use newer prototypes, we allow
73 * deprecated functions for openssl-internal code */
74 #ifdef OPENSSL_NO_DEPRECATED
75 #undef OPENSSL_NO_DEPRECATED
76 #endif
77
78 #include <stdio.h>
79 #include <stdlib.h>
80 #include <string.h>
81
82 #include "e_os.h"
83
84 #include <openssl/bio.h>
85 #include <openssl/bn.h>
86 #include <openssl/rand.h>
87 #include <openssl/x509.h>
88 #include <openssl/err.h>
89
90 const int num0 = 100; /* number of tests */
91 const int num1 = 50; /* additional tests for some functions */
92 const int num2 = 5; /* number of tests for slow functions */
93
94 int test_add(BIO *bp);
95 int test_sub(BIO *bp);
96 int test_lshift1(BIO *bp);
97 int test_lshift(BIO *bp,BN_CTX *ctx,BIGNUM *a_);
98 int test_rshift1(BIO *bp);
99 int test_rshift(BIO *bp,BN_CTX *ctx);
100 int test_div(BIO *bp,BN_CTX *ctx);
101 int test_div_word(BIO *bp);
102 int test_div_recp(BIO *bp,BN_CTX *ctx);
103 int test_mul(BIO *bp);
104 int test_sqr(BIO *bp,BN_CTX *ctx);
105 int test_mont(BIO *bp,BN_CTX *ctx);
106 int test_mod(BIO *bp,BN_CTX *ctx);
107 int test_mod_mul(BIO *bp,BN_CTX *ctx);
108 int test_mod_exp(BIO *bp,BN_CTX *ctx);
109 int test_mod_exp_mont_consttime(BIO *bp,BN_CTX *ctx);
110 int test_exp(BIO *bp,BN_CTX *ctx);
111 int test_gf2m_add(BIO *bp);
112 int test_gf2m_mod(BIO *bp);
113 int test_gf2m_mod_mul(BIO *bp,BN_CTX *ctx);
114 int test_gf2m_mod_sqr(BIO *bp,BN_CTX *ctx);
115 int test_gf2m_mod_inv(BIO *bp,BN_CTX *ctx);
116 int test_gf2m_mod_div(BIO *bp,BN_CTX *ctx);
117 int test_gf2m_mod_exp(BIO *bp,BN_CTX *ctx);
118 int test_gf2m_mod_sqrt(BIO *bp,BN_CTX *ctx);
119 int test_gf2m_mod_solve_quad(BIO *bp,BN_CTX *ctx);
120 int test_kron(BIO *bp,BN_CTX *ctx);
121 int test_sqrt(BIO *bp,BN_CTX *ctx);
122 int rand_neg(void);
123 static int results=0;
124
125 static unsigned char lst[]="\xC6\x4F\x43\x04\x2A\xEA\xCA\x6E\x58\x36\x80\x5B\xE8\xC9"
126 "\x9B\x04\x5D\x48\x36\xC2\xFD\x16\xC9\x64\xF0";
127
128 static const char rnd_seed[] = "string to make the random number generator think it has entropy";
129
message(BIO * out,char * m)130 static void message(BIO *out, char *m)
131 {
132 fprintf(stderr, "test %s\n", m);
133 BIO_puts(out, "print \"test ");
134 BIO_puts(out, m);
135 BIO_puts(out, "\\n\"\n");
136 }
137
main(int argc,char * argv[])138 int main(int argc, char *argv[])
139 {
140 BN_CTX *ctx;
141 BIO *out;
142 char *outfile=NULL;
143
144 results = 0;
145
146 RAND_seed(rnd_seed, sizeof rnd_seed); /* or BN_generate_prime may fail */
147
148 argc--;
149 argv++;
150 while (argc >= 1)
151 {
152 if (strcmp(*argv,"-results") == 0)
153 results=1;
154 else if (strcmp(*argv,"-out") == 0)
155 {
156 if (--argc < 1) break;
157 outfile= *(++argv);
158 }
159 argc--;
160 argv++;
161 }
162
163
164 ctx=BN_CTX_new();
165 if (ctx == NULL) EXIT(1);
166
167 out=BIO_new(BIO_s_file());
168 if (out == NULL) EXIT(1);
169 if (outfile == NULL)
170 {
171 BIO_set_fp(out,stdout,BIO_NOCLOSE);
172 }
173 else
174 {
175 if (!BIO_write_filename(out,outfile))
176 {
177 perror(outfile);
178 EXIT(1);
179 }
180 }
181
182 if (!results)
183 BIO_puts(out,"obase=16\nibase=16\n");
184
185 message(out,"BN_add");
186 if (!test_add(out)) goto err;
187 BIO_flush(out);
188
189 message(out,"BN_sub");
190 if (!test_sub(out)) goto err;
191 BIO_flush(out);
192
193 message(out,"BN_lshift1");
194 if (!test_lshift1(out)) goto err;
195 BIO_flush(out);
196
197 message(out,"BN_lshift (fixed)");
198 if (!test_lshift(out,ctx,BN_bin2bn(lst,sizeof(lst)-1,NULL)))
199 goto err;
200 BIO_flush(out);
201
202 message(out,"BN_lshift");
203 if (!test_lshift(out,ctx,NULL)) goto err;
204 BIO_flush(out);
205
206 message(out,"BN_rshift1");
207 if (!test_rshift1(out)) goto err;
208 BIO_flush(out);
209
210 message(out,"BN_rshift");
211 if (!test_rshift(out,ctx)) goto err;
212 BIO_flush(out);
213
214 message(out,"BN_sqr");
215 if (!test_sqr(out,ctx)) goto err;
216 BIO_flush(out);
217
218 message(out,"BN_mul");
219 if (!test_mul(out)) goto err;
220 BIO_flush(out);
221
222 message(out,"BN_div");
223 if (!test_div(out,ctx)) goto err;
224 BIO_flush(out);
225
226 message(out,"BN_div_word");
227 if (!test_div_word(out)) goto err;
228 BIO_flush(out);
229
230 message(out,"BN_div_recp");
231 if (!test_div_recp(out,ctx)) goto err;
232 BIO_flush(out);
233
234 message(out,"BN_mod");
235 if (!test_mod(out,ctx)) goto err;
236 BIO_flush(out);
237
238 message(out,"BN_mod_mul");
239 if (!test_mod_mul(out,ctx)) goto err;
240 BIO_flush(out);
241
242 message(out,"BN_mont");
243 if (!test_mont(out,ctx)) goto err;
244 BIO_flush(out);
245
246 message(out,"BN_mod_exp");
247 if (!test_mod_exp(out,ctx)) goto err;
248 BIO_flush(out);
249
250 message(out,"BN_mod_exp_mont_consttime");
251 if (!test_mod_exp_mont_consttime(out,ctx)) goto err;
252 BIO_flush(out);
253
254 message(out,"BN_exp");
255 if (!test_exp(out,ctx)) goto err;
256 BIO_flush(out);
257
258 message(out,"BN_kronecker");
259 if (!test_kron(out,ctx)) goto err;
260 BIO_flush(out);
261
262 message(out,"BN_mod_sqrt");
263 if (!test_sqrt(out,ctx)) goto err;
264 BIO_flush(out);
265
266 message(out,"BN_GF2m_add");
267 if (!test_gf2m_add(out)) goto err;
268 BIO_flush(out);
269
270 message(out,"BN_GF2m_mod");
271 if (!test_gf2m_mod(out)) goto err;
272 BIO_flush(out);
273
274 message(out,"BN_GF2m_mod_mul");
275 if (!test_gf2m_mod_mul(out,ctx)) goto err;
276 BIO_flush(out);
277
278 message(out,"BN_GF2m_mod_sqr");
279 if (!test_gf2m_mod_sqr(out,ctx)) goto err;
280 BIO_flush(out);
281
282 message(out,"BN_GF2m_mod_inv");
283 if (!test_gf2m_mod_inv(out,ctx)) goto err;
284 BIO_flush(out);
285
286 message(out,"BN_GF2m_mod_div");
287 if (!test_gf2m_mod_div(out,ctx)) goto err;
288 BIO_flush(out);
289
290 message(out,"BN_GF2m_mod_exp");
291 if (!test_gf2m_mod_exp(out,ctx)) goto err;
292 BIO_flush(out);
293
294 message(out,"BN_GF2m_mod_sqrt");
295 if (!test_gf2m_mod_sqrt(out,ctx)) goto err;
296 BIO_flush(out);
297
298 message(out,"BN_GF2m_mod_solve_quad");
299 if (!test_gf2m_mod_solve_quad(out,ctx)) goto err;
300 BIO_flush(out);
301
302 BN_CTX_free(ctx);
303 BIO_free(out);
304
305 /**/
306 EXIT(0);
307 err:
308 BIO_puts(out,"1\n"); /* make sure the Perl script fed by bc notices
309 * the failure, see test_bn in test/Makefile.ssl*/
310 BIO_flush(out);
311 ERR_load_crypto_strings();
312 ERR_print_errors_fp(stderr);
313 EXIT(1);
314 return(1);
315 }
316
test_add(BIO * bp)317 int test_add(BIO *bp)
318 {
319 BIGNUM a,b,c;
320 int i;
321
322 BN_init(&a);
323 BN_init(&b);
324 BN_init(&c);
325
326 BN_bntest_rand(&a,512,0,0);
327 for (i=0; i<num0; i++)
328 {
329 BN_bntest_rand(&b,450+i,0,0);
330 a.neg=rand_neg();
331 b.neg=rand_neg();
332 BN_add(&c,&a,&b);
333 if (bp != NULL)
334 {
335 if (!results)
336 {
337 BN_print(bp,&a);
338 BIO_puts(bp," + ");
339 BN_print(bp,&b);
340 BIO_puts(bp," - ");
341 }
342 BN_print(bp,&c);
343 BIO_puts(bp,"\n");
344 }
345 a.neg=!a.neg;
346 b.neg=!b.neg;
347 BN_add(&c,&c,&b);
348 BN_add(&c,&c,&a);
349 if(!BN_is_zero(&c))
350 {
351 fprintf(stderr,"Add test failed!\n");
352 return 0;
353 }
354 }
355 BN_free(&a);
356 BN_free(&b);
357 BN_free(&c);
358 return(1);
359 }
360
test_sub(BIO * bp)361 int test_sub(BIO *bp)
362 {
363 BIGNUM a,b,c;
364 int i;
365
366 BN_init(&a);
367 BN_init(&b);
368 BN_init(&c);
369
370 for (i=0; i<num0+num1; i++)
371 {
372 if (i < num1)
373 {
374 BN_bntest_rand(&a,512,0,0);
375 BN_copy(&b,&a);
376 if (BN_set_bit(&a,i)==0) return(0);
377 BN_add_word(&b,i);
378 }
379 else
380 {
381 BN_bntest_rand(&b,400+i-num1,0,0);
382 a.neg=rand_neg();
383 b.neg=rand_neg();
384 }
385 BN_sub(&c,&a,&b);
386 if (bp != NULL)
387 {
388 if (!results)
389 {
390 BN_print(bp,&a);
391 BIO_puts(bp," - ");
392 BN_print(bp,&b);
393 BIO_puts(bp," - ");
394 }
395 BN_print(bp,&c);
396 BIO_puts(bp,"\n");
397 }
398 BN_add(&c,&c,&b);
399 BN_sub(&c,&c,&a);
400 if(!BN_is_zero(&c))
401 {
402 fprintf(stderr,"Subtract test failed!\n");
403 return 0;
404 }
405 }
406 BN_free(&a);
407 BN_free(&b);
408 BN_free(&c);
409 return(1);
410 }
411
test_div(BIO * bp,BN_CTX * ctx)412 int test_div(BIO *bp, BN_CTX *ctx)
413 {
414 BIGNUM a,b,c,d,e;
415 int i;
416
417 BN_init(&a);
418 BN_init(&b);
419 BN_init(&c);
420 BN_init(&d);
421 BN_init(&e);
422
423 for (i=0; i<num0+num1; i++)
424 {
425 if (i < num1)
426 {
427 BN_bntest_rand(&a,400,0,0);
428 BN_copy(&b,&a);
429 BN_lshift(&a,&a,i);
430 BN_add_word(&a,i);
431 }
432 else
433 BN_bntest_rand(&b,50+3*(i-num1),0,0);
434 a.neg=rand_neg();
435 b.neg=rand_neg();
436 BN_div(&d,&c,&a,&b,ctx);
437 if (bp != NULL)
438 {
439 if (!results)
440 {
441 BN_print(bp,&a);
442 BIO_puts(bp," / ");
443 BN_print(bp,&b);
444 BIO_puts(bp," - ");
445 }
446 BN_print(bp,&d);
447 BIO_puts(bp,"\n");
448
449 if (!results)
450 {
451 BN_print(bp,&a);
452 BIO_puts(bp," % ");
453 BN_print(bp,&b);
454 BIO_puts(bp," - ");
455 }
456 BN_print(bp,&c);
457 BIO_puts(bp,"\n");
458 }
459 BN_mul(&e,&d,&b,ctx);
460 BN_add(&d,&e,&c);
461 BN_sub(&d,&d,&a);
462 if(!BN_is_zero(&d))
463 {
464 fprintf(stderr,"Division test failed!\n");
465 return 0;
466 }
467 }
468 BN_free(&a);
469 BN_free(&b);
470 BN_free(&c);
471 BN_free(&d);
472 BN_free(&e);
473 return(1);
474 }
475
print_word(BIO * bp,BN_ULONG w)476 static void print_word(BIO *bp,BN_ULONG w)
477 {
478 #ifdef SIXTY_FOUR_BIT
479 if (sizeof(w) > sizeof(unsigned long))
480 {
481 unsigned long h=(unsigned long)(w>>32),
482 l=(unsigned long)(w);
483
484 if (h) BIO_printf(bp,"%lX%08lX",h,l);
485 else BIO_printf(bp,"%lX",l);
486 return;
487 }
488 #endif
489 BIO_printf(bp,"%lX",w);
490 }
491
test_div_word(BIO * bp)492 int test_div_word(BIO *bp)
493 {
494 BIGNUM a,b;
495 BN_ULONG r,s;
496 int i;
497
498 BN_init(&a);
499 BN_init(&b);
500
501 for (i=0; i<num0; i++)
502 {
503 do {
504 BN_bntest_rand(&a,512,-1,0);
505 BN_bntest_rand(&b,BN_BITS2,-1,0);
506 s = b.d[0];
507 } while (!s);
508
509 BN_copy(&b, &a);
510 r = BN_div_word(&b, s);
511
512 if (bp != NULL)
513 {
514 if (!results)
515 {
516 BN_print(bp,&a);
517 BIO_puts(bp," / ");
518 print_word(bp,s);
519 BIO_puts(bp," - ");
520 }
521 BN_print(bp,&b);
522 BIO_puts(bp,"\n");
523
524 if (!results)
525 {
526 BN_print(bp,&a);
527 BIO_puts(bp," % ");
528 print_word(bp,s);
529 BIO_puts(bp," - ");
530 }
531 print_word(bp,r);
532 BIO_puts(bp,"\n");
533 }
534 BN_mul_word(&b,s);
535 BN_add_word(&b,r);
536 BN_sub(&b,&a,&b);
537 if(!BN_is_zero(&b))
538 {
539 fprintf(stderr,"Division (word) test failed!\n");
540 return 0;
541 }
542 }
543 BN_free(&a);
544 BN_free(&b);
545 return(1);
546 }
547
test_div_recp(BIO * bp,BN_CTX * ctx)548 int test_div_recp(BIO *bp, BN_CTX *ctx)
549 {
550 BIGNUM a,b,c,d,e;
551 BN_RECP_CTX recp;
552 int i;
553
554 BN_RECP_CTX_init(&recp);
555 BN_init(&a);
556 BN_init(&b);
557 BN_init(&c);
558 BN_init(&d);
559 BN_init(&e);
560
561 for (i=0; i<num0+num1; i++)
562 {
563 if (i < num1)
564 {
565 BN_bntest_rand(&a,400,0,0);
566 BN_copy(&b,&a);
567 BN_lshift(&a,&a,i);
568 BN_add_word(&a,i);
569 }
570 else
571 BN_bntest_rand(&b,50+3*(i-num1),0,0);
572 a.neg=rand_neg();
573 b.neg=rand_neg();
574 BN_RECP_CTX_set(&recp,&b,ctx);
575 BN_div_recp(&d,&c,&a,&recp,ctx);
576 if (bp != NULL)
577 {
578 if (!results)
579 {
580 BN_print(bp,&a);
581 BIO_puts(bp," / ");
582 BN_print(bp,&b);
583 BIO_puts(bp," - ");
584 }
585 BN_print(bp,&d);
586 BIO_puts(bp,"\n");
587
588 if (!results)
589 {
590 BN_print(bp,&a);
591 BIO_puts(bp," % ");
592 BN_print(bp,&b);
593 BIO_puts(bp," - ");
594 }
595 BN_print(bp,&c);
596 BIO_puts(bp,"\n");
597 }
598 BN_mul(&e,&d,&b,ctx);
599 BN_add(&d,&e,&c);
600 BN_sub(&d,&d,&a);
601 if(!BN_is_zero(&d))
602 {
603 fprintf(stderr,"Reciprocal division test failed!\n");
604 fprintf(stderr,"a=");
605 BN_print_fp(stderr,&a);
606 fprintf(stderr,"\nb=");
607 BN_print_fp(stderr,&b);
608 fprintf(stderr,"\n");
609 return 0;
610 }
611 }
612 BN_free(&a);
613 BN_free(&b);
614 BN_free(&c);
615 BN_free(&d);
616 BN_free(&e);
617 BN_RECP_CTX_free(&recp);
618 return(1);
619 }
620
test_mul(BIO * bp)621 int test_mul(BIO *bp)
622 {
623 BIGNUM a,b,c,d,e;
624 int i;
625 BN_CTX *ctx;
626
627 ctx = BN_CTX_new();
628 if (ctx == NULL) EXIT(1);
629
630 BN_init(&a);
631 BN_init(&b);
632 BN_init(&c);
633 BN_init(&d);
634 BN_init(&e);
635
636 for (i=0; i<num0+num1; i++)
637 {
638 if (i <= num1)
639 {
640 BN_bntest_rand(&a,100,0,0);
641 BN_bntest_rand(&b,100,0,0);
642 }
643 else
644 BN_bntest_rand(&b,i-num1,0,0);
645 a.neg=rand_neg();
646 b.neg=rand_neg();
647 BN_mul(&c,&a,&b,ctx);
648 if (bp != NULL)
649 {
650 if (!results)
651 {
652 BN_print(bp,&a);
653 BIO_puts(bp," * ");
654 BN_print(bp,&b);
655 BIO_puts(bp," - ");
656 }
657 BN_print(bp,&c);
658 BIO_puts(bp,"\n");
659 }
660 BN_div(&d,&e,&c,&a,ctx);
661 BN_sub(&d,&d,&b);
662 if(!BN_is_zero(&d) || !BN_is_zero(&e))
663 {
664 fprintf(stderr,"Multiplication test failed!\n");
665 return 0;
666 }
667 }
668 BN_free(&a);
669 BN_free(&b);
670 BN_free(&c);
671 BN_free(&d);
672 BN_free(&e);
673 BN_CTX_free(ctx);
674 return(1);
675 }
676
test_sqr(BIO * bp,BN_CTX * ctx)677 int test_sqr(BIO *bp, BN_CTX *ctx)
678 {
679 BIGNUM a,c,d,e;
680 int i;
681
682 BN_init(&a);
683 BN_init(&c);
684 BN_init(&d);
685 BN_init(&e);
686
687 for (i=0; i<num0; i++)
688 {
689 BN_bntest_rand(&a,40+i*10,0,0);
690 a.neg=rand_neg();
691 BN_sqr(&c,&a,ctx);
692 if (bp != NULL)
693 {
694 if (!results)
695 {
696 BN_print(bp,&a);
697 BIO_puts(bp," * ");
698 BN_print(bp,&a);
699 BIO_puts(bp," - ");
700 }
701 BN_print(bp,&c);
702 BIO_puts(bp,"\n");
703 }
704 BN_div(&d,&e,&c,&a,ctx);
705 BN_sub(&d,&d,&a);
706 if(!BN_is_zero(&d) || !BN_is_zero(&e))
707 {
708 fprintf(stderr,"Square test failed!\n");
709 return 0;
710 }
711 }
712 BN_free(&a);
713 BN_free(&c);
714 BN_free(&d);
715 BN_free(&e);
716 return(1);
717 }
718
test_mont(BIO * bp,BN_CTX * ctx)719 int test_mont(BIO *bp, BN_CTX *ctx)
720 {
721 BIGNUM a,b,c,d,A,B;
722 BIGNUM n;
723 int i;
724 BN_MONT_CTX *mont;
725
726 BN_init(&a);
727 BN_init(&b);
728 BN_init(&c);
729 BN_init(&d);
730 BN_init(&A);
731 BN_init(&B);
732 BN_init(&n);
733
734 mont=BN_MONT_CTX_new();
735
736 BN_bntest_rand(&a,100,0,0); /**/
737 BN_bntest_rand(&b,100,0,0); /**/
738 for (i=0; i<num2; i++)
739 {
740 int bits = (200*(i+1))/num2;
741
742 if (bits == 0)
743 continue;
744 BN_bntest_rand(&n,bits,0,1);
745 BN_MONT_CTX_set(mont,&n,ctx);
746
747 BN_nnmod(&a,&a,&n,ctx);
748 BN_nnmod(&b,&b,&n,ctx);
749
750 BN_to_montgomery(&A,&a,mont,ctx);
751 BN_to_montgomery(&B,&b,mont,ctx);
752
753 BN_mod_mul_montgomery(&c,&A,&B,mont,ctx);/**/
754 BN_from_montgomery(&A,&c,mont,ctx);/**/
755 if (bp != NULL)
756 {
757 if (!results)
758 {
759 #ifdef undef
760 fprintf(stderr,"%d * %d %% %d\n",
761 BN_num_bits(&a),
762 BN_num_bits(&b),
763 BN_num_bits(mont->N));
764 #endif
765 BN_print(bp,&a);
766 BIO_puts(bp," * ");
767 BN_print(bp,&b);
768 BIO_puts(bp," % ");
769 BN_print(bp,&(mont->N));
770 BIO_puts(bp," - ");
771 }
772 BN_print(bp,&A);
773 BIO_puts(bp,"\n");
774 }
775 BN_mod_mul(&d,&a,&b,&n,ctx);
776 BN_sub(&d,&d,&A);
777 if(!BN_is_zero(&d))
778 {
779 fprintf(stderr,"Montgomery multiplication test failed!\n");
780 return 0;
781 }
782 }
783 BN_MONT_CTX_free(mont);
784 BN_free(&a);
785 BN_free(&b);
786 BN_free(&c);
787 BN_free(&d);
788 BN_free(&A);
789 BN_free(&B);
790 BN_free(&n);
791 return(1);
792 }
793
test_mod(BIO * bp,BN_CTX * ctx)794 int test_mod(BIO *bp, BN_CTX *ctx)
795 {
796 BIGNUM *a,*b,*c,*d,*e;
797 int i;
798
799 a=BN_new();
800 b=BN_new();
801 c=BN_new();
802 d=BN_new();
803 e=BN_new();
804
805 BN_bntest_rand(a,1024,0,0); /**/
806 for (i=0; i<num0; i++)
807 {
808 BN_bntest_rand(b,450+i*10,0,0); /**/
809 a->neg=rand_neg();
810 b->neg=rand_neg();
811 BN_mod(c,a,b,ctx);/**/
812 if (bp != NULL)
813 {
814 if (!results)
815 {
816 BN_print(bp,a);
817 BIO_puts(bp," % ");
818 BN_print(bp,b);
819 BIO_puts(bp," - ");
820 }
821 BN_print(bp,c);
822 BIO_puts(bp,"\n");
823 }
824 BN_div(d,e,a,b,ctx);
825 BN_sub(e,e,c);
826 if(!BN_is_zero(e))
827 {
828 fprintf(stderr,"Modulo test failed!\n");
829 return 0;
830 }
831 }
832 BN_free(a);
833 BN_free(b);
834 BN_free(c);
835 BN_free(d);
836 BN_free(e);
837 return(1);
838 }
839
test_mod_mul(BIO * bp,BN_CTX * ctx)840 int test_mod_mul(BIO *bp, BN_CTX *ctx)
841 {
842 BIGNUM *a,*b,*c,*d,*e;
843 int i,j;
844
845 a=BN_new();
846 b=BN_new();
847 c=BN_new();
848 d=BN_new();
849 e=BN_new();
850
851 for (j=0; j<3; j++) {
852 BN_bntest_rand(c,1024,0,0); /**/
853 for (i=0; i<num0; i++)
854 {
855 BN_bntest_rand(a,475+i*10,0,0); /**/
856 BN_bntest_rand(b,425+i*11,0,0); /**/
857 a->neg=rand_neg();
858 b->neg=rand_neg();
859 if (!BN_mod_mul(e,a,b,c,ctx))
860 {
861 unsigned long l;
862
863 while ((l=ERR_get_error()))
864 fprintf(stderr,"ERROR:%s\n",
865 ERR_error_string(l,NULL));
866 EXIT(1);
867 }
868 if (bp != NULL)
869 {
870 if (!results)
871 {
872 BN_print(bp,a);
873 BIO_puts(bp," * ");
874 BN_print(bp,b);
875 BIO_puts(bp," % ");
876 BN_print(bp,c);
877 if ((a->neg ^ b->neg) && !BN_is_zero(e))
878 {
879 /* If (a*b) % c is negative, c must be added
880 * in order to obtain the normalized remainder
881 * (new with OpenSSL 0.9.7, previous versions of
882 * BN_mod_mul could generate negative results)
883 */
884 BIO_puts(bp," + ");
885 BN_print(bp,c);
886 }
887 BIO_puts(bp," - ");
888 }
889 BN_print(bp,e);
890 BIO_puts(bp,"\n");
891 }
892 BN_mul(d,a,b,ctx);
893 BN_sub(d,d,e);
894 BN_div(a,b,d,c,ctx);
895 if(!BN_is_zero(b))
896 {
897 fprintf(stderr,"Modulo multiply test failed!\n");
898 ERR_print_errors_fp(stderr);
899 return 0;
900 }
901 }
902 }
903 BN_free(a);
904 BN_free(b);
905 BN_free(c);
906 BN_free(d);
907 BN_free(e);
908 return(1);
909 }
910
test_mod_exp(BIO * bp,BN_CTX * ctx)911 int test_mod_exp(BIO *bp, BN_CTX *ctx)
912 {
913 BIGNUM *a,*b,*c,*d,*e;
914 int i;
915
916 a=BN_new();
917 b=BN_new();
918 c=BN_new();
919 d=BN_new();
920 e=BN_new();
921
922 BN_bntest_rand(c,30,0,1); /* must be odd for montgomery */
923 for (i=0; i<num2; i++)
924 {
925 BN_bntest_rand(a,20+i*5,0,0); /**/
926 BN_bntest_rand(b,2+i,0,0); /**/
927
928 if (!BN_mod_exp(d,a,b,c,ctx))
929 return(00);
930
931 if (bp != NULL)
932 {
933 if (!results)
934 {
935 BN_print(bp,a);
936 BIO_puts(bp," ^ ");
937 BN_print(bp,b);
938 BIO_puts(bp," % ");
939 BN_print(bp,c);
940 BIO_puts(bp," - ");
941 }
942 BN_print(bp,d);
943 BIO_puts(bp,"\n");
944 }
945 BN_exp(e,a,b,ctx);
946 BN_sub(e,e,d);
947 BN_div(a,b,e,c,ctx);
948 if(!BN_is_zero(b))
949 {
950 fprintf(stderr,"Modulo exponentiation test failed!\n");
951 return 0;
952 }
953 }
954 BN_free(a);
955 BN_free(b);
956 BN_free(c);
957 BN_free(d);
958 BN_free(e);
959 return(1);
960 }
961
test_mod_exp_mont_consttime(BIO * bp,BN_CTX * ctx)962 int test_mod_exp_mont_consttime(BIO *bp, BN_CTX *ctx)
963 {
964 BIGNUM *a,*b,*c,*d,*e;
965 int i;
966
967 a=BN_new();
968 b=BN_new();
969 c=BN_new();
970 d=BN_new();
971 e=BN_new();
972
973 BN_bntest_rand(c,30,0,1); /* must be odd for montgomery */
974 for (i=0; i<num2; i++)
975 {
976 BN_bntest_rand(a,20+i*5,0,0); /**/
977 BN_bntest_rand(b,2+i,0,0); /**/
978
979 if (!BN_mod_exp_mont_consttime(d,a,b,c,ctx,NULL))
980 return(00);
981
982 if (bp != NULL)
983 {
984 if (!results)
985 {
986 BN_print(bp,a);
987 BIO_puts(bp," ^ ");
988 BN_print(bp,b);
989 BIO_puts(bp," % ");
990 BN_print(bp,c);
991 BIO_puts(bp," - ");
992 }
993 BN_print(bp,d);
994 BIO_puts(bp,"\n");
995 }
996 BN_exp(e,a,b,ctx);
997 BN_sub(e,e,d);
998 BN_div(a,b,e,c,ctx);
999 if(!BN_is_zero(b))
1000 {
1001 fprintf(stderr,"Modulo exponentiation test failed!\n");
1002 return 0;
1003 }
1004 }
1005 BN_free(a);
1006 BN_free(b);
1007 BN_free(c);
1008 BN_free(d);
1009 BN_free(e);
1010 return(1);
1011 }
1012
test_exp(BIO * bp,BN_CTX * ctx)1013 int test_exp(BIO *bp, BN_CTX *ctx)
1014 {
1015 BIGNUM *a,*b,*d,*e,*one;
1016 int i;
1017
1018 a=BN_new();
1019 b=BN_new();
1020 d=BN_new();
1021 e=BN_new();
1022 one=BN_new();
1023 BN_one(one);
1024
1025 for (i=0; i<num2; i++)
1026 {
1027 BN_bntest_rand(a,20+i*5,0,0); /**/
1028 BN_bntest_rand(b,2+i,0,0); /**/
1029
1030 if (!BN_exp(d,a,b,ctx))
1031 return(00);
1032
1033 if (bp != NULL)
1034 {
1035 if (!results)
1036 {
1037 BN_print(bp,a);
1038 BIO_puts(bp," ^ ");
1039 BN_print(bp,b);
1040 BIO_puts(bp," - ");
1041 }
1042 BN_print(bp,d);
1043 BIO_puts(bp,"\n");
1044 }
1045 BN_one(e);
1046 for( ; !BN_is_zero(b) ; BN_sub(b,b,one))
1047 BN_mul(e,e,a,ctx);
1048 BN_sub(e,e,d);
1049 if(!BN_is_zero(e))
1050 {
1051 fprintf(stderr,"Exponentiation test failed!\n");
1052 return 0;
1053 }
1054 }
1055 BN_free(a);
1056 BN_free(b);
1057 BN_free(d);
1058 BN_free(e);
1059 BN_free(one);
1060 return(1);
1061 }
1062
test_gf2m_add(BIO * bp)1063 int test_gf2m_add(BIO *bp)
1064 {
1065 BIGNUM a,b,c;
1066 int i, ret = 0;
1067
1068 BN_init(&a);
1069 BN_init(&b);
1070 BN_init(&c);
1071
1072 for (i=0; i<num0; i++)
1073 {
1074 BN_rand(&a,512,0,0);
1075 BN_copy(&b, BN_value_one());
1076 a.neg=rand_neg();
1077 b.neg=rand_neg();
1078 BN_GF2m_add(&c,&a,&b);
1079 #if 0 /* make test uses ouput in bc but bc can't handle GF(2^m) arithmetic */
1080 if (bp != NULL)
1081 {
1082 if (!results)
1083 {
1084 BN_print(bp,&a);
1085 BIO_puts(bp," ^ ");
1086 BN_print(bp,&b);
1087 BIO_puts(bp," = ");
1088 }
1089 BN_print(bp,&c);
1090 BIO_puts(bp,"\n");
1091 }
1092 #endif
1093 /* Test that two added values have the correct parity. */
1094 if((BN_is_odd(&a) && BN_is_odd(&c)) || (!BN_is_odd(&a) && !BN_is_odd(&c)))
1095 {
1096 fprintf(stderr,"GF(2^m) addition test (a) failed!\n");
1097 goto err;
1098 }
1099 BN_GF2m_add(&c,&c,&c);
1100 /* Test that c + c = 0. */
1101 if(!BN_is_zero(&c))
1102 {
1103 fprintf(stderr,"GF(2^m) addition test (b) failed!\n");
1104 goto err;
1105 }
1106 }
1107 ret = 1;
1108 err:
1109 BN_free(&a);
1110 BN_free(&b);
1111 BN_free(&c);
1112 return ret;
1113 }
1114
test_gf2m_mod(BIO * bp)1115 int test_gf2m_mod(BIO *bp)
1116 {
1117 BIGNUM *a,*b[2],*c,*d,*e;
1118 int i, j, ret = 0;
1119 unsigned int p0[] = {163,7,6,3,0};
1120 unsigned int p1[] = {193,15,0};
1121
1122 a=BN_new();
1123 b[0]=BN_new();
1124 b[1]=BN_new();
1125 c=BN_new();
1126 d=BN_new();
1127 e=BN_new();
1128
1129 BN_GF2m_arr2poly(p0, b[0]);
1130 BN_GF2m_arr2poly(p1, b[1]);
1131
1132 for (i=0; i<num0; i++)
1133 {
1134 BN_bntest_rand(a, 1024, 0, 0);
1135 for (j=0; j < 2; j++)
1136 {
1137 BN_GF2m_mod(c, a, b[j]);
1138 #if 0 /* make test uses ouput in bc but bc can't handle GF(2^m) arithmetic */
1139 if (bp != NULL)
1140 {
1141 if (!results)
1142 {
1143 BN_print(bp,a);
1144 BIO_puts(bp," % ");
1145 BN_print(bp,b[j]);
1146 BIO_puts(bp," - ");
1147 BN_print(bp,c);
1148 BIO_puts(bp,"\n");
1149 }
1150 }
1151 #endif
1152 BN_GF2m_add(d, a, c);
1153 BN_GF2m_mod(e, d, b[j]);
1154 /* Test that a + (a mod p) mod p == 0. */
1155 if(!BN_is_zero(e))
1156 {
1157 fprintf(stderr,"GF(2^m) modulo test failed!\n");
1158 goto err;
1159 }
1160 }
1161 }
1162 ret = 1;
1163 err:
1164 BN_free(a);
1165 BN_free(b[0]);
1166 BN_free(b[1]);
1167 BN_free(c);
1168 BN_free(d);
1169 BN_free(e);
1170 return ret;
1171 }
1172
test_gf2m_mod_mul(BIO * bp,BN_CTX * ctx)1173 int test_gf2m_mod_mul(BIO *bp,BN_CTX *ctx)
1174 {
1175 BIGNUM *a,*b[2],*c,*d,*e,*f,*g,*h;
1176 int i, j, ret = 0;
1177 unsigned int p0[] = {163,7,6,3,0};
1178 unsigned int p1[] = {193,15,0};
1179
1180 a=BN_new();
1181 b[0]=BN_new();
1182 b[1]=BN_new();
1183 c=BN_new();
1184 d=BN_new();
1185 e=BN_new();
1186 f=BN_new();
1187 g=BN_new();
1188 h=BN_new();
1189
1190 BN_GF2m_arr2poly(p0, b[0]);
1191 BN_GF2m_arr2poly(p1, b[1]);
1192
1193 for (i=0; i<num0; i++)
1194 {
1195 BN_bntest_rand(a, 1024, 0, 0);
1196 BN_bntest_rand(c, 1024, 0, 0);
1197 BN_bntest_rand(d, 1024, 0, 0);
1198 for (j=0; j < 2; j++)
1199 {
1200 BN_GF2m_mod_mul(e, a, c, b[j], ctx);
1201 #if 0 /* make test uses ouput in bc but bc can't handle GF(2^m) arithmetic */
1202 if (bp != NULL)
1203 {
1204 if (!results)
1205 {
1206 BN_print(bp,a);
1207 BIO_puts(bp," * ");
1208 BN_print(bp,c);
1209 BIO_puts(bp," % ");
1210 BN_print(bp,b[j]);
1211 BIO_puts(bp," - ");
1212 BN_print(bp,e);
1213 BIO_puts(bp,"\n");
1214 }
1215 }
1216 #endif
1217 BN_GF2m_add(f, a, d);
1218 BN_GF2m_mod_mul(g, f, c, b[j], ctx);
1219 BN_GF2m_mod_mul(h, d, c, b[j], ctx);
1220 BN_GF2m_add(f, e, g);
1221 BN_GF2m_add(f, f, h);
1222 /* Test that (a+d)*c = a*c + d*c. */
1223 if(!BN_is_zero(f))
1224 {
1225 fprintf(stderr,"GF(2^m) modular multiplication test failed!\n");
1226 goto err;
1227 }
1228 }
1229 }
1230 ret = 1;
1231 err:
1232 BN_free(a);
1233 BN_free(b[0]);
1234 BN_free(b[1]);
1235 BN_free(c);
1236 BN_free(d);
1237 BN_free(e);
1238 BN_free(f);
1239 BN_free(g);
1240 BN_free(h);
1241 return ret;
1242 }
1243
test_gf2m_mod_sqr(BIO * bp,BN_CTX * ctx)1244 int test_gf2m_mod_sqr(BIO *bp,BN_CTX *ctx)
1245 {
1246 BIGNUM *a,*b[2],*c,*d;
1247 int i, j, ret = 0;
1248 unsigned int p0[] = {163,7,6,3,0};
1249 unsigned int p1[] = {193,15,0};
1250
1251 a=BN_new();
1252 b[0]=BN_new();
1253 b[1]=BN_new();
1254 c=BN_new();
1255 d=BN_new();
1256
1257 BN_GF2m_arr2poly(p0, b[0]);
1258 BN_GF2m_arr2poly(p1, b[1]);
1259
1260 for (i=0; i<num0; i++)
1261 {
1262 BN_bntest_rand(a, 1024, 0, 0);
1263 for (j=0; j < 2; j++)
1264 {
1265 BN_GF2m_mod_sqr(c, a, b[j], ctx);
1266 BN_copy(d, a);
1267 BN_GF2m_mod_mul(d, a, d, b[j], ctx);
1268 #if 0 /* make test uses ouput in bc but bc can't handle GF(2^m) arithmetic */
1269 if (bp != NULL)
1270 {
1271 if (!results)
1272 {
1273 BN_print(bp,a);
1274 BIO_puts(bp," ^ 2 % ");
1275 BN_print(bp,b[j]);
1276 BIO_puts(bp, " = ");
1277 BN_print(bp,c);
1278 BIO_puts(bp,"; a * a = ");
1279 BN_print(bp,d);
1280 BIO_puts(bp,"\n");
1281 }
1282 }
1283 #endif
1284 BN_GF2m_add(d, c, d);
1285 /* Test that a*a = a^2. */
1286 if(!BN_is_zero(d))
1287 {
1288 fprintf(stderr,"GF(2^m) modular squaring test failed!\n");
1289 goto err;
1290 }
1291 }
1292 }
1293 ret = 1;
1294 err:
1295 BN_free(a);
1296 BN_free(b[0]);
1297 BN_free(b[1]);
1298 BN_free(c);
1299 BN_free(d);
1300 return ret;
1301 }
1302
test_gf2m_mod_inv(BIO * bp,BN_CTX * ctx)1303 int test_gf2m_mod_inv(BIO *bp,BN_CTX *ctx)
1304 {
1305 BIGNUM *a,*b[2],*c,*d;
1306 int i, j, ret = 0;
1307 unsigned int p0[] = {163,7,6,3,0};
1308 unsigned int p1[] = {193,15,0};
1309
1310 a=BN_new();
1311 b[0]=BN_new();
1312 b[1]=BN_new();
1313 c=BN_new();
1314 d=BN_new();
1315
1316 BN_GF2m_arr2poly(p0, b[0]);
1317 BN_GF2m_arr2poly(p1, b[1]);
1318
1319 for (i=0; i<num0; i++)
1320 {
1321 BN_bntest_rand(a, 512, 0, 0);
1322 for (j=0; j < 2; j++)
1323 {
1324 BN_GF2m_mod_inv(c, a, b[j], ctx);
1325 BN_GF2m_mod_mul(d, a, c, b[j], ctx);
1326 #if 0 /* make test uses ouput in bc but bc can't handle GF(2^m) arithmetic */
1327 if (bp != NULL)
1328 {
1329 if (!results)
1330 {
1331 BN_print(bp,a);
1332 BIO_puts(bp, " * ");
1333 BN_print(bp,c);
1334 BIO_puts(bp," - 1 % ");
1335 BN_print(bp,b[j]);
1336 BIO_puts(bp,"\n");
1337 }
1338 }
1339 #endif
1340 /* Test that ((1/a)*a) = 1. */
1341 if(!BN_is_one(d))
1342 {
1343 fprintf(stderr,"GF(2^m) modular inversion test failed!\n");
1344 goto err;
1345 }
1346 }
1347 }
1348 ret = 1;
1349 err:
1350 BN_free(a);
1351 BN_free(b[0]);
1352 BN_free(b[1]);
1353 BN_free(c);
1354 BN_free(d);
1355 return ret;
1356 }
1357
test_gf2m_mod_div(BIO * bp,BN_CTX * ctx)1358 int test_gf2m_mod_div(BIO *bp,BN_CTX *ctx)
1359 {
1360 BIGNUM *a,*b[2],*c,*d,*e,*f;
1361 int i, j, ret = 0;
1362 unsigned int p0[] = {163,7,6,3,0};
1363 unsigned int p1[] = {193,15,0};
1364
1365 a=BN_new();
1366 b[0]=BN_new();
1367 b[1]=BN_new();
1368 c=BN_new();
1369 d=BN_new();
1370 e=BN_new();
1371 f=BN_new();
1372
1373 BN_GF2m_arr2poly(p0, b[0]);
1374 BN_GF2m_arr2poly(p1, b[1]);
1375
1376 for (i=0; i<num0; i++)
1377 {
1378 BN_bntest_rand(a, 512, 0, 0);
1379 BN_bntest_rand(c, 512, 0, 0);
1380 for (j=0; j < 2; j++)
1381 {
1382 BN_GF2m_mod_div(d, a, c, b[j], ctx);
1383 BN_GF2m_mod_mul(e, d, c, b[j], ctx);
1384 BN_GF2m_mod_div(f, a, e, b[j], ctx);
1385 #if 0 /* make test uses ouput in bc but bc can't handle GF(2^m) arithmetic */
1386 if (bp != NULL)
1387 {
1388 if (!results)
1389 {
1390 BN_print(bp,a);
1391 BIO_puts(bp, " = ");
1392 BN_print(bp,c);
1393 BIO_puts(bp," * ");
1394 BN_print(bp,d);
1395 BIO_puts(bp, " % ");
1396 BN_print(bp,b[j]);
1397 BIO_puts(bp,"\n");
1398 }
1399 }
1400 #endif
1401 /* Test that ((a/c)*c)/a = 1. */
1402 if(!BN_is_one(f))
1403 {
1404 fprintf(stderr,"GF(2^m) modular division test failed!\n");
1405 goto err;
1406 }
1407 }
1408 }
1409 ret = 1;
1410 err:
1411 BN_free(a);
1412 BN_free(b[0]);
1413 BN_free(b[1]);
1414 BN_free(c);
1415 BN_free(d);
1416 BN_free(e);
1417 BN_free(f);
1418 return ret;
1419 }
1420
test_gf2m_mod_exp(BIO * bp,BN_CTX * ctx)1421 int test_gf2m_mod_exp(BIO *bp,BN_CTX *ctx)
1422 {
1423 BIGNUM *a,*b[2],*c,*d,*e,*f;
1424 int i, j, ret = 0;
1425 unsigned int p0[] = {163,7,6,3,0};
1426 unsigned int p1[] = {193,15,0};
1427
1428 a=BN_new();
1429 b[0]=BN_new();
1430 b[1]=BN_new();
1431 c=BN_new();
1432 d=BN_new();
1433 e=BN_new();
1434 f=BN_new();
1435
1436 BN_GF2m_arr2poly(p0, b[0]);
1437 BN_GF2m_arr2poly(p1, b[1]);
1438
1439 for (i=0; i<num0; i++)
1440 {
1441 BN_bntest_rand(a, 512, 0, 0);
1442 BN_bntest_rand(c, 512, 0, 0);
1443 BN_bntest_rand(d, 512, 0, 0);
1444 for (j=0; j < 2; j++)
1445 {
1446 BN_GF2m_mod_exp(e, a, c, b[j], ctx);
1447 BN_GF2m_mod_exp(f, a, d, b[j], ctx);
1448 BN_GF2m_mod_mul(e, e, f, b[j], ctx);
1449 BN_add(f, c, d);
1450 BN_GF2m_mod_exp(f, a, f, b[j], ctx);
1451 #if 0 /* make test uses ouput in bc but bc can't handle GF(2^m) arithmetic */
1452 if (bp != NULL)
1453 {
1454 if (!results)
1455 {
1456 BN_print(bp,a);
1457 BIO_puts(bp, " ^ (");
1458 BN_print(bp,c);
1459 BIO_puts(bp," + ");
1460 BN_print(bp,d);
1461 BIO_puts(bp, ") = ");
1462 BN_print(bp,e);
1463 BIO_puts(bp, "; - ");
1464 BN_print(bp,f);
1465 BIO_puts(bp, " % ");
1466 BN_print(bp,b[j]);
1467 BIO_puts(bp,"\n");
1468 }
1469 }
1470 #endif
1471 BN_GF2m_add(f, e, f);
1472 /* Test that a^(c+d)=a^c*a^d. */
1473 if(!BN_is_zero(f))
1474 {
1475 fprintf(stderr,"GF(2^m) modular exponentiation test failed!\n");
1476 goto err;
1477 }
1478 }
1479 }
1480 ret = 1;
1481 err:
1482 BN_free(a);
1483 BN_free(b[0]);
1484 BN_free(b[1]);
1485 BN_free(c);
1486 BN_free(d);
1487 BN_free(e);
1488 BN_free(f);
1489 return ret;
1490 }
1491
test_gf2m_mod_sqrt(BIO * bp,BN_CTX * ctx)1492 int test_gf2m_mod_sqrt(BIO *bp,BN_CTX *ctx)
1493 {
1494 BIGNUM *a,*b[2],*c,*d,*e,*f;
1495 int i, j, ret = 0;
1496 unsigned int p0[] = {163,7,6,3,0};
1497 unsigned int p1[] = {193,15,0};
1498
1499 a=BN_new();
1500 b[0]=BN_new();
1501 b[1]=BN_new();
1502 c=BN_new();
1503 d=BN_new();
1504 e=BN_new();
1505 f=BN_new();
1506
1507 BN_GF2m_arr2poly(p0, b[0]);
1508 BN_GF2m_arr2poly(p1, b[1]);
1509
1510 for (i=0; i<num0; i++)
1511 {
1512 BN_bntest_rand(a, 512, 0, 0);
1513 for (j=0; j < 2; j++)
1514 {
1515 BN_GF2m_mod(c, a, b[j]);
1516 BN_GF2m_mod_sqrt(d, a, b[j], ctx);
1517 BN_GF2m_mod_sqr(e, d, b[j], ctx);
1518 #if 0 /* make test uses ouput in bc but bc can't handle GF(2^m) arithmetic */
1519 if (bp != NULL)
1520 {
1521 if (!results)
1522 {
1523 BN_print(bp,d);
1524 BIO_puts(bp, " ^ 2 - ");
1525 BN_print(bp,a);
1526 BIO_puts(bp,"\n");
1527 }
1528 }
1529 #endif
1530 BN_GF2m_add(f, c, e);
1531 /* Test that d^2 = a, where d = sqrt(a). */
1532 if(!BN_is_zero(f))
1533 {
1534 fprintf(stderr,"GF(2^m) modular square root test failed!\n");
1535 goto err;
1536 }
1537 }
1538 }
1539 ret = 1;
1540 err:
1541 BN_free(a);
1542 BN_free(b[0]);
1543 BN_free(b[1]);
1544 BN_free(c);
1545 BN_free(d);
1546 BN_free(e);
1547 BN_free(f);
1548 return ret;
1549 }
1550
test_gf2m_mod_solve_quad(BIO * bp,BN_CTX * ctx)1551 int test_gf2m_mod_solve_quad(BIO *bp,BN_CTX *ctx)
1552 {
1553 BIGNUM *a,*b[2],*c,*d,*e;
1554 int i, j, s = 0, t, ret = 0;
1555 unsigned int p0[] = {163,7,6,3,0};
1556 unsigned int p1[] = {193,15,0};
1557
1558 a=BN_new();
1559 b[0]=BN_new();
1560 b[1]=BN_new();
1561 c=BN_new();
1562 d=BN_new();
1563 e=BN_new();
1564
1565 BN_GF2m_arr2poly(p0, b[0]);
1566 BN_GF2m_arr2poly(p1, b[1]);
1567
1568 for (i=0; i<num0; i++)
1569 {
1570 BN_bntest_rand(a, 512, 0, 0);
1571 for (j=0; j < 2; j++)
1572 {
1573 t = BN_GF2m_mod_solve_quad(c, a, b[j], ctx);
1574 if (t)
1575 {
1576 s++;
1577 BN_GF2m_mod_sqr(d, c, b[j], ctx);
1578 BN_GF2m_add(d, c, d);
1579 BN_GF2m_mod(e, a, b[j]);
1580 #if 0 /* make test uses ouput in bc but bc can't handle GF(2^m) arithmetic */
1581 if (bp != NULL)
1582 {
1583 if (!results)
1584 {
1585 BN_print(bp,c);
1586 BIO_puts(bp, " is root of z^2 + z = ");
1587 BN_print(bp,a);
1588 BIO_puts(bp, " % ");
1589 BN_print(bp,b[j]);
1590 BIO_puts(bp, "\n");
1591 }
1592 }
1593 #endif
1594 BN_GF2m_add(e, e, d);
1595 /* Test that solution of quadratic c satisfies c^2 + c = a. */
1596 if(!BN_is_zero(e))
1597 {
1598 fprintf(stderr,"GF(2^m) modular solve quadratic test failed!\n");
1599 goto err;
1600 }
1601
1602 }
1603 else
1604 {
1605 #if 0 /* make test uses ouput in bc but bc can't handle GF(2^m) arithmetic */
1606 if (bp != NULL)
1607 {
1608 if (!results)
1609 {
1610 BIO_puts(bp, "There are no roots of z^2 + z = ");
1611 BN_print(bp,a);
1612 BIO_puts(bp, " % ");
1613 BN_print(bp,b[j]);
1614 BIO_puts(bp, "\n");
1615 }
1616 }
1617 #endif
1618 }
1619 }
1620 }
1621 if (s == 0)
1622 {
1623 fprintf(stderr,"All %i tests of GF(2^m) modular solve quadratic resulted in no roots;\n", num0);
1624 fprintf(stderr,"this is very unlikely and probably indicates an error.\n");
1625 goto err;
1626 }
1627 ret = 1;
1628 err:
1629 BN_free(a);
1630 BN_free(b[0]);
1631 BN_free(b[1]);
1632 BN_free(c);
1633 BN_free(d);
1634 BN_free(e);
1635 return ret;
1636 }
1637
genprime_cb(int p,int n,BN_GENCB * arg)1638 static int genprime_cb(int p, int n, BN_GENCB *arg)
1639 {
1640 char c='*';
1641
1642 if (p == 0) c='.';
1643 if (p == 1) c='+';
1644 if (p == 2) c='*';
1645 if (p == 3) c='\n';
1646 putc(c, stderr);
1647 fflush(stderr);
1648 return 1;
1649 }
1650
test_kron(BIO * bp,BN_CTX * ctx)1651 int test_kron(BIO *bp, BN_CTX *ctx)
1652 {
1653 BN_GENCB cb;
1654 BIGNUM *a,*b,*r,*t;
1655 int i;
1656 int legendre, kronecker;
1657 int ret = 0;
1658
1659 a = BN_new();
1660 b = BN_new();
1661 r = BN_new();
1662 t = BN_new();
1663 if (a == NULL || b == NULL || r == NULL || t == NULL) goto err;
1664
1665 BN_GENCB_set(&cb, genprime_cb, NULL);
1666
1667 /* We test BN_kronecker(a, b, ctx) just for b odd (Jacobi symbol).
1668 * In this case we know that if b is prime, then BN_kronecker(a, b, ctx)
1669 * is congruent to $a^{(b-1)/2}$, modulo $b$ (Legendre symbol).
1670 * So we generate a random prime b and compare these values
1671 * for a number of random a's. (That is, we run the Solovay-Strassen
1672 * primality test to confirm that b is prime, except that we
1673 * don't want to test whether b is prime but whether BN_kronecker
1674 * works.) */
1675
1676 if (!BN_generate_prime_ex(b, 512, 0, NULL, NULL, &cb)) goto err;
1677 b->neg = rand_neg();
1678 putc('\n', stderr);
1679
1680 for (i = 0; i < num0; i++)
1681 {
1682 if (!BN_bntest_rand(a, 512, 0, 0)) goto err;
1683 a->neg = rand_neg();
1684
1685 /* t := (|b|-1)/2 (note that b is odd) */
1686 if (!BN_copy(t, b)) goto err;
1687 t->neg = 0;
1688 if (!BN_sub_word(t, 1)) goto err;
1689 if (!BN_rshift1(t, t)) goto err;
1690 /* r := a^t mod b */
1691 b->neg=0;
1692
1693 if (!BN_mod_exp_recp(r, a, t, b, ctx)) goto err;
1694 b->neg=1;
1695
1696 if (BN_is_word(r, 1))
1697 legendre = 1;
1698 else if (BN_is_zero(r))
1699 legendre = 0;
1700 else
1701 {
1702 if (!BN_add_word(r, 1)) goto err;
1703 if (0 != BN_ucmp(r, b))
1704 {
1705 fprintf(stderr, "Legendre symbol computation failed\n");
1706 goto err;
1707 }
1708 legendre = -1;
1709 }
1710
1711 kronecker = BN_kronecker(a, b, ctx);
1712 if (kronecker < -1) goto err;
1713 /* we actually need BN_kronecker(a, |b|) */
1714 if (a->neg && b->neg)
1715 kronecker = -kronecker;
1716
1717 if (legendre != kronecker)
1718 {
1719 fprintf(stderr, "legendre != kronecker; a = ");
1720 BN_print_fp(stderr, a);
1721 fprintf(stderr, ", b = ");
1722 BN_print_fp(stderr, b);
1723 fprintf(stderr, "\n");
1724 goto err;
1725 }
1726
1727 putc('.', stderr);
1728 fflush(stderr);
1729 }
1730
1731 putc('\n', stderr);
1732 fflush(stderr);
1733 ret = 1;
1734 err:
1735 if (a != NULL) BN_free(a);
1736 if (b != NULL) BN_free(b);
1737 if (r != NULL) BN_free(r);
1738 if (t != NULL) BN_free(t);
1739 return ret;
1740 }
1741
test_sqrt(BIO * bp,BN_CTX * ctx)1742 int test_sqrt(BIO *bp, BN_CTX *ctx)
1743 {
1744 BN_GENCB cb;
1745 BIGNUM *a,*p,*r;
1746 int i, j;
1747 int ret = 0;
1748
1749 a = BN_new();
1750 p = BN_new();
1751 r = BN_new();
1752 if (a == NULL || p == NULL || r == NULL) goto err;
1753
1754 BN_GENCB_set(&cb, genprime_cb, NULL);
1755
1756 for (i = 0; i < 16; i++)
1757 {
1758 if (i < 8)
1759 {
1760 unsigned primes[8] = { 2, 3, 5, 7, 11, 13, 17, 19 };
1761
1762 if (!BN_set_word(p, primes[i])) goto err;
1763 }
1764 else
1765 {
1766 if (!BN_set_word(a, 32)) goto err;
1767 if (!BN_set_word(r, 2*i + 1)) goto err;
1768
1769 if (!BN_generate_prime_ex(p, 256, 0, a, r, &cb)) goto err;
1770 putc('\n', stderr);
1771 }
1772 p->neg = rand_neg();
1773
1774 for (j = 0; j < num2; j++)
1775 {
1776 /* construct 'a' such that it is a square modulo p,
1777 * but in general not a proper square and not reduced modulo p */
1778 if (!BN_bntest_rand(r, 256, 0, 3)) goto err;
1779 if (!BN_nnmod(r, r, p, ctx)) goto err;
1780 if (!BN_mod_sqr(r, r, p, ctx)) goto err;
1781 if (!BN_bntest_rand(a, 256, 0, 3)) goto err;
1782 if (!BN_nnmod(a, a, p, ctx)) goto err;
1783 if (!BN_mod_sqr(a, a, p, ctx)) goto err;
1784 if (!BN_mul(a, a, r, ctx)) goto err;
1785 if (rand_neg())
1786 if (!BN_sub(a, a, p)) goto err;
1787
1788 if (!BN_mod_sqrt(r, a, p, ctx)) goto err;
1789 if (!BN_mod_sqr(r, r, p, ctx)) goto err;
1790
1791 if (!BN_nnmod(a, a, p, ctx)) goto err;
1792
1793 if (BN_cmp(a, r) != 0)
1794 {
1795 fprintf(stderr, "BN_mod_sqrt failed: a = ");
1796 BN_print_fp(stderr, a);
1797 fprintf(stderr, ", r = ");
1798 BN_print_fp(stderr, r);
1799 fprintf(stderr, ", p = ");
1800 BN_print_fp(stderr, p);
1801 fprintf(stderr, "\n");
1802 goto err;
1803 }
1804
1805 putc('.', stderr);
1806 fflush(stderr);
1807 }
1808
1809 putc('\n', stderr);
1810 fflush(stderr);
1811 }
1812 ret = 1;
1813 err:
1814 if (a != NULL) BN_free(a);
1815 if (p != NULL) BN_free(p);
1816 if (r != NULL) BN_free(r);
1817 return ret;
1818 }
1819
test_lshift(BIO * bp,BN_CTX * ctx,BIGNUM * a_)1820 int test_lshift(BIO *bp,BN_CTX *ctx,BIGNUM *a_)
1821 {
1822 BIGNUM *a,*b,*c,*d;
1823 int i;
1824
1825 b=BN_new();
1826 c=BN_new();
1827 d=BN_new();
1828 BN_one(c);
1829
1830 if(a_)
1831 a=a_;
1832 else
1833 {
1834 a=BN_new();
1835 BN_bntest_rand(a,200,0,0); /**/
1836 a->neg=rand_neg();
1837 }
1838 for (i=0; i<num0; i++)
1839 {
1840 BN_lshift(b,a,i+1);
1841 BN_add(c,c,c);
1842 if (bp != NULL)
1843 {
1844 if (!results)
1845 {
1846 BN_print(bp,a);
1847 BIO_puts(bp," * ");
1848 BN_print(bp,c);
1849 BIO_puts(bp," - ");
1850 }
1851 BN_print(bp,b);
1852 BIO_puts(bp,"\n");
1853 }
1854 BN_mul(d,a,c,ctx);
1855 BN_sub(d,d,b);
1856 if(!BN_is_zero(d))
1857 {
1858 fprintf(stderr,"Left shift test failed!\n");
1859 fprintf(stderr,"a=");
1860 BN_print_fp(stderr,a);
1861 fprintf(stderr,"\nb=");
1862 BN_print_fp(stderr,b);
1863 fprintf(stderr,"\nc=");
1864 BN_print_fp(stderr,c);
1865 fprintf(stderr,"\nd=");
1866 BN_print_fp(stderr,d);
1867 fprintf(stderr,"\n");
1868 return 0;
1869 }
1870 }
1871 BN_free(a);
1872 BN_free(b);
1873 BN_free(c);
1874 BN_free(d);
1875 return(1);
1876 }
1877
test_lshift1(BIO * bp)1878 int test_lshift1(BIO *bp)
1879 {
1880 BIGNUM *a,*b,*c;
1881 int i;
1882
1883 a=BN_new();
1884 b=BN_new();
1885 c=BN_new();
1886
1887 BN_bntest_rand(a,200,0,0); /**/
1888 a->neg=rand_neg();
1889 for (i=0; i<num0; i++)
1890 {
1891 BN_lshift1(b,a);
1892 if (bp != NULL)
1893 {
1894 if (!results)
1895 {
1896 BN_print(bp,a);
1897 BIO_puts(bp," * 2");
1898 BIO_puts(bp," - ");
1899 }
1900 BN_print(bp,b);
1901 BIO_puts(bp,"\n");
1902 }
1903 BN_add(c,a,a);
1904 BN_sub(a,b,c);
1905 if(!BN_is_zero(a))
1906 {
1907 fprintf(stderr,"Left shift one test failed!\n");
1908 return 0;
1909 }
1910
1911 BN_copy(a,b);
1912 }
1913 BN_free(a);
1914 BN_free(b);
1915 BN_free(c);
1916 return(1);
1917 }
1918
test_rshift(BIO * bp,BN_CTX * ctx)1919 int test_rshift(BIO *bp,BN_CTX *ctx)
1920 {
1921 BIGNUM *a,*b,*c,*d,*e;
1922 int i;
1923
1924 a=BN_new();
1925 b=BN_new();
1926 c=BN_new();
1927 d=BN_new();
1928 e=BN_new();
1929 BN_one(c);
1930
1931 BN_bntest_rand(a,200,0,0); /**/
1932 a->neg=rand_neg();
1933 for (i=0; i<num0; i++)
1934 {
1935 BN_rshift(b,a,i+1);
1936 BN_add(c,c,c);
1937 if (bp != NULL)
1938 {
1939 if (!results)
1940 {
1941 BN_print(bp,a);
1942 BIO_puts(bp," / ");
1943 BN_print(bp,c);
1944 BIO_puts(bp," - ");
1945 }
1946 BN_print(bp,b);
1947 BIO_puts(bp,"\n");
1948 }
1949 BN_div(d,e,a,c,ctx);
1950 BN_sub(d,d,b);
1951 if(!BN_is_zero(d))
1952 {
1953 fprintf(stderr,"Right shift test failed!\n");
1954 return 0;
1955 }
1956 }
1957 BN_free(a);
1958 BN_free(b);
1959 BN_free(c);
1960 BN_free(d);
1961 BN_free(e);
1962 return(1);
1963 }
1964
test_rshift1(BIO * bp)1965 int test_rshift1(BIO *bp)
1966 {
1967 BIGNUM *a,*b,*c;
1968 int i;
1969
1970 a=BN_new();
1971 b=BN_new();
1972 c=BN_new();
1973
1974 BN_bntest_rand(a,200,0,0); /**/
1975 a->neg=rand_neg();
1976 for (i=0; i<num0; i++)
1977 {
1978 BN_rshift1(b,a);
1979 if (bp != NULL)
1980 {
1981 if (!results)
1982 {
1983 BN_print(bp,a);
1984 BIO_puts(bp," / 2");
1985 BIO_puts(bp," - ");
1986 }
1987 BN_print(bp,b);
1988 BIO_puts(bp,"\n");
1989 }
1990 BN_sub(c,a,b);
1991 BN_sub(c,c,b);
1992 if(!BN_is_zero(c) && !BN_abs_is_word(c, 1))
1993 {
1994 fprintf(stderr,"Right shift one test failed!\n");
1995 return 0;
1996 }
1997 BN_copy(a,b);
1998 }
1999 BN_free(a);
2000 BN_free(b);
2001 BN_free(c);
2002 return(1);
2003 }
2004
rand_neg(void)2005 int rand_neg(void)
2006 {
2007 static unsigned int neg=0;
2008 static int sign[8]={0,0,0,1,1,0,1,1};
2009
2010 return(sign[(neg++)%8]);
2011 }
2012