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