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