9162999c27d3d84a4397159e72d7f8a4c1f9a591
[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         BN_set_word(b,65537);
953 #endif
954         putc('\n', stderr);
955
956         for (i = 0; i < num0; i++)
957                 {
958                 if (!BN_rand(a, 512, 0, 0)) goto err;
959                 a->neg = rand_neg();
960
961                 /* t := (b-1)/2  (note that b is odd) */
962                 if (!BN_copy(t, b)) goto err;
963                 if (!BN_sub_word(t, 1)) goto err;
964                 if (!BN_rshift1(t, t)) goto err;
965                 /* r := a^t mod b */
966 #if 1
967                 if (!BN_mod_exp(r, a, t, b, ctx)) goto err;
968 #elif 0
969                 if (!BN_mod_exp_recp(r, a, t, b, ctx)) goto err;
970 #else
971                 if (!BN_mod_exp_simple(r, a, t, b, ctx)) goto err;
972 #endif
973
974                 if (BN_is_word(r, 1))
975                         legendre = 1;
976                 else
977                         {
978                         if (!BN_add_word(r, 1)) goto err;
979                         if (0 != BN_cmp(r, b))
980                                 {
981                                 fprintf(stderr, "Legendre symbol computation failed\n");
982                                 goto err;
983                                 }
984                         legendre = -1;
985                         }
986
987                 kronecker = BN_kronecker(a, b, ctx);
988                 if (kronecker < -1) goto err;
989                 
990                 if (legendre != kronecker)
991                         {
992                         fprintf(stderr, "legendre != kronecker; a = ");
993                         BN_print_fp(stderr, a);
994                         fprintf(stderr, ", a = ");
995                         BN_print_fp(stderr, b);
996                         fprintf(stderr, "\n");
997                         goto err;
998                         }
999
1000                 putc('.', stderr);
1001                 fflush(stderr);
1002                 }
1003
1004         putc('\n', stderr);
1005         fflush(stderr);
1006         ret = 1;
1007  err:
1008         if (a != NULL) BN_free(a);
1009         if (b != NULL) BN_free(b);
1010         if (r != NULL) BN_free(r);
1011         if (t != NULL) BN_free(t);
1012         return ret;
1013         }
1014
1015 int test_sqrt(BIO *bp, BN_CTX *ctx)
1016         {
1017         BIGNUM *a,*p,*r;
1018         int i, j;
1019         int ret = 0;
1020
1021         a = BN_new();
1022         p = BN_new();
1023         r = BN_new();
1024         if (a == NULL || p == NULL || r == NULL) goto err;
1025         
1026         for (i = 0; i < 16; i++)
1027                 {
1028                 if (i < 8)
1029                         {
1030                         unsigned primes[8] = { 2, 3, 5, 7, 11, 13, 17, 19 };
1031                         
1032                         if (!BN_set_word(p, primes[i])) goto err;
1033                         }
1034                 else
1035                         {
1036                         if (!BN_set_word(a, 32)) goto err;
1037                         if (!BN_set_word(r, 2*i + 1)) goto err;
1038                 
1039                         if (!BN_generate_prime(p, 256, 0, a, r, genprime_cb, NULL)) goto err;
1040                         putc('\n', stderr);
1041                         }
1042
1043                 for (j = 0; j < num2; j++)
1044                         {
1045                         /* construct 'a' such that it is a square modulo p,
1046                          * but in general not a proper square and not reduced modulo p */
1047                         if (!BN_rand(r, 256, 0, 3)) goto err;
1048                         if (!BN_nnmod(r, r, p, ctx)) goto err;
1049                         if (!BN_mod_sqr(r, r, p, ctx)) goto err;
1050                         if (!BN_rand(a, 256, 0, 3)) goto err;
1051                         if (!BN_nnmod(a, a, p, ctx)) goto err;
1052                         if (!BN_mod_sqr(a, a, p, ctx)) goto err;
1053                         if (!BN_mul(a, a, r, ctx)) goto err;
1054
1055                         if (!BN_mod_sqrt(r, a, p, ctx)) goto err;
1056                         if (!BN_mod_sqr(r, r, p, ctx)) goto err;
1057
1058                         if (!BN_nnmod(a, a, p, ctx)) goto err;
1059
1060                         if (BN_cmp(a, r) != 0)
1061                                 {
1062                                 fprintf(stderr, "BN_mod_sqrt failed: a = ");
1063                                 BN_print_fp(stderr, a);
1064                                 fprintf(stderr, ", r = ");
1065                                 BN_print_fp(stderr, r);
1066                                 fprintf(stderr, ", p = ");
1067                                 BN_print_fp(stderr, p);
1068                                 fprintf(stderr, "\n");
1069                                 goto err;
1070                                 }
1071
1072                         putc('.', stderr);
1073                         fflush(stderr);
1074                         }
1075                 
1076                 putc('\n', stderr);
1077                 fflush(stderr);
1078                 }
1079         ret = 1;
1080  err:
1081         if (a != NULL) BN_free(a);
1082         if (p != NULL) BN_free(p);
1083         if (r != NULL) BN_free(r);
1084         return ret;
1085         }
1086
1087 int test_lshift(BIO *bp,BN_CTX *ctx,BIGNUM *a_)
1088         {
1089         BIGNUM *a,*b,*c,*d;
1090         int i;
1091
1092         b=BN_new();
1093         c=BN_new();
1094         d=BN_new();
1095         BN_one(c);
1096
1097         if(a_)
1098             a=a_;
1099         else
1100             {
1101             a=BN_new();
1102             BN_rand(a,200,0,0); /**/
1103             a->neg=rand_neg();
1104             }
1105         for (i=0; i<num0; i++)
1106                 {
1107                 BN_lshift(b,a,i+1);
1108                 BN_add(c,c,c);
1109                 if (bp != NULL)
1110                         {
1111                         if (!results)
1112                                 {
1113                                 BN_print(bp,a);
1114                                 BIO_puts(bp," * ");
1115                                 BN_print(bp,c);
1116                                 BIO_puts(bp," - ");
1117                                 }
1118                         BN_print(bp,b);
1119                         BIO_puts(bp,"\n");
1120                         }
1121                 BN_mul(d,a,c,ctx);
1122                 BN_sub(d,d,b);
1123                 if(!BN_is_zero(d))
1124                     {
1125                     fprintf(stderr,"Left shift test failed!\n");
1126                     fprintf(stderr,"a=");
1127                     BN_print_fp(stderr,a);
1128                     fprintf(stderr,"\nb=");
1129                     BN_print_fp(stderr,b);
1130                     fprintf(stderr,"\nc=");
1131                     BN_print_fp(stderr,c);
1132                     fprintf(stderr,"\nd=");
1133                     BN_print_fp(stderr,d);
1134                     fprintf(stderr,"\n");
1135                     return 0;
1136                     }
1137                 }
1138         BN_free(a);
1139         BN_free(b);
1140         BN_free(c);
1141         BN_free(d);
1142         return(1);
1143         }
1144
1145 int test_lshift1(BIO *bp)
1146         {
1147         BIGNUM *a,*b,*c;
1148         int i;
1149
1150         a=BN_new();
1151         b=BN_new();
1152         c=BN_new();
1153
1154         BN_rand(a,200,0,0); /**/
1155         a->neg=rand_neg();
1156         for (i=0; i<num0; i++)
1157                 {
1158                 BN_lshift1(b,a);
1159                 if (bp != NULL)
1160                         {
1161                         if (!results)
1162                                 {
1163                                 BN_print(bp,a);
1164                                 BIO_puts(bp," * 2");
1165                                 BIO_puts(bp," - ");
1166                                 }
1167                         BN_print(bp,b);
1168                         BIO_puts(bp,"\n");
1169                         }
1170                 BN_add(c,a,a);
1171                 BN_sub(a,b,c);
1172                 if(!BN_is_zero(a))
1173                     {
1174                     fprintf(stderr,"Left shift one test failed!\n");
1175                     return 0;
1176                     }
1177                 
1178                 BN_copy(a,b);
1179                 }
1180         BN_free(a);
1181         BN_free(b);
1182         BN_free(c);
1183         return(1);
1184         }
1185
1186 int test_rshift(BIO *bp,BN_CTX *ctx)
1187         {
1188         BIGNUM *a,*b,*c,*d,*e;
1189         int i;
1190
1191         a=BN_new();
1192         b=BN_new();
1193         c=BN_new();
1194         d=BN_new();
1195         e=BN_new();
1196         BN_one(c);
1197
1198         BN_rand(a,200,0,0); /**/
1199         a->neg=rand_neg();
1200         for (i=0; i<num0; i++)
1201                 {
1202                 BN_rshift(b,a,i+1);
1203                 BN_add(c,c,c);
1204                 if (bp != NULL)
1205                         {
1206                         if (!results)
1207                                 {
1208                                 BN_print(bp,a);
1209                                 BIO_puts(bp," / ");
1210                                 BN_print(bp,c);
1211                                 BIO_puts(bp," - ");
1212                                 }
1213                         BN_print(bp,b);
1214                         BIO_puts(bp,"\n");
1215                         }
1216                 BN_div(d,e,a,c,ctx);
1217                 BN_sub(d,d,b);
1218                 if(!BN_is_zero(d))
1219                     {
1220                     fprintf(stderr,"Right shift test failed!\n");
1221                     return 0;
1222                     }
1223                 }
1224         BN_free(a);
1225         BN_free(b);
1226         BN_free(c);
1227         BN_free(d);
1228         BN_free(e);
1229         return(1);
1230         }
1231
1232 int test_rshift1(BIO *bp)
1233         {
1234         BIGNUM *a,*b,*c;
1235         int i;
1236
1237         a=BN_new();
1238         b=BN_new();
1239         c=BN_new();
1240
1241         BN_rand(a,200,0,0); /**/
1242         a->neg=rand_neg();
1243         for (i=0; i<num0; i++)
1244                 {
1245                 BN_rshift1(b,a);
1246                 if (bp != NULL)
1247                         {
1248                         if (!results)
1249                                 {
1250                                 BN_print(bp,a);
1251                                 BIO_puts(bp," / 2");
1252                                 BIO_puts(bp," - ");
1253                                 }
1254                         BN_print(bp,b);
1255                         BIO_puts(bp,"\n");
1256                         }
1257                 BN_sub(c,a,b);
1258                 BN_sub(c,c,b);
1259                 if(!BN_is_zero(c) && !BN_is_one(c))
1260                     {
1261                     fprintf(stderr,"Right shift one test failed!\n");
1262                     return 0;
1263                     }
1264                 BN_copy(a,b);
1265                 }
1266         BN_free(a);
1267         BN_free(b);
1268         BN_free(c);
1269         return(1);
1270         }
1271
1272 int rand_neg(void)
1273         {
1274         static unsigned int neg=0;
1275         static int sign[8]={0,0,0,1,1,0,1,1};
1276
1277         return(sign[(neg++)%8]);
1278         }