Remove redundant OPENSSL_NO_DEPRECATED suppression
[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;
694
695         BN_init(&a);
696         BN_init(&c);
697         BN_init(&d);
698         BN_init(&e);
699
700         for (i=0; i<num0; i++)
701                 {
702                 BN_bntest_rand(&a,40+i*10,0,0);
703                 a.neg=rand_neg();
704                 BN_sqr(&c,&a,ctx);
705                 if (bp != NULL)
706                         {
707                         if (!results)
708                                 {
709                                 BN_print(bp,&a);
710                                 BIO_puts(bp," * ");
711                                 BN_print(bp,&a);
712                                 BIO_puts(bp," - ");
713                                 }
714                         BN_print(bp,&c);
715                         BIO_puts(bp,"\n");
716                         }
717                 BN_div(&d,&e,&c,&a,ctx);
718                 BN_sub(&d,&d,&a);
719                 if(!BN_is_zero(&d) || !BN_is_zero(&e))
720                     {
721                     fprintf(stderr,"Square test failed!\n");
722                     return 0;
723                     }
724                 }
725         BN_free(&a);
726         BN_free(&c);
727         BN_free(&d);
728         BN_free(&e);
729         return(1);
730         }
731
732 int test_mont(BIO *bp, BN_CTX *ctx)
733         {
734         BIGNUM a,b,c,d,A,B;
735         BIGNUM n;
736         int i;
737         BN_MONT_CTX *mont;
738
739         BN_init(&a);
740         BN_init(&b);
741         BN_init(&c);
742         BN_init(&d);
743         BN_init(&A);
744         BN_init(&B);
745         BN_init(&n);
746
747         mont=BN_MONT_CTX_new();
748         if (mont == NULL)
749                 return 0;
750
751         BN_bntest_rand(&a,100,0,0); /**/
752         BN_bntest_rand(&b,100,0,0); /**/
753         for (i=0; i<num2; i++)
754                 {
755                 int bits = (200*(i+1))/num2;
756
757                 if (bits == 0)
758                         continue;
759                 BN_bntest_rand(&n,bits,0,1);
760                 BN_MONT_CTX_set(mont,&n,ctx);
761
762                 BN_nnmod(&a,&a,&n,ctx);
763                 BN_nnmod(&b,&b,&n,ctx);
764
765                 BN_to_montgomery(&A,&a,mont,ctx);
766                 BN_to_montgomery(&B,&b,mont,ctx);
767
768                 BN_mod_mul_montgomery(&c,&A,&B,mont,ctx);/**/
769                 BN_from_montgomery(&A,&c,mont,ctx);/**/
770                 if (bp != NULL)
771                         {
772                         if (!results)
773                                 {
774 #ifdef undef
775 fprintf(stderr,"%d * %d %% %d\n",
776 BN_num_bits(&a),
777 BN_num_bits(&b),
778 BN_num_bits(mont->N));
779 #endif
780                                 BN_print(bp,&a);
781                                 BIO_puts(bp," * ");
782                                 BN_print(bp,&b);
783                                 BIO_puts(bp," % ");
784                                 BN_print(bp,&(mont->N));
785                                 BIO_puts(bp," - ");
786                                 }
787                         BN_print(bp,&A);
788                         BIO_puts(bp,"\n");
789                         }
790                 BN_mod_mul(&d,&a,&b,&n,ctx);
791                 BN_sub(&d,&d,&A);
792                 if(!BN_is_zero(&d))
793                     {
794                     fprintf(stderr,"Montgomery multiplication test failed!\n");
795                     return 0;
796                     }
797                 }
798         BN_MONT_CTX_free(mont);
799         BN_free(&a);
800         BN_free(&b);
801         BN_free(&c);
802         BN_free(&d);
803         BN_free(&A);
804         BN_free(&B);
805         BN_free(&n);
806         return(1);
807         }
808
809 int test_mod(BIO *bp, BN_CTX *ctx)
810         {
811         BIGNUM *a,*b,*c,*d,*e;
812         int i;
813
814         a=BN_new();
815         b=BN_new();
816         c=BN_new();
817         d=BN_new();
818         e=BN_new();
819
820         BN_bntest_rand(a,1024,0,0); /**/
821         for (i=0; i<num0; i++)
822                 {
823                 BN_bntest_rand(b,450+i*10,0,0); /**/
824                 a->neg=rand_neg();
825                 b->neg=rand_neg();
826                 BN_mod(c,a,b,ctx);/**/
827                 if (bp != NULL)
828                         {
829                         if (!results)
830                                 {
831                                 BN_print(bp,a);
832                                 BIO_puts(bp," % ");
833                                 BN_print(bp,b);
834                                 BIO_puts(bp," - ");
835                                 }
836                         BN_print(bp,c);
837                         BIO_puts(bp,"\n");
838                         }
839                 BN_div(d,e,a,b,ctx);
840                 BN_sub(e,e,c);
841                 if(!BN_is_zero(e))
842                     {
843                     fprintf(stderr,"Modulo test failed!\n");
844                     return 0;
845                     }
846                 }
847         BN_free(a);
848         BN_free(b);
849         BN_free(c);
850         BN_free(d);
851         BN_free(e);
852         return(1);
853         }
854
855 int test_mod_mul(BIO *bp, BN_CTX *ctx)
856         {
857         BIGNUM *a,*b,*c,*d,*e;
858         int i,j;
859
860         a=BN_new();
861         b=BN_new();
862         c=BN_new();
863         d=BN_new();
864         e=BN_new();
865
866         for (j=0; j<3; j++) {
867         BN_bntest_rand(c,1024,0,0); /**/
868         for (i=0; i<num0; i++)
869                 {
870                 BN_bntest_rand(a,475+i*10,0,0); /**/
871                 BN_bntest_rand(b,425+i*11,0,0); /**/
872                 a->neg=rand_neg();
873                 b->neg=rand_neg();
874                 if (!BN_mod_mul(e,a,b,c,ctx))
875                         {
876                         unsigned long l;
877
878                         while ((l=ERR_get_error()))
879                                 fprintf(stderr,"ERROR:%s\n",
880                                         ERR_error_string(l,NULL));
881                         EXIT(1);
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                                 BN_print(bp,c);
892                                 if ((a->neg ^ b->neg) && !BN_is_zero(e))
893                                         {
894                                         /* If  (a*b) % c  is negative,  c  must be added
895                                          * in order to obtain the normalized remainder
896                                          * (new with OpenSSL 0.9.7, previous versions of
897                                          * BN_mod_mul could generate negative results)
898                                          */
899                                         BIO_puts(bp," + ");
900                                         BN_print(bp,c);
901                                         }
902                                 BIO_puts(bp," - ");
903                                 }
904                         BN_print(bp,e);
905                         BIO_puts(bp,"\n");
906                         }
907                 BN_mul(d,a,b,ctx);
908                 BN_sub(d,d,e);
909                 BN_div(a,b,d,c,ctx);
910                 if(!BN_is_zero(b))
911                     {
912                     fprintf(stderr,"Modulo multiply test failed!\n");
913                     ERR_print_errors_fp(stderr);
914                     return 0;
915                     }
916                 }
917         }
918         BN_free(a);
919         BN_free(b);
920         BN_free(c);
921         BN_free(d);
922         BN_free(e);
923         return(1);
924         }
925
926 int test_mod_exp(BIO *bp, BN_CTX *ctx)
927         {
928         BIGNUM *a,*b,*c,*d,*e;
929         int i;
930
931         a=BN_new();
932         b=BN_new();
933         c=BN_new();
934         d=BN_new();
935         e=BN_new();
936
937         BN_bntest_rand(c,30,0,1); /* must be odd for montgomery */
938         for (i=0; i<num2; i++)
939                 {
940                 BN_bntest_rand(a,20+i*5,0,0); /**/
941                 BN_bntest_rand(b,2+i,0,0); /**/
942
943                 if (!BN_mod_exp(d,a,b,c,ctx))
944                         return(0);
945
946                 if (bp != NULL)
947                         {
948                         if (!results)
949                                 {
950                                 BN_print(bp,a);
951                                 BIO_puts(bp," ^ ");
952                                 BN_print(bp,b);
953                                 BIO_puts(bp," % ");
954                                 BN_print(bp,c);
955                                 BIO_puts(bp," - ");
956                                 }
957                         BN_print(bp,d);
958                         BIO_puts(bp,"\n");
959                         }
960                 BN_exp(e,a,b,ctx);
961                 BN_sub(e,e,d);
962                 BN_div(a,b,e,c,ctx);
963                 if(!BN_is_zero(b))
964                     {
965                     fprintf(stderr,"Modulo exponentiation test failed!\n");
966                     return 0;
967                     }
968                 }
969         BN_free(a);
970         BN_free(b);
971         BN_free(c);
972         BN_free(d);
973         BN_free(e);
974         return(1);
975         }
976
977 int test_mod_exp_mont_consttime(BIO *bp, BN_CTX *ctx)
978         {
979         BIGNUM *a,*b,*c,*d,*e;
980         int i;
981
982         a=BN_new();
983         b=BN_new();
984         c=BN_new();
985         d=BN_new();
986         e=BN_new();
987
988         BN_bntest_rand(c,30,0,1); /* must be odd for montgomery */
989         for (i=0; i<num2; i++)
990                 {
991                 BN_bntest_rand(a,20+i*5,0,0); /**/
992                 BN_bntest_rand(b,2+i,0,0); /**/
993
994                 if (!BN_mod_exp_mont_consttime(d,a,b,c,ctx,NULL))
995                         return(00);
996
997                 if (bp != NULL)
998                         {
999                         if (!results)
1000                                 {
1001                                 BN_print(bp,a);
1002                                 BIO_puts(bp," ^ ");
1003                                 BN_print(bp,b);
1004                                 BIO_puts(bp," % ");
1005                                 BN_print(bp,c);
1006                                 BIO_puts(bp," - ");
1007                                 }
1008                         BN_print(bp,d);
1009                         BIO_puts(bp,"\n");
1010                         }
1011                 BN_exp(e,a,b,ctx);
1012                 BN_sub(e,e,d);
1013                 BN_div(a,b,e,c,ctx);
1014                 if(!BN_is_zero(b))
1015                     {
1016                     fprintf(stderr,"Modulo exponentiation test failed!\n");
1017                     return 0;
1018                     }
1019                 }
1020         BN_free(a);
1021         BN_free(b);
1022         BN_free(c);
1023         BN_free(d);
1024         BN_free(e);
1025         return(1);
1026         }
1027
1028 /* Test constant-time modular exponentiation with 1024-bit inputs,
1029  * which on x86_64 cause a different code branch to be taken.
1030  */
1031 int test_mod_exp_mont5(BIO *bp, BN_CTX *ctx)
1032         {
1033         BIGNUM *a,*p,*m,*d,*e;
1034
1035         BN_MONT_CTX *mont;
1036
1037         a=BN_new();
1038         p=BN_new();
1039         m=BN_new();
1040         d=BN_new();
1041         e=BN_new();
1042
1043         mont = BN_MONT_CTX_new();
1044
1045         BN_bntest_rand(m,1024,0,1); /* must be odd for montgomery */
1046         /* Zero exponent */
1047         BN_bntest_rand(a,1024,0,0);
1048         BN_zero(p);
1049         if(!BN_mod_exp_mont_consttime(d,a,p,m,ctx,NULL))
1050                 return 0;
1051         if(!BN_is_one(d))
1052                 {
1053                 fprintf(stderr, "Modular exponentiation test failed!\n");
1054                 return 0;
1055                 }
1056         /* Zero input */
1057         BN_bntest_rand(p,1024,0,0);
1058         BN_zero(a);
1059         if(!BN_mod_exp_mont_consttime(d,a,p,m,ctx,NULL))
1060                 return 0;
1061         if(!BN_is_zero(d))
1062                 {
1063                 fprintf(stderr, "Modular exponentiation test failed!\n");
1064                 return 0;
1065                 }
1066         /* Craft an input whose Montgomery representation is 1,
1067          * i.e., shorter than the modulus m, in order to test
1068          * the const time precomputation scattering/gathering.
1069          */
1070         BN_one(a);
1071         BN_MONT_CTX_set(mont,m,ctx);
1072         if(!BN_from_montgomery(e,a,mont,ctx))
1073                 return 0;
1074         if(!BN_mod_exp_mont_consttime(d,e,p,m,ctx,NULL))
1075                 return 0;
1076         if(!BN_mod_exp_simple(a,e,p,m,ctx))
1077                 return 0;
1078         if(BN_cmp(a,d) != 0)
1079                 {
1080                 fprintf(stderr,"Modular exponentiation test failed!\n");
1081                 return 0;
1082                 }
1083         /* Finally, some regular test vectors. */
1084         BN_bntest_rand(e,1024,0,0);
1085         if(!BN_mod_exp_mont_consttime(d,e,p,m,ctx,NULL))
1086                 return 0;
1087         if(!BN_mod_exp_simple(a,e,p,m,ctx))
1088                 return 0;
1089         if(BN_cmp(a,d) != 0)
1090                 {
1091                 fprintf(stderr,"Modular exponentiation test failed!\n");
1092                 return 0;
1093                 }
1094         BN_free(a);
1095         BN_free(p);
1096         BN_free(m);
1097         BN_free(d);
1098         BN_free(e);
1099         return(1);
1100         }
1101
1102 int test_exp(BIO *bp, BN_CTX *ctx)
1103         {
1104         BIGNUM *a,*b,*d,*e,*one;
1105         int i;
1106
1107         a=BN_new();
1108         b=BN_new();
1109         d=BN_new();
1110         e=BN_new();
1111         one=BN_new();
1112         BN_one(one);
1113
1114         for (i=0; i<num2; i++)
1115                 {
1116                 BN_bntest_rand(a,20+i*5,0,0); /**/
1117                 BN_bntest_rand(b,2+i,0,0); /**/
1118
1119                 if (BN_exp(d,a,b,ctx) <= 0)
1120                         return(0);
1121
1122                 if (bp != NULL)
1123                         {
1124                         if (!results)
1125                                 {
1126                                 BN_print(bp,a);
1127                                 BIO_puts(bp," ^ ");
1128                                 BN_print(bp,b);
1129                                 BIO_puts(bp," - ");
1130                                 }
1131                         BN_print(bp,d);
1132                         BIO_puts(bp,"\n");
1133                         }
1134                 BN_one(e);
1135                 for( ; !BN_is_zero(b) ; BN_sub(b,b,one))
1136                     BN_mul(e,e,a,ctx);
1137                 BN_sub(e,e,d);
1138                 if(!BN_is_zero(e))
1139                     {
1140                     fprintf(stderr,"Exponentiation test failed!\n");
1141                     return 0;
1142                     }
1143                 }
1144         BN_free(a);
1145         BN_free(b);
1146         BN_free(d);
1147         BN_free(e);
1148         BN_free(one);
1149         return(1);
1150         }
1151 #ifndef OPENSSL_NO_EC2M
1152 int test_gf2m_add(BIO *bp)
1153         {
1154         BIGNUM a,b,c;
1155         int i, ret = 0;
1156
1157         BN_init(&a);
1158         BN_init(&b);
1159         BN_init(&c);
1160
1161         for (i=0; i<num0; i++)
1162                 {
1163                 BN_rand(&a,512,0,0);
1164                 BN_copy(&b, BN_value_one());
1165                 a.neg=rand_neg();
1166                 b.neg=rand_neg();
1167                 BN_GF2m_add(&c,&a,&b);
1168 #if 0 /* make test uses ouput in bc but bc can't handle GF(2^m) arithmetic */
1169                 if (bp != NULL)
1170                         {
1171                         if (!results)
1172                                 {
1173                                 BN_print(bp,&a);
1174                                 BIO_puts(bp," ^ ");
1175                                 BN_print(bp,&b);
1176                                 BIO_puts(bp," = ");
1177                                 }
1178                         BN_print(bp,&c);
1179                         BIO_puts(bp,"\n");
1180                         }
1181 #endif
1182                 /* Test that two added values have the correct parity. */
1183                 if((BN_is_odd(&a) && BN_is_odd(&c)) || (!BN_is_odd(&a) && !BN_is_odd(&c)))
1184                         {
1185                     fprintf(stderr,"GF(2^m) addition test (a) failed!\n");
1186                         goto err;
1187                         }
1188                 BN_GF2m_add(&c,&c,&c);
1189                 /* Test that c + c = 0. */
1190                 if(!BN_is_zero(&c))
1191                     {
1192                     fprintf(stderr,"GF(2^m) addition test (b) failed!\n");
1193                         goto err;
1194                     }
1195                 }
1196         ret = 1;
1197   err:
1198         BN_free(&a);
1199         BN_free(&b);
1200         BN_free(&c);
1201         return ret;
1202         }
1203
1204 int test_gf2m_mod(BIO *bp)
1205         {
1206         BIGNUM *a,*b[2],*c,*d,*e;
1207         int i, j, ret = 0;
1208         int p0[] = {163,7,6,3,0,-1};
1209         int p1[] = {193,15,0,-1};
1210
1211         a=BN_new();
1212         b[0]=BN_new();
1213         b[1]=BN_new();
1214         c=BN_new();
1215         d=BN_new();
1216         e=BN_new();
1217
1218         BN_GF2m_arr2poly(p0, b[0]);
1219         BN_GF2m_arr2poly(p1, b[1]);
1220
1221         for (i=0; i<num0; i++)
1222                 {
1223                 BN_bntest_rand(a, 1024, 0, 0);
1224                 for (j=0; j < 2; j++)
1225                         {
1226                         BN_GF2m_mod(c, a, b[j]);
1227 #if 0 /* make test uses ouput in bc but bc can't handle GF(2^m) arithmetic */
1228                         if (bp != NULL)
1229                                 {
1230                                 if (!results)
1231                                         {
1232                                         BN_print(bp,a);
1233                                         BIO_puts(bp," % ");
1234                                         BN_print(bp,b[j]);
1235                                         BIO_puts(bp," - ");
1236                                         BN_print(bp,c);
1237                                         BIO_puts(bp,"\n");
1238                                         }
1239                                 }
1240 #endif
1241                         BN_GF2m_add(d, a, c);
1242                         BN_GF2m_mod(e, d, b[j]);
1243                         /* Test that a + (a mod p) mod p == 0. */
1244                         if(!BN_is_zero(e))
1245                                 {
1246                                 fprintf(stderr,"GF(2^m) modulo test failed!\n");
1247                                 goto err;
1248                                 }
1249                         }
1250                 }
1251         ret = 1;
1252   err:
1253         BN_free(a);
1254         BN_free(b[0]);
1255         BN_free(b[1]);
1256         BN_free(c);
1257         BN_free(d);
1258         BN_free(e);
1259         return ret;
1260         }
1261
1262 int test_gf2m_mod_mul(BIO *bp,BN_CTX *ctx)
1263         {
1264         BIGNUM *a,*b[2],*c,*d,*e,*f,*g,*h;
1265         int i, j, ret = 0;
1266         int p0[] = {163,7,6,3,0,-1};
1267         int p1[] = {193,15,0,-1};
1268
1269         a=BN_new();
1270         b[0]=BN_new();
1271         b[1]=BN_new();
1272         c=BN_new();
1273         d=BN_new();
1274         e=BN_new();
1275         f=BN_new();
1276         g=BN_new();
1277         h=BN_new();
1278
1279         BN_GF2m_arr2poly(p0, b[0]);
1280         BN_GF2m_arr2poly(p1, b[1]);
1281
1282         for (i=0; i<num0; i++)
1283                 {
1284                 BN_bntest_rand(a, 1024, 0, 0);
1285                 BN_bntest_rand(c, 1024, 0, 0);
1286                 BN_bntest_rand(d, 1024, 0, 0);
1287                 for (j=0; j < 2; j++)
1288                         {
1289                         BN_GF2m_mod_mul(e, a, c, b[j], ctx);
1290 #if 0 /* make test uses ouput in bc but bc can't handle GF(2^m) arithmetic */
1291                         if (bp != NULL)
1292                                 {
1293                                 if (!results)
1294                                         {
1295                                         BN_print(bp,a);
1296                                         BIO_puts(bp," * ");
1297                                         BN_print(bp,c);
1298                                         BIO_puts(bp," % ");
1299                                         BN_print(bp,b[j]);
1300                                         BIO_puts(bp," - ");
1301                                         BN_print(bp,e);
1302                                         BIO_puts(bp,"\n");
1303                                         }
1304                                 }
1305 #endif
1306                         BN_GF2m_add(f, a, d);
1307                         BN_GF2m_mod_mul(g, f, c, b[j], ctx);
1308                         BN_GF2m_mod_mul(h, d, c, b[j], ctx);
1309                         BN_GF2m_add(f, e, g);
1310                         BN_GF2m_add(f, f, h);
1311                         /* Test that (a+d)*c = a*c + d*c. */
1312                         if(!BN_is_zero(f))
1313                                 {
1314                                 fprintf(stderr,"GF(2^m) modular multiplication test failed!\n");
1315                                 goto err;
1316                                 }
1317                         }
1318                 }
1319         ret = 1;
1320   err:
1321         BN_free(a);
1322         BN_free(b[0]);
1323         BN_free(b[1]);
1324         BN_free(c);
1325         BN_free(d);
1326         BN_free(e);
1327         BN_free(f);
1328         BN_free(g);
1329         BN_free(h);
1330         return ret;
1331         }
1332
1333 int test_gf2m_mod_sqr(BIO *bp,BN_CTX *ctx)
1334         {
1335         BIGNUM *a,*b[2],*c,*d;
1336         int i, j, ret = 0;
1337         int p0[] = {163,7,6,3,0,-1};
1338         int p1[] = {193,15,0,-1};
1339
1340         a=BN_new();
1341         b[0]=BN_new();
1342         b[1]=BN_new();
1343         c=BN_new();
1344         d=BN_new();
1345
1346         BN_GF2m_arr2poly(p0, b[0]);
1347         BN_GF2m_arr2poly(p1, b[1]);
1348
1349         for (i=0; i<num0; i++)
1350                 {
1351                 BN_bntest_rand(a, 1024, 0, 0);
1352                 for (j=0; j < 2; j++)
1353                         {
1354                         BN_GF2m_mod_sqr(c, a, b[j], ctx);
1355                         BN_copy(d, a);
1356                         BN_GF2m_mod_mul(d, a, d, b[j], ctx);
1357 #if 0 /* make test uses ouput in bc but bc can't handle GF(2^m) arithmetic */
1358                         if (bp != NULL)
1359                                 {
1360                                 if (!results)
1361                                         {
1362                                         BN_print(bp,a);
1363                                         BIO_puts(bp," ^ 2 % ");
1364                                         BN_print(bp,b[j]);
1365                                         BIO_puts(bp, " = ");
1366                                         BN_print(bp,c);
1367                                         BIO_puts(bp,"; a * a = ");
1368                                         BN_print(bp,d);
1369                                         BIO_puts(bp,"\n");
1370                                         }
1371                                 }
1372 #endif
1373                         BN_GF2m_add(d, c, d);
1374                         /* Test that a*a = a^2. */
1375                         if(!BN_is_zero(d))
1376                                 {
1377                                 fprintf(stderr,"GF(2^m) modular squaring test failed!\n");
1378                                 goto err;
1379                                 }
1380                         }
1381                 }
1382         ret = 1;
1383   err:
1384         BN_free(a);
1385         BN_free(b[0]);
1386         BN_free(b[1]);
1387         BN_free(c);
1388         BN_free(d);
1389         return ret;
1390         }
1391
1392 int test_gf2m_mod_inv(BIO *bp,BN_CTX *ctx)
1393         {
1394         BIGNUM *a,*b[2],*c,*d;
1395         int i, j, ret = 0;
1396         int p0[] = {163,7,6,3,0,-1};
1397         int p1[] = {193,15,0,-1};
1398
1399         a=BN_new();
1400         b[0]=BN_new();
1401         b[1]=BN_new();
1402         c=BN_new();
1403         d=BN_new();
1404
1405         BN_GF2m_arr2poly(p0, b[0]);
1406         BN_GF2m_arr2poly(p1, b[1]);
1407
1408         for (i=0; i<num0; i++)
1409                 {
1410                 BN_bntest_rand(a, 512, 0, 0); 
1411                 for (j=0; j < 2; j++)
1412                         {
1413                         BN_GF2m_mod_inv(c, a, b[j], ctx);
1414                         BN_GF2m_mod_mul(d, a, c, b[j], ctx);
1415 #if 0 /* make test uses ouput in bc but bc can't handle GF(2^m) arithmetic */
1416                         if (bp != NULL)
1417                                 {
1418                                 if (!results)
1419                                         {
1420                                         BN_print(bp,a);
1421                                         BIO_puts(bp, " * ");
1422                                         BN_print(bp,c);
1423                                         BIO_puts(bp," - 1 % ");
1424                                         BN_print(bp,b[j]);
1425                                         BIO_puts(bp,"\n");
1426                                         }
1427                                 }
1428 #endif
1429                         /* Test that ((1/a)*a) = 1. */
1430                         if(!BN_is_one(d))
1431                                 {
1432                                 fprintf(stderr,"GF(2^m) modular inversion test failed!\n");
1433                                 goto err;
1434                                 }
1435                         }
1436                 }
1437         ret = 1;
1438   err:
1439         BN_free(a);
1440         BN_free(b[0]);
1441         BN_free(b[1]);
1442         BN_free(c);
1443         BN_free(d);
1444         return ret;
1445         }
1446
1447 int test_gf2m_mod_div(BIO *bp,BN_CTX *ctx)
1448         {
1449         BIGNUM *a,*b[2],*c,*d,*e,*f;
1450         int i, j, ret = 0;
1451         int p0[] = {163,7,6,3,0,-1};
1452         int p1[] = {193,15,0,-1};
1453
1454         a=BN_new();
1455         b[0]=BN_new();
1456         b[1]=BN_new();
1457         c=BN_new();
1458         d=BN_new();
1459         e=BN_new();
1460         f=BN_new();
1461
1462         BN_GF2m_arr2poly(p0, b[0]);
1463         BN_GF2m_arr2poly(p1, b[1]);
1464
1465         for (i=0; i<num0; i++)
1466                 {
1467                 BN_bntest_rand(a, 512, 0, 0); 
1468                 BN_bntest_rand(c, 512, 0, 0);
1469                 for (j=0; j < 2; j++)
1470                         {
1471                         BN_GF2m_mod_div(d, a, c, b[j], ctx);
1472                         BN_GF2m_mod_mul(e, d, c, b[j], ctx);
1473                         BN_GF2m_mod_div(f, a, e, b[j], ctx);
1474 #if 0 /* make test uses ouput in bc but bc can't handle GF(2^m) arithmetic */
1475                         if (bp != NULL)
1476                                 {
1477                                 if (!results)
1478                                         {
1479                                         BN_print(bp,a);
1480                                         BIO_puts(bp, " = ");
1481                                         BN_print(bp,c);
1482                                         BIO_puts(bp," * ");
1483                                         BN_print(bp,d);
1484                                         BIO_puts(bp, " % ");
1485                                         BN_print(bp,b[j]);
1486                                         BIO_puts(bp,"\n");
1487                                         }
1488                                 }
1489 #endif
1490                         /* Test that ((a/c)*c)/a = 1. */
1491                         if(!BN_is_one(f))
1492                                 {
1493                                 fprintf(stderr,"GF(2^m) modular division test failed!\n");
1494                                 goto err;
1495                                 }
1496                         }
1497                 }
1498         ret = 1;
1499   err:
1500         BN_free(a);
1501         BN_free(b[0]);
1502         BN_free(b[1]);
1503         BN_free(c);
1504         BN_free(d);
1505         BN_free(e);
1506         BN_free(f);
1507         return ret;
1508         }
1509
1510 int test_gf2m_mod_exp(BIO *bp,BN_CTX *ctx)
1511         {
1512         BIGNUM *a,*b[2],*c,*d,*e,*f;
1513         int i, j, ret = 0;
1514         int p0[] = {163,7,6,3,0,-1};
1515         int p1[] = {193,15,0,-1};
1516
1517         a=BN_new();
1518         b[0]=BN_new();
1519         b[1]=BN_new();
1520         c=BN_new();
1521         d=BN_new();
1522         e=BN_new();
1523         f=BN_new();
1524
1525         BN_GF2m_arr2poly(p0, b[0]);
1526         BN_GF2m_arr2poly(p1, b[1]);
1527
1528         for (i=0; i<num0; i++)
1529                 {
1530                 BN_bntest_rand(a, 512, 0, 0);
1531                 BN_bntest_rand(c, 512, 0, 0);
1532                 BN_bntest_rand(d, 512, 0, 0);
1533                 for (j=0; j < 2; j++)
1534                         {
1535                         BN_GF2m_mod_exp(e, a, c, b[j], ctx);
1536                         BN_GF2m_mod_exp(f, a, d, b[j], ctx);
1537                         BN_GF2m_mod_mul(e, e, f, b[j], ctx);
1538                         BN_add(f, c, d);
1539                         BN_GF2m_mod_exp(f, a, f, b[j], ctx);
1540 #if 0 /* make test uses ouput in bc but bc can't handle GF(2^m) arithmetic */
1541                         if (bp != NULL)
1542                                 {
1543                                 if (!results)
1544                                         {
1545                                         BN_print(bp,a);
1546                                         BIO_puts(bp, " ^ (");
1547                                         BN_print(bp,c);
1548                                         BIO_puts(bp," + ");
1549                                         BN_print(bp,d);
1550                                         BIO_puts(bp, ") = ");
1551                                         BN_print(bp,e);
1552                                         BIO_puts(bp, "; - ");
1553                                         BN_print(bp,f);
1554                                         BIO_puts(bp, " % ");
1555                                         BN_print(bp,b[j]);
1556                                         BIO_puts(bp,"\n");
1557                                         }
1558                                 }
1559 #endif
1560                         BN_GF2m_add(f, e, f);
1561                         /* Test that a^(c+d)=a^c*a^d. */
1562                         if(!BN_is_zero(f))
1563                                 {
1564                                 fprintf(stderr,"GF(2^m) modular exponentiation test failed!\n");
1565                                 goto err;
1566                                 }
1567                         }
1568                 }
1569         ret = 1;
1570   err:
1571         BN_free(a);
1572         BN_free(b[0]);
1573         BN_free(b[1]);
1574         BN_free(c);
1575         BN_free(d);
1576         BN_free(e);
1577         BN_free(f);
1578         return ret;
1579         }
1580
1581 int test_gf2m_mod_sqrt(BIO *bp,BN_CTX *ctx)
1582         {
1583         BIGNUM *a,*b[2],*c,*d,*e,*f;
1584         int i, j, ret = 0;
1585         int p0[] = {163,7,6,3,0,-1};
1586         int p1[] = {193,15,0,-1};
1587
1588         a=BN_new();
1589         b[0]=BN_new();
1590         b[1]=BN_new();
1591         c=BN_new();
1592         d=BN_new();
1593         e=BN_new();
1594         f=BN_new();
1595
1596         BN_GF2m_arr2poly(p0, b[0]);
1597         BN_GF2m_arr2poly(p1, b[1]);
1598
1599         for (i=0; i<num0; i++)
1600                 {
1601                 BN_bntest_rand(a, 512, 0, 0);
1602                 for (j=0; j < 2; j++)
1603                         {
1604                         BN_GF2m_mod(c, a, b[j]);
1605                         BN_GF2m_mod_sqrt(d, a, b[j], ctx);
1606                         BN_GF2m_mod_sqr(e, d, b[j], ctx);
1607 #if 0 /* make test uses ouput in bc but bc can't handle GF(2^m) arithmetic */
1608                         if (bp != NULL)
1609                                 {
1610                                 if (!results)
1611                                         {
1612                                         BN_print(bp,d);
1613                                         BIO_puts(bp, " ^ 2 - ");
1614                                         BN_print(bp,a);
1615                                         BIO_puts(bp,"\n");
1616                                         }
1617                                 }
1618 #endif
1619                         BN_GF2m_add(f, c, e);
1620                         /* Test that d^2 = a, where d = sqrt(a). */
1621                         if(!BN_is_zero(f))
1622                                 {
1623                                 fprintf(stderr,"GF(2^m) modular square root test failed!\n");
1624                                 goto err;
1625                                 }
1626                         }
1627                 }
1628         ret = 1;
1629   err:
1630         BN_free(a);
1631         BN_free(b[0]);
1632         BN_free(b[1]);
1633         BN_free(c);
1634         BN_free(d);
1635         BN_free(e);
1636         BN_free(f);
1637         return ret;
1638         }
1639
1640 int test_gf2m_mod_solve_quad(BIO *bp,BN_CTX *ctx)
1641         {
1642         BIGNUM *a,*b[2],*c,*d,*e;
1643         int i, j, s = 0, t, ret = 0;
1644         int p0[] = {163,7,6,3,0,-1};
1645         int p1[] = {193,15,0,-1};
1646
1647         a=BN_new();
1648         b[0]=BN_new();
1649         b[1]=BN_new();
1650         c=BN_new();
1651         d=BN_new();
1652         e=BN_new();
1653
1654         BN_GF2m_arr2poly(p0, b[0]);
1655         BN_GF2m_arr2poly(p1, b[1]);
1656
1657         for (i=0; i<num0; i++)
1658                 {
1659                 BN_bntest_rand(a, 512, 0, 0);
1660                 for (j=0; j < 2; j++)
1661                         {
1662                         t = BN_GF2m_mod_solve_quad(c, a, b[j], ctx);
1663                         if (t)
1664                                 {
1665                                 s++;
1666                                 BN_GF2m_mod_sqr(d, c, b[j], ctx);
1667                                 BN_GF2m_add(d, c, d);
1668                                 BN_GF2m_mod(e, a, b[j]);
1669 #if 0 /* make test uses ouput in bc but bc can't handle GF(2^m) arithmetic */
1670                                 if (bp != NULL)
1671                                         {
1672                                         if (!results)
1673                                                 {
1674                                                 BN_print(bp,c);
1675                                                 BIO_puts(bp, " is root of z^2 + z = ");
1676                                                 BN_print(bp,a);
1677                                                 BIO_puts(bp, " % ");
1678                                                 BN_print(bp,b[j]);
1679                                                 BIO_puts(bp, "\n");
1680                                                 }
1681                                         }
1682 #endif
1683                                 BN_GF2m_add(e, e, d);
1684                                 /* Test that solution of quadratic c satisfies c^2 + c = a. */
1685                                 if(!BN_is_zero(e))
1686                                         {
1687                                         fprintf(stderr,"GF(2^m) modular solve quadratic test failed!\n");
1688                                         goto err;
1689                                         }
1690
1691                                 }
1692                         else 
1693                                 {
1694 #if 0 /* make test uses ouput in bc but bc can't handle GF(2^m) arithmetic */
1695                                 if (bp != NULL)
1696                                         {
1697                                         if (!results)
1698                                                 {
1699                                                 BIO_puts(bp, "There are no roots of z^2 + z = ");
1700                                                 BN_print(bp,a);
1701                                                 BIO_puts(bp, " % ");
1702                                                 BN_print(bp,b[j]);
1703                                                 BIO_puts(bp, "\n");
1704                                                 }
1705                                         }
1706 #endif
1707                                 }
1708                         }
1709                 }
1710         if (s == 0)
1711                 {       
1712                 fprintf(stderr,"All %i tests of GF(2^m) modular solve quadratic resulted in no roots;\n", num0);
1713                 fprintf(stderr,"this is very unlikely and probably indicates an error.\n");
1714                 goto err;
1715                 }
1716         ret = 1;
1717   err:
1718         BN_free(a);
1719         BN_free(b[0]);
1720         BN_free(b[1]);
1721         BN_free(c);
1722         BN_free(d);
1723         BN_free(e);
1724         return ret;
1725         }
1726 #endif
1727 static int genprime_cb(int p, int n, BN_GENCB *arg)
1728         {
1729         char c='*';
1730
1731         if (p == 0) c='.';
1732         if (p == 1) c='+';
1733         if (p == 2) c='*';
1734         if (p == 3) c='\n';
1735         putc(c, stderr);
1736         fflush(stderr);
1737         return 1;
1738         }
1739
1740 int test_kron(BIO *bp, BN_CTX *ctx)
1741         {
1742         BN_GENCB cb;
1743         BIGNUM *a,*b,*r,*t;
1744         int i;
1745         int legendre, kronecker;
1746         int ret = 0;
1747
1748         a = BN_new();
1749         b = BN_new();
1750         r = BN_new();
1751         t = BN_new();
1752         if (a == NULL || b == NULL || r == NULL || t == NULL) goto err;
1753
1754         BN_GENCB_set(&cb, genprime_cb, NULL);
1755         
1756         /* We test BN_kronecker(a, b, ctx) just for  b  odd (Jacobi symbol).
1757          * In this case we know that if  b  is prime, then BN_kronecker(a, b, ctx)
1758          * is congruent to $a^{(b-1)/2}$, modulo $b$ (Legendre symbol).
1759          * So we generate a random prime  b  and compare these values
1760          * for a number of random  a's.  (That is, we run the Solovay-Strassen
1761          * primality test to confirm that  b  is prime, except that we
1762          * don't want to test whether  b  is prime but whether BN_kronecker
1763          * works.) */
1764
1765         if (!BN_generate_prime_ex(b, 512, 0, NULL, NULL, &cb)) goto err;
1766         b->neg = rand_neg();
1767         putc('\n', stderr);
1768
1769         for (i = 0; i < num0; i++)
1770                 {
1771                 if (!BN_bntest_rand(a, 512, 0, 0)) goto err;
1772                 a->neg = rand_neg();
1773
1774                 /* t := (|b|-1)/2  (note that b is odd) */
1775                 if (!BN_copy(t, b)) goto err;
1776                 t->neg = 0;
1777                 if (!BN_sub_word(t, 1)) goto err;
1778                 if (!BN_rshift1(t, t)) goto err;
1779                 /* r := a^t mod b */
1780                 b->neg=0;
1781                 
1782                 if (!BN_mod_exp_recp(r, a, t, b, ctx)) goto err;
1783                 b->neg=1;
1784
1785                 if (BN_is_word(r, 1))
1786                         legendre = 1;
1787                 else if (BN_is_zero(r))
1788                         legendre = 0;
1789                 else
1790                         {
1791                         if (!BN_add_word(r, 1)) goto err;
1792                         if (0 != BN_ucmp(r, b))
1793                                 {
1794                                 fprintf(stderr, "Legendre symbol computation failed\n");
1795                                 goto err;
1796                                 }
1797                         legendre = -1;
1798                         }
1799                 
1800                 kronecker = BN_kronecker(a, b, ctx);
1801                 if (kronecker < -1) goto err;
1802                 /* we actually need BN_kronecker(a, |b|) */
1803                 if (a->neg && b->neg)
1804                         kronecker = -kronecker;
1805                 
1806                 if (legendre != kronecker)
1807                         {
1808                         fprintf(stderr, "legendre != kronecker; a = ");
1809                         BN_print_fp(stderr, a);
1810                         fprintf(stderr, ", b = ");
1811                         BN_print_fp(stderr, b);
1812                         fprintf(stderr, "\n");
1813                         goto err;
1814                         }
1815
1816                 putc('.', stderr);
1817                 fflush(stderr);
1818                 }
1819
1820         putc('\n', stderr);
1821         fflush(stderr);
1822         ret = 1;
1823  err:
1824         if (a != NULL) BN_free(a);
1825         if (b != NULL) BN_free(b);
1826         if (r != NULL) BN_free(r);
1827         if (t != NULL) BN_free(t);
1828         return ret;
1829         }
1830
1831 int test_sqrt(BIO *bp, BN_CTX *ctx)
1832         {
1833         BN_GENCB cb;
1834         BIGNUM *a,*p,*r;
1835         int i, j;
1836         int ret = 0;
1837
1838         a = BN_new();
1839         p = BN_new();
1840         r = BN_new();
1841         if (a == NULL || p == NULL || r == NULL) goto err;
1842
1843         BN_GENCB_set(&cb, genprime_cb, NULL);
1844
1845         for (i = 0; i < 16; i++)
1846                 {
1847                 if (i < 8)
1848                         {
1849                         unsigned primes[8] = { 2, 3, 5, 7, 11, 13, 17, 19 };
1850                         
1851                         if (!BN_set_word(p, primes[i])) goto err;
1852                         }
1853                 else
1854                         {
1855                         if (!BN_set_word(a, 32)) goto err;
1856                         if (!BN_set_word(r, 2*i + 1)) goto err;
1857                 
1858                         if (!BN_generate_prime_ex(p, 256, 0, a, r, &cb)) goto err;
1859                         putc('\n', stderr);
1860                         }
1861                 p->neg = rand_neg();
1862
1863                 for (j = 0; j < num2; j++)
1864                         {
1865                         /* construct 'a' such that it is a square modulo p,
1866                          * but in general not a proper square and not reduced modulo p */
1867                         if (!BN_bntest_rand(r, 256, 0, 3)) goto err;
1868                         if (!BN_nnmod(r, r, p, ctx)) goto err;
1869                         if (!BN_mod_sqr(r, r, p, ctx)) goto err;
1870                         if (!BN_bntest_rand(a, 256, 0, 3)) goto err;
1871                         if (!BN_nnmod(a, a, p, ctx)) goto err;
1872                         if (!BN_mod_sqr(a, a, p, ctx)) goto err;
1873                         if (!BN_mul(a, a, r, ctx)) goto err;
1874                         if (rand_neg())
1875                                 if (!BN_sub(a, a, p)) goto err;
1876
1877                         if (!BN_mod_sqrt(r, a, p, ctx)) goto err;
1878                         if (!BN_mod_sqr(r, r, p, ctx)) goto err;
1879
1880                         if (!BN_nnmod(a, a, p, ctx)) goto err;
1881
1882                         if (BN_cmp(a, r) != 0)
1883                                 {
1884                                 fprintf(stderr, "BN_mod_sqrt failed: a = ");
1885                                 BN_print_fp(stderr, a);
1886                                 fprintf(stderr, ", r = ");
1887                                 BN_print_fp(stderr, r);
1888                                 fprintf(stderr, ", p = ");
1889                                 BN_print_fp(stderr, p);
1890                                 fprintf(stderr, "\n");
1891                                 goto err;
1892                                 }
1893
1894                         putc('.', stderr);
1895                         fflush(stderr);
1896                         }
1897                 
1898                 putc('\n', stderr);
1899                 fflush(stderr);
1900                 }
1901         ret = 1;
1902  err:
1903         if (a != NULL) BN_free(a);
1904         if (p != NULL) BN_free(p);
1905         if (r != NULL) BN_free(r);
1906         return ret;
1907         }
1908
1909 int test_small_prime(BIO *bp,BN_CTX *ctx)
1910         {
1911         static const int bits = 10;
1912         int ret = 0;
1913         BIGNUM r;
1914
1915         BN_init(&r);
1916         if (!BN_generate_prime_ex(&r, bits, 0, NULL, NULL, NULL))
1917                 goto err;
1918         if (BN_num_bits(&r) != bits)
1919                 {
1920                 BIO_printf(bp, "Expected %d bit prime, got %d bit number\n", bits, BN_num_bits(&r));
1921                 goto err;
1922                 }
1923
1924         ret = 1;
1925
1926 err:
1927         BN_clear(&r);
1928         return ret;
1929         }
1930 #ifndef OPENSSL_SYS_WIN32
1931 int test_probable_prime_coprime(BIO *bp, BN_CTX *ctx)
1932         {
1933         int i, j, ret = 0;
1934         BIGNUM r;
1935         BN_ULONG primes[5] = { 2, 3, 5, 7, 11 };
1936
1937         BN_init(&r);
1938         
1939         for (i = 0; i < 1000; i++)
1940                 {
1941                 if (!bn_probable_prime_dh_coprime(&r, 1024, ctx)) goto err;
1942                 
1943                 for (j = 0; j < 5; j++)
1944                         {
1945                         if (BN_mod_word(&r, primes[j]) == 0)
1946                                 {
1947                                 BIO_printf(bp, "Number generated is not coprime to %ld:\n", primes[j]);
1948                                 BN_print_fp(stdout, &r);
1949                                 BIO_printf(bp, "\n");
1950                                 goto err;
1951                                 }
1952                         }
1953                 }
1954
1955         ret = 1;
1956
1957 err:
1958         BN_clear(&r);
1959         return ret;
1960         }
1961 #endif
1962 int test_lshift(BIO *bp,BN_CTX *ctx,BIGNUM *a_)
1963         {
1964         BIGNUM *a,*b,*c,*d;
1965         int i;
1966
1967         b=BN_new();
1968         c=BN_new();
1969         d=BN_new();
1970         BN_one(c);
1971
1972         if(a_)
1973             a=a_;
1974         else
1975             {
1976             a=BN_new();
1977             BN_bntest_rand(a,200,0,0); /**/
1978             a->neg=rand_neg();
1979             }
1980         for (i=0; i<num0; i++)
1981                 {
1982                 BN_lshift(b,a,i+1);
1983                 BN_add(c,c,c);
1984                 if (bp != NULL)
1985                         {
1986                         if (!results)
1987                                 {
1988                                 BN_print(bp,a);
1989                                 BIO_puts(bp," * ");
1990                                 BN_print(bp,c);
1991                                 BIO_puts(bp," - ");
1992                                 }
1993                         BN_print(bp,b);
1994                         BIO_puts(bp,"\n");
1995                         }
1996                 BN_mul(d,a,c,ctx);
1997                 BN_sub(d,d,b);
1998                 if(!BN_is_zero(d))
1999                     {
2000                     fprintf(stderr,"Left shift test failed!\n");
2001                     fprintf(stderr,"a=");
2002                     BN_print_fp(stderr,a);
2003                     fprintf(stderr,"\nb=");
2004                     BN_print_fp(stderr,b);
2005                     fprintf(stderr,"\nc=");
2006                     BN_print_fp(stderr,c);
2007                     fprintf(stderr,"\nd=");
2008                     BN_print_fp(stderr,d);
2009                     fprintf(stderr,"\n");
2010                     return 0;
2011                     }
2012                 }
2013         BN_free(a);
2014         BN_free(b);
2015         BN_free(c);
2016         BN_free(d);
2017         return(1);
2018         }
2019
2020 int test_lshift1(BIO *bp)
2021         {
2022         BIGNUM *a,*b,*c;
2023         int i;
2024
2025         a=BN_new();
2026         b=BN_new();
2027         c=BN_new();
2028
2029         BN_bntest_rand(a,200,0,0); /**/
2030         a->neg=rand_neg();
2031         for (i=0; i<num0; i++)
2032                 {
2033                 BN_lshift1(b,a);
2034                 if (bp != NULL)
2035                         {
2036                         if (!results)
2037                                 {
2038                                 BN_print(bp,a);
2039                                 BIO_puts(bp," * 2");
2040                                 BIO_puts(bp," - ");
2041                                 }
2042                         BN_print(bp,b);
2043                         BIO_puts(bp,"\n");
2044                         }
2045                 BN_add(c,a,a);
2046                 BN_sub(a,b,c);
2047                 if(!BN_is_zero(a))
2048                     {
2049                     fprintf(stderr,"Left shift one test failed!\n");
2050                     return 0;
2051                     }
2052                 
2053                 BN_copy(a,b);
2054                 }
2055         BN_free(a);
2056         BN_free(b);
2057         BN_free(c);
2058         return(1);
2059         }
2060
2061 int test_rshift(BIO *bp,BN_CTX *ctx)
2062         {
2063         BIGNUM *a,*b,*c,*d,*e;
2064         int i;
2065
2066         a=BN_new();
2067         b=BN_new();
2068         c=BN_new();
2069         d=BN_new();
2070         e=BN_new();
2071         BN_one(c);
2072
2073         BN_bntest_rand(a,200,0,0); /**/
2074         a->neg=rand_neg();
2075         for (i=0; i<num0; i++)
2076                 {
2077                 BN_rshift(b,a,i+1);
2078                 BN_add(c,c,c);
2079                 if (bp != NULL)
2080                         {
2081                         if (!results)
2082                                 {
2083                                 BN_print(bp,a);
2084                                 BIO_puts(bp," / ");
2085                                 BN_print(bp,c);
2086                                 BIO_puts(bp," - ");
2087                                 }
2088                         BN_print(bp,b);
2089                         BIO_puts(bp,"\n");
2090                         }
2091                 BN_div(d,e,a,c,ctx);
2092                 BN_sub(d,d,b);
2093                 if(!BN_is_zero(d))
2094                     {
2095                     fprintf(stderr,"Right shift test failed!\n");
2096                     return 0;
2097                     }
2098                 }
2099         BN_free(a);
2100         BN_free(b);
2101         BN_free(c);
2102         BN_free(d);
2103         BN_free(e);
2104         return(1);
2105         }
2106
2107 int test_rshift1(BIO *bp)
2108         {
2109         BIGNUM *a,*b,*c;
2110         int i;
2111
2112         a=BN_new();
2113         b=BN_new();
2114         c=BN_new();
2115
2116         BN_bntest_rand(a,200,0,0); /**/
2117         a->neg=rand_neg();
2118         for (i=0; i<num0; i++)
2119                 {
2120                 BN_rshift1(b,a);
2121                 if (bp != NULL)
2122                         {
2123                         if (!results)
2124                                 {
2125                                 BN_print(bp,a);
2126                                 BIO_puts(bp," / 2");
2127                                 BIO_puts(bp," - ");
2128                                 }
2129                         BN_print(bp,b);
2130                         BIO_puts(bp,"\n");
2131                         }
2132                 BN_sub(c,a,b);
2133                 BN_sub(c,c,b);
2134                 if(!BN_is_zero(c) && !BN_abs_is_word(c, 1))
2135                     {
2136                     fprintf(stderr,"Right shift one test failed!\n");
2137                     return 0;
2138                     }
2139                 BN_copy(a,b);
2140                 }
2141         BN_free(a);
2142         BN_free(b);
2143         BN_free(c);
2144         return(1);
2145         }
2146
2147 int rand_neg(void)
2148         {
2149         static unsigned int neg=0;
2150         static int sign[8]={0,0,0,1,1,0,1,1};
2151
2152         return(sign[(neg++)%8]);
2153         }