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