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