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