76e91e67c04d701a033e595db8a5bc30f7c107bf
[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 #include <assert.h>
10 #include <errno.h>
11 #include <stdio.h>
12 #include <string.h>
13 #include <ctype.h>
14
15 #include "e_os.h"
16 #include <internal/numbers.h>
17 #include <openssl/bn.h>
18 #include <openssl/crypto.h>
19 #include <openssl/err.h>
20 #include <openssl/rand.h>
21 #include "testutil.h"
22 #include "test_main_custom.h"
23
24 /*
25  * In bn_lcl.h, bn_expand() is defined as a static ossl_inline function.
26  * This is fine in itself, it will end up as an unused static function in
27  * the worst case.  However, it references bn_expand2(), which is a private
28  * function in libcrypto and therefore unavailable on some systems.  This
29  * may result in a linker error because of unresolved symbols.
30  *
31  * To avoid this, we define a dummy variant of bn_expand2() here, and to
32  * avoid possible clashes with libcrypto, we rename it first, using a macro.
33  */
34 #define bn_expand2 dummy_bn_expand2
35 BIGNUM *bn_expand2(BIGNUM *b, int words);
36 BIGNUM *bn_expand2(BIGNUM *b, int words) { return NULL; }
37 #include "../crypto/bn/bn_lcl.h"
38
39 #define MAXPAIRS        20
40
41 /*
42  * Things in boring, not in openssl.  TODO we should add them.
43  */
44 #define HAVE_BN_PADDED 0
45 #define HAVE_BN_SQRT 0
46
47 typedef struct pair_st {
48     char *key;
49     char *value;
50 } PAIR;
51
52 typedef struct stanza_st {
53     int start;
54     int numpairs;
55     PAIR pairs[MAXPAIRS];
56 } STANZA;
57
58 typedef struct filetest_st {
59     const char *name;
60     int (*func)(STANZA *s);
61 } FILETEST;
62
63 typedef struct mpitest_st {
64     const char *base10;
65     const char *mpi;
66     size_t mpi_len;
67 } MPITEST;
68
69 static const int NUM0 = 100;           /* number of tests */
70 static const int NUM1 = 50;            /* additional tests for some functions */
71 static FILE *fp;
72 static BN_CTX *ctx;
73
74
75 /*
76  * Look for |key| in the stanza and return it or NULL if not found.
77  */
78 static const char *findattr(STANZA *s, const char *key)
79 {
80     int i = s->numpairs;
81     PAIR *pp = s->pairs;
82
83     for ( ; --i >= 0; pp++)
84         if (strcasecmp(pp->key, key) == 0)
85             return pp->value;
86     return NULL;
87 }
88
89 /*
90  * Parse BIGNUM, return number of bytes parsed.
91  */
92 static int parseBN(BIGNUM **out, const char *in)
93 {
94     *out = NULL;
95     return BN_hex2bn(out, in);
96 }
97
98 static int parsedecBN(BIGNUM **out, const char *in)
99 {
100     *out = NULL;
101     return BN_dec2bn(out, in);
102 }
103
104 static BIGNUM *getBN(STANZA *s, const char *attribute)
105 {
106     const char *hex;
107     BIGNUM *ret = NULL;
108
109     if ((hex = findattr(s, attribute)) == NULL) {
110         fprintf(stderr, "Can't find %s in test at line %d\n",
111                 attribute, s->start);
112         return NULL;
113     }
114
115     if (parseBN(&ret, hex) != (int)strlen(hex)) {
116         fprintf(stderr, "Could not decode '%s'.\n", hex);
117         return NULL;
118     }
119     return ret;
120 }
121
122 static int getint(STANZA *s, int *out, const char *attribute)
123 {
124     BIGNUM *ret = getBN(s, attribute);
125     BN_ULONG word;
126     int st = 0;
127
128     if (ret == NULL)
129         goto err;
130
131     if ((word = BN_get_word(ret)) > INT_MAX)
132         goto err;
133
134     *out = (int)word;
135     st = 1;
136 err:
137     BN_free(ret);
138     return st;
139 }
140
141 static int equalBN(const char *op, const BIGNUM *expected, const BIGNUM *actual)
142 {
143     char *exstr = NULL;
144     char *actstr = NULL;
145
146     if (BN_cmp(expected, actual) == 0)
147         return 1;
148
149     if (BN_is_zero(expected) && BN_is_negative(expected))
150         exstr = OPENSSL_strdup("-0");
151     else
152         exstr = BN_bn2hex(expected);
153     if (BN_is_zero(actual) && BN_is_negative(actual))
154         actstr = OPENSSL_strdup("-0");
155     else
156         actstr = BN_bn2hex(actual);
157     if (exstr == NULL || actstr == NULL)
158         goto err;
159
160     fprintf(stderr, "Got %s =\n", op);
161     fprintf(stderr, "\t%s\n", actstr);
162     fprintf(stderr, "wanted:\n");
163     fprintf(stderr, "\t%s\n", exstr);
164
165 err:
166     OPENSSL_free(exstr);
167     OPENSSL_free(actstr);
168     return 0;
169 }
170
171
172 /*
173  * Return a "random" flag for if a BN should be negated.
174  */
175 static int rand_neg(void)
176 {
177     static unsigned int neg = 0;
178     static int sign[8] = { 0, 0, 0, 1, 1, 0, 1, 1 };
179
180     return sign[(neg++) % 8];
181 }
182
183
184 static int test_sub()
185 {
186     BIGNUM *a, *b, *c;
187     int i;
188
189     a = BN_new();
190     b = BN_new();
191     c = BN_new();
192
193     for (i = 0; i < NUM0 + NUM1; i++) {
194         if (i < NUM1) {
195             BN_bntest_rand(a, 512, 0, 0);
196             BN_copy(b, a);
197             if (BN_set_bit(a, i) == 0)
198                 return 0;
199             BN_add_word(b, i);
200         } else {
201             BN_bntest_rand(b, 400 + i - NUM1, 0, 0);
202             a->neg = rand_neg();
203             b->neg = rand_neg();
204         }
205         BN_sub(c, a, b);
206         BN_add(c, c, b);
207         BN_sub(c, c, a);
208         if (!BN_is_zero(c)) {
209             printf("Subtract test failed!\n");
210             return 0;
211         }
212     }
213     BN_free(a);
214     BN_free(b);
215     BN_free(c);
216     return 1;
217 }
218
219
220 static int test_div_recip()
221 {
222     BIGNUM *a, *b, *c, *d, *e;
223     BN_RECP_CTX *recp;
224     int i;
225
226     recp = BN_RECP_CTX_new();
227     a = BN_new();
228     b = BN_new();
229     c = BN_new();
230     d = BN_new();
231     e = BN_new();
232
233     for (i = 0; i < NUM0 + NUM1; i++) {
234         if (i < NUM1) {
235             BN_bntest_rand(a, 400, 0, 0);
236             BN_copy(b, a);
237             BN_lshift(a, a, i);
238             BN_add_word(a, i);
239         } else
240             BN_bntest_rand(b, 50 + 3 * (i - NUM1), 0, 0);
241         a->neg = rand_neg();
242         b->neg = rand_neg();
243         BN_RECP_CTX_set(recp, b, ctx);
244         BN_div_recp(d, c, a, recp, ctx);
245         BN_mul(e, d, b, ctx);
246         BN_add(d, e, c);
247         BN_sub(d, d, a);
248         if (!BN_is_zero(d)) {
249             printf("Reciprocal division test failed!\n");
250             printf("a=");
251             BN_print_fp(stdout, a);
252             printf("\nb=");
253             BN_print_fp(stdout, b);
254             printf("\n");
255             return 0;
256         }
257     }
258     BN_free(a);
259     BN_free(b);
260     BN_free(c);
261     BN_free(d);
262     BN_free(e);
263     BN_RECP_CTX_free(recp);
264     return 1;
265 }
266
267
268 static int test_mod()
269 {
270     BIGNUM *a, *b, *c, *d, *e;
271     int i;
272
273     a = BN_new();
274     b = BN_new();
275     c = BN_new();
276     d = BN_new();
277     e = BN_new();
278
279     BN_bntest_rand(a, 1024, 0, 0);
280     for (i = 0; i < NUM0; i++) {
281         BN_bntest_rand(b, 450 + i * 10, 0, 0);
282         a->neg = rand_neg();
283         b->neg = rand_neg();
284         BN_mod(c, a, b, ctx);
285         BN_div(d, e, a, b, ctx);
286         BN_sub(e, e, c);
287         if (!BN_is_zero(e)) {
288             printf("Modulo test failed!\n");
289             return 0;
290         }
291     }
292     BN_free(a);
293     BN_free(b);
294     BN_free(c);
295     BN_free(d);
296     BN_free(e);
297     return 1;
298 }
299
300 static const char *bn1strings[] = {
301     "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
302     "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
303     "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
304     "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
305     "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
306     "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
307     "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
308     "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00000000000000FFFFFFFF00",
309     "0000000000000000000000000000000000000000000000000000000000000000",
310     "0000000000000000000000000000000000000000000000000000000000000000",
311     "0000000000000000000000000000000000000000000000000000000000000000",
312     "0000000000000000000000000000000000000000000000000000000000000000",
313     "0000000000000000000000000000000000000000000000000000000000000000",
314     "0000000000000000000000000000000000000000000000000000000000000000",
315     "0000000000000000000000000000000000000000000000000000000000000000",
316     "00000000000000000000000000000000000000000000000000FFFFFFFFFFFFFF",
317     NULL
318 };
319
320 static const char *bn2strings[] = {
321     "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
322     "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
323     "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
324     "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
325     "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
326     "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
327     "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
328     "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00000000000000FFFFFFFF0000000000",
329     "0000000000000000000000000000000000000000000000000000000000000000",
330     "0000000000000000000000000000000000000000000000000000000000000000",
331     "0000000000000000000000000000000000000000000000000000000000000000",
332     "0000000000000000000000000000000000000000000000000000000000000000",
333     "0000000000000000000000000000000000000000000000000000000000000000",
334     "0000000000000000000000000000000000000000000000000000000000000000",
335     "0000000000000000000000000000000000000000000000000000000000000000",
336     "000000000000000000000000000000000000000000FFFFFFFFFFFFFF00000000",
337     NULL
338 };
339
340 static char *glue(const char *list[])
341 {
342     size_t len = 0;
343     char *p, *save;
344     int i;
345
346     for (i = 0; list[i] != NULL; i++)
347         len += strlen(list[i]);
348     p = save = OPENSSL_malloc(len + 1);
349     if (p != NULL) {
350         for (i = 0; list[i] != NULL; i++)
351             p += strlen(strcpy(p, list[i]));
352     }
353     return save;
354 }
355
356 /*
357  * Test constant-time modular exponentiation with 1024-bit inputs, which on
358  * x86_64 cause a different code branch to be taken.
359  */
360 static int test_modexp_mont5()
361 {
362     BIGNUM *a, *p, *m, *d, *e, *b, *n, *c;
363     BN_MONT_CTX *mont;
364     char *bigstring;
365
366     a = BN_new();
367     p = BN_new();
368     m = BN_new();
369     d = BN_new();
370     e = BN_new();
371     b = BN_new();
372     n = BN_new();
373     c = BN_new();
374     mont = BN_MONT_CTX_new();
375
376     BN_bntest_rand(m, 1024, 0, 1); /* must be odd for montgomery */
377     /* Zero exponent */
378     BN_bntest_rand(a, 1024, 0, 0);
379     BN_zero(p);
380     if (!BN_mod_exp_mont_consttime(d, a, p, m, ctx, NULL))
381         return 0;
382     if (!BN_is_one(d)) {
383         printf("Modular exponentiation test failed!\n");
384         return 0;
385     }
386
387     /* Regression test for carry bug in mulx4x_mont */
388     BN_hex2bn(&a,
389         "7878787878787878787878787878787878787878787878787878787878787878"
390         "7878787878787878787878787878787878787878787878787878787878787878"
391         "7878787878787878787878787878787878787878787878787878787878787878"
392         "7878787878787878787878787878787878787878787878787878787878787878");
393     BN_hex2bn(&b,
394         "095D72C08C097BA488C5E439C655A192EAFB6380073D8C2664668EDDB4060744"
395         "E16E57FB4EDB9AE10A0CEFCDC28A894F689A128379DB279D48A2E20849D68593"
396         "9B7803BCF46CEBF5C533FB0DD35B080593DE5472E3FE5DB951B8BFF9B4CB8F03"
397         "9CC638A5EE8CDD703719F8000E6A9F63BEED5F2FCD52FF293EA05A251BB4AB81");
398     BN_hex2bn(&n,
399         "D78AF684E71DB0C39CFF4E64FB9DB567132CB9C50CC98009FEB820B26F2DED9B"
400         "91B9B5E2B83AE0AE4EB4E0523CA726BFBE969B89FD754F674CE99118C3F2D1C5"
401         "D81FDC7C54E02B60262B241D53C040E99E45826ECA37A804668E690E1AFC1CA4"
402         "2C9A15D84D4954425F0B7642FC0BD9D7B24E2618D2DCC9B729D944BADACFDDAF");
403     BN_MONT_CTX_set(mont, n, ctx);
404     BN_mod_mul_montgomery(c, a, b, mont, ctx);
405     BN_mod_mul_montgomery(d, b, a, mont, ctx);
406     if (BN_cmp(c, d)) {
407         fprintf(stderr, "Montgomery multiplication test failed:"
408                         " a*b != b*a.\n");
409         return 0;
410     }
411
412     /* Regression test for carry bug in sqr[x]8x_mont */
413     bigstring = glue(bn1strings);
414     BN_hex2bn(&n, bigstring);
415     OPENSSL_free(bigstring);
416     bigstring = glue(bn2strings);
417     BN_hex2bn(&a, bigstring);
418     OPENSSL_free(bigstring);
419     BN_free(b);
420     b = BN_dup(a);
421     BN_MONT_CTX_set(mont, n, ctx);
422     BN_mod_mul_montgomery(c, a, a, mont, ctx);
423     BN_mod_mul_montgomery(d, a, b, mont, ctx);
424     if (BN_cmp(c, d)) {
425         fprintf(stderr, "Montgomery multiplication test failed:"
426                         " a**2 != a*a.\n");
427         return 0;
428     }
429
430     /* Zero input */
431     BN_bntest_rand(p, 1024, 0, 0);
432     BN_zero(a);
433     if (!BN_mod_exp_mont_consttime(d, a, p, m, ctx, NULL))
434         return 0;
435     if (!BN_is_zero(d)) {
436         fprintf(stderr, "Modular exponentiation test failed!\n");
437         return 0;
438     }
439     /*
440      * Craft an input whose Montgomery representation is 1, i.e., shorter
441      * than the modulus m, in order to test the const time precomputation
442      * scattering/gathering.
443      */
444     BN_one(a);
445     BN_MONT_CTX_set(mont, m, ctx);
446     if (!BN_from_montgomery(e, a, mont, ctx))
447         return 0;
448     if (!BN_mod_exp_mont_consttime(d, e, p, m, ctx, NULL))
449         return 0;
450     if (!BN_mod_exp_simple(a, e, p, m, ctx))
451         return 0;
452     if (BN_cmp(a, d) != 0) {
453         printf("Modular exponentiation test failed!\n");
454         return 0;
455     }
456     /* Finally, some regular test vectors. */
457     BN_bntest_rand(e, 1024, 0, 0);
458     if (!BN_mod_exp_mont_consttime(d, e, p, m, ctx, NULL))
459         return 0;
460     if (!BN_mod_exp_simple(a, e, p, m, ctx))
461         return 0;
462     if (BN_cmp(a, d) != 0) {
463         printf("Modular exponentiation test failed!\n");
464         return 0;
465     }
466     BN_MONT_CTX_free(mont);
467     BN_free(a);
468     BN_free(p);
469     BN_free(m);
470     BN_free(d);
471     BN_free(e);
472     BN_free(b);
473     BN_free(n);
474     BN_free(c);
475     return 1;
476 }
477
478 #ifndef OPENSSL_NO_EC2M
479 static int test_gf2m_add()
480 {
481     BIGNUM *a, *b, *c;
482     int i, st = 0;
483
484     a = BN_new();
485     b = BN_new();
486     c = BN_new();
487
488     for (i = 0; i < NUM0; i++) {
489         BN_rand(a, 512, 0, 0);
490         BN_copy(b, BN_value_one());
491         a->neg = rand_neg();
492         b->neg = rand_neg();
493         BN_GF2m_add(c, a, b);
494         /* Test that two added values have the correct parity. */
495         if ((BN_is_odd(a) && BN_is_odd(c))
496             || (!BN_is_odd(a) && !BN_is_odd(c))) {
497             printf("GF(2^m) addition test (a) failed!\n");
498             goto err;
499         }
500         BN_GF2m_add(c, c, c);
501         /* Test that c + c = 0. */
502         if (!BN_is_zero(c)) {
503             printf("GF(2^m) addition test (b) failed!\n");
504             goto err;
505         }
506     }
507     st = 1;
508  err:
509     BN_free(a);
510     BN_free(b);
511     BN_free(c);
512     return st;
513 }
514
515 static int test_gf2m_mod()
516 {
517     static int p0[] = { 163, 7, 6, 3, 0, -1 };
518     static int p1[] = { 193, 15, 0, -1 };
519     BIGNUM *a, *b[2], *c, *d, *e;
520     int i, j, st = 0;
521
522     a = BN_new();
523     b[0] = BN_new();
524     b[1] = BN_new();
525     c = BN_new();
526     d = BN_new();
527     e = BN_new();
528
529     BN_GF2m_arr2poly(p0, b[0]);
530     BN_GF2m_arr2poly(p1, b[1]);
531
532     for (i = 0; i < NUM0; i++) {
533         BN_bntest_rand(a, 1024, 0, 0);
534         for (j = 0; j < 2; j++) {
535             BN_GF2m_mod(c, a, b[j]);
536             BN_GF2m_add(d, a, c);
537             BN_GF2m_mod(e, d, b[j]);
538             /* Test that a + (a mod p) mod p == 0. */
539             if (!BN_is_zero(e)) {
540                 printf("GF(2^m) modulo test failed!\n");
541                 goto err;
542             }
543         }
544     }
545     st = 1;
546  err:
547     BN_free(a);
548     BN_free(b[0]);
549     BN_free(b[1]);
550     BN_free(c);
551     BN_free(d);
552     BN_free(e);
553     return st;
554 }
555
556 static int test_gf2m_mul()
557 {
558     BIGNUM *a, *b[2], *c, *d, *e, *f, *g, *h;
559     int i, j, st = 0;
560     int p0[] = { 163, 7, 6, 3, 0, -1 };
561     int p1[] = { 193, 15, 0, -1 };
562
563     a = BN_new();
564     b[0] = BN_new();
565     b[1] = BN_new();
566     c = BN_new();
567     d = BN_new();
568     e = BN_new();
569     f = BN_new();
570     g = BN_new();
571     h = BN_new();
572
573     BN_GF2m_arr2poly(p0, b[0]);
574     BN_GF2m_arr2poly(p1, b[1]);
575
576     for (i = 0; i < NUM0; i++) {
577         BN_bntest_rand(a, 1024, 0, 0);
578         BN_bntest_rand(c, 1024, 0, 0);
579         BN_bntest_rand(d, 1024, 0, 0);
580         for (j = 0; j < 2; j++) {
581             BN_GF2m_mod_mul(e, a, c, b[j], ctx);
582             BN_GF2m_add(f, a, d);
583             BN_GF2m_mod_mul(g, f, c, b[j], ctx);
584             BN_GF2m_mod_mul(h, d, c, b[j], ctx);
585             BN_GF2m_add(f, e, g);
586             BN_GF2m_add(f, f, h);
587             /* Test that (a+d)*c = a*c + d*c. */
588             if (!BN_is_zero(f)) {
589                 printf("GF(2^m) modular multiplication test failed!\n");
590                 goto err;
591             }
592         }
593     }
594     st = 1;
595  err:
596     BN_free(a);
597     BN_free(b[0]);
598     BN_free(b[1]);
599     BN_free(c);
600     BN_free(d);
601     BN_free(e);
602     BN_free(f);
603     BN_free(g);
604     BN_free(h);
605     return st;
606 }
607
608 static int test_gf2m_sqr()
609 {
610     BIGNUM *a, *b[2], *c, *d;
611     int i, j, st = 0;
612     int p0[] = { 163, 7, 6, 3, 0, -1 };
613     int p1[] = { 193, 15, 0, -1 };
614
615     a = BN_new();
616     b[0] = BN_new();
617     b[1] = BN_new();
618     c = BN_new();
619     d = BN_new();
620
621     BN_GF2m_arr2poly(p0, b[0]);
622     BN_GF2m_arr2poly(p1, b[1]);
623
624     for (i = 0; i < NUM0; i++) {
625         BN_bntest_rand(a, 1024, 0, 0);
626         for (j = 0; j < 2; j++) {
627             BN_GF2m_mod_sqr(c, a, b[j], ctx);
628             BN_copy(d, a);
629             BN_GF2m_mod_mul(d, a, d, b[j], ctx);
630             BN_GF2m_add(d, c, d);
631             /* Test that a*a = a^2. */
632             if (!BN_is_zero(d)) {
633                 printf("GF(2^m) modular squaring test failed!\n");
634                 goto err;
635             }
636         }
637     }
638     st = 1;
639  err:
640     BN_free(a);
641     BN_free(b[0]);
642     BN_free(b[1]);
643     BN_free(c);
644     BN_free(d);
645     return st;
646 }
647
648 static int test_gf2m_modinv()
649 {
650     BIGNUM *a, *b[2], *c, *d;
651     int i, j, st = 0;
652     int p0[] = { 163, 7, 6, 3, 0, -1 };
653     int p1[] = { 193, 15, 0, -1 };
654
655     a = BN_new();
656     b[0] = BN_new();
657     b[1] = BN_new();
658     c = BN_new();
659     d = BN_new();
660
661     BN_GF2m_arr2poly(p0, b[0]);
662     BN_GF2m_arr2poly(p1, b[1]);
663
664     for (i = 0; i < NUM0; i++) {
665         BN_bntest_rand(a, 512, 0, 0);
666         for (j = 0; j < 2; j++) {
667             BN_GF2m_mod_inv(c, a, b[j], ctx);
668             BN_GF2m_mod_mul(d, a, c, b[j], ctx);
669             /* Test that ((1/a)*a) = 1. */
670             if (!BN_is_one(d)) {
671                 printf("GF(2^m) modular inversion test failed!\n");
672                 goto err;
673             }
674         }
675     }
676     st = 1;
677  err:
678     BN_free(a);
679     BN_free(b[0]);
680     BN_free(b[1]);
681     BN_free(c);
682     BN_free(d);
683     return st;
684 }
685
686 static int test_gf2m_moddiv()
687 {
688     BIGNUM *a, *b[2], *c, *d, *e, *f;
689     int i, j, st = 0;
690     int p0[] = { 163, 7, 6, 3, 0, -1 };
691     int p1[] = { 193, 15, 0, -1 };
692
693     a = BN_new();
694     b[0] = BN_new();
695     b[1] = BN_new();
696     c = BN_new();
697     d = BN_new();
698     e = BN_new();
699     f = BN_new();
700
701     BN_GF2m_arr2poly(p0, b[0]);
702     BN_GF2m_arr2poly(p1, b[1]);
703
704     for (i = 0; i < NUM0; i++) {
705         BN_bntest_rand(a, 512, 0, 0);
706         BN_bntest_rand(c, 512, 0, 0);
707         for (j = 0; j < 2; j++) {
708             BN_GF2m_mod_div(d, a, c, b[j], ctx);
709             BN_GF2m_mod_mul(e, d, c, b[j], ctx);
710             BN_GF2m_mod_div(f, a, e, b[j], ctx);
711             /* Test that ((a/c)*c)/a = 1. */
712             if (!BN_is_one(f)) {
713                 printf("GF(2^m) modular division test failed!\n");
714                 goto err;
715             }
716         }
717     }
718     st = 1;
719  err:
720     BN_free(a);
721     BN_free(b[0]);
722     BN_free(b[1]);
723     BN_free(c);
724     BN_free(d);
725     BN_free(e);
726     BN_free(f);
727     return st;
728 }
729
730 static int test_gf2m_modexp()
731 {
732     BIGNUM *a, *b[2], *c, *d, *e, *f;
733     int i, j, st = 0;
734     int p0[] = { 163, 7, 6, 3, 0, -1 };
735     int p1[] = { 193, 15, 0, -1 };
736
737     a = BN_new();
738     b[0] = BN_new();
739     b[1] = BN_new();
740     c = BN_new();
741     d = BN_new();
742     e = BN_new();
743     f = BN_new();
744
745     BN_GF2m_arr2poly(p0, b[0]);
746     BN_GF2m_arr2poly(p1, b[1]);
747
748     for (i = 0; i < NUM0; i++) {
749         BN_bntest_rand(a, 512, 0, 0);
750         BN_bntest_rand(c, 512, 0, 0);
751         BN_bntest_rand(d, 512, 0, 0);
752         for (j = 0; j < 2; j++) {
753             BN_GF2m_mod_exp(e, a, c, b[j], ctx);
754             BN_GF2m_mod_exp(f, a, d, b[j], ctx);
755             BN_GF2m_mod_mul(e, e, f, b[j], ctx);
756             BN_add(f, c, d);
757             BN_GF2m_mod_exp(f, a, f, b[j], ctx);
758             BN_GF2m_add(f, e, f);
759             /* Test that a^(c+d)=a^c*a^d. */
760             if (!BN_is_zero(f)) {
761                 printf("GF(2^m) modular exponentiation test failed!\n");
762                 goto err;
763             }
764         }
765     }
766     st = 1;
767  err:
768     BN_free(a);
769     BN_free(b[0]);
770     BN_free(b[1]);
771     BN_free(c);
772     BN_free(d);
773     BN_free(e);
774     BN_free(f);
775     return st;
776 }
777
778 static int test_gf2m_modsqrt()
779 {
780     BIGNUM *a, *b[2], *c, *d, *e, *f;
781     int i, j, st = 0;
782     int p0[] = { 163, 7, 6, 3, 0, -1 };
783     int p1[] = { 193, 15, 0, -1 };
784
785     a = BN_new();
786     b[0] = BN_new();
787     b[1] = BN_new();
788     c = BN_new();
789     d = BN_new();
790     e = BN_new();
791     f = BN_new();
792
793     BN_GF2m_arr2poly(p0, b[0]);
794     BN_GF2m_arr2poly(p1, b[1]);
795
796     for (i = 0; i < NUM0; i++) {
797         BN_bntest_rand(a, 512, 0, 0);
798         for (j = 0; j < 2; j++) {
799             BN_GF2m_mod(c, a, b[j]);
800             BN_GF2m_mod_sqrt(d, a, b[j], ctx);
801             BN_GF2m_mod_sqr(e, d, b[j], ctx);
802             BN_GF2m_add(f, c, e);
803             /* Test that d^2 = a, where d = sqrt(a). */
804             if (!BN_is_zero(f)) {
805                 printf("GF(2^m) modular square root test failed!\n");
806                 goto err;
807             }
808         }
809     }
810     st = 1;
811  err:
812     BN_free(a);
813     BN_free(b[0]);
814     BN_free(b[1]);
815     BN_free(c);
816     BN_free(d);
817     BN_free(e);
818     BN_free(f);
819     return st;
820 }
821
822 static int test_gf2m_modsolvequad()
823 {
824     BIGNUM *a, *b[2], *c, *d, *e;
825     int i, j, s = 0, t, st = 0;
826     int p0[] = { 163, 7, 6, 3, 0, -1 };
827     int p1[] = { 193, 15, 0, -1 };
828
829     a = BN_new();
830     b[0] = BN_new();
831     b[1] = BN_new();
832     c = BN_new();
833     d = BN_new();
834     e = BN_new();
835
836     BN_GF2m_arr2poly(p0, b[0]);
837     BN_GF2m_arr2poly(p1, b[1]);
838
839     for (i = 0; i < NUM0; i++) {
840         BN_bntest_rand(a, 512, 0, 0);
841         for (j = 0; j < 2; j++) {
842             t = BN_GF2m_mod_solve_quad(c, a, b[j], ctx);
843             if (t) {
844                 s++;
845                 BN_GF2m_mod_sqr(d, c, b[j], ctx);
846                 BN_GF2m_add(d, c, d);
847                 BN_GF2m_mod(e, a, b[j]);
848                 BN_GF2m_add(e, e, d);
849                 /*
850                  * Test that solution of quadratic c satisfies c^2 + c = a.
851                  */
852                 if (!BN_is_zero(e)) {
853                     printf("GF(2^m) modular solve quadratic test failed!\n");
854                     goto err;
855                 }
856
857             }
858         }
859     }
860     if (s == 0) {
861         printf("All %i tests of GF(2^m) modular solve quadratic resulted in no roots;\n",
862                 NUM0);
863         printf("this is very unlikely and probably indicates an error.\n");
864         goto err;
865     }
866     st = 1;
867  err:
868     BN_free(a);
869     BN_free(b[0]);
870     BN_free(b[1]);
871     BN_free(c);
872     BN_free(d);
873     BN_free(e);
874     return st;
875 }
876 #endif
877
878 static int test_kronecker()
879 {
880     BIGNUM *a, *b, *r, *t;
881     int i;
882     int legendre, kronecker;
883     int st = 0;
884
885     a = BN_new();
886     b = BN_new();
887     r = BN_new();
888     t = BN_new();
889     if (a == NULL || b == NULL || r == NULL || t == NULL)
890         goto err;
891
892     /*
893      * We test BN_kronecker(a, b, ctx) just for b odd (Jacobi symbol). In
894      * this case we know that if b is prime, then BN_kronecker(a, b, ctx) is
895      * congruent to $a^{(b-1)/2}$, modulo $b$ (Legendre symbol). So we
896      * generate a random prime b and compare these values for a number of
897      * random a's.  (That is, we run the Solovay-Strassen primality test to
898      * confirm that b is prime, except that we don't want to test whether b
899      * is prime but whether BN_kronecker works.)
900      */
901
902     if (!BN_generate_prime_ex(b, 512, 0, NULL, NULL, NULL))
903         goto err;
904     b->neg = rand_neg();
905
906     for (i = 0; i < NUM0; i++) {
907         if (!BN_bntest_rand(a, 512, 0, 0))
908             goto err;
909         a->neg = rand_neg();
910
911         /* t := (|b|-1)/2  (note that b is odd) */
912         if (!BN_copy(t, b))
913             goto err;
914         t->neg = 0;
915         if (!BN_sub_word(t, 1))
916             goto err;
917         if (!BN_rshift1(t, t))
918             goto err;
919         /* r := a^t mod b */
920         b->neg = 0;
921
922         if (!BN_mod_exp_recp(r, a, t, b, ctx))
923             goto err;
924         b->neg = 1;
925
926         if (BN_is_word(r, 1))
927             legendre = 1;
928         else if (BN_is_zero(r))
929             legendre = 0;
930         else {
931             if (!BN_add_word(r, 1))
932                 goto err;
933             if (0 != BN_ucmp(r, b)) {
934                 printf("Legendre symbol computation failed\n");
935                 goto err;
936             }
937             legendre = -1;
938         }
939
940         kronecker = BN_kronecker(a, b, ctx);
941         if (kronecker < -1)
942             goto err;
943         /* we actually need BN_kronecker(a, |b|) */
944         if (a->neg && b->neg)
945             kronecker = -kronecker;
946
947         if (legendre != kronecker) {
948             printf("legendre != kronecker; a = ");
949             BN_print_fp(stdout, a);
950             printf(", b = ");
951             BN_print_fp(stdout, b);
952             printf("\n");
953             goto err;
954         }
955     }
956
957     st = 1;
958  err:
959     BN_free(a);
960     BN_free(b);
961     BN_free(r);
962     BN_free(t);
963     return st;
964 }
965
966 static int file_sum(STANZA *s)
967 {
968     BIGNUM *a = getBN(s, "A");
969     BIGNUM *b = getBN(s, "B");
970     BIGNUM *sum = getBN(s, "Sum");
971     BIGNUM *ret = BN_new();
972     BN_ULONG b_word;
973     int st = 0;
974
975     if (a == NULL || b == NULL || sum == NULL || ret == NULL)
976         goto err;
977
978     if (!BN_add(ret, a, b)
979             || !equalBN("A + B", sum, ret)
980             || !BN_sub(ret, sum, a)
981             || !equalBN("Sum - A", b, ret)
982             || !BN_sub(ret, sum, b)
983             || !equalBN("Sum - B", a, ret))
984         goto err;
985
986     /*
987      * Test that the functions work when |r| and |a| point to the same BIGNUM,
988      * or when |r| and |b| point to the same BIGNUM.
989      * TODO: Test where all of |r|, |a|, and |b| point to the same BIGNUM.
990      */
991     if (!BN_copy(ret, a)
992             || !BN_add(ret, ret, b)
993             || !equalBN("A + B (r is a)", sum, ret)
994             || !BN_copy(ret, b)
995             || !BN_add(ret, a, ret)
996             || !equalBN("A + B (r is b)", sum, ret)
997             || !BN_copy(ret, sum)
998             || !BN_sub(ret, ret, a)
999             || !equalBN("Sum - A (r is a)", b, ret)
1000             || !BN_copy(ret, a)
1001             || !BN_sub(ret, sum, ret)
1002             || !equalBN("Sum - A (r is b)", b, ret)
1003             || !BN_copy(ret, sum)
1004             || !BN_sub(ret, ret, b)
1005             || !equalBN("Sum - B (r is a)", a, ret)
1006             || !BN_copy(ret, b)
1007             || !BN_sub(ret, sum, ret)
1008             || !equalBN("Sum - B (r is b)", a, ret))
1009         goto err;
1010
1011     /*
1012      * Test BN_uadd() and BN_usub() with the prerequisites they are
1013      * documented as having. Note that these functions are frequently used
1014      * when the prerequisites don't hold. In those cases, they are supposed
1015      * to work as if the prerequisite hold, but we don't test that yet.
1016      * TODO: test that.
1017      */
1018     if (!BN_is_negative(a) && !BN_is_negative(b) && BN_cmp(a, b) >= 0) {
1019         if (!BN_uadd(ret, a, b)
1020                 || !equalBN("A +u B", sum, ret)
1021                 || !BN_usub(ret, sum, a)
1022                 || !equalBN("Sum -u A", b, ret)
1023                 || !BN_usub(ret, sum, b)
1024                 || !equalBN("Sum -u B", a, ret))
1025             goto err;
1026         /*
1027          * Test that the functions work when |r| and |a| point to the same
1028          * BIGNUM, or when |r| and |b| point to the same BIGNUM.
1029          * TODO: Test where all of |r|, |a|, and |b| point to the same BIGNUM.
1030          */
1031         if (!BN_copy(ret, a)
1032                 || !BN_uadd(ret, ret, b)
1033                 || !equalBN("A +u B (r is a)", sum, ret)
1034                 || !BN_copy(ret, b)
1035                 || !BN_uadd(ret, a, ret)
1036                 || !equalBN("A +u B (r is b)", sum, ret)
1037                 || !BN_copy(ret, sum)
1038                 || !BN_usub(ret, ret, a)
1039                 || !equalBN("Sum -u A (r is a)", b, ret)
1040                 || !BN_copy(ret, a)
1041                 || !BN_usub(ret, sum, ret)
1042                 || !equalBN("Sum -u A (r is b)", b, ret)
1043                 || !BN_copy(ret, sum)
1044                 || !BN_usub(ret, ret, b)
1045                 || !equalBN("Sum -u B (r is a)", a, ret)
1046                 || !BN_copy(ret, b)
1047                 || !BN_usub(ret, sum, ret)
1048                 || !equalBN("Sum -u B (r is b)", a, ret))
1049             goto err;
1050     }
1051
1052     /*
1053      * Test with BN_add_word() and BN_sub_word() if |b| is small enough.
1054      */
1055     b_word = BN_get_word(b);
1056     if (!BN_is_negative(b) && b_word != (BN_ULONG)-1) {
1057         if (!BN_copy(ret, a)
1058                 || !BN_add_word(ret, b_word)
1059                 || !equalBN("A + B (word)", sum, ret)
1060                 || !BN_copy(ret, sum)
1061                 || !BN_sub_word(ret, b_word)
1062                 || !equalBN("Sum - B (word)", a, ret))
1063             goto err;
1064     }
1065     st = 1;
1066
1067 err:
1068     BN_free(a);
1069     BN_free(b);
1070     BN_free(sum);
1071     BN_free(ret);
1072     return st;
1073 }
1074
1075 static int file_lshift1(STANZA *s)
1076 {
1077     BIGNUM *a = getBN(s, "A");
1078     BIGNUM *lshift1 = getBN(s, "LShift1");
1079     BIGNUM *zero = BN_new();
1080     BIGNUM *ret = BN_new();
1081     BIGNUM *two = BN_new();
1082     BIGNUM *remainder = BN_new();
1083     int st = 0;
1084
1085     if (a == NULL || lshift1 == NULL || zero == NULL
1086             || ret == NULL || two == NULL || remainder == NULL)
1087         goto err;
1088
1089     BN_zero(zero);
1090
1091     if (!BN_set_word(two, 2)
1092             || !BN_add(ret, a, a)
1093             || !equalBN("A + A", lshift1, ret)
1094             || !BN_mul(ret, a, two, ctx)
1095             || !equalBN("A * 2", lshift1, ret)
1096             || !BN_div(ret, remainder, lshift1, two, ctx)
1097             || !equalBN("LShift1 / 2", a, ret)
1098             || !equalBN("LShift1 % 2", zero, remainder)
1099             || !BN_lshift1(ret, a)
1100             || !equalBN("A << 1", lshift1, ret)
1101             || !BN_rshift1(ret, lshift1)
1102             || !equalBN("LShift >> 1", a, ret)
1103             || !BN_rshift1(ret, lshift1)
1104             || !equalBN("LShift >> 1", a, ret))
1105         goto err;
1106
1107     /* Set the LSB to 1 and test rshift1 again. */
1108     if (!BN_set_bit(lshift1, 0)
1109             || !BN_div(ret, NULL /* rem */ , lshift1, two, ctx)
1110             || !equalBN("(LShift1 | 1) / 2", a, ret)
1111             || !BN_rshift1(ret, lshift1)
1112             || !equalBN("(LShift | 1) >> 1", a, ret))
1113         goto err;
1114
1115     st = 1;
1116 err:
1117     BN_free(a);
1118     BN_free(lshift1);
1119     BN_free(zero);
1120     BN_free(ret);
1121     BN_free(two);
1122     BN_free(remainder);
1123
1124     return st;
1125 }
1126
1127 static int file_lshift(STANZA *s)
1128 {
1129     BIGNUM *a = getBN(s, "A");
1130     BIGNUM *lshift = getBN(s, "LShift");
1131     BIGNUM *ret = BN_new();
1132     int n = 0;
1133     int st = 0;
1134
1135     if (a == NULL || lshift == NULL || ret == NULL || !getint(s, &n, "N"))
1136         goto err;
1137
1138     if (!BN_lshift(ret, a, n)
1139             || !equalBN("A << N", lshift, ret)
1140             || !BN_rshift(ret, lshift, n)
1141             || !equalBN("A >> N", a, ret))
1142         goto err;
1143
1144     st = 1;
1145 err:
1146     BN_free(a);
1147     BN_free(lshift);
1148     BN_free(ret);
1149     return st;
1150 }
1151
1152 static int file_rshift(STANZA *s)
1153 {
1154     BIGNUM *a = getBN(s, "A");
1155     BIGNUM *rshift = getBN(s, "RShift");
1156     BIGNUM *ret = BN_new();
1157     int n = 0;
1158     int errcnt = 1;
1159
1160     if (a == NULL || rshift == NULL || ret == NULL || !getint(s, &n, "N"))
1161         goto err;
1162
1163     errcnt = 0;
1164     if (!BN_rshift(ret, a, n)
1165             || !equalBN("A >> N", rshift, ret))
1166         errcnt++;
1167
1168     /* If N == 1, try with rshift1 as well */
1169     if (n == 1) {
1170         if (!BN_rshift1(ret, a)
1171                 || !equalBN("A >> 1 (rshift1)", rshift, ret))
1172             errcnt++;
1173     }
1174
1175 err:
1176     BN_free(a);
1177     BN_free(rshift);
1178     BN_free(ret);
1179     return errcnt == 0;
1180 }
1181
1182 static int file_square(STANZA *s)
1183 {
1184     BIGNUM *a = getBN(s, "A");
1185     BIGNUM *square = getBN(s, "Square");
1186     BIGNUM *zero = BN_new();
1187     BIGNUM *ret = BN_new();
1188     BIGNUM *remainder = BN_new();
1189     BIGNUM *tmp = NULL;
1190     int st = 0;
1191
1192     if (a == NULL || square == NULL || zero == NULL || ret == NULL
1193             || remainder == NULL)
1194         goto err;
1195
1196     BN_zero(zero);
1197
1198     if (!BN_sqr(ret, a, ctx)
1199             || !equalBN("A^2", square, ret)
1200             || !BN_mul(ret, a, a, ctx)
1201             || !equalBN("A * A", square, ret)
1202             || !BN_div(ret, remainder, square, a, ctx)
1203             || !equalBN("Square / A", a, ret)
1204             || !equalBN("Square % A", zero, remainder))
1205         goto err;
1206
1207 #if HAVE_BN_SQRT
1208     BN_set_negative(a, 0);
1209     if (!BN_sqrt(ret, square, ctx)
1210             || !equalBN("sqrt(Square)", a, ret))
1211         goto err;
1212
1213     /* BN_sqrt should fail on non-squares and negative numbers. */
1214     if (!BN_is_zero(square)) {
1215         tmp = BN_new();
1216         if (tmp == NULL || !BN_copy(tmp, square))
1217             goto err;
1218         BN_set_negative(tmp, 1);
1219
1220         if (BN_sqrt(ret, tmp, ctx)) {
1221             fprintf(stderr, "BN_sqrt succeeded on a negative number");
1222             goto err;
1223         }
1224         ERR_clear_error();
1225
1226         BN_set_negative(tmp, 0);
1227         if (BN_add(tmp, tmp, BN_value_one()))
1228             goto err;
1229         if (BN_sqrt(ret, tmp, ctx)) {
1230             fprintf(stderr, "BN_sqrt succeeded on a non-square");
1231             goto err;
1232         }
1233         ERR_clear_error();
1234     }
1235 #endif
1236
1237     st = 1;
1238 err:
1239     BN_free(a);
1240     BN_free(square);
1241     BN_free(zero);
1242     BN_free(ret);
1243     BN_free(remainder);
1244     BN_free(tmp);
1245     return st;
1246 }
1247
1248 static int file_product(STANZA *s)
1249 {
1250     BIGNUM *a = getBN(s, "A");
1251     BIGNUM *b = getBN(s, "B");
1252     BIGNUM *product = getBN(s, "Product");
1253     BIGNUM *ret = BN_new();
1254     BIGNUM *remainder = BN_new();
1255     BIGNUM *zero = BN_new();
1256     int st = 0;
1257
1258     if (a == NULL || b == NULL || product == NULL || ret == NULL
1259             || remainder == NULL || zero == NULL)
1260         goto err;
1261
1262     BN_zero(zero);
1263
1264     if (!BN_mul(ret, a, b, ctx)
1265             || !equalBN("A * B", product, ret)
1266             || !BN_div(ret, remainder, product, a, ctx)
1267             || !equalBN("Product / A", b, ret)
1268             || !equalBN("Product % A", zero, remainder)
1269             || !BN_div(ret, remainder, product, b, ctx)
1270             || !equalBN("Product / B", a, ret)
1271             || !equalBN("Product % B", zero, remainder))
1272         goto err;
1273
1274     st = 1;
1275 err:
1276     BN_free(a);
1277     BN_free(b);
1278     BN_free(product);
1279     BN_free(ret);
1280     BN_free(remainder);
1281     BN_free(zero);
1282     return st;
1283 }
1284
1285 static int file_quotient(STANZA *s)
1286 {
1287     BIGNUM *a = getBN(s, "A");
1288     BIGNUM *b = getBN(s, "B");
1289     BIGNUM *quotient = getBN(s, "Quotient");
1290     BIGNUM *remainder = getBN(s, "Remainder");
1291     BIGNUM *ret = BN_new();
1292     BIGNUM *ret2 = BN_new();
1293     BIGNUM *nnmod = BN_new();
1294     BN_ULONG b_word, ret_word;
1295     int st = 0;
1296
1297     if (a == NULL || b == NULL || quotient == NULL || remainder == NULL
1298             || ret == NULL || ret2 == NULL || nnmod == NULL)
1299         goto err;
1300
1301     if (!BN_div(ret, ret2, a, b, ctx)
1302             || !equalBN("A / B", quotient, ret)
1303             || !equalBN("A % B", remainder, ret2)
1304             || !BN_mul(ret, quotient, b, ctx)
1305             || !BN_add(ret, ret, remainder)
1306             || !equalBN("Quotient * B + Remainder", a, ret))
1307         goto err;
1308
1309     /*
1310      * Test with BN_mod_word() and BN_div_word() if the divisor is
1311      * small enough.
1312      */
1313     b_word = BN_get_word(b);
1314     if (!BN_is_negative(b) && b_word != (BN_ULONG)-1) {
1315         BN_ULONG remainder_word = BN_get_word(remainder);
1316
1317         assert(remainder_word != (BN_ULONG)-1);
1318         if (!BN_copy(ret, a))
1319             goto err;
1320         ret_word = BN_div_word(ret, b_word);
1321         if (ret_word != remainder_word) {
1322 #ifdef BN_DEC_FMT1
1323             fprintf(stderr,
1324                     "Got A %% B (word) = " BN_DEC_FMT1 ", wanted " BN_DEC_FMT1 "\n",
1325                     ret_word, remainder_word);
1326 #else
1327             fprintf(stderr, "Got A %% B (word) mismatch\n");
1328 #endif
1329             goto err;
1330         }
1331         if (!equalBN ("A / B (word)", quotient, ret))
1332             goto err;
1333
1334         ret_word = BN_mod_word(a, b_word);
1335         if (ret_word != remainder_word) {
1336 #ifdef BN_DEC_FMT1
1337             fprintf(stderr,
1338                     "Got A %% B (word) = " BN_DEC_FMT1 ", wanted " BN_DEC_FMT1 "\n",
1339                     ret_word, remainder_word);
1340 #else
1341             fprintf(stderr, "Got A %% B (word) mismatch\n");
1342 #endif
1343             goto err;
1344         }
1345     }
1346
1347     /* Test BN_nnmod. */
1348     if (!BN_is_negative(b)) {
1349         if (!BN_copy(nnmod, remainder)
1350                 || (BN_is_negative(nnmod) && !BN_add(nnmod, nnmod, b))
1351                 || !BN_nnmod(ret, a, b, ctx)
1352                 || !equalBN("A % B (non-negative)", nnmod, ret))
1353             goto err;
1354     }
1355
1356     st = 1;
1357 err:
1358     BN_free(a);
1359     BN_free(b);
1360     BN_free(quotient);
1361     BN_free(remainder);
1362     BN_free(ret);
1363     BN_free(ret2);
1364     BN_free(nnmod);
1365     return st;
1366 }
1367
1368 static int file_modmul(STANZA *s)
1369 {
1370     BIGNUM *a = getBN(s, "A");
1371     BIGNUM *b = getBN(s, "B");
1372     BIGNUM *m = getBN(s, "M");
1373     BIGNUM *mod_mul = getBN(s, "ModMul");
1374     BIGNUM *ret = BN_new();
1375     int st = 0;
1376
1377     if (a == NULL || b == NULL || m == NULL || mod_mul == NULL || ret == NULL)
1378         goto err;
1379
1380     if (!BN_mod_mul(ret, a, b, m, ctx)
1381             || !equalBN("A * B (mod M)", mod_mul, ret))
1382         goto err;
1383
1384     if (BN_is_odd(m)) {
1385         /* Reduce |a| and |b| and test the Montgomery version. */
1386         BN_MONT_CTX *mont = BN_MONT_CTX_new();
1387         BIGNUM *a_tmp = BN_new();
1388         BIGNUM *b_tmp = BN_new();
1389         if (mont == NULL || a_tmp == NULL || b_tmp == NULL
1390                 || !BN_MONT_CTX_set(mont, m, ctx)
1391                 || !BN_nnmod(a_tmp, a, m, ctx)
1392                 || !BN_nnmod(b_tmp, b, m, ctx)
1393                 || !BN_to_montgomery(a_tmp, a_tmp, mont, ctx)
1394                 || !BN_to_montgomery(b_tmp, b_tmp, mont, ctx)
1395                 || !BN_mod_mul_montgomery(ret, a_tmp, b_tmp, mont, ctx)
1396                 || !BN_from_montgomery(ret, ret, mont, ctx)
1397                 || !equalBN("A * B (mod M) (mont)", mod_mul, ret)) {
1398             st = 0;
1399         } else {
1400             st = 1;
1401         }
1402         BN_MONT_CTX_free(mont);
1403         BN_free(a_tmp);
1404         BN_free(b_tmp);
1405         if (st == 0)
1406             goto err;
1407     }
1408
1409     st = 1;
1410 err:
1411     BN_free(a);
1412     BN_free(b);
1413     BN_free(m);
1414     BN_free(mod_mul);
1415     BN_free(ret);
1416     return st;
1417 }
1418
1419 static int file_modexp(STANZA *s)
1420 {
1421     BIGNUM *a = getBN(s, "A");
1422     BIGNUM *e = getBN(s, "E");
1423     BIGNUM *m = getBN(s, "M");
1424     BIGNUM *mod_exp = getBN(s, "ModExp");
1425     BIGNUM *ret = BN_new();
1426     BIGNUM *b = NULL, *c = NULL, *d = BN_new();
1427     int st = 0;
1428
1429     if (a == NULL || e == NULL || m == NULL || mod_exp == NULL || ret == NULL)
1430         goto err;
1431
1432     if (!BN_mod_exp(ret, a, e, m, ctx)
1433             || !equalBN("A ^ E (mod M)", mod_exp, ret))
1434         goto err;
1435
1436     if (BN_is_odd(m)) {
1437         if (!BN_mod_exp_mont(ret, a, e, m, ctx, NULL)
1438                 || !equalBN("A ^ E (mod M) (mont)", mod_exp, ret)
1439                 || !BN_mod_exp_mont_consttime(ret, a, e, m, ctx, NULL)
1440                 || !equalBN("A ^ E (mod M) (mont const", mod_exp, ret))
1441             goto err;
1442     }
1443
1444     /* Regression test for carry propagation bug in sqr8x_reduction */
1445     BN_hex2bn(&a, "050505050505");
1446     BN_hex2bn(&b, "02");
1447     BN_hex2bn(&c,
1448         "4141414141414141414141274141414141414141414141414141414141414141"
1449         "4141414141414141414141414141414141414141414141414141414141414141"
1450         "4141414141414141414141800000000000000000000000000000000000000000"
1451         "0000000000000000000000000000000000000000000000000000000000000000"
1452         "0000000000000000000000000000000000000000000000000000000000000000"
1453         "0000000000000000000000000000000000000000000000000000000001");
1454     BN_mod_exp(d, a, b, c, ctx);
1455     BN_mul(e, a, a, ctx);
1456     if (BN_cmp(d, e)) {
1457         fprintf(stderr, "BN_mod_exp and BN_mul produce different results!\n");
1458         goto err;
1459     }
1460
1461     st = 1;
1462 err:
1463     BN_free(a);
1464     BN_free(b);
1465     BN_free(c);
1466     BN_free(d);
1467     BN_free(e);
1468     BN_free(m);
1469     BN_free(mod_exp);
1470     BN_free(ret);
1471     return st;
1472 }
1473
1474 static int file_exp(STANZA *s)
1475 {
1476     BIGNUM *a = getBN(s, "A");
1477     BIGNUM *e = getBN(s, "E");
1478     BIGNUM *exp = getBN(s, "Exp");
1479     BIGNUM *ret = BN_new();
1480     int st = 0;
1481
1482     if (a == NULL || e == NULL || exp == NULL || ret == NULL)
1483         goto err;
1484
1485     if (!BN_exp(ret, a, e, ctx)
1486             || !equalBN("A ^ E", exp, ret))
1487         goto err;
1488
1489     st = 1;
1490 err:
1491     BN_free(a);
1492     BN_free(e);
1493     BN_free(exp);
1494     BN_free(ret);
1495     return st;
1496 }
1497
1498 static int file_modsqrt(STANZA *s)
1499 {
1500     BIGNUM *a = getBN(s, "A");
1501     BIGNUM *p = getBN(s, "P");
1502     BIGNUM *mod_sqrt = getBN(s, "ModSqrt");
1503     BIGNUM *ret = BN_new();
1504     BIGNUM *ret2 = BN_new();
1505     int st = 0;
1506
1507     if (a == NULL || p == NULL || mod_sqrt == NULL
1508             || ret == NULL || ret2 == NULL)
1509         goto err;
1510
1511     /* There are two possible answers. */
1512     if (!BN_mod_sqrt(ret, a, p, ctx) || !BN_sub(ret2, p, ret))
1513         goto err;
1514
1515     if (BN_cmp(ret2, mod_sqrt) != 0
1516             && !equalBN("sqrt(A) (mod P)", mod_sqrt, ret))
1517         goto err;
1518
1519     st = 1;
1520 err:
1521     BN_free(a);
1522     BN_free(p);
1523     BN_free(mod_sqrt);
1524     BN_free(ret);
1525     BN_free(ret2);
1526     return st;
1527 }
1528
1529 static int test_bn2padded()
1530 {
1531 #if HAVE_BN_PADDED
1532     uint8_t zeros[256], out[256], reference[128];
1533     BIGNUM *n = BN_new();
1534     int st = 0;
1535
1536     /* Test edge case at 0. */
1537     if (n == NULL)
1538         goto err;
1539     if (!BN_bn2bin_padded(NULL, 0, n)) {
1540         fprintf(stderr,
1541                 "BN_bn2bin_padded failed to encode 0 in an empty buffer.\n");
1542         goto err;
1543     }
1544     memset(out, -1, sizeof(out));
1545     if (!BN_bn2bin_padded(out, sizeof(out), n)) {
1546         fprintf(stderr,
1547                 "BN_bn2bin_padded failed to encode 0 in a non-empty buffer.\n");
1548         goto err;
1549     }
1550     memset(zeros, 0, sizeof(zeros));
1551     if (memcmp(zeros, out, sizeof(out))) {
1552         fprintf(stderr, "BN_bn2bin_padded did not zero buffer.\n");
1553         goto err;
1554     }
1555
1556     /* Test a random numbers at various byte lengths. */
1557     for (size_t bytes = 128 - 7; bytes <= 128; bytes++) {
1558 #define TOP_BIT_ON 0
1559 #define BOTTOM_BIT_NOTOUCH 0
1560         if (!BN_rand(n, bytes * 8, TOP_BIT_ON, BOTTOM_BIT_NOTOUCH)) {
1561             ERR_print_errors_fp(stderr);
1562             goto err;
1563         }
1564         if (BN_num_bytes(n) != bytes
1565                 || BN_bn2bin(n, reference) != bytes) {
1566             fprintf(stderr, "Bad result from BN_rand; bytes.\n");
1567             goto err;
1568         }
1569         /* Empty buffer should fail. */
1570         if (BN_bn2bin_padded(NULL, 0, n)) {
1571             fprintf(stderr,
1572                     "BN_bn2bin_padded incorrectly succeeded on empty buffer.\n");
1573             goto err;
1574         }
1575         /* One byte short should fail. */
1576         if (BN_bn2bin_padded(out, bytes - 1, n)) {
1577             fprintf(stderr,
1578                     "BN_bn2bin_padded incorrectly succeeded on short.\n");
1579             goto err;
1580         }
1581         /* Exactly right size should encode. */
1582         if (!BN_bn2bin_padded(out, bytes, n)
1583                 || memcmp(out, reference, bytes) != 0) {
1584             fprintf(stderr,
1585                     "BN_bn2bin_padded gave a bad result.\n");
1586             goto err;
1587         }
1588         /* Pad up one byte extra. */
1589         if (!BN_bn2bin_padded(out, bytes + 1, n)
1590                 || memcmp(out + 1, reference, bytes)
1591                 || memcmp(out, zeros, 1)) {
1592             fprintf(stderr,
1593                     "BN_bn2bin_padded gave a bad result.\n");
1594             goto err;
1595         }
1596         /* Pad up to 256. */
1597         if (!BN_bn2bin_padded(out, sizeof(out), n)
1598                 || memcmp(out + sizeof(out) - bytes, reference, bytes)
1599                 || memcmp(out, zeros, sizeof(out) - bytes)) {
1600             fprintf(stderr,
1601                     "BN_bn2bin_padded gave a bad result.\n");
1602             goto err;
1603         }
1604     }
1605
1606     st = 1;
1607 err:
1608     BN_free(n);
1609     return st;
1610 #else
1611     return ctx != NULL;
1612 #endif
1613 }
1614
1615 static int test_dec2bn()
1616 {
1617     BIGNUM *bn = NULL;
1618     int st = 0;
1619
1620     int ret = parsedecBN(&bn, "0");
1621     if (ret != 1 || !BN_is_zero(bn) || BN_is_negative(bn)) {
1622         fprintf(stderr, "BN_dec2bn(0) gave a bad result.\n");
1623         goto err;
1624     }
1625     BN_free(bn);
1626
1627     ret = parsedecBN(&bn, "256");
1628     if (ret != 3 || !BN_is_word(bn, 256) || BN_is_negative(bn)) {
1629         fprintf(stderr, "BN_dec2bn(256) gave a bad result.\n");
1630         goto err;
1631     }
1632     BN_free(bn);
1633
1634     ret = parsedecBN(&bn, "-42");
1635     if (ret != 3 || !BN_abs_is_word(bn, 42) || !BN_is_negative(bn)) {
1636         fprintf(stderr, "BN_dec2bn(42) gave a bad result.\n");
1637         goto err;
1638     }
1639     BN_free(bn);
1640
1641     ret = parsedecBN(&bn, "-0");
1642     if (ret != 2 || !BN_is_zero(bn) || BN_is_negative(bn)) {
1643         fprintf(stderr, "BN_dec2bn(-0) gave a bad result.\n");
1644         goto err;
1645     }
1646     BN_free(bn);
1647
1648     ret = parsedecBN(&bn, "42trailing garbage is ignored");
1649     if (ret != 2 || !BN_abs_is_word(bn, 42)
1650             || BN_is_negative(bn)) {
1651         fprintf(stderr, "BN_dec2bn(42trailing...) gave a bad result.\n");
1652         goto err;
1653     }
1654
1655     st = 1;
1656 err:
1657     BN_free(bn);
1658     return st;
1659 }
1660
1661 static int test_hex2bn()
1662 {
1663     BIGNUM *bn = NULL;
1664     int ret, st = 0;
1665
1666     ret = parseBN(&bn, "0");
1667     if (ret != 1 || !BN_is_zero(bn) || BN_is_negative(bn)) {
1668         fprintf(stderr, "BN_hex2bn(0) gave a bad result.\n");
1669         goto err;
1670     }
1671     BN_free(bn);
1672
1673     ret = parseBN(&bn, "256");
1674     if (ret != 3 || !BN_is_word(bn, 0x256) || BN_is_negative(bn)) {
1675         fprintf(stderr, "BN_hex2bn(256) gave a bad result.\n");
1676         goto err;
1677     }
1678     BN_free(bn);
1679
1680     ret = parseBN(&bn, "-42");
1681     if (ret != 3 || !BN_abs_is_word(bn, 0x42) || !BN_is_negative(bn)) {
1682         fprintf(stderr, "BN_hex2bn(-42) gave a bad result.\n");
1683         goto err;
1684     }
1685     BN_free(bn);
1686
1687     ret = parseBN(&bn, "-0");
1688     if (ret != 2 || !BN_is_zero(bn) || BN_is_negative(bn)) {
1689         fprintf(stderr, "BN_hex2bn(-0) gave a bad result.\n");
1690         goto err;
1691     }
1692     BN_free(bn);
1693
1694     ret = parseBN(&bn, "abctrailing garbage is ignored");
1695     if (ret != 3 || !BN_is_word(bn, 0xabc) || BN_is_negative(bn)) {
1696         fprintf(stderr, "BN_hex2bn(abctrail...) gave a bad result.\n");
1697         goto err;
1698     }
1699     st = 1;
1700
1701 err:
1702     BN_free(bn);
1703     return st;
1704 }
1705
1706 static int test_asc2bn()
1707 {
1708     BIGNUM *bn = BN_new();
1709     int st = 0;
1710
1711     if (!BN_asc2bn(&bn, "0") || !BN_is_zero(bn) || BN_is_negative(bn)) {
1712         fprintf(stderr, "BN_asc2bn(0) gave a bad result.\n");
1713         goto err;
1714     }
1715
1716     if (!BN_asc2bn(&bn, "256") || !BN_is_word(bn, 256) || BN_is_negative(bn)) {
1717         fprintf(stderr, "BN_asc2bn(256) gave a bad result.\n");
1718         goto err;
1719     }
1720
1721     if (!BN_asc2bn(&bn, "-42")
1722             || !BN_abs_is_word(bn, 42) || !BN_is_negative(bn)) {
1723         fprintf(stderr, "BN_asc2bn(-42) gave a bad result.\n");
1724         goto err;
1725     }
1726
1727     if (!BN_asc2bn(&bn, "0x1234")
1728             || !BN_is_word(bn, 0x1234) || BN_is_negative(bn)) {
1729         fprintf(stderr, "BN_asc2bn(0x1234) gave a bad result.\n");
1730         goto err;
1731     }
1732
1733     if (!BN_asc2bn(&bn, "0X1234")
1734             || !BN_is_word(bn, 0x1234) || BN_is_negative(bn)) {
1735         fprintf(stderr, "BN_asc2bn(0X1234) gave a bad result.\n");
1736         goto err;
1737     }
1738
1739     if (!BN_asc2bn(&bn, "-0xabcd")
1740             || !BN_abs_is_word(bn, 0xabcd) || !BN_is_negative(bn)) {
1741         fprintf(stderr, "BN_asc2bn(-0xabcd) gave a bad result.\n");
1742         goto err;
1743     }
1744
1745     if (!BN_asc2bn(&bn, "-0") || !BN_is_zero(bn) || BN_is_negative(bn)) {
1746         fprintf(stderr, "BN_asc2bn(-0) gave a bad result.\n");
1747         goto err;
1748     }
1749
1750     if (!BN_asc2bn(&bn, "123trailing garbage is ignored")
1751             || !BN_is_word(bn, 123) || BN_is_negative(bn)) {
1752         fprintf(stderr, "BN_asc2bn(123trail...) gave a bad result.\n");
1753         goto err;
1754     }
1755
1756     st = 1;
1757 err:
1758     BN_free(bn);
1759     return st;
1760 }
1761
1762 static const MPITEST kMPITests[] = {
1763     {"0", "\x00\x00\x00\x00", 4},
1764     {"1", "\x00\x00\x00\x01\x01", 5},
1765     {"-1", "\x00\x00\x00\x01\x81", 5},
1766     {"128", "\x00\x00\x00\x02\x00\x80", 6},
1767     {"256", "\x00\x00\x00\x02\x01\x00", 6},
1768     {"-256", "\x00\x00\x00\x02\x81\x00", 6},
1769 };
1770
1771 static int test_mpi()
1772 {
1773     uint8_t scratch[8];
1774     int i = (int)sizeof(kMPITests) / sizeof(kMPITests[0]);
1775     const MPITEST *test = kMPITests;
1776     size_t mpi_len, mpi_len2;
1777     BIGNUM *bn = BN_new();
1778     BIGNUM *bn2 = NULL;
1779     int st = 0;
1780
1781     for ( ; --i >= 0; test++) {
1782         if (!BN_asc2bn(&bn, test->base10)) {
1783             fprintf(stderr, "Can't convert %s\n", test->base10);
1784             goto err;
1785         }
1786         mpi_len = BN_bn2mpi(bn, NULL);
1787         if (mpi_len > sizeof (scratch)) {
1788             fprintf(stderr,
1789                     "MPI test #%u: MPI size is too large to test.\n",
1790                     (unsigned)i);
1791             goto err;
1792         }
1793
1794         mpi_len2 = BN_bn2mpi(bn, scratch);
1795         if (mpi_len != mpi_len2) {
1796             fprintf(stderr, "MPI test #%u: length changes.\n",
1797                     (unsigned)i);
1798             goto err;
1799         }
1800
1801         if (mpi_len != test->mpi_len
1802                 || memcmp(test->mpi, scratch, mpi_len) != 0) {
1803             fprintf(stderr, "MPI test #%u failed:\n", (unsigned)i);
1804             goto err;
1805         }
1806
1807         bn2 = BN_mpi2bn(scratch, mpi_len, NULL);
1808         if (bn2 == NULL) {
1809             fprintf(stderr, "MPI test #%u: failed to parse\n",
1810                     (unsigned)i);
1811             goto err;
1812         }
1813
1814         if (BN_cmp(bn, bn2) != 0) {
1815             fprintf(stderr, "MPI test #%u: wrong result\n",
1816                     (unsigned)i);
1817             BN_free(bn2);
1818             goto err;
1819         }
1820         BN_free(bn2);
1821     }
1822
1823     st = 1;
1824 err:
1825     BN_free(bn);
1826     return st;
1827 }
1828
1829 static int test_rand()
1830 {
1831     BIGNUM *bn = BN_new();
1832     int st = 0;
1833
1834     if (bn == NULL)
1835         return 0;
1836
1837     /*
1838      * Test BN_rand for degenerate cases with |top| and |bottom| parameters.
1839      */
1840     if (BN_rand(bn, 0, 0 /* top */ , 0 /* bottom */ )) {
1841         fprintf(stderr, "BN_rand1 gave a bad result.\n");
1842         goto err;
1843     }
1844     if (BN_rand(bn, 0, 1 /* top */ , 1 /* bottom */ )) {
1845         fprintf(stderr, "BN_rand2 gave a bad result.\n");
1846         goto err;
1847     }
1848
1849     if (!BN_rand(bn, 1, 0 /* top */ , 0 /* bottom */ ) || !BN_is_word(bn, 1)) {
1850         fprintf(stderr, "BN_rand3 gave a bad result.\n");
1851         goto err;
1852     }
1853     if (BN_rand(bn, 1, 1 /* top */ , 0 /* bottom */ )) {
1854         fprintf(stderr, "BN_rand4 gave a bad result.\n");
1855         goto err;
1856     }
1857     if (!BN_rand(bn, 1, -1 /* top */ , 1 /* bottom */ ) || !BN_is_word(bn, 1)) {
1858         fprintf(stderr, "BN_rand5 gave a bad result.\n");
1859         goto err;
1860     }
1861
1862     if (!BN_rand(bn, 2, 1 /* top */ , 0 /* bottom */ ) || !BN_is_word(bn, 3)) {
1863         fprintf(stderr, "BN_rand6 gave a bad result.\n");
1864         goto err;
1865     }
1866
1867     st = 1;
1868 err:
1869     BN_free(bn);
1870     return st;
1871 }
1872
1873 static int test_negzero()
1874 {
1875     BIGNUM *a = BN_new();
1876     BIGNUM *b = BN_new();
1877     BIGNUM *c = BN_new();
1878     BIGNUM *d = BN_new();
1879     BIGNUM *numerator = NULL, *denominator = NULL;
1880     int consttime, st = 0;
1881
1882     if (a == NULL || b == NULL || c == NULL || d == NULL)
1883         goto err;
1884
1885     /* Test that BN_mul never gives negative zero. */
1886     if (!BN_set_word(a, 1))
1887         goto err;
1888     BN_set_negative(a, 1);
1889     BN_zero(b);
1890     if (!BN_mul(c, a, b, ctx))
1891         goto err;
1892     if (!BN_is_zero(c) || BN_is_negative(c)) {
1893         fprintf(stderr, "Multiplication test failed!\n");
1894         goto err;
1895     }
1896
1897     for (consttime = 0; consttime < 2; consttime++) {
1898         numerator = BN_new();
1899         denominator = BN_new();
1900         if (numerator == NULL || denominator == NULL)
1901             goto err;
1902         if (consttime) {
1903             BN_set_flags(numerator, BN_FLG_CONSTTIME);
1904             BN_set_flags(denominator, BN_FLG_CONSTTIME);
1905         }
1906         /* Test that BN_div never gives negative zero in the quotient. */
1907         if (!BN_set_word(numerator, 1) || !BN_set_word(denominator, 2))
1908             goto err;
1909         BN_set_negative(numerator, 1);
1910         if (!BN_div(a, b, numerator, denominator, ctx))
1911             goto err;
1912         if (!BN_is_zero(a) || BN_is_negative(a)) {
1913             fprintf(stderr, "Incorrect quotient (consttime = %d).\n",
1914                     consttime);
1915             goto err;
1916         }
1917
1918         /* Test that BN_div never gives negative zero in the remainder. */
1919         if (!BN_set_word(denominator, 1))
1920             goto err;
1921         if (!BN_div(a, b, numerator, denominator, ctx))
1922             goto err;
1923         if (!BN_is_zero(b) || BN_is_negative(b)) {
1924             fprintf(stderr, "Incorrect remainder (consttime = %d).\n",
1925                     consttime);
1926             goto err;
1927         }
1928         BN_free(numerator);
1929         BN_free(denominator);
1930         numerator = denominator = NULL;
1931     }
1932
1933     /* Test that BN_set_negative will not produce a negative zero. */
1934     BN_zero(a);
1935     BN_set_negative(a, 1);
1936     if (BN_is_negative(a)) {
1937         fprintf(stderr, "BN_set_negative produced a negative zero.\n");
1938         goto err;
1939     }
1940
1941     st = 1;
1942 err:
1943     BN_free(a);
1944     BN_free(b);
1945     BN_free(c);
1946     BN_free(d);
1947     BN_free(numerator);
1948     BN_free(denominator);
1949     return st;
1950 }
1951
1952 static int test_badmod()
1953 {
1954     BIGNUM *a = BN_new();
1955     BIGNUM *b = BN_new();
1956     BIGNUM *zero = BN_new();
1957     BN_MONT_CTX *mont = BN_MONT_CTX_new();
1958     int st = 0;
1959
1960     if (a == NULL || b == NULL || zero == NULL || mont == NULL)
1961         goto err;
1962     BN_zero(zero);
1963
1964     if (BN_div(a, b, BN_value_one(), zero, ctx)) {
1965         fprintf(stderr, "Division by zero succeeded!\n");
1966         goto err;
1967     }
1968     ERR_clear_error();
1969
1970     if (BN_mod_mul(a, BN_value_one(), BN_value_one(), zero, ctx)) {
1971         fprintf(stderr, "BN_mod_mul with zero modulus succeeded!\n");
1972         goto err;
1973     }
1974     ERR_clear_error();
1975
1976     if (BN_mod_exp(a, BN_value_one(), BN_value_one(), zero, ctx)) {
1977         fprintf(stderr, "BN_mod_exp with zero modulus succeeded!\n");
1978         goto err;
1979     }
1980     ERR_clear_error();
1981
1982     if (BN_mod_exp_mont(a, BN_value_one(), BN_value_one(), zero, ctx, NULL)) {
1983         fprintf(stderr, "BN_mod_exp_mont with zero modulus succeeded!\n");
1984         goto err;
1985     }
1986     ERR_clear_error();
1987
1988     if (BN_mod_exp_mont_consttime(a, BN_value_one(), BN_value_one(),
1989                                   zero, ctx, NULL)) {
1990         fprintf(stderr,
1991                 "BN_mod_exp_mont_consttime with zero modulus succeeded!\n");
1992         goto err;
1993     }
1994     ERR_clear_error();
1995
1996     if (BN_MONT_CTX_set(mont, zero, ctx)) {
1997         fprintf(stderr, "BN_MONT_CTX_set succeeded for zero modulus!\n");
1998         goto err;
1999     }
2000     ERR_clear_error();
2001
2002     /* Some operations also may not be used with an even modulus. */
2003     if (!BN_set_word(b, 16))
2004         goto err;
2005
2006     if (BN_MONT_CTX_set(mont, b, ctx)) {
2007         fprintf(stderr,
2008                 "BN_MONT_CTX_set succeeded for even modulus!\n");
2009         goto err;
2010     }
2011     ERR_clear_error();
2012
2013     if (BN_mod_exp_mont(a, BN_value_one(), BN_value_one(), b, ctx, NULL)) {
2014         fprintf(stderr,
2015                 "BN_mod_exp_mont with even modulus succeeded!\n");
2016         goto err;
2017     }
2018     ERR_clear_error();
2019
2020     if (BN_mod_exp_mont_consttime(a, BN_value_one(), BN_value_one(),
2021                                   b, ctx, NULL)) {
2022         fprintf(stderr,
2023                 "BN_mod_exp_mont_consttime with even modulus succeeded!\n");
2024         goto err;
2025     }
2026     ERR_clear_error();
2027
2028     st = 1;
2029 err:
2030     BN_free(a);
2031     BN_free(b);
2032     BN_free(zero);
2033     BN_MONT_CTX_free(mont);
2034     return st;
2035 }
2036
2037 static int test_expmodzero()
2038 {
2039     BIGNUM *zero = BN_new();
2040     BIGNUM *a = BN_new();
2041     BIGNUM *r = BN_new();
2042     int st = 0;
2043
2044     if (zero == NULL || a == NULL || r == NULL || !BN_rand(a, 1024, 0, 0))
2045         goto err;
2046     BN_zero(zero);
2047
2048     if (!BN_mod_exp(r, a, zero, BN_value_one(), NULL)
2049             || !BN_is_zero(r)
2050             || !BN_mod_exp_mont(r, a, zero, BN_value_one(), NULL, NULL)
2051             || !BN_is_zero(r)
2052             || !BN_mod_exp_mont_consttime(r, a, zero, BN_value_one(), NULL, NULL)
2053             || !BN_is_zero(r)
2054             || !BN_mod_exp_mont_word(r, 42, zero, BN_value_one(), NULL, NULL)
2055             || !BN_is_zero(r))
2056         goto err;
2057
2058     st = 1;
2059 err:
2060     BN_free(zero);
2061     BN_free(a);
2062     BN_free(r);
2063     return st;
2064 }
2065
2066 static int test_smallprime()
2067 {
2068     static const int kBits = 10;
2069     BIGNUM *r = BN_new();
2070     int st = 0;
2071
2072     if (r == NULL
2073             || !BN_generate_prime_ex(r, (int)kBits, 0, NULL, NULL, NULL))
2074         goto err;
2075     if (BN_num_bits(r) != kBits) {
2076         fprintf(stderr, "Expected %u bit prime, got %u bit number\n",
2077                 kBits, BN_num_bits(r));
2078         goto err;
2079     }
2080
2081     st = 1;
2082 err:
2083     BN_free(r);
2084     return st;
2085 }
2086
2087
2088 /* Delete leading and trailing spaces from a string */
2089 static char *strip_spaces(char *p)
2090 {
2091     char *q;
2092
2093     /* Skip over leading spaces */
2094     while (*p && isspace(*p))
2095         p++;
2096     if (!*p)
2097         return NULL;
2098
2099     for (q = p + strlen(p) - 1; q != p && isspace(*q); )
2100         *q-- = '\0';
2101     return *p ? p : NULL;
2102 }
2103
2104 /*
2105  * Read next test stanza; return 1 if found, 0 on EOF or error.
2106  */
2107 static int readstanza(STANZA *s, int *linesread)
2108 {
2109     PAIR *pp = s->pairs;
2110     char *p, *equals, *key, *value;
2111     char buff[1024];
2112
2113     while (fgets(buff, sizeof(buff), fp) != NULL) {
2114         (*linesread)++;
2115         if ((p = strchr(buff, '\n')) == NULL) {
2116             fprintf(stderr, "Line %d too long.\n", s->start);
2117             return 0;
2118         }
2119         *p = '\0';
2120
2121         /* Blank line marks end of tests. */
2122         if (buff[0] == '\0')
2123             break;
2124
2125         /* Lines starting with a pound sign are ignored. */
2126         if (buff[0] == '#')
2127             continue;
2128
2129         if ((equals = strchr(buff, '=')) == NULL) {
2130             fprintf(stderr, "Line %d missing equals.\n", s->start);
2131             return 0;
2132         }
2133         *equals++ = '\0';
2134
2135         key = strip_spaces(buff);
2136         value = strip_spaces(equals);
2137         if (key == NULL || value == NULL) {
2138             fprintf(stderr, "Line %d missing field.\n", s->start);
2139             return 0;
2140         }
2141         s->numpairs++;
2142         if (s->numpairs >= MAXPAIRS) {
2143             fprintf(stderr, "Line %d too many lines\n", s->start);
2144             return 0;
2145         }
2146         pp->key = OPENSSL_strdup(key);
2147         pp->value = OPENSSL_strdup(value);
2148         pp++;
2149     }
2150
2151     /* If we read anything, return ok. */
2152     return 1;
2153 }
2154
2155 static void clearstanza(STANZA *s)
2156 {
2157     PAIR *pp = s->pairs;
2158     int i = s->numpairs;
2159     int start = s->start;
2160
2161     for ( ; --i >= 0; pp++) {
2162         OPENSSL_free(pp->key);
2163         OPENSSL_free(pp->value);
2164     }
2165     memset(s, 0, sizeof(*s));
2166     s->start = start;
2167 }
2168
2169 static int file_test_run(STANZA *s)
2170 {
2171     static const FILETEST filetests[] = {
2172         {"Sum", file_sum},
2173         {"LShift1", file_lshift1},
2174         {"LShift", file_lshift},
2175         {"RShift", file_rshift},
2176         {"Square", file_square},
2177         {"Product", file_product},
2178         {"Quotient", file_quotient},
2179         {"ModMul", file_modmul},
2180         {"ModExp", file_modexp},
2181         {"Exp", file_exp},
2182         {"ModSqrt", file_modsqrt},
2183     };
2184     int numtests = OSSL_NELEM(filetests);
2185     const FILETEST *tp = filetests;
2186
2187     for ( ; --numtests >= 0; tp++) {
2188         if (findattr(s, tp->name) != NULL)
2189             return tp->func(s);
2190     }
2191     fprintf(stderr, "Unknown test at %d\n", s->start);
2192     return 0;
2193 }
2194
2195 static int file_tests()
2196 {
2197     STANZA s;
2198     int linesread = 0, result = 0;
2199
2200     /* Read test file. */
2201     memset(&s, 0, sizeof(s));
2202     while (!feof(fp) && readstanza(&s, &linesread)) {
2203         if (s.numpairs == 0)
2204             continue;
2205         if (!file_test_run(&s)) {
2206             if (result == 0)
2207                 fprintf(stderr, "Test at %d failed\n", s.start);
2208             goto err;
2209         }
2210         clearstanza(&s);
2211         s.start = linesread;
2212     }
2213     result = 1;
2214
2215 err:
2216     return result;
2217 }
2218
2219 int test_main(int argc, char *argv[])
2220 {
2221     static const char rnd_seed[] =
2222         "If not seeded, BN_generate_prime might fail";
2223     int result = 0;
2224
2225     if (argc != 2) {
2226         fprintf(stderr, "%s TEST_FILE\n", argv[0]);
2227         return 1;
2228     }
2229
2230     ADD_TEST(test_sub);
2231     ADD_TEST(test_div_recip);
2232     ADD_TEST(test_mod);
2233     ADD_TEST(test_modexp_mont5);
2234     ADD_TEST(test_kronecker);
2235     ADD_TEST(test_rand);
2236     ADD_TEST(test_bn2padded);
2237     ADD_TEST(test_dec2bn);
2238     ADD_TEST(test_hex2bn);
2239     ADD_TEST(test_asc2bn);
2240     ADD_TEST(test_mpi);
2241     ADD_TEST(test_negzero);
2242     ADD_TEST(test_badmod);
2243     ADD_TEST(test_expmodzero);
2244     ADD_TEST(test_smallprime);
2245 #ifndef OPENSSL_NO_EC2M
2246     ADD_TEST(test_gf2m_add);
2247     ADD_TEST(test_gf2m_mod);
2248     ADD_TEST(test_gf2m_mul);
2249     ADD_TEST(test_gf2m_sqr);
2250     ADD_TEST(test_gf2m_modinv);
2251     ADD_TEST(test_gf2m_moddiv);
2252     ADD_TEST(test_gf2m_modexp);
2253     ADD_TEST(test_gf2m_modsqrt);
2254     ADD_TEST(test_gf2m_modsolvequad);
2255 #endif
2256     ADD_TEST(file_tests);
2257
2258     RAND_seed(rnd_seed, sizeof rnd_seed);
2259     ctx = BN_CTX_new();
2260     TEST_check(ctx != NULL);
2261
2262     fp = fopen(argv[1], "r");
2263     TEST_check(fp != NULL);
2264     result = run_tests(argv[0]);
2265     fclose(fp);
2266
2267     BN_CTX_free(ctx);
2268     return result;
2269 }