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