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