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