b58028a3014132e7a714d93637ac495d46ed11e3
[openssl.git] / test / bntest.c
1 /*
2  * Copyright 1995-2021 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 <openssl/bn.h>
16 #include <openssl/crypto.h>
17 #include <openssl/err.h>
18 #include <openssl/rand.h>
19 #include "internal/nelem.h"
20 #include "internal/numbers.h"
21 #include "testutil.h"
22
23 #ifdef OPENSSL_SYS_WINDOWS
24 # define strcasecmp _stricmp
25 #endif
26
27 /*
28  * Things in boring, not in openssl.  TODO we should add them.
29  */
30 #define HAVE_BN_SQRT 0
31
32 typedef struct filetest_st {
33     const char *name;
34     int (*func)(STANZA *s);
35 } FILETEST;
36
37 typedef struct mpitest_st {
38     const char *base10;
39     const char *mpi;
40     size_t mpi_len;
41 } MPITEST;
42
43 static const int NUM0 = 100;           /* number of tests */
44 static const int NUM1 = 50;            /* additional tests for some functions */
45 static BN_CTX *ctx;
46
47 /*
48  * Polynomial coefficients used in GFM tests.
49  */
50 #ifndef OPENSSL_NO_EC2M
51 static int p0[] = { 163, 7, 6, 3, 0, -1 };
52 static int p1[] = { 193, 15, 0, -1 };
53 #endif
54
55 /*
56  * Look for |key| in the stanza and return it or NULL if not found.
57  */
58 static const char *findattr(STANZA *s, const char *key)
59 {
60     int i = s->numpairs;
61     PAIR *pp = s->pairs;
62
63     for ( ; --i >= 0; pp++)
64         if (strcasecmp(pp->key, key) == 0)
65             return pp->value;
66     return NULL;
67 }
68
69 /*
70  * Parse BIGNUM from sparse hex-strings, return |BN_hex2bn| result.
71  */
72 static int parse_bigBN(BIGNUM **out, const char *bn_strings[])
73 {
74     char *bigstring = glue_strings(bn_strings, NULL);
75     int ret = BN_hex2bn(out, bigstring);
76
77     OPENSSL_free(bigstring);
78     return ret;
79 }
80
81 /*
82  * Parse BIGNUM, return number of bytes parsed.
83  */
84 static int parseBN(BIGNUM **out, const char *in)
85 {
86     *out = NULL;
87     return BN_hex2bn(out, in);
88 }
89
90 static int parsedecBN(BIGNUM **out, const char *in)
91 {
92     *out = NULL;
93     return BN_dec2bn(out, in);
94 }
95
96 static BIGNUM *getBN(STANZA *s, const char *attribute)
97 {
98     const char *hex;
99     BIGNUM *ret = NULL;
100
101     if ((hex = findattr(s, attribute)) == NULL) {
102         TEST_error("%s:%d: Can't find %s", s->test_file, s->start, attribute);
103         return NULL;
104     }
105
106     if (parseBN(&ret, hex) != (int)strlen(hex)) {
107         TEST_error("Could not decode '%s'", hex);
108         return NULL;
109     }
110     return ret;
111 }
112
113 static int getint(STANZA *s, int *out, const char *attribute)
114 {
115     BIGNUM *ret;
116     BN_ULONG word;
117     int st = 0;
118
119     if (!TEST_ptr(ret = getBN(s, attribute))
120             || !TEST_ulong_le(word = BN_get_word(ret), INT_MAX))
121         goto err;
122
123     *out = (int)word;
124     st = 1;
125  err:
126     BN_free(ret);
127     return st;
128 }
129
130 static int equalBN(const char *op, const BIGNUM *expected, const BIGNUM *actual)
131 {
132     if (BN_cmp(expected, actual) == 0)
133         return 1;
134
135     TEST_error("unexpected %s value", op);
136     TEST_BN_eq(expected, actual);
137     return 0;
138 }
139
140 /*
141  * Return a "random" flag for if a BN should be negated.
142  */
143 static int rand_neg(void)
144 {
145     static unsigned int neg = 0;
146     static int sign[8] = { 0, 0, 0, 1, 1, 0, 1, 1 };
147
148     return sign[(neg++) % 8];
149 }
150
151 static int test_swap(void)
152 {
153     BIGNUM *a = NULL, *b = NULL, *c = NULL, *d = NULL;
154     int top, cond, st = 0;
155
156     if (!TEST_ptr(a = BN_new())
157             || !TEST_ptr(b = BN_new())
158             || !TEST_ptr(c = BN_new())
159             || !TEST_ptr(d = BN_new()))
160         goto err;
161
162     if (!(TEST_true(BN_bntest_rand(a, 1024, 1, 0))
163             && TEST_true(BN_bntest_rand(b, 1024, 1, 0))
164             && TEST_ptr(BN_copy(c, a))
165             && TEST_ptr(BN_copy(d, b))))
166         goto err;
167     top = BN_num_bits(a) / BN_BITS2;
168
169     /* regular swap */
170     BN_swap(a, b);
171     if (!equalBN("swap", a, d)
172             || !equalBN("swap", b, c))
173         goto err;
174
175     /* conditional swap: true */
176     cond = 1;
177     BN_consttime_swap(cond, a, b, top);
178     if (!equalBN("cswap true", a, c)
179             || !equalBN("cswap true", b, d))
180         goto err;
181
182     /* conditional swap: false */
183     cond = 0;
184     BN_consttime_swap(cond, a, b, top);
185     if (!equalBN("cswap false", a, c)
186             || !equalBN("cswap false", b, d))
187         goto err;
188
189     /* same tests but checking flag swap */
190     BN_set_flags(a, BN_FLG_CONSTTIME);
191
192     BN_swap(a, b);
193     if (!equalBN("swap, flags", a, d)
194             || !equalBN("swap, flags", b, c)
195             || !TEST_true(BN_get_flags(b, BN_FLG_CONSTTIME))
196             || !TEST_false(BN_get_flags(a, BN_FLG_CONSTTIME)))
197         goto err;
198
199     cond = 1;
200     BN_consttime_swap(cond, a, b, top);
201     if (!equalBN("cswap true, flags", a, c)
202             || !equalBN("cswap true, flags", b, d)
203             || !TEST_true(BN_get_flags(a, BN_FLG_CONSTTIME))
204             || !TEST_false(BN_get_flags(b, BN_FLG_CONSTTIME)))
205         goto err;
206
207     cond = 0;
208     BN_consttime_swap(cond, a, b, top);
209     if (!equalBN("cswap false, flags", a, c)
210             || !equalBN("cswap false, flags", b, d)
211             || !TEST_true(BN_get_flags(a, BN_FLG_CONSTTIME))
212             || !TEST_false(BN_get_flags(b, BN_FLG_CONSTTIME)))
213         goto err;
214
215     st = 1;
216  err:
217     BN_free(a);
218     BN_free(b);
219     BN_free(c);
220     BN_free(d);
221     return st;
222 }
223
224 static int test_sub(void)
225 {
226     BIGNUM *a = NULL, *b = NULL, *c = NULL;
227     int i, st = 0;
228
229     if (!TEST_ptr(a = BN_new())
230             || !TEST_ptr(b = BN_new())
231             || !TEST_ptr(c = BN_new()))
232         goto err;
233
234     for (i = 0; i < NUM0 + NUM1; i++) {
235         if (i < NUM1) {
236             if (!(TEST_true(BN_bntest_rand(a, 512, 0, 0)))
237                     && TEST_ptr(BN_copy(b, a))
238                     && TEST_int_ne(BN_set_bit(a, i), 0)
239                     && TEST_true(BN_add_word(b, i)))
240                 goto err;
241         } else {
242             if (!TEST_true(BN_bntest_rand(b, 400 + i - NUM1, 0, 0)))
243                 goto err;
244             BN_set_negative(a, rand_neg());
245             BN_set_negative(b, rand_neg());
246         }
247         if (!(TEST_true(BN_sub(c, a, b))
248                 && TEST_true(BN_add(c, c, b))
249                 && TEST_true(BN_sub(c, c, a))
250                 && TEST_BN_eq_zero(c)))
251             goto err;
252     }
253     st = 1;
254  err:
255     BN_free(a);
256     BN_free(b);
257     BN_free(c);
258     return st;
259 }
260
261 static int test_div_recip(void)
262 {
263     BIGNUM *a = NULL, *b = NULL, *c = NULL, *d = NULL, *e = NULL;
264     BN_RECP_CTX *recp = NULL;
265     int st = 0, i;
266
267     if (!TEST_ptr(a = BN_new())
268             || !TEST_ptr(b = BN_new())
269             || !TEST_ptr(c = BN_new())
270             || !TEST_ptr(d = BN_new())
271             || !TEST_ptr(e = BN_new())
272             || !TEST_ptr(recp = BN_RECP_CTX_new()))
273         goto err;
274
275     for (i = 0; i < NUM0 + NUM1; i++) {
276         if (i < NUM1) {
277             if (!(TEST_true(BN_bntest_rand(a, 400, 0, 0))
278                     && TEST_ptr(BN_copy(b, a))
279                     && TEST_true(BN_lshift(a, a, i))
280                     && TEST_true(BN_add_word(a, i))))
281                 goto err;
282         } else {
283             if (!(TEST_true(BN_bntest_rand(b, 50 + 3 * (i - NUM1), 0, 0))))
284                 goto err;
285         }
286         BN_set_negative(a, rand_neg());
287         BN_set_negative(b, rand_neg());
288         if (!(TEST_true(BN_RECP_CTX_set(recp, b, ctx))
289                 && TEST_true(BN_div_recp(d, c, a, recp, ctx))
290                 && TEST_true(BN_mul(e, d, b, ctx))
291                 && TEST_true(BN_add(d, e, c))
292                 && TEST_true(BN_sub(d, d, a))
293                 && TEST_BN_eq_zero(d)))
294             goto err;
295     }
296     st = 1;
297  err:
298     BN_free(a);
299     BN_free(b);
300     BN_free(c);
301     BN_free(d);
302     BN_free(e);
303     BN_RECP_CTX_free(recp);
304     return st;
305 }
306
307 static struct {
308     int n, divisor, result, remainder;
309 } signed_mod_tests[] = {
310     {  10,   3,   3,   1 },
311     { -10,   3,  -3,  -1 },
312     {  10,  -3,  -3,   1 },
313     { -10,  -3,   3,  -1 },
314 };
315
316 static BIGNUM *set_signed_bn(int value)
317 {
318     BIGNUM *bn = BN_new();
319
320     if (bn == NULL)
321         return NULL;
322     if (!BN_set_word(bn, value < 0 ? -value : value)) {
323         BN_free(bn);
324         return NULL;
325     }
326     BN_set_negative(bn, value < 0);
327     return bn;
328 }
329
330 static int test_signed_mod_replace_ab(int n)
331 {
332     BIGNUM *a = NULL, *b = NULL, *c = NULL, *d = NULL;
333     int st = 0;
334
335     if (!TEST_ptr(a = set_signed_bn(signed_mod_tests[n].n))
336             || !TEST_ptr(b = set_signed_bn(signed_mod_tests[n].divisor))
337             || !TEST_ptr(c = set_signed_bn(signed_mod_tests[n].result))
338             || !TEST_ptr(d = set_signed_bn(signed_mod_tests[n].remainder)))
339         goto err;
340
341     if (TEST_true(BN_div(a, b, a, b, ctx))
342             && TEST_BN_eq(a, c)
343             && TEST_BN_eq(b, d))
344         st = 1;
345  err:
346     BN_free(a);
347     BN_free(b);
348     BN_free(c);
349     BN_free(d);
350     return st;
351 }
352
353 static int test_signed_mod_replace_ba(int n)
354 {
355     BIGNUM *a = NULL, *b = NULL, *c = NULL, *d = NULL;
356     int st = 0;
357
358     if (!TEST_ptr(a = set_signed_bn(signed_mod_tests[n].n))
359             || !TEST_ptr(b = set_signed_bn(signed_mod_tests[n].divisor))
360             || !TEST_ptr(c = set_signed_bn(signed_mod_tests[n].result))
361             || !TEST_ptr(d = set_signed_bn(signed_mod_tests[n].remainder)))
362         goto err;
363
364     if (TEST_true(BN_div(b, a, a, b, ctx))
365             && TEST_BN_eq(b, c)
366             && TEST_BN_eq(a, d))
367         st = 1;
368  err:
369     BN_free(a);
370     BN_free(b);
371     BN_free(c);
372     BN_free(d);
373     return st;
374 }
375
376 static int test_mod(void)
377 {
378     BIGNUM *a = NULL, *b = NULL, *c = NULL, *d = NULL, *e = NULL;
379     int st = 0, i;
380
381     if (!TEST_ptr(a = BN_new())
382             || !TEST_ptr(b = BN_new())
383             || !TEST_ptr(c = BN_new())
384             || !TEST_ptr(d = BN_new())
385             || !TEST_ptr(e = BN_new()))
386         goto err;
387
388     if (!(TEST_true(BN_bntest_rand(a, 1024, 0, 0))))
389         goto err;
390     for (i = 0; i < NUM0; i++) {
391         if (!(TEST_true(BN_bntest_rand(b, 450 + i * 10, 0, 0))))
392             goto err;
393         BN_set_negative(a, rand_neg());
394         BN_set_negative(b, rand_neg());
395         if (!(TEST_true(BN_mod(c, a, b, ctx))
396                 && TEST_true(BN_div(d, e, a, b, ctx))
397                 && TEST_BN_eq(e, c)
398                 && TEST_true(BN_mul(c, d, b, ctx))
399                 && TEST_true(BN_add(d, c, e))
400                 && TEST_BN_eq(d, a)))
401             goto err;
402     }
403     st = 1;
404  err:
405     BN_free(a);
406     BN_free(b);
407     BN_free(c);
408     BN_free(d);
409     BN_free(e);
410     return st;
411 }
412
413 static const char *bn1strings[] = {
414     "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
415     "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
416     "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
417     "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
418     "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
419     "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
420     "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
421     "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00000000000000FFFFFFFF00",
422     "0000000000000000000000000000000000000000000000000000000000000000",
423     "0000000000000000000000000000000000000000000000000000000000000000",
424     "0000000000000000000000000000000000000000000000000000000000000000",
425     "0000000000000000000000000000000000000000000000000000000000000000",
426     "0000000000000000000000000000000000000000000000000000000000000000",
427     "0000000000000000000000000000000000000000000000000000000000000000",
428     "0000000000000000000000000000000000000000000000000000000000000000",
429     "00000000000000000000000000000000000000000000000000FFFFFFFFFFFFFF",
430     NULL
431 };
432
433 static const char *bn2strings[] = {
434     "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
435     "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
436     "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
437     "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
438     "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
439     "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
440     "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
441     "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00000000000000FFFFFFFF0000000000",
442     "0000000000000000000000000000000000000000000000000000000000000000",
443     "0000000000000000000000000000000000000000000000000000000000000000",
444     "0000000000000000000000000000000000000000000000000000000000000000",
445     "0000000000000000000000000000000000000000000000000000000000000000",
446     "0000000000000000000000000000000000000000000000000000000000000000",
447     "0000000000000000000000000000000000000000000000000000000000000000",
448     "0000000000000000000000000000000000000000000000000000000000000000",
449     "000000000000000000000000000000000000000000FFFFFFFFFFFFFF00000000",
450     NULL
451 };
452
453 /*
454  * Test constant-time modular exponentiation with 1024-bit inputs, which on
455  * x86_64 cause a different code branch to be taken.
456  */
457 static int test_modexp_mont5(void)
458 {
459     BIGNUM *a = NULL, *p = NULL, *m = NULL, *d = NULL, *e = NULL;
460     BIGNUM *b = NULL, *n = NULL, *c = NULL;
461     BN_MONT_CTX *mont = NULL;
462     int st = 0;
463
464     if (!TEST_ptr(a = BN_new())
465             || !TEST_ptr(p = BN_new())
466             || !TEST_ptr(m = BN_new())
467             || !TEST_ptr(d = BN_new())
468             || !TEST_ptr(e = BN_new())
469             || !TEST_ptr(b = BN_new())
470             || !TEST_ptr(n = BN_new())
471             || !TEST_ptr(c = BN_new())
472             || !TEST_ptr(mont = BN_MONT_CTX_new()))
473         goto err;
474
475     /* must be odd for montgomery */
476     if (!(TEST_true(BN_bntest_rand(m, 1024, 0, 1))
477             /* Zero exponent */
478             && TEST_true(BN_bntest_rand(a, 1024, 0, 0))))
479         goto err;
480     BN_zero(p);
481
482     if (!TEST_true(BN_mod_exp_mont_consttime(d, a, p, m, ctx, NULL)))
483         goto err;
484     if (!TEST_BN_eq_one(d))
485         goto err;
486
487     /* Regression test for carry bug in mulx4x_mont */
488     if (!(TEST_true(BN_hex2bn(&a,
489         "7878787878787878787878787878787878787878787878787878787878787878"
490         "7878787878787878787878787878787878787878787878787878787878787878"
491         "7878787878787878787878787878787878787878787878787878787878787878"
492         "7878787878787878787878787878787878787878787878787878787878787878"))
493         && TEST_true(BN_hex2bn(&b,
494         "095D72C08C097BA488C5E439C655A192EAFB6380073D8C2664668EDDB4060744"
495         "E16E57FB4EDB9AE10A0CEFCDC28A894F689A128379DB279D48A2E20849D68593"
496         "9B7803BCF46CEBF5C533FB0DD35B080593DE5472E3FE5DB951B8BFF9B4CB8F03"
497         "9CC638A5EE8CDD703719F8000E6A9F63BEED5F2FCD52FF293EA05A251BB4AB81"))
498         && TEST_true(BN_hex2bn(&n,
499         "D78AF684E71DB0C39CFF4E64FB9DB567132CB9C50CC98009FEB820B26F2DED9B"
500         "91B9B5E2B83AE0AE4EB4E0523CA726BFBE969B89FD754F674CE99118C3F2D1C5"
501         "D81FDC7C54E02B60262B241D53C040E99E45826ECA37A804668E690E1AFC1CA4"
502         "2C9A15D84D4954425F0B7642FC0BD9D7B24E2618D2DCC9B729D944BADACFDDAF"))))
503         goto err;
504
505     if (!(TEST_true(BN_MONT_CTX_set(mont, n, ctx))
506             && TEST_true(BN_mod_mul_montgomery(c, a, b, mont, ctx))
507             && TEST_true(BN_mod_mul_montgomery(d, b, a, mont, ctx))
508             && TEST_BN_eq(c, d)))
509         goto err;
510
511     /* Regression test for carry bug in sqr[x]8x_mont */
512     if (!(TEST_true(parse_bigBN(&n, bn1strings))
513             && TEST_true(parse_bigBN(&a, bn2strings))))
514         goto err;
515     BN_free(b);
516     if (!(TEST_ptr(b = BN_dup(a))
517             && TEST_true(BN_MONT_CTX_set(mont, n, ctx))
518             && TEST_true(BN_mod_mul_montgomery(c, a, a, mont, ctx))
519             && TEST_true(BN_mod_mul_montgomery(d, a, b, mont, ctx))
520             && TEST_BN_eq(c, d)))
521         goto err;
522
523     /* Regression test for carry bug in bn_sqrx8x_internal */
524     {
525         static const char *ahex[] = {
526                       "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
527             "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
528             "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
529             "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
530             "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF8FFEADBCFC4DAE7FFF908E92820306B",
531             "9544D954000000006C0000000000000000000000000000000000000000000000",
532             "00000000000000000000FF030202FFFFF8FFEBDBCFC4DAE7FFF908E92820306B",
533             "9544D954000000006C000000FF0302030000000000FFFFFFFFFFFFFFFFFFFFFF",
534             "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF01FC00FF02FFFFFFFF",
535             "00FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00FCFD",
536             "FCFFFFFFFFFF000000000000000000FF0302030000000000FFFFFFFFFFFFFFFF",
537             "FF00FCFDFDFF030202FF00000000FFFFFFFFFFFFFFFFFF00FCFDFCFFFFFFFFFF",
538             NULL
539         };
540         static const char *nhex[] = {
541                       "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
542             "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
543             "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
544             "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
545             "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF8F8F8F8000000",
546             "00000010000000006C0000000000000000000000000000000000000000000000",
547             "00000000000000000000000000000000000000FFFFFFFFFFFFF8F8F8F8000000",
548             "00000010000000006C000000000000000000000000FFFFFFFFFFFFFFFFFFFFFF",
549             "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
550             "00FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
551             "FFFFFFFFFFFF000000000000000000000000000000000000FFFFFFFFFFFFFFFF",
552             "FFFFFFFFFFFFFFFFFFFF00000000FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
553             NULL
554         };
555
556         if (!(TEST_true(parse_bigBN(&a, ahex))
557                 && TEST_true(parse_bigBN(&n, nhex))))
558             goto err;
559     }
560     BN_free(b);
561     if (!(TEST_ptr(b = BN_dup(a))
562             && TEST_true(BN_MONT_CTX_set(mont, n, ctx))))
563         goto err;
564
565     if (!TEST_true(BN_mod_mul_montgomery(c, a, a, mont, ctx))
566             || !TEST_true(BN_mod_mul_montgomery(d, a, b, mont, ctx))
567             || !TEST_BN_eq(c, d))
568         goto err;
569
570     /* Regression test for bug in BN_from_montgomery_word */
571     if (!(TEST_true(BN_hex2bn(&a,
572         "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
573         "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
574         "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"))
575          && TEST_true(BN_hex2bn(&n,
576         "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
577         "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"))
578         && TEST_true(BN_MONT_CTX_set(mont, n, ctx))
579         && TEST_false(BN_mod_mul_montgomery(d, a, a, mont, ctx))))
580         goto err;
581
582     /* Regression test for bug in rsaz_1024_mul_avx2 */
583     if (!(TEST_true(BN_hex2bn(&a,
584         "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
585         "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
586         "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
587         "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF2020202020DF"))
588         && TEST_true(BN_hex2bn(&b,
589         "2020202020202020202020202020202020202020202020202020202020202020"
590         "2020202020202020202020202020202020202020202020202020202020202020"
591         "20202020202020FF202020202020202020202020202020202020202020202020"
592         "2020202020202020202020202020202020202020202020202020202020202020"))
593         && TEST_true(BN_hex2bn(&n,
594         "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
595         "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
596         "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
597         "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF2020202020FF"))
598         && TEST_true(BN_MONT_CTX_set(mont, n, ctx))
599         && TEST_true(BN_mod_exp_mont_consttime(c, a, b, n, ctx, mont))
600         && TEST_true(BN_mod_exp_mont(d, a, b, n, ctx, mont))
601         && TEST_BN_eq(c, d)))
602         goto err;
603
604     /*
605      * rsaz_1024_mul_avx2 expects fully-reduced inputs.
606      * BN_mod_exp_mont_consttime should reduce the input first.
607      */
608     if (!(TEST_true(BN_hex2bn(&a,
609         "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
610         "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
611         "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
612         "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF2020202020DF"))
613         && TEST_true(BN_hex2bn(&b,
614         "1FA53F26F8811C58BE0357897AA5E165693230BC9DF5F01DFA6A2D59229EC69D"
615         "9DE6A89C36E3B6957B22D6FAAD5A3C73AE587B710DBE92E83D3A9A3339A085CB"
616         "B58F508CA4F837924BB52CC1698B7FDC2FD74362456A595A5B58E38E38E38E38"
617         "E38E38E38E38E38E38E38E38E38E38E38E38E38E38E38E38E38E38E38E38E38E"))
618         && TEST_true(BN_hex2bn(&n,
619         "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
620         "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
621         "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
622         "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF2020202020DF"))
623         && TEST_true(BN_MONT_CTX_set(mont, n, ctx))
624         && TEST_true(BN_mod_exp_mont_consttime(c, a, b, n, ctx, mont))))
625         goto err;
626     BN_zero(d);
627     if (!TEST_BN_eq(c, d))
628         goto err;
629
630     /* Zero input */
631     if (!TEST_true(BN_bntest_rand(p, 1024, 0, 0)))
632         goto err;
633     BN_zero(a);
634     if (!TEST_true(BN_mod_exp_mont_consttime(d, a, p, m, ctx, NULL))
635             || !TEST_BN_eq_zero(d))
636         goto err;
637
638     /*
639      * Craft an input whose Montgomery representation is 1, i.e., shorter
640      * than the modulus m, in order to test the const time precomputation
641      * scattering/gathering.
642      */
643     if (!(TEST_true(BN_one(a))
644             && TEST_true(BN_MONT_CTX_set(mont, m, ctx))))
645         goto err;
646     if (!TEST_true(BN_from_montgomery(e, a, mont, ctx))
647             || !TEST_true(BN_mod_exp_mont_consttime(d, e, p, m, ctx, NULL))
648             || !TEST_true(BN_mod_exp_simple(a, e, p, m, ctx))
649             || !TEST_BN_eq(a, d))
650         goto err;
651
652     /* Finally, some regular test vectors. */
653     if (!(TEST_true(BN_bntest_rand(e, 1024, 0, 0))
654             && TEST_true(BN_mod_exp_mont_consttime(d, e, p, m, ctx, NULL))
655             && TEST_true(BN_mod_exp_simple(a, e, p, m, ctx))
656             && TEST_BN_eq(a, d)))
657         goto err;
658
659     st = 1;
660
661  err:
662     BN_MONT_CTX_free(mont);
663     BN_free(a);
664     BN_free(p);
665     BN_free(m);
666     BN_free(d);
667     BN_free(e);
668     BN_free(b);
669     BN_free(n);
670     BN_free(c);
671     return st;
672 }
673
674 #ifndef OPENSSL_NO_EC2M
675 static int test_gf2m_add(void)
676 {
677     BIGNUM *a = NULL, *b = NULL, *c = NULL;
678     int i, st = 0;
679
680     if (!TEST_ptr(a = BN_new())
681             || !TEST_ptr(b = BN_new())
682             || !TEST_ptr(c = BN_new()))
683         goto err;
684
685     for (i = 0; i < NUM0; i++) {
686         if (!(TEST_true(BN_rand(a, 512, 0, 0))
687                 && TEST_ptr(BN_copy(b, BN_value_one()))))
688             goto err;
689         BN_set_negative(a, rand_neg());
690         BN_set_negative(b, rand_neg());
691         if (!(TEST_true(BN_GF2m_add(c, a, b))
692                 /* Test that two added values have the correct parity. */
693                 && TEST_false((BN_is_odd(a) && BN_is_odd(c))
694                         || (!BN_is_odd(a) && !BN_is_odd(c)))))
695             goto err;
696         if (!(TEST_true(BN_GF2m_add(c, c, c))
697                 /* Test that c + c = 0. */
698                 && TEST_BN_eq_zero(c)))
699             goto err;
700     }
701     st = 1;
702  err:
703     BN_free(a);
704     BN_free(b);
705     BN_free(c);
706     return st;
707 }
708
709 static int test_gf2m_mod(void)
710 {
711     BIGNUM *a = NULL, *b[2] = {NULL,NULL}, *c = NULL, *d = NULL, *e = NULL;
712     int i, j, st = 0;
713
714     if (!TEST_ptr(a = BN_new())
715             || !TEST_ptr(b[0] = BN_new())
716             || !TEST_ptr(b[1] = BN_new())
717             || !TEST_ptr(c = BN_new())
718             || !TEST_ptr(d = BN_new())
719             || !TEST_ptr(e = BN_new()))
720         goto err;
721
722     if (!(TEST_true(BN_GF2m_arr2poly(p0, b[0]))
723             && TEST_true(BN_GF2m_arr2poly(p1, b[1]))))
724         goto err;
725
726     for (i = 0; i < NUM0; i++) {
727         if (!TEST_true(BN_bntest_rand(a, 1024, 0, 0)))
728             goto err;
729         for (j = 0; j < 2; j++) {
730             if (!(TEST_true(BN_GF2m_mod(c, a, b[j]))
731                     && TEST_true(BN_GF2m_add(d, a, c))
732                     && TEST_true(BN_GF2m_mod(e, d, b[j]))
733                     /* Test that a + (a mod p) mod p == 0. */
734                     && TEST_BN_eq_zero(e)))
735                 goto err;
736         }
737     }
738     st = 1;
739  err:
740     BN_free(a);
741     BN_free(b[0]);
742     BN_free(b[1]);
743     BN_free(c);
744     BN_free(d);
745     BN_free(e);
746     return st;
747 }
748
749 static int test_gf2m_mul(void)
750 {
751     BIGNUM *a, *b[2] = {NULL, NULL}, *c = NULL, *d = NULL;
752     BIGNUM *e = NULL, *f = NULL, *g = NULL, *h = NULL;
753     int i, j, st = 0;
754
755     if (!TEST_ptr(a = BN_new())
756             || !TEST_ptr(b[0] = BN_new())
757             || !TEST_ptr(b[1] = BN_new())
758             || !TEST_ptr(c = BN_new())
759             || !TEST_ptr(d = BN_new())
760             || !TEST_ptr(e = BN_new())
761             || !TEST_ptr(f = BN_new())
762             || !TEST_ptr(g = BN_new())
763             || !TEST_ptr(h = BN_new()))
764         goto err;
765
766     if (!(TEST_true(BN_GF2m_arr2poly(p0, b[0]))
767             && TEST_true(BN_GF2m_arr2poly(p1, b[1]))))
768         goto err;
769
770     for (i = 0; i < NUM0; i++) {
771         if (!(TEST_true(BN_bntest_rand(a, 1024, 0, 0))
772                 && TEST_true(BN_bntest_rand(c, 1024, 0, 0))
773                 && TEST_true(BN_bntest_rand(d, 1024, 0, 0))))
774             goto err;
775         for (j = 0; j < 2; j++) {
776             if (!(TEST_true(BN_GF2m_mod_mul(e, a, c, b[j], ctx))
777                     && TEST_true(BN_GF2m_add(f, a, d))
778                     && TEST_true(BN_GF2m_mod_mul(g, f, c, b[j], ctx))
779                     && TEST_true(BN_GF2m_mod_mul(h, d, c, b[j], ctx))
780                     && TEST_true(BN_GF2m_add(f, e, g))
781                     && TEST_true(BN_GF2m_add(f, f, h))
782                     /* Test that (a+d)*c = a*c + d*c. */
783                     && TEST_BN_eq_zero(f)))
784                 goto err;
785         }
786     }
787     st = 1;
788
789  err:
790     BN_free(a);
791     BN_free(b[0]);
792     BN_free(b[1]);
793     BN_free(c);
794     BN_free(d);
795     BN_free(e);
796     BN_free(f);
797     BN_free(g);
798     BN_free(h);
799     return st;
800 }
801
802 static int test_gf2m_sqr(void)
803 {
804     BIGNUM *a = NULL, *b[2] = {NULL,NULL}, *c = NULL, *d = NULL;
805     int i, j, st = 0;
806
807     if (!TEST_ptr(a = BN_new())
808             || !TEST_ptr(b[0] = BN_new())
809             || !TEST_ptr(b[1] = BN_new())
810             || !TEST_ptr(c = BN_new())
811             || !TEST_ptr(d = BN_new()))
812         goto err;
813
814     if (!(TEST_true(BN_GF2m_arr2poly(p0, b[0]))
815             && TEST_true(BN_GF2m_arr2poly(p1, b[1]))))
816         goto err;
817
818     for (i = 0; i < NUM0; i++) {
819         if (!TEST_true(BN_bntest_rand(a, 1024, 0, 0)))
820                 goto err;
821         for (j = 0; j < 2; j++) {
822             if (!(TEST_true(BN_GF2m_mod_sqr(c, a, b[j], ctx))
823                     && TEST_true(BN_copy(d, a))
824                     && TEST_true(BN_GF2m_mod_mul(d, a, d, b[j], ctx))
825                     && TEST_true(BN_GF2m_add(d, c, d))
826                     /* Test that a*a = a^2. */
827                     && TEST_BN_eq_zero(d)))
828                 goto err;
829         }
830     }
831     st = 1;
832  err:
833     BN_free(a);
834     BN_free(b[0]);
835     BN_free(b[1]);
836     BN_free(c);
837     BN_free(d);
838     return st;
839 }
840
841 static int test_gf2m_modinv(void)
842 {
843     BIGNUM *a = NULL, *b[2] = {NULL,NULL}, *c = NULL, *d = NULL;
844     int i, j, st = 0;
845
846     if (!TEST_ptr(a = BN_new())
847             || !TEST_ptr(b[0] = BN_new())
848             || !TEST_ptr(b[1] = BN_new())
849             || !TEST_ptr(c = BN_new())
850             || !TEST_ptr(d = BN_new()))
851         goto err;
852
853     if (!(TEST_true(BN_GF2m_arr2poly(p0, b[0]))
854             && TEST_true(BN_GF2m_arr2poly(p1, b[1]))))
855         goto err;
856
857     for (i = 0; i < NUM0; i++) {
858         if (!TEST_true(BN_bntest_rand(a, 512, 0, 0)))
859             goto err;
860         for (j = 0; j < 2; j++) {
861             if (!(TEST_true(BN_GF2m_mod_inv(c, a, b[j], ctx))
862                     && TEST_true(BN_GF2m_mod_mul(d, a, c, b[j], ctx))
863                     /* Test that ((1/a)*a) = 1. */
864                     && TEST_BN_eq_one(d)))
865                 goto err;
866         }
867     }
868     st = 1;
869  err:
870     BN_free(a);
871     BN_free(b[0]);
872     BN_free(b[1]);
873     BN_free(c);
874     BN_free(d);
875     return st;
876 }
877
878 static int test_gf2m_moddiv(void)
879 {
880     BIGNUM *a = NULL, *b[2] = {NULL,NULL}, *c = NULL, *d = NULL;
881     BIGNUM *e = NULL, *f = NULL;
882     int i, j, st = 0;
883
884     if (!TEST_ptr(a = BN_new())
885             || !TEST_ptr(b[0] = BN_new())
886             || !TEST_ptr(b[1] = BN_new())
887             || !TEST_ptr(c = BN_new())
888             || !TEST_ptr(d = BN_new())
889             || !TEST_ptr(e = BN_new())
890             || !TEST_ptr(f = BN_new()))
891         goto err;
892
893     if (!(TEST_true(BN_GF2m_arr2poly(p0, b[0]))
894             && TEST_true(BN_GF2m_arr2poly(p1, b[1]))))
895         goto err;
896
897     for (i = 0; i < NUM0; i++) {
898         if (!(TEST_true(BN_bntest_rand(a, 512, 0, 0))
899                 && TEST_true(BN_bntest_rand(c, 512, 0, 0))))
900             goto err;
901         for (j = 0; j < 2; j++) {
902             if (!(TEST_true(BN_GF2m_mod_div(d, a, c, b[j], ctx))
903                     && TEST_true(BN_GF2m_mod_mul(e, d, c, b[j], ctx))
904                     && TEST_true(BN_GF2m_mod_div(f, a, e, b[j], ctx))
905                     /* Test that ((a/c)*c)/a = 1. */
906                     && TEST_BN_eq_one(f)))
907                 goto err;
908         }
909     }
910     st = 1;
911  err:
912     BN_free(a);
913     BN_free(b[0]);
914     BN_free(b[1]);
915     BN_free(c);
916     BN_free(d);
917     BN_free(e);
918     BN_free(f);
919     return st;
920 }
921
922 static int test_gf2m_modexp(void)
923 {
924     BIGNUM *a = NULL, *b[2] = {NULL,NULL}, *c = NULL, *d = NULL;
925     BIGNUM *e = NULL, *f = NULL;
926     int i, j, st = 0;
927
928     if (!TEST_ptr(a = BN_new())
929             || !TEST_ptr(b[0] = BN_new())
930             || !TEST_ptr(b[1] = BN_new())
931             || !TEST_ptr(c = BN_new())
932             || !TEST_ptr(d = BN_new())
933             || !TEST_ptr(e = BN_new())
934             || !TEST_ptr(f = BN_new()))
935         goto err;
936
937     if (!(TEST_true(BN_GF2m_arr2poly(p0, b[0]))
938             && TEST_true(BN_GF2m_arr2poly(p1, b[1]))))
939         goto err;
940
941     for (i = 0; i < NUM0; i++) {
942         if (!(TEST_true(BN_bntest_rand(a, 512, 0, 0))
943                 && TEST_true(BN_bntest_rand(c, 512, 0, 0))
944                 && TEST_true(BN_bntest_rand(d, 512, 0, 0))))
945             goto err;
946         for (j = 0; j < 2; j++) {
947             if (!(TEST_true(BN_GF2m_mod_exp(e, a, c, b[j], ctx))
948                     && TEST_true(BN_GF2m_mod_exp(f, a, d, b[j], ctx))
949                     && TEST_true(BN_GF2m_mod_mul(e, e, f, b[j], ctx))
950                     && TEST_true(BN_add(f, c, d))
951                     && TEST_true(BN_GF2m_mod_exp(f, a, f, b[j], ctx))
952                     && TEST_true(BN_GF2m_add(f, e, f))
953                     /* Test that a^(c+d)=a^c*a^d. */
954                     && TEST_BN_eq_zero(f)))
955                 goto err;
956         }
957     }
958     st = 1;
959  err:
960     BN_free(a);
961     BN_free(b[0]);
962     BN_free(b[1]);
963     BN_free(c);
964     BN_free(d);
965     BN_free(e);
966     BN_free(f);
967     return st;
968 }
969
970 static int test_gf2m_modsqrt(void)
971 {
972     BIGNUM *a = NULL, *b[2] = {NULL,NULL}, *c = NULL, *d = NULL;
973     BIGNUM *e = NULL, *f = NULL;
974     int i, j, st = 0;
975
976     if (!TEST_ptr(a = BN_new())
977             || !TEST_ptr(b[0] = BN_new())
978             || !TEST_ptr(b[1] = BN_new())
979             || !TEST_ptr(c = BN_new())
980             || !TEST_ptr(d = BN_new())
981             || !TEST_ptr(e = BN_new())
982             || !TEST_ptr(f = BN_new()))
983         goto err;
984
985     if (!(TEST_true(BN_GF2m_arr2poly(p0, b[0]))
986             && TEST_true(BN_GF2m_arr2poly(p1, b[1]))))
987         goto err;
988
989     for (i = 0; i < NUM0; i++) {
990         if (!TEST_true(BN_bntest_rand(a, 512, 0, 0)))
991             goto err;
992
993         for (j = 0; j < 2; j++) {
994             if (!(TEST_true(BN_GF2m_mod(c, a, b[j]))
995                     && TEST_true(BN_GF2m_mod_sqrt(d, a, b[j], ctx))
996                     && TEST_true(BN_GF2m_mod_sqr(e, d, b[j], ctx))
997                     && TEST_true(BN_GF2m_add(f, c, e))
998                     /* Test that d^2 = a, where d = sqrt(a). */
999                     && TEST_BN_eq_zero(f)))
1000                 goto err;
1001         }
1002     }
1003     st = 1;
1004  err:
1005     BN_free(a);
1006     BN_free(b[0]);
1007     BN_free(b[1]);
1008     BN_free(c);
1009     BN_free(d);
1010     BN_free(e);
1011     BN_free(f);
1012     return st;
1013 }
1014
1015 static int test_gf2m_modsolvequad(void)
1016 {
1017     BIGNUM *a = NULL, *b[2] = {NULL,NULL}, *c = NULL, *d = NULL;
1018     BIGNUM *e = NULL;
1019     int i, j, s = 0, t, st = 0;
1020
1021     if (!TEST_ptr(a = BN_new())
1022             || !TEST_ptr(b[0] = BN_new())
1023             || !TEST_ptr(b[1] = BN_new())
1024             || !TEST_ptr(c = BN_new())
1025             || !TEST_ptr(d = BN_new())
1026             || !TEST_ptr(e = BN_new()))
1027         goto err;
1028
1029     if (!(TEST_true(BN_GF2m_arr2poly(p0, b[0]))
1030             && TEST_true(BN_GF2m_arr2poly(p1, b[1]))))
1031         goto err;
1032
1033     for (i = 0; i < NUM0; i++) {
1034         if (!TEST_true(BN_bntest_rand(a, 512, 0, 0)))
1035             goto err;
1036         for (j = 0; j < 2; j++) {
1037             t = BN_GF2m_mod_solve_quad(c, a, b[j], ctx);
1038             if (t) {
1039                 s++;
1040                 if (!(TEST_true(BN_GF2m_mod_sqr(d, c, b[j], ctx))
1041                         && TEST_true(BN_GF2m_add(d, c, d))
1042                         && TEST_true(BN_GF2m_mod(e, a, b[j]))
1043                         && TEST_true(BN_GF2m_add(e, e, d))
1044                         /*
1045                          * Test that solution of quadratic c
1046                          * satisfies c^2 + c = a.
1047                          */
1048                         && TEST_BN_eq_zero(e)))
1049                     goto err;
1050             }
1051         }
1052     }
1053     if (!TEST_int_ge(s, 0)) {
1054         TEST_info("%d tests found no roots; probably an error", NUM0);
1055         goto err;
1056     }
1057     st = 1;
1058  err:
1059     BN_free(a);
1060     BN_free(b[0]);
1061     BN_free(b[1]);
1062     BN_free(c);
1063     BN_free(d);
1064     BN_free(e);
1065     return st;
1066 }
1067 #endif
1068
1069 static int test_kronecker(void)
1070 {
1071     BIGNUM *a = NULL, *b = NULL, *r = NULL, *t = NULL;
1072     int i, legendre, kronecker, st = 0;
1073
1074     if (!TEST_ptr(a = BN_new())
1075             || !TEST_ptr(b = BN_new())
1076             || !TEST_ptr(r = BN_new())
1077             || !TEST_ptr(t = BN_new()))
1078         goto err;
1079
1080     /*
1081      * We test BN_kronecker(a, b, ctx) just for b odd (Jacobi symbol). In
1082      * this case we know that if b is prime, then BN_kronecker(a, b, ctx) is
1083      * congruent to $a^{(b-1)/2}$, modulo $b$ (Legendre symbol). So we
1084      * generate a random prime b and compare these values for a number of
1085      * random a's.  (That is, we run the Solovay-Strassen primality test to
1086      * confirm that b is prime, except that we don't want to test whether b
1087      * is prime but whether BN_kronecker works.)
1088      */
1089
1090     if (!TEST_true(BN_generate_prime_ex(b, 512, 0, NULL, NULL, NULL)))
1091         goto err;
1092     BN_set_negative(b, rand_neg());
1093
1094     for (i = 0; i < NUM0; i++) {
1095         if (!TEST_true(BN_bntest_rand(a, 512, 0, 0)))
1096             goto err;
1097         BN_set_negative(a, rand_neg());
1098
1099         /* t := (|b|-1)/2  (note that b is odd) */
1100         if (!TEST_true(BN_copy(t, b)))
1101             goto err;
1102         BN_set_negative(t, 0);
1103         if (!TEST_true(BN_sub_word(t, 1)))
1104             goto err;
1105         if (!TEST_true(BN_rshift1(t, t)))
1106             goto err;
1107         /* r := a^t mod b */
1108         BN_set_negative(b, 0);
1109
1110         if (!TEST_true(BN_mod_exp_recp(r, a, t, b, ctx)))
1111             goto err;
1112         BN_set_negative(b, 1);
1113
1114         if (BN_is_word(r, 1))
1115             legendre = 1;
1116         else if (BN_is_zero(r))
1117             legendre = 0;
1118         else {
1119             if (!TEST_true(BN_add_word(r, 1)))
1120                 goto err;
1121             if (!TEST_int_eq(BN_ucmp(r, b), 0)) {
1122                 TEST_info("Legendre symbol computation failed");
1123                 goto err;
1124             }
1125             legendre = -1;
1126         }
1127
1128         if (!TEST_int_ge(kronecker = BN_kronecker(a, b, ctx), -1))
1129             goto err;
1130         /* we actually need BN_kronecker(a, |b|) */
1131         if (BN_is_negative(a) && BN_is_negative(b))
1132             kronecker = -kronecker;
1133
1134         if (!TEST_int_eq(legendre, kronecker))
1135             goto err;
1136     }
1137
1138     st = 1;
1139  err:
1140     BN_free(a);
1141     BN_free(b);
1142     BN_free(r);
1143     BN_free(t);
1144     return st;
1145 }
1146
1147 static int file_sum(STANZA *s)
1148 {
1149     BIGNUM *a = NULL, *b = NULL, *sum = NULL, *ret = NULL;
1150     BN_ULONG b_word;
1151     int st = 0;
1152
1153     if (!TEST_ptr(a = getBN(s, "A"))
1154             || !TEST_ptr(b = getBN(s, "B"))
1155             || !TEST_ptr(sum = getBN(s, "Sum"))
1156             || !TEST_ptr(ret = BN_new()))
1157         goto err;
1158
1159     if (!TEST_true(BN_add(ret, a, b))
1160             || !equalBN("A + B", sum, ret)
1161             || !TEST_true(BN_sub(ret, sum, a))
1162             || !equalBN("Sum - A", b, ret)
1163             || !TEST_true(BN_sub(ret, sum, b))
1164             || !equalBN("Sum - B", a, ret))
1165         goto err;
1166
1167     /*
1168      * Test that the functions work when |r| and |a| point to the same BIGNUM,
1169      * or when |r| and |b| point to the same BIGNUM.
1170      * TODO: Test where all of |r|, |a|, and |b| point to the same BIGNUM.
1171      */
1172     if (!TEST_true(BN_copy(ret, a))
1173             || !TEST_true(BN_add(ret, ret, b))
1174             || !equalBN("A + B (r is a)", sum, ret)
1175             || !TEST_true(BN_copy(ret, b))
1176             || !TEST_true(BN_add(ret, a, ret))
1177             || !equalBN("A + B (r is b)", sum, ret)
1178             || !TEST_true(BN_copy(ret, sum))
1179             || !TEST_true(BN_sub(ret, ret, a))
1180             || !equalBN("Sum - A (r is a)", b, ret)
1181             || !TEST_true(BN_copy(ret, a))
1182             || !TEST_true(BN_sub(ret, sum, ret))
1183             || !equalBN("Sum - A (r is b)", b, ret)
1184             || !TEST_true(BN_copy(ret, sum))
1185             || !TEST_true(BN_sub(ret, ret, b))
1186             || !equalBN("Sum - B (r is a)", a, ret)
1187             || !TEST_true(BN_copy(ret, b))
1188             || !TEST_true(BN_sub(ret, sum, ret))
1189             || !equalBN("Sum - B (r is b)", a, ret))
1190         goto err;
1191
1192     /*
1193      * Test BN_uadd() and BN_usub() with the prerequisites they are
1194      * documented as having. Note that these functions are frequently used
1195      * when the prerequisites don't hold. In those cases, they are supposed
1196      * to work as if the prerequisite hold, but we don't test that yet.
1197      * TODO: test that.
1198      */
1199     if (!BN_is_negative(a) && !BN_is_negative(b) && BN_cmp(a, b) >= 0) {
1200         if (!TEST_true(BN_uadd(ret, a, b))
1201                 || !equalBN("A +u B", sum, ret)
1202                 || !TEST_true(BN_usub(ret, sum, a))
1203                 || !equalBN("Sum -u A", b, ret)
1204                 || !TEST_true(BN_usub(ret, sum, b))
1205                 || !equalBN("Sum -u B", a, ret))
1206             goto err;
1207         /*
1208          * Test that the functions work when |r| and |a| point to the same
1209          * BIGNUM, or when |r| and |b| point to the same BIGNUM.
1210          * TODO: Test where all of |r|, |a|, and |b| point to the same BIGNUM.
1211          */
1212         if (!TEST_true(BN_copy(ret, a))
1213                 || !TEST_true(BN_uadd(ret, ret, b))
1214                 || !equalBN("A +u B (r is a)", sum, ret)
1215                 || !TEST_true(BN_copy(ret, b))
1216                 || !TEST_true(BN_uadd(ret, a, ret))
1217                 || !equalBN("A +u B (r is b)", sum, ret)
1218                 || !TEST_true(BN_copy(ret, sum))
1219                 || !TEST_true(BN_usub(ret, ret, a))
1220                 || !equalBN("Sum -u A (r is a)", b, ret)
1221                 || !TEST_true(BN_copy(ret, a))
1222                 || !TEST_true(BN_usub(ret, sum, ret))
1223                 || !equalBN("Sum -u A (r is b)", b, ret)
1224                 || !TEST_true(BN_copy(ret, sum))
1225                 || !TEST_true(BN_usub(ret, ret, b))
1226                 || !equalBN("Sum -u B (r is a)", a, ret)
1227                 || !TEST_true(BN_copy(ret, b))
1228                 || !TEST_true(BN_usub(ret, sum, ret))
1229                 || !equalBN("Sum -u B (r is b)", a, ret))
1230             goto err;
1231     }
1232
1233     /*
1234      * Test with BN_add_word() and BN_sub_word() if |b| is small enough.
1235      */
1236     b_word = BN_get_word(b);
1237     if (!BN_is_negative(b) && b_word != (BN_ULONG)-1) {
1238         if (!TEST_true(BN_copy(ret, a))
1239                 || !TEST_true(BN_add_word(ret, b_word))
1240                 || !equalBN("A + B (word)", sum, ret)
1241                 || !TEST_true(BN_copy(ret, sum))
1242                 || !TEST_true(BN_sub_word(ret, b_word))
1243                 || !equalBN("Sum - B (word)", a, ret))
1244             goto err;
1245     }
1246     st = 1;
1247
1248  err:
1249     BN_free(a);
1250     BN_free(b);
1251     BN_free(sum);
1252     BN_free(ret);
1253     return st;
1254 }
1255
1256 static int file_lshift1(STANZA *s)
1257 {
1258     BIGNUM *a = NULL, *lshift1 = NULL, *zero = NULL, *ret = NULL;
1259     BIGNUM *two = NULL, *remainder = NULL;
1260     int st = 0;
1261
1262     if (!TEST_ptr(a = getBN(s, "A"))
1263             || !TEST_ptr(lshift1 = getBN(s, "LShift1"))
1264             || !TEST_ptr(zero = BN_new())
1265             || !TEST_ptr(ret = BN_new())
1266             || !TEST_ptr(two = BN_new())
1267             || !TEST_ptr(remainder = BN_new()))
1268         goto err;
1269
1270     BN_zero(zero);
1271
1272     if (!TEST_true(BN_set_word(two, 2))
1273             || !TEST_true(BN_add(ret, a, a))
1274             || !equalBN("A + A", lshift1, ret)
1275             || !TEST_true(BN_mul(ret, a, two, ctx))
1276             || !equalBN("A * 2", lshift1, ret)
1277             || !TEST_true(BN_div(ret, remainder, lshift1, two, ctx))
1278             || !equalBN("LShift1 / 2", a, ret)
1279             || !equalBN("LShift1 % 2", zero, remainder)
1280             || !TEST_true(BN_lshift1(ret, a))
1281             || !equalBN("A << 1", lshift1, ret)
1282             || !TEST_true(BN_rshift1(ret, lshift1))
1283             || !equalBN("LShift >> 1", a, ret)
1284             || !TEST_true(BN_rshift1(ret, lshift1))
1285             || !equalBN("LShift >> 1", a, ret))
1286         goto err;
1287
1288     /* Set the LSB to 1 and test rshift1 again. */
1289     if (!TEST_true(BN_set_bit(lshift1, 0))
1290             || !TEST_true(BN_div(ret, NULL /* rem */ , lshift1, two, ctx))
1291             || !equalBN("(LShift1 | 1) / 2", a, ret)
1292             || !TEST_true(BN_rshift1(ret, lshift1))
1293             || !equalBN("(LShift | 1) >> 1", a, ret))
1294         goto err;
1295
1296     st = 1;
1297  err:
1298     BN_free(a);
1299     BN_free(lshift1);
1300     BN_free(zero);
1301     BN_free(ret);
1302     BN_free(two);
1303     BN_free(remainder);
1304
1305     return st;
1306 }
1307
1308 static int file_lshift(STANZA *s)
1309 {
1310     BIGNUM *a = NULL, *lshift = NULL, *ret = NULL;
1311     int n = 0, st = 0;
1312
1313     if (!TEST_ptr(a = getBN(s, "A"))
1314             || !TEST_ptr(lshift = getBN(s, "LShift"))
1315             || !TEST_ptr(ret = BN_new())
1316             || !getint(s, &n, "N"))
1317         goto err;
1318
1319     if (!TEST_true(BN_lshift(ret, a, n))
1320             || !equalBN("A << N", lshift, ret)
1321             || !TEST_true(BN_rshift(ret, lshift, n))
1322             || !equalBN("A >> N", a, ret))
1323         goto err;
1324
1325     st = 1;
1326  err:
1327     BN_free(a);
1328     BN_free(lshift);
1329     BN_free(ret);
1330     return st;
1331 }
1332
1333 static int file_rshift(STANZA *s)
1334 {
1335     BIGNUM *a = NULL, *rshift = NULL, *ret = NULL;
1336     int n = 0, st = 0;
1337
1338     if (!TEST_ptr(a = getBN(s, "A"))
1339             || !TEST_ptr(rshift = getBN(s, "RShift"))
1340             || !TEST_ptr(ret = BN_new())
1341             || !getint(s, &n, "N"))
1342         goto err;
1343
1344     if (!TEST_true(BN_rshift(ret, a, n))
1345             || !equalBN("A >> N", rshift, ret))
1346         goto err;
1347
1348     /* If N == 1, try with rshift1 as well */
1349     if (n == 1) {
1350         if (!TEST_true(BN_rshift1(ret, a))
1351                 || !equalBN("A >> 1 (rshift1)", rshift, ret))
1352             goto err;
1353     }
1354     st = 1;
1355
1356  err:
1357     BN_free(a);
1358     BN_free(rshift);
1359     BN_free(ret);
1360     return st;
1361 }
1362
1363 static int file_square(STANZA *s)
1364 {
1365     BIGNUM *a = NULL, *square = NULL, *zero = NULL, *ret = NULL;
1366     BIGNUM *remainder = NULL, *tmp = NULL;
1367     int st = 0;
1368
1369     if (!TEST_ptr(a = getBN(s, "A"))
1370             || !TEST_ptr(square = getBN(s, "Square"))
1371             || !TEST_ptr(zero = BN_new())
1372             || !TEST_ptr(ret = BN_new())
1373             || !TEST_ptr(remainder = BN_new()))
1374         goto err;
1375
1376     BN_zero(zero);
1377     if (!TEST_true(BN_sqr(ret, a, ctx))
1378             || !equalBN("A^2", square, ret)
1379             || !TEST_true(BN_mul(ret, a, a, ctx))
1380             || !equalBN("A * A", square, ret)
1381             || !TEST_true(BN_div(ret, remainder, square, a, ctx))
1382             || !equalBN("Square / A", a, ret)
1383             || !equalBN("Square % A", zero, remainder))
1384         goto err;
1385
1386 #if HAVE_BN_SQRT
1387     BN_set_negative(a, 0);
1388     if (!TEST_true(BN_sqrt(ret, square, ctx))
1389             || !equalBN("sqrt(Square)", a, ret))
1390         goto err;
1391
1392     /* BN_sqrt should fail on non-squares and negative numbers. */
1393     if (!TEST_BN_eq_zero(square)) {
1394         if (!TEST_ptr(tmp = BN_new())
1395                 || !TEST_true(BN_copy(tmp, square)))
1396             goto err;
1397         BN_set_negative(tmp, 1);
1398
1399         if (!TEST_int_eq(BN_sqrt(ret, tmp, ctx), 0))
1400             goto err;
1401         ERR_clear_error();
1402
1403         BN_set_negative(tmp, 0);
1404         if (BN_add(tmp, tmp, BN_value_one()))
1405             goto err;
1406         if (!TEST_int_eq(BN_sqrt(ret, tmp, ctx)))
1407             goto err;
1408         ERR_clear_error();
1409     }
1410 #endif
1411
1412     st = 1;
1413  err:
1414     BN_free(a);
1415     BN_free(square);
1416     BN_free(zero);
1417     BN_free(ret);
1418     BN_free(remainder);
1419     BN_free(tmp);
1420     return st;
1421 }
1422
1423 static int file_product(STANZA *s)
1424 {
1425     BIGNUM *a = NULL, *b = NULL, *product = NULL, *ret = NULL;
1426     BIGNUM *remainder = NULL, *zero = NULL;
1427     int st = 0;
1428
1429     if (!TEST_ptr(a = getBN(s, "A"))
1430             || !TEST_ptr(b = getBN(s, "B"))
1431             || !TEST_ptr(product = getBN(s, "Product"))
1432             || !TEST_ptr(ret = BN_new())
1433             || !TEST_ptr(remainder = BN_new())
1434             || !TEST_ptr(zero = BN_new()))
1435         goto err;
1436
1437     BN_zero(zero);
1438
1439     if (!TEST_true(BN_mul(ret, a, b, ctx))
1440             || !equalBN("A * B", product, ret)
1441             || !TEST_true(BN_div(ret, remainder, product, a, ctx))
1442             || !equalBN("Product / A", b, ret)
1443             || !equalBN("Product % A", zero, remainder)
1444             || !TEST_true(BN_div(ret, remainder, product, b, ctx))
1445             || !equalBN("Product / B", a, ret)
1446             || !equalBN("Product % B", zero, remainder))
1447         goto err;
1448
1449     st = 1;
1450  err:
1451     BN_free(a);
1452     BN_free(b);
1453     BN_free(product);
1454     BN_free(ret);
1455     BN_free(remainder);
1456     BN_free(zero);
1457     return st;
1458 }
1459
1460 static int file_quotient(STANZA *s)
1461 {
1462     BIGNUM *a = NULL, *b = NULL, *quotient = NULL, *remainder = NULL;
1463     BIGNUM *ret = NULL, *ret2 = NULL, *nnmod = NULL;
1464     BN_ULONG b_word, ret_word;
1465     int st = 0;
1466
1467     if (!TEST_ptr(a = getBN(s, "A"))
1468             || !TEST_ptr(b = getBN(s, "B"))
1469             || !TEST_ptr(quotient = getBN(s, "Quotient"))
1470             || !TEST_ptr(remainder = getBN(s, "Remainder"))
1471             || !TEST_ptr(ret = BN_new())
1472             || !TEST_ptr(ret2 = BN_new())
1473             || !TEST_ptr(nnmod = BN_new()))
1474         goto err;
1475
1476     if (!TEST_true(BN_div(ret, ret2, a, b, ctx))
1477             || !equalBN("A / B", quotient, ret)
1478             || !equalBN("A % B", remainder, ret2)
1479             || !TEST_true(BN_mul(ret, quotient, b, ctx))
1480             || !TEST_true(BN_add(ret, ret, remainder))
1481             || !equalBN("Quotient * B + Remainder", a, ret))
1482         goto err;
1483
1484     /*
1485      * Test with BN_mod_word() and BN_div_word() if the divisor is
1486      * small enough.
1487      */
1488     b_word = BN_get_word(b);
1489     if (!BN_is_negative(b) && b_word != (BN_ULONG)-1) {
1490         BN_ULONG remainder_word = BN_get_word(remainder);
1491
1492         assert(remainder_word != (BN_ULONG)-1);
1493         if (!TEST_ptr(BN_copy(ret, a)))
1494             goto err;
1495         ret_word = BN_div_word(ret, b_word);
1496         if (ret_word != remainder_word) {
1497 #ifdef BN_DEC_FMT1
1498             TEST_error(
1499                     "Got A %% B (word) = " BN_DEC_FMT1 ", wanted " BN_DEC_FMT1,
1500                     ret_word, remainder_word);
1501 #else
1502             TEST_error("Got A %% B (word) mismatch");
1503 #endif
1504             goto err;
1505         }
1506         if (!equalBN ("A / B (word)", quotient, ret))
1507             goto err;
1508
1509         ret_word = BN_mod_word(a, b_word);
1510         if (ret_word != remainder_word) {
1511 #ifdef BN_DEC_FMT1
1512             TEST_error(
1513                     "Got A %% B (word) = " BN_DEC_FMT1 ", wanted " BN_DEC_FMT1 "",
1514                     ret_word, remainder_word);
1515 #else
1516             TEST_error("Got A %% B (word) mismatch");
1517 #endif
1518             goto err;
1519         }
1520     }
1521
1522     /* Test BN_nnmod. */
1523     if (!BN_is_negative(b)) {
1524         if (!TEST_true(BN_copy(nnmod, remainder))
1525                 || (BN_is_negative(nnmod)
1526                         && !TEST_true(BN_add(nnmod, nnmod, b)))
1527                 || !TEST_true(BN_nnmod(ret, a, b, ctx))
1528                 || !equalBN("A % B (non-negative)", nnmod, ret))
1529             goto err;
1530     }
1531
1532     st = 1;
1533  err:
1534     BN_free(a);
1535     BN_free(b);
1536     BN_free(quotient);
1537     BN_free(remainder);
1538     BN_free(ret);
1539     BN_free(ret2);
1540     BN_free(nnmod);
1541     return st;
1542 }
1543
1544 static int file_modmul(STANZA *s)
1545 {
1546     BIGNUM *a = NULL, *b = NULL, *m = NULL, *mod_mul = NULL, *ret = NULL;
1547     int st = 0;
1548
1549     if (!TEST_ptr(a = getBN(s, "A"))
1550             || !TEST_ptr(b = getBN(s, "B"))
1551             || !TEST_ptr(m = getBN(s, "M"))
1552             || !TEST_ptr(mod_mul = getBN(s, "ModMul"))
1553             || !TEST_ptr(ret = BN_new()))
1554         goto err;
1555
1556     if (!TEST_true(BN_mod_mul(ret, a, b, m, ctx))
1557             || !equalBN("A * B (mod M)", mod_mul, ret))
1558         goto err;
1559
1560     if (BN_is_odd(m)) {
1561         /* Reduce |a| and |b| and test the Montgomery version. */
1562         BN_MONT_CTX *mont = BN_MONT_CTX_new();
1563         BIGNUM *a_tmp = BN_new();
1564         BIGNUM *b_tmp = BN_new();
1565
1566         if (mont == NULL || a_tmp == NULL || b_tmp == NULL
1567                 || !TEST_true(BN_MONT_CTX_set(mont, m, ctx))
1568                 || !TEST_true(BN_nnmod(a_tmp, a, m, ctx))
1569                 || !TEST_true(BN_nnmod(b_tmp, b, m, ctx))
1570                 || !TEST_true(BN_to_montgomery(a_tmp, a_tmp, mont, ctx))
1571                 || !TEST_true(BN_to_montgomery(b_tmp, b_tmp, mont, ctx))
1572                 || !TEST_true(BN_mod_mul_montgomery(ret, a_tmp, b_tmp,
1573                                                     mont, ctx))
1574                 || !TEST_true(BN_from_montgomery(ret, ret, mont, ctx))
1575                 || !equalBN("A * B (mod M) (mont)", mod_mul, ret))
1576             st = 0;
1577         else
1578             st = 1;
1579         BN_MONT_CTX_free(mont);
1580         BN_free(a_tmp);
1581         BN_free(b_tmp);
1582         if (st == 0)
1583             goto err;
1584     }
1585
1586     st = 1;
1587  err:
1588     BN_free(a);
1589     BN_free(b);
1590     BN_free(m);
1591     BN_free(mod_mul);
1592     BN_free(ret);
1593     return st;
1594 }
1595
1596 static int file_modexp(STANZA *s)
1597 {
1598     BIGNUM *a = NULL, *e = NULL, *m = NULL, *mod_exp = NULL, *ret = NULL;
1599     BIGNUM *b = NULL, *c = NULL, *d = NULL;
1600     int st = 0;
1601
1602     if (!TEST_ptr(a = getBN(s, "A"))
1603             || !TEST_ptr(e = getBN(s, "E"))
1604             || !TEST_ptr(m = getBN(s, "M"))
1605             || !TEST_ptr(mod_exp = getBN(s, "ModExp"))
1606             || !TEST_ptr(ret = BN_new())
1607             || !TEST_ptr(d = BN_new()))
1608         goto err;
1609
1610     if (!TEST_true(BN_mod_exp(ret, a, e, m, ctx))
1611             || !equalBN("A ^ E (mod M)", mod_exp, ret))
1612         goto err;
1613
1614     if (BN_is_odd(m)) {
1615         if (!TEST_true(BN_mod_exp_mont(ret, a, e, m, ctx, NULL))
1616                 || !equalBN("A ^ E (mod M) (mont)", mod_exp, ret)
1617                 || !TEST_true(BN_mod_exp_mont_consttime(ret, a, e, m,
1618                                                         ctx, NULL))
1619                 || !equalBN("A ^ E (mod M) (mont const", mod_exp, ret))
1620             goto err;
1621     }
1622
1623     /* Regression test for carry propagation bug in sqr8x_reduction */
1624     BN_hex2bn(&a, "050505050505");
1625     BN_hex2bn(&b, "02");
1626     BN_hex2bn(&c,
1627         "4141414141414141414141274141414141414141414141414141414141414141"
1628         "4141414141414141414141414141414141414141414141414141414141414141"
1629         "4141414141414141414141800000000000000000000000000000000000000000"
1630         "0000000000000000000000000000000000000000000000000000000000000000"
1631         "0000000000000000000000000000000000000000000000000000000000000000"
1632         "0000000000000000000000000000000000000000000000000000000001");
1633     if (!TEST_true(BN_mod_exp(d, a, b, c, ctx))
1634         || !TEST_true(BN_mul(e, a, a, ctx))
1635         || !TEST_BN_eq(d, e))
1636         goto err;
1637
1638     st = 1;
1639  err:
1640     BN_free(a);
1641     BN_free(b);
1642     BN_free(c);
1643     BN_free(d);
1644     BN_free(e);
1645     BN_free(m);
1646     BN_free(mod_exp);
1647     BN_free(ret);
1648     return st;
1649 }
1650
1651 static int file_exp(STANZA *s)
1652 {
1653     BIGNUM *a = NULL, *e = NULL, *exp = NULL, *ret = NULL;
1654     int st = 0;
1655
1656     if (!TEST_ptr(a = getBN(s, "A"))
1657             || !TEST_ptr(e = getBN(s, "E"))
1658             || !TEST_ptr(exp = getBN(s, "Exp"))
1659             || !TEST_ptr(ret = BN_new()))
1660         goto err;
1661
1662     if (!TEST_true(BN_exp(ret, a, e, ctx))
1663             || !equalBN("A ^ E", exp, ret))
1664         goto err;
1665
1666     st = 1;
1667  err:
1668     BN_free(a);
1669     BN_free(e);
1670     BN_free(exp);
1671     BN_free(ret);
1672     return st;
1673 }
1674
1675 static int file_modsqrt(STANZA *s)
1676 {
1677     BIGNUM *a = NULL, *p = NULL, *mod_sqrt = NULL, *ret = NULL, *ret2 = NULL;
1678     int st = 0;
1679
1680     if (!TEST_ptr(a = getBN(s, "A"))
1681             || !TEST_ptr(p = getBN(s, "P"))
1682             || !TEST_ptr(mod_sqrt = getBN(s, "ModSqrt"))
1683             || !TEST_ptr(ret = BN_new())
1684             || !TEST_ptr(ret2 = BN_new()))
1685         goto err;
1686
1687     /* There are two possible answers. */
1688     if (!TEST_true(BN_mod_sqrt(ret, a, p, ctx))
1689             || !TEST_true(BN_sub(ret2, p, ret)))
1690         goto err;
1691
1692     /* The first condition should NOT be a test. */
1693     if (BN_cmp(ret2, mod_sqrt) != 0
1694             && !equalBN("sqrt(A) (mod P)", mod_sqrt, ret))
1695         goto err;
1696
1697     st = 1;
1698  err:
1699     BN_free(a);
1700     BN_free(p);
1701     BN_free(mod_sqrt);
1702     BN_free(ret);
1703     BN_free(ret2);
1704     return st;
1705 }
1706
1707 static int file_gcd(STANZA *s)
1708 {
1709     BIGNUM *a = NULL, *b = NULL, *gcd = NULL, *ret = NULL;
1710     int st = 0;
1711
1712     if (!TEST_ptr(a = getBN(s, "A"))
1713             || !TEST_ptr(b = getBN(s, "B"))
1714             || !TEST_ptr(gcd = getBN(s, "GCD"))
1715             || !TEST_ptr(ret = BN_new()))
1716         goto err;
1717
1718     if (!TEST_true(BN_gcd(ret, a, b, ctx))
1719             || !equalBN("gcd(A,B)", gcd, ret))
1720         goto err;
1721
1722     st = 1;
1723  err:
1724     BN_free(a);
1725     BN_free(b);
1726     BN_free(gcd);
1727     BN_free(ret);
1728     return st;
1729 }
1730
1731 static int test_bn2padded(void)
1732 {
1733     uint8_t zeros[256], out[256], reference[128];
1734     size_t bytes;
1735     BIGNUM *n;
1736     int st = 0;
1737
1738     /* Test edge case at 0. */
1739     if (!TEST_ptr((n = BN_new())))
1740         goto err;
1741     if (!TEST_int_eq(BN_bn2binpad(n, NULL, 0), 0))
1742         goto err;
1743     memset(out, -1, sizeof(out));
1744     if (!TEST_int_eq(BN_bn2binpad(n, out, sizeof(out)), sizeof(out)))
1745         goto err;
1746     memset(zeros, 0, sizeof(zeros));
1747     if (!TEST_mem_eq(zeros, sizeof(zeros), out, sizeof(out)))
1748         goto err;
1749
1750     /* Test a random numbers at various byte lengths. */
1751     for (bytes = 128 - 7; bytes <= 128; bytes++) {
1752 # define TOP_BIT_ON 0
1753 # define BOTTOM_BIT_NOTOUCH 0
1754         if (!TEST_true(BN_rand(n, bytes * 8, TOP_BIT_ON, BOTTOM_BIT_NOTOUCH)))
1755             goto err;
1756         if (!TEST_int_eq(BN_num_bytes(n), bytes)
1757                 || !TEST_int_eq(BN_bn2bin(n, reference), bytes))
1758             goto err;
1759         /* Empty buffer should fail. */
1760         if (!TEST_int_eq(BN_bn2binpad(n, NULL, 0), -1))
1761             goto err;
1762         /* One byte short should fail. */
1763         if (!TEST_int_eq(BN_bn2binpad(n, out, bytes - 1), -1))
1764             goto err;
1765         /* Exactly right size should encode. */
1766         if (!TEST_int_eq(BN_bn2binpad(n, out, bytes), bytes)
1767                 || !TEST_mem_eq(out, bytes, reference, bytes))
1768             goto err;
1769         /* Pad up one byte extra. */
1770         if (!TEST_int_eq(BN_bn2binpad(n, out, bytes + 1), bytes + 1)
1771                 || !TEST_mem_eq(out + 1, bytes, reference, bytes)
1772                 || !TEST_mem_eq(out, 1, zeros, 1))
1773             goto err;
1774         /* Pad up to 256. */
1775         if (!TEST_int_eq(BN_bn2binpad(n, out, sizeof(out)), sizeof(out))
1776                 || !TEST_mem_eq(out + sizeof(out) - bytes, bytes,
1777                                 reference, bytes)
1778                 || !TEST_mem_eq(out, sizeof(out) - bytes,
1779                                 zeros, sizeof(out) - bytes))
1780             goto err;
1781     }
1782
1783     st = 1;
1784  err:
1785     BN_free(n);
1786     return st;
1787 }
1788
1789 static int test_dec2bn(void)
1790 {
1791     BIGNUM *bn = NULL;
1792     int st = 0;
1793
1794     if (!TEST_int_eq(parsedecBN(&bn, "0"), 1)
1795             || !TEST_BN_eq_word(bn, 0)
1796             || !TEST_BN_eq_zero(bn)
1797             || !TEST_BN_le_zero(bn)
1798             || !TEST_BN_ge_zero(bn)
1799             || !TEST_BN_even(bn))
1800         goto err;
1801     BN_free(bn);
1802     bn = NULL;
1803
1804     if (!TEST_int_eq(parsedecBN(&bn, "256"), 3)
1805             || !TEST_BN_eq_word(bn, 256)
1806             || !TEST_BN_ge_zero(bn)
1807             || !TEST_BN_gt_zero(bn)
1808             || !TEST_BN_ne_zero(bn)
1809             || !TEST_BN_even(bn))
1810         goto err;
1811     BN_free(bn);
1812     bn = NULL;
1813
1814     if (!TEST_int_eq(parsedecBN(&bn, "-42"), 3)
1815             || !TEST_BN_abs_eq_word(bn, 42)
1816             || !TEST_BN_lt_zero(bn)
1817             || !TEST_BN_le_zero(bn)
1818             || !TEST_BN_ne_zero(bn)
1819             || !TEST_BN_even(bn))
1820         goto err;
1821     BN_free(bn);
1822     bn = NULL;
1823
1824     if (!TEST_int_eq(parsedecBN(&bn, "1"), 1)
1825             || !TEST_BN_eq_word(bn, 1)
1826             || !TEST_BN_ne_zero(bn)
1827             || !TEST_BN_gt_zero(bn)
1828             || !TEST_BN_ge_zero(bn)
1829             || !TEST_BN_eq_one(bn)
1830             || !TEST_BN_odd(bn))
1831         goto err;
1832     BN_free(bn);
1833     bn = NULL;
1834
1835     if (!TEST_int_eq(parsedecBN(&bn, "-0"), 2)
1836             || !TEST_BN_eq_zero(bn)
1837             || !TEST_BN_ge_zero(bn)
1838             || !TEST_BN_le_zero(bn)
1839             || !TEST_BN_even(bn))
1840         goto err;
1841     BN_free(bn);
1842     bn = NULL;
1843
1844     if (!TEST_int_eq(parsedecBN(&bn, "42trailing garbage is ignored"), 2)
1845             || !TEST_BN_abs_eq_word(bn, 42)
1846             || !TEST_BN_ge_zero(bn)
1847             || !TEST_BN_gt_zero(bn)
1848             || !TEST_BN_ne_zero(bn)
1849             || !TEST_BN_even(bn))
1850         goto err;
1851
1852     st = 1;
1853  err:
1854     BN_free(bn);
1855     return st;
1856 }
1857
1858 static int test_hex2bn(void)
1859 {
1860     BIGNUM *bn = NULL;
1861     int st = 0;
1862
1863     if (!TEST_int_eq(parseBN(&bn, "0"), 1)
1864             || !TEST_BN_eq_zero(bn)
1865             || !TEST_BN_ge_zero(bn)
1866             || !TEST_BN_even(bn))
1867         goto err;
1868     BN_free(bn);
1869     bn = NULL;
1870
1871     if (!TEST_int_eq(parseBN(&bn, "256"), 3)
1872             || !TEST_BN_eq_word(bn, 0x256)
1873             || !TEST_BN_ge_zero(bn)
1874             || !TEST_BN_gt_zero(bn)
1875             || !TEST_BN_ne_zero(bn)
1876             || !TEST_BN_even(bn))
1877         goto err;
1878     BN_free(bn);
1879     bn = NULL;
1880
1881     if (!TEST_int_eq(parseBN(&bn, "-42"), 3)
1882             || !TEST_BN_abs_eq_word(bn, 0x42)
1883             || !TEST_BN_lt_zero(bn)
1884             || !TEST_BN_le_zero(bn)
1885             || !TEST_BN_ne_zero(bn)
1886             || !TEST_BN_even(bn))
1887         goto err;
1888     BN_free(bn);
1889     bn = NULL;
1890
1891     if (!TEST_int_eq(parseBN(&bn, "cb"), 2)
1892             || !TEST_BN_eq_word(bn, 0xCB)
1893             || !TEST_BN_ge_zero(bn)
1894             || !TEST_BN_gt_zero(bn)
1895             || !TEST_BN_ne_zero(bn)
1896             || !TEST_BN_odd(bn))
1897         goto err;
1898     BN_free(bn);
1899     bn = NULL;
1900
1901     if (!TEST_int_eq(parseBN(&bn, "-0"), 2)
1902             || !TEST_BN_eq_zero(bn)
1903             || !TEST_BN_ge_zero(bn)
1904             || !TEST_BN_le_zero(bn)
1905             || !TEST_BN_even(bn))
1906         goto err;
1907     BN_free(bn);
1908     bn = NULL;
1909
1910     if (!TEST_int_eq(parseBN(&bn, "abctrailing garbage is ignored"), 3)
1911             || !TEST_BN_eq_word(bn, 0xabc)
1912             || !TEST_BN_ge_zero(bn)
1913             || !TEST_BN_gt_zero(bn)
1914             || !TEST_BN_ne_zero(bn)
1915             || !TEST_BN_even(bn))
1916         goto err;
1917     st = 1;
1918
1919  err:
1920     BN_free(bn);
1921     return st;
1922 }
1923
1924 static int test_asc2bn(void)
1925 {
1926     BIGNUM *bn = NULL;
1927     int st = 0;
1928
1929     if (!TEST_ptr(bn = BN_new()))
1930         goto err;
1931
1932     if (!TEST_true(BN_asc2bn(&bn, "0"))
1933             || !TEST_BN_eq_zero(bn)
1934             || !TEST_BN_ge_zero(bn))
1935         goto err;
1936
1937     if (!TEST_true(BN_asc2bn(&bn, "256"))
1938             || !TEST_BN_eq_word(bn, 256)
1939             || !TEST_BN_ge_zero(bn))
1940         goto err;
1941
1942     if (!TEST_true(BN_asc2bn(&bn, "-42"))
1943             || !TEST_BN_abs_eq_word(bn, 42)
1944             || !TEST_BN_lt_zero(bn))
1945         goto err;
1946
1947     if (!TEST_true(BN_asc2bn(&bn, "0x1234"))
1948             || !TEST_BN_eq_word(bn, 0x1234)
1949             || !TEST_BN_ge_zero(bn))
1950         goto err;
1951
1952     if (!TEST_true(BN_asc2bn(&bn, "0X1234"))
1953             || !TEST_BN_eq_word(bn, 0x1234)
1954             || !TEST_BN_ge_zero(bn))
1955         goto err;
1956
1957     if (!TEST_true(BN_asc2bn(&bn, "-0xabcd"))
1958             || !TEST_BN_abs_eq_word(bn, 0xabcd)
1959             || !TEST_BN_lt_zero(bn))
1960         goto err;
1961
1962     if (!TEST_true(BN_asc2bn(&bn, "-0"))
1963             || !TEST_BN_eq_zero(bn)
1964             || !TEST_BN_ge_zero(bn))
1965         goto err;
1966
1967     if (!TEST_true(BN_asc2bn(&bn, "123trailing garbage is ignored"))
1968             || !TEST_BN_eq_word(bn, 123)
1969             || !TEST_BN_ge_zero(bn))
1970         goto err;
1971
1972     st = 1;
1973  err:
1974     BN_free(bn);
1975     return st;
1976 }
1977
1978 static const MPITEST kMPITests[] = {
1979     {"0", "\x00\x00\x00\x00", 4},
1980     {"1", "\x00\x00\x00\x01\x01", 5},
1981     {"-1", "\x00\x00\x00\x01\x81", 5},
1982     {"128", "\x00\x00\x00\x02\x00\x80", 6},
1983     {"256", "\x00\x00\x00\x02\x01\x00", 6},
1984     {"-256", "\x00\x00\x00\x02\x81\x00", 6},
1985 };
1986
1987 static int test_mpi(int i)
1988 {
1989     uint8_t scratch[8];
1990     const MPITEST *test = &kMPITests[i];
1991     size_t mpi_len, mpi_len2;
1992     BIGNUM *bn = NULL;
1993     BIGNUM *bn2 = NULL;
1994     int st = 0;
1995
1996     if (!TEST_ptr(bn = BN_new())
1997             || !TEST_true(BN_asc2bn(&bn, test->base10)))
1998         goto err;
1999     mpi_len = BN_bn2mpi(bn, NULL);
2000     if (!TEST_size_t_le(mpi_len, sizeof(scratch)))
2001         goto err;
2002
2003     if (!TEST_size_t_eq(mpi_len2 = BN_bn2mpi(bn, scratch), mpi_len)
2004             || !TEST_mem_eq(test->mpi, test->mpi_len, scratch, mpi_len))
2005         goto err;
2006
2007     if (!TEST_ptr(bn2 = BN_mpi2bn(scratch, mpi_len, NULL)))
2008         goto err;
2009
2010     if (!TEST_BN_eq(bn, bn2)) {
2011         BN_free(bn2);
2012         goto err;
2013     }
2014     BN_free(bn2);
2015
2016     st = 1;
2017  err:
2018     BN_free(bn);
2019     return st;
2020 }
2021
2022 static int test_rand(void)
2023 {
2024     BIGNUM *bn = NULL;
2025     int st = 0;
2026
2027     if (!TEST_ptr(bn = BN_new()))
2028         return 0;
2029
2030     /* Test BN_rand for degenerate cases with |top| and |bottom| parameters. */
2031     if (!TEST_false(BN_rand(bn, 0, 0 /* top */ , 0 /* bottom */ ))
2032             || !TEST_false(BN_rand(bn, 0, 1 /* top */ , 1 /* bottom */ ))
2033             || !TEST_true(BN_rand(bn, 1, 0 /* top */ , 0 /* bottom */ ))
2034             || !TEST_BN_eq_one(bn)
2035             || !TEST_false(BN_rand(bn, 1, 1 /* top */ , 0 /* bottom */ ))
2036             || !TEST_true(BN_rand(bn, 1, -1 /* top */ , 1 /* bottom */ ))
2037             || !TEST_BN_eq_one(bn)
2038             || !TEST_true(BN_rand(bn, 2, 1 /* top */ , 0 /* bottom */ ))
2039             || !TEST_BN_eq_word(bn, 3))
2040         goto err;
2041
2042     st = 1;
2043  err:
2044     BN_free(bn);
2045     return st;
2046 }
2047
2048 static int test_negzero(void)
2049 {
2050     BIGNUM *a = NULL, *b = NULL, *c = NULL, *d = NULL;
2051     BIGNUM *numerator = NULL, *denominator = NULL;
2052     int consttime, st = 0;
2053
2054     if (!TEST_ptr(a = BN_new())
2055             || !TEST_ptr(b = BN_new())
2056             || !TEST_ptr(c = BN_new())
2057             || !TEST_ptr(d = BN_new()))
2058         goto err;
2059
2060     /* Test that BN_mul never gives negative zero. */
2061     if (!TEST_true(BN_set_word(a, 1)))
2062         goto err;
2063     BN_set_negative(a, 1);
2064     BN_zero(b);
2065     if (!TEST_true(BN_mul(c, a, b, ctx)))
2066         goto err;
2067     if (!TEST_BN_eq_zero(c)
2068             || !TEST_BN_ge_zero(c))
2069         goto err;
2070
2071     for (consttime = 0; consttime < 2; consttime++) {
2072         if (!TEST_ptr(numerator = BN_new())
2073                 || !TEST_ptr(denominator = BN_new()))
2074             goto err;
2075         if (consttime) {
2076             BN_set_flags(numerator, BN_FLG_CONSTTIME);
2077             BN_set_flags(denominator, BN_FLG_CONSTTIME);
2078         }
2079         /* Test that BN_div never gives negative zero in the quotient. */
2080         if (!TEST_true(BN_set_word(numerator, 1))
2081                 || !TEST_true(BN_set_word(denominator, 2)))
2082             goto err;
2083         BN_set_negative(numerator, 1);
2084         if (!TEST_true(BN_div(a, b, numerator, denominator, ctx))
2085                 || !TEST_BN_eq_zero(a)
2086                 || !TEST_BN_ge_zero(a))
2087             goto err;
2088
2089         /* Test that BN_div never gives negative zero in the remainder. */
2090         if (!TEST_true(BN_set_word(denominator, 1))
2091                 || !TEST_true(BN_div(a, b, numerator, denominator, ctx))
2092                 || !TEST_BN_eq_zero(b)
2093                 || !TEST_BN_ge_zero(b))
2094             goto err;
2095         BN_free(numerator);
2096         BN_free(denominator);
2097         numerator = denominator = NULL;
2098     }
2099
2100     /* Test that BN_set_negative will not produce a negative zero. */
2101     BN_zero(a);
2102     BN_set_negative(a, 1);
2103     if (BN_is_negative(a))
2104         goto err;
2105     st = 1;
2106
2107  err:
2108     BN_free(a);
2109     BN_free(b);
2110     BN_free(c);
2111     BN_free(d);
2112     BN_free(numerator);
2113     BN_free(denominator);
2114     return st;
2115 }
2116
2117 static int test_badmod(void)
2118 {
2119     BIGNUM *a = NULL, *b = NULL, *zero = NULL;
2120     BN_MONT_CTX *mont = NULL;
2121     int st = 0;
2122
2123     if (!TEST_ptr(a = BN_new())
2124             || !TEST_ptr(b = BN_new())
2125             || !TEST_ptr(zero = BN_new())
2126             || !TEST_ptr(mont = BN_MONT_CTX_new()))
2127         goto err;
2128     BN_zero(zero);
2129
2130     if (!TEST_false(BN_div(a, b, BN_value_one(), zero, ctx)))
2131         goto err;
2132     ERR_clear_error();
2133
2134     if (!TEST_false(BN_mod_mul(a, BN_value_one(), BN_value_one(), zero, ctx)))
2135         goto err;
2136     ERR_clear_error();
2137
2138     if (!TEST_false(BN_mod_exp(a, BN_value_one(), BN_value_one(), zero, ctx)))
2139         goto err;
2140     ERR_clear_error();
2141
2142     if (!TEST_false(BN_mod_exp_mont(a, BN_value_one(), BN_value_one(),
2143                                     zero, ctx, NULL)))
2144         goto err;
2145     ERR_clear_error();
2146
2147     if (!TEST_false(BN_mod_exp_mont_consttime(a, BN_value_one(), BN_value_one(),
2148                                               zero, ctx, NULL)))
2149         goto err;
2150     ERR_clear_error();
2151
2152     if (!TEST_false(BN_MONT_CTX_set(mont, zero, ctx)))
2153         goto err;
2154     ERR_clear_error();
2155
2156     /* Some operations also may not be used with an even modulus. */
2157     if (!TEST_true(BN_set_word(b, 16)))
2158         goto err;
2159
2160     if (!TEST_false(BN_MONT_CTX_set(mont, b, ctx)))
2161         goto err;
2162     ERR_clear_error();
2163
2164     if (!TEST_false(BN_mod_exp_mont(a, BN_value_one(), BN_value_one(),
2165                                     b, ctx, NULL)))
2166         goto err;
2167     ERR_clear_error();
2168
2169     if (!TEST_false(BN_mod_exp_mont_consttime(a, BN_value_one(), BN_value_one(),
2170                                               b, ctx, NULL)))
2171         goto err;
2172     ERR_clear_error();
2173
2174     st = 1;
2175  err:
2176     BN_free(a);
2177     BN_free(b);
2178     BN_free(zero);
2179     BN_MONT_CTX_free(mont);
2180     return st;
2181 }
2182
2183 static int test_expmodzero(void)
2184 {
2185     BIGNUM *a = NULL, *r = NULL, *zero = NULL;
2186     int st = 0;
2187
2188     if (!TEST_ptr(zero = BN_new())
2189             || !TEST_ptr(a = BN_new())
2190             || !TEST_ptr(r = BN_new()))
2191         goto err;
2192     BN_zero(zero);
2193
2194     if (!TEST_true(BN_mod_exp(r, a, zero, BN_value_one(), NULL))
2195             || !TEST_BN_eq_zero(r)
2196             || !TEST_true(BN_mod_exp_mont(r, a, zero, BN_value_one(),
2197                                           NULL, NULL))
2198             || !TEST_BN_eq_zero(r)
2199             || !TEST_true(BN_mod_exp_mont_consttime(r, a, zero,
2200                                                     BN_value_one(),
2201                                                     NULL, NULL))
2202             || !TEST_BN_eq_zero(r)
2203             || !TEST_true(BN_mod_exp_mont_word(r, 42, zero,
2204                                                BN_value_one(), NULL, NULL))
2205             || !TEST_BN_eq_zero(r))
2206         goto err;
2207
2208     st = 1;
2209  err:
2210     BN_free(zero);
2211     BN_free(a);
2212     BN_free(r);
2213     return st;
2214 }
2215
2216 static int test_expmodone(void)
2217 {
2218     int ret = 0, i;
2219     BIGNUM *r = BN_new();
2220     BIGNUM *a = BN_new();
2221     BIGNUM *p = BN_new();
2222     BIGNUM *m = BN_new();
2223
2224     if (!TEST_ptr(r)
2225             || !TEST_ptr(a)
2226             || !TEST_ptr(p)
2227             || !TEST_ptr(p)
2228             || !TEST_ptr(m)
2229             || !TEST_true(BN_set_word(a, 1))
2230             || !TEST_true(BN_set_word(p, 0))
2231             || !TEST_true(BN_set_word(m, 1)))
2232         goto err;
2233
2234     /* Calculate r = 1 ^ 0 mod 1, and check the result is always 0 */
2235     for (i = 0; i < 2; i++) {
2236         if (!TEST_true(BN_mod_exp(r, a, p, m, NULL))
2237                 || !TEST_BN_eq_zero(r)
2238                 || !TEST_true(BN_mod_exp_mont(r, a, p, m, NULL, NULL))
2239                 || !TEST_BN_eq_zero(r)
2240                 || !TEST_true(BN_mod_exp_mont_consttime(r, a, p, m, NULL, NULL))
2241                 || !TEST_BN_eq_zero(r)
2242                 || !TEST_true(BN_mod_exp_mont_word(r, 1, p, m, NULL, NULL))
2243                 || !TEST_BN_eq_zero(r)
2244                 || !TEST_true(BN_mod_exp_simple(r, a, p, m, NULL))
2245                 || !TEST_BN_eq_zero(r)
2246                 || !TEST_true(BN_mod_exp_recp(r, a, p, m, NULL))
2247                 || !TEST_BN_eq_zero(r))
2248             goto err;
2249         /* Repeat for r = 1 ^ 0 mod -1 */
2250         if (i == 0)
2251             BN_set_negative(m, 1);
2252     }
2253
2254     ret = 1;
2255  err:
2256     BN_free(r);
2257     BN_free(a);
2258     BN_free(p);
2259     BN_free(m);
2260     return ret;
2261 }
2262
2263 static int test_smallprime(int kBits)
2264 {
2265     BIGNUM *r;
2266     int st = 0;
2267
2268     if (!TEST_ptr(r = BN_new()))
2269         goto err;
2270
2271     if (kBits <= 1) {
2272         if (!TEST_false(BN_generate_prime_ex(r, kBits, 0,
2273                                              NULL, NULL, NULL)))
2274             goto err;
2275     } else {
2276         if (!TEST_true(BN_generate_prime_ex(r, kBits, 0,
2277                                             NULL, NULL, NULL))
2278                 || !TEST_int_eq(BN_num_bits(r), kBits))
2279             goto err;
2280     }
2281
2282     st = 1;
2283  err:
2284     BN_free(r);
2285     return st;
2286 }
2287
2288 static int test_smallsafeprime(int kBits)
2289 {
2290     BIGNUM *r;
2291     int st = 0;
2292
2293     if (!TEST_ptr(r = BN_new()))
2294         goto err;
2295
2296     if (kBits <= 5 && kBits != 3) {
2297         if (!TEST_false(BN_generate_prime_ex(r, kBits, 1,
2298                                              NULL, NULL, NULL)))
2299             goto err;
2300     } else {
2301         if (!TEST_true(BN_generate_prime_ex(r, kBits, 1,
2302                                             NULL, NULL, NULL))
2303                 || !TEST_int_eq(BN_num_bits(r), kBits))
2304             goto err;
2305     }
2306
2307     st = 1;
2308  err:
2309     BN_free(r);
2310     return st;
2311 }
2312
2313 static int primes[] = { 2, 3, 5, 7, 17863 };
2314
2315 static int test_is_prime(int i)
2316 {
2317     int ret = 0;
2318     BIGNUM *r = NULL;
2319     int trial;
2320
2321     if (!TEST_ptr(r = BN_new()))
2322         goto err;
2323
2324     for (trial = 0; trial <= 1; ++trial) {
2325         if (!TEST_true(BN_set_word(r, primes[i]))
2326                 || !TEST_int_eq(BN_is_prime_fasttest_ex(r, 1, ctx, trial, NULL),
2327                                 1))
2328             goto err;
2329     }
2330
2331     ret = 1;
2332  err:
2333     BN_free(r);
2334     return ret;
2335 }
2336
2337 static int not_primes[] = { -1, 0, 1, 4 };
2338
2339 static int test_not_prime(int i)
2340 {
2341     int ret = 0;
2342     BIGNUM *r = NULL;
2343     int trial;
2344
2345     if (!TEST_ptr(r = BN_new()))
2346         goto err;
2347
2348     for (trial = 0; trial <= 1; ++trial) {
2349         if (!TEST_true(BN_set_word(r, not_primes[i]))
2350                 || !TEST_false(BN_is_prime_fasttest_ex(r, 1, ctx, trial, NULL)))
2351             goto err;
2352     }
2353
2354     ret = 1;
2355  err:
2356     BN_free(r);
2357     return ret;
2358 }
2359
2360 static int test_ctx_set_ct_flag(BN_CTX *c)
2361 {
2362     int st = 0;
2363     size_t i;
2364     BIGNUM *b[15];
2365
2366     BN_CTX_start(c);
2367     for (i = 0; i < OSSL_NELEM(b); i++) {
2368         if (!TEST_ptr(b[i] = BN_CTX_get(c)))
2369             goto err;
2370         if (i % 2 == 1)
2371             BN_set_flags(b[i], BN_FLG_CONSTTIME);
2372     }
2373
2374     st = 1;
2375  err:
2376     BN_CTX_end(c);
2377     return st;
2378 }
2379
2380 static int test_ctx_check_ct_flag(BN_CTX *c)
2381 {
2382     int st = 0;
2383     size_t i;
2384     BIGNUM *b[30];
2385
2386     BN_CTX_start(c);
2387     for (i = 0; i < OSSL_NELEM(b); i++) {
2388         if (!TEST_ptr(b[i] = BN_CTX_get(c)))
2389             goto err;
2390         if (!TEST_false(BN_get_flags(b[i], BN_FLG_CONSTTIME)))
2391             goto err;
2392     }
2393
2394     st = 1;
2395  err:
2396     BN_CTX_end(c);
2397     return st;
2398 }
2399
2400 static int test_ctx_consttime_flag(void)
2401 {
2402     /*-
2403      * The constant-time flag should not "leak" among BN_CTX frames:
2404      *
2405      * - test_ctx_set_ct_flag() starts a frame in the given BN_CTX and
2406      *   sets the BN_FLG_CONSTTIME flag on some of the BIGNUMs obtained
2407      *   from the frame before ending it.
2408      * - test_ctx_check_ct_flag() then starts a new frame and gets a
2409      *   number of BIGNUMs from it. In absence of leaks, none of the
2410      *   BIGNUMs in the new frame should have BN_FLG_CONSTTIME set.
2411      *
2412      * In actual BN_CTX usage inside libcrypto the leak could happen at
2413      * any depth level in the BN_CTX stack, with varying results
2414      * depending on the patterns of sibling trees of nested function
2415      * calls sharing the same BN_CTX object, and the effect of
2416      * unintended BN_FLG_CONSTTIME on the called BN_* functions.
2417      *
2418      * This simple unit test abstracts away this complexity and verifies
2419      * that the leak does not happen between two sibling functions
2420      * sharing the same BN_CTX object at the same level of nesting.
2421      *
2422      */
2423     BN_CTX *nctx = NULL;
2424     BN_CTX *sctx = NULL;
2425     size_t i = 0;
2426     int st = 0;
2427
2428     if (!TEST_ptr(nctx = BN_CTX_new())
2429             || !TEST_ptr(sctx = BN_CTX_secure_new()))
2430         goto err;
2431
2432     for (i = 0; i < 2; i++) {
2433         BN_CTX *c = i == 0 ? nctx : sctx;
2434         if (!TEST_true(test_ctx_set_ct_flag(c))
2435                 || !TEST_true(test_ctx_check_ct_flag(c)))
2436             goto err;
2437     }
2438
2439     st = 1;
2440  err:
2441     BN_CTX_free(nctx);
2442     BN_CTX_free(sctx);
2443     return st;
2444 }
2445
2446 static int test_gcd_prime(void)
2447 {
2448     BIGNUM *a = NULL, *b = NULL, *gcd = NULL;
2449     int i, st = 0;
2450
2451     if (!TEST_ptr(a = BN_new())
2452             || !TEST_ptr(b = BN_new())
2453             || !TEST_ptr(gcd = BN_new()))
2454         goto err;
2455
2456     if (!TEST_true(BN_generate_prime_ex(a, 1024, 0, NULL, NULL, NULL)))
2457             goto err;
2458     for (i = 0; i < NUM0; i++) {
2459         if (!TEST_true(BN_generate_prime_ex(b, 1024, 0,
2460                                             NULL, NULL, NULL))
2461                 || !TEST_true(BN_gcd(gcd, a, b, ctx))
2462                 || !TEST_true(BN_is_one(gcd)))
2463             goto err;
2464     }
2465
2466     st = 1;
2467  err:
2468     BN_free(a);
2469     BN_free(b);
2470     BN_free(gcd);
2471     return st;
2472 }
2473
2474 typedef struct mod_exp_test_st
2475 {
2476   const char *base;
2477   const char *exp;
2478   const char *mod;
2479   const char *res;
2480 } MOD_EXP_TEST;
2481
2482 static const MOD_EXP_TEST ModExpTests[] = {
2483    /* original test vectors for rsaz_512_sqr bug, by OSS-Fuzz */
2484    {
2485        "1166180238001879113042182292626169621106255558914000595999312084"
2486        "4627946820899490684928760491249738643524880720584249698100907201"
2487        "002086675047927600340800371",
2488        "8000000000000000000000000000000000000000000000000000000000000000"
2489        "0000000000000000000000000000000000000000000000000000000000000000"
2490        "00000000",
2491        "1340780792684523720980737645613191762604395855615117867483316354"
2492        "3294276330515137663421134775482798690129946803802212663956180562"
2493        "088664022929883876655300863",
2494        "8243904058268085430037326628480645845409758077568738532059032482"
2495        "8294114415890603594730158120426756266457928475330450251339773498"
2496        "26758407619521544102068438"
2497    },
2498    {
2499        "4974270041410803822078866696159586946995877618987010219312844726"
2500        "0284386121835740784990869050050504348861513337232530490826340663"
2501        "197278031692737429054",
2502        "4974270041410803822078866696159586946995877428188754995041148539"
2503        "1663243362592271353668158565195557417149981094324650322556843202"
2504        "946445882670777892608",
2505        "1340780716511420227215592830971452482815377482627251725537099028"
2506        "4429769497230131760206012644403029349547320953206103351725462999"
2507        "947509743623340557059752191",
2508        "5296244594780707015616522701706118082963369547253192207884519362"
2509        "1767869984947542695665420219028522815539559194793619684334900442"
2510        "49304558011362360473525933"
2511    },
2512    /* test vectors for rsaz_512_srq bug, with rcx/rbx=1 */
2513    {   /* between first and second iteration */
2514        "5148719036160389201525610950887605325980251964889646556085286545"
2515        "3931548809178823413169359635978762036512397113080988070677858033"
2516        "36463909753993540214027190",
2517        "6703903964971298549787012499102923063739682910296196688861780721"
2518        "8608820150367734884009371490834517138450159290932430254268769414"
2519        "05973284973216824503042158",
2520        "6703903964971298549787012499102923063739682910296196688861780721"
2521        "8608820150367734884009371490834517138450159290932430254268769414"
2522        "05973284973216824503042159",
2523        "1"
2524    },
2525    {   /* between second and third iteration */
2526        "8908340854353752577419678771330460827942371434853054158622636544"
2527        "8151360109722890949471912566649465436296659601091730745087014189"
2528        "2672764191218875181826063",
2529        "6703903964971298549787012499102923063739682910296196688861780721"
2530        "8608820150367734884009371490834517138450159290932430254268769414"
2531        "05973284973216824503042158",
2532        "6703903964971298549787012499102923063739682910296196688861780721"
2533        "8608820150367734884009371490834517138450159290932430254268769414"
2534        "05973284973216824503042159",
2535        "1"
2536    },
2537    {   /* between third and fourth iteration */
2538        "3427446396505596330634350984901719674479522569002785244080234738"
2539        "4288743635435746136297299366444548736533053717416735379073185344"
2540        "26985272974404612945608761",
2541        "6703903964971298549787012499102923063739682910296196688861780721"
2542        "8608820150367734884009371490834517138450159290932430254268769414"
2543        "05973284973216824503042158",
2544        "6703903964971298549787012499102923063739682910296196688861780721"
2545        "8608820150367734884009371490834517138450159290932430254268769414"
2546        "05973284973216824503042159",
2547        "1"
2548    },
2549    {   /* between fourth and fifth iteration */
2550        "3472743044917564564078857826111874560045331237315597383869652985"
2551        "6919870028890895988478351133601517365908445058405433832718206902"
2552        "4088133164805266956353542",
2553        "6703903964971298549787012499102923063739682910296196688861780721"
2554        "8608820150367734884009371490834517138450159290932430254268769414"
2555        "05973284973216824503042158",
2556        "6703903964971298549787012499102923063739682910296196688861780721"
2557        "8608820150367734884009371490834517138450159290932430254268769414"
2558        "05973284973216824503042159",
2559        "1"
2560    },
2561    {   /* between fifth and sixth iteration */
2562        "3608632990153469264412378349742339216742409743898601587274768025"
2563        "0110772032985643555192767717344946174122842255204082586753499651"
2564        "14483434992887431333675068",
2565        "6703903964971298549787012499102923063739682910296196688861780721"
2566        "8608820150367734884009371490834517138450159290932430254268769414"
2567        "05973284973216824503042158",
2568        "6703903964971298549787012499102923063739682910296196688861780721"
2569        "8608820150367734884009371490834517138450159290932430254268769414"
2570        "05973284973216824503042159",
2571        "1"
2572    },
2573    {   /* between sixth and seventh iteration */
2574        "8455374370234070242910508226941981520235709767260723212165264877"
2575        "8689064388017521524568434328264431772644802567028663962962025746"
2576        "9283458217850119569539086",
2577        "6703903964971298549787012499102923063739682910296196688861780721"
2578        "8608820150367734884009371490834517138450159290932430254268769414"
2579        "05973284973216824503042158",
2580        "6703903964971298549787012499102923063739682910296196688861780721"
2581        "8608820150367734884009371490834517138450159290932430254268769414"
2582        "05973284973216824503042159",
2583        "1"
2584    },
2585    {   /* between seventh and eighth iteration */
2586        "5155371529688532178421209781159131443543419764974688878527112131"
2587        "7446518205609427412336183157918981038066636807317733319323257603"
2588        "04416292040754017461076359",
2589        "1005585594745694782468051874865438459560952436544429503329267108"
2590        "2791323022555160232601405723625177570767523893639864538140315412"
2591        "108959927459825236754563832",
2592        "1005585594745694782468051874865438459560952436544429503329267108"
2593        "2791323022555160232601405723625177570767523893639864538140315412"
2594        "108959927459825236754563833",
2595        "1"
2596    },
2597    /* test vectors for rsaz_512_srq bug, with rcx/rbx=2 */
2598    {   /* between first and second iteration */
2599        "3155666506033786929967309937640790361084670559125912405342594979"
2600        "4345142818528956285490897841406338022378565972533508820577760065"
2601        "58494345853302083699912572",
2602        "6703903964971298549787012499102923063739682910296196688861780721"
2603        "8608820150367734884009371490834517138450159290932430254268769414"
2604        "05973284973216824503042158",
2605        "6703903964971298549787012499102923063739682910296196688861780721"
2606        "8608820150367734884009371490834517138450159290932430254268769414"
2607        "05973284973216824503042159",
2608        "1"
2609    },
2610    {   /* between second and third iteration */
2611        "3789819583801342198190405714582958759005991915505282362397087750"
2612        "4213544724644823098843135685133927198668818185338794377239590049"
2613        "41019388529192775771488319",
2614        "6703903964971298549787012499102923063739682910296196688861780721"
2615        "8608820150367734884009371490834517138450159290932430254268769414"
2616        "05973284973216824503042158",
2617        "6703903964971298549787012499102923063739682910296196688861780721"
2618        "8608820150367734884009371490834517138450159290932430254268769414"
2619        "05973284973216824503042159",
2620        "1"
2621    },
2622    {   /* between third and forth iteration */
2623        "4695752552040706867080542538786056470322165281761525158189220280"
2624        "4025547447667484759200742764246905647644662050122968912279199065"
2625        "48065034299166336940507214",
2626        "6703903964971298549787012499102923063739682910296196688861780721"
2627        "8608820150367734884009371490834517138450159290932430254268769414"
2628        "05973284973216824503042158",
2629        "6703903964971298549787012499102923063739682910296196688861780721"
2630        "8608820150367734884009371490834517138450159290932430254268769414"
2631        "05973284973216824503042159",
2632        "1"
2633    },
2634    {   /* between forth and fifth iteration */
2635        "2159140240970485794188159431017382878636879856244045329971239574"
2636        "8919691133560661162828034323196457386059819832804593989740268964"
2637        "74502911811812651475927076",
2638        "6703903964971298549787012499102923063739682910296196688861780721"
2639        "8608820150367734884009371490834517138450159290932430254268769414"
2640        "05973284973216824503042158",
2641        "6703903964971298549787012499102923063739682910296196688861780721"
2642        "8608820150367734884009371490834517138450159290932430254268769414"
2643        "05973284973216824503042159",
2644        "1"
2645    },
2646    {   /* between fifth and sixth iteration */
2647        "5239312332984325668414624633307915097111691815000872662334695514"
2648        "5436533521392362443557163429336808208137221322444780490437871903"
2649        "99972784701334569424519255",
2650        "6703903964971298549787012499102923063739682910296196688861780721"
2651        "8608820150367734884009371490834517138450159290932430254268769414"
2652        "05973284973216824503042158",
2653        "6703903964971298549787012499102923063739682910296196688861780721"
2654        "8608820150367734884009371490834517138450159290932430254268769414"
2655        "05973284973216824503042159",
2656        "1"
2657    },
2658    {   /* between sixth and seventh iteration */
2659        "1977953647322612860406858017869125467496941904523063466791308891"
2660        "1172796739058531929470539758361774569875505293428856181093904091"
2661        "33788264851714311303725089",
2662        "6703903964971298549787012499102923063739682910296196688861780721"
2663        "8608820150367734884009371490834517138450159290932430254268769414"
2664        "05973284973216824503042158",
2665        "6703903964971298549787012499102923063739682910296196688861780721"
2666        "8608820150367734884009371490834517138450159290932430254268769414"
2667        "05973284973216824503042159",
2668        "1"
2669    },
2670    {   /* between seventh and eighth iteration */
2671        "6456987954117763835533395796948878140715006860263624787492985786"
2672        "8514630216966738305923915688821526449499763719943997120302368211"
2673        "04813318117996225041943964",
2674        "1340780792994259709957402499820584612747936582059239337772356144"
2675        "3721764030073546976801874298166903427690031858186486050853753882"
2676        "811946551499689575296532556",
2677        "1340780792994259709957402499820584612747936582059239337772356144"
2678        "3721764030073546976801874298166903427690031858186486050853753882"
2679        "811946551499689575296532557",
2680        "1"
2681    }
2682 };
2683
2684 static int test_mod_exp(int i)
2685 {
2686     const MOD_EXP_TEST *test = &ModExpTests[i];
2687     int res = 0;
2688     BIGNUM* result = NULL;
2689     BIGNUM *base = NULL, *exponent = NULL, *modulo = NULL;
2690     char *s = NULL;
2691
2692     if (!TEST_ptr(result = BN_new())
2693             || !TEST_true(BN_dec2bn(&base, test->base))
2694             || !TEST_true(BN_dec2bn(&exponent, test->exp))
2695             || !TEST_true(BN_dec2bn(&modulo, test->mod)))
2696         goto err;
2697
2698     if (!TEST_int_eq(BN_mod_exp(result, base, exponent, modulo, ctx), 1))
2699         goto err;
2700
2701     if (!TEST_ptr(s = BN_bn2dec(result)))
2702         goto err;
2703
2704     if (!TEST_mem_eq(s, strlen(s), test->res, strlen(test->res)))
2705         goto err;
2706
2707     res = 1;
2708
2709  err:
2710     OPENSSL_free(s);
2711     BN_free(result);
2712     BN_free(base);
2713     BN_free(exponent);
2714     BN_free(modulo);
2715     return res;
2716 }
2717
2718 static int test_mod_exp_consttime(int i)
2719 {
2720     const MOD_EXP_TEST *test = &ModExpTests[i];
2721     int res = 0;
2722     BIGNUM* result = NULL;
2723     BIGNUM *base = NULL, *exponent = NULL, *modulo = NULL;
2724     char *s = NULL;
2725
2726     if (!TEST_ptr(result = BN_new())
2727             || !TEST_true(BN_dec2bn(&base, test->base))
2728             || !TEST_true(BN_dec2bn(&exponent, test->exp))
2729             || !TEST_true(BN_dec2bn(&modulo, test->mod)))
2730         goto err;
2731
2732     BN_set_flags(base, BN_FLG_CONSTTIME);
2733     BN_set_flags(exponent, BN_FLG_CONSTTIME);
2734     BN_set_flags(modulo, BN_FLG_CONSTTIME);
2735
2736     if (!TEST_int_eq(BN_mod_exp(result, base, exponent, modulo, ctx), 1))
2737         goto err;
2738
2739     if (!TEST_ptr(s = BN_bn2dec(result)))
2740         goto err;
2741
2742     if (!TEST_mem_eq(s, strlen(s), test->res, strlen(test->res)))
2743         goto err;
2744
2745     res = 1;
2746
2747  err:
2748     OPENSSL_free(s);
2749     BN_free(result);
2750     BN_free(base);
2751     BN_free(exponent);
2752     BN_free(modulo);
2753     return res;
2754 }
2755
2756 static int file_test_run(STANZA *s)
2757 {
2758     static const FILETEST filetests[] = {
2759         {"Sum", file_sum},
2760         {"LShift1", file_lshift1},
2761         {"LShift", file_lshift},
2762         {"RShift", file_rshift},
2763         {"Square", file_square},
2764         {"Product", file_product},
2765         {"Quotient", file_quotient},
2766         {"ModMul", file_modmul},
2767         {"ModExp", file_modexp},
2768         {"Exp", file_exp},
2769         {"ModSqrt", file_modsqrt},
2770         {"GCD", file_gcd},
2771     };
2772     int numtests = OSSL_NELEM(filetests);
2773     const FILETEST *tp = filetests;
2774
2775     for ( ; --numtests >= 0; tp++) {
2776         if (findattr(s, tp->name) != NULL) {
2777             if (!tp->func(s)) {
2778                 TEST_info("%s:%d: Failed %s test",
2779                           s->test_file, s->start, tp->name);
2780                 return 0;
2781             }
2782             return 1;
2783         }
2784     }
2785     TEST_info("%s:%d: Unknown test", s->test_file, s->start);
2786     return 0;
2787 }
2788
2789 static int run_file_tests(int i)
2790 {
2791     STANZA *s = NULL;
2792     char *testfile = test_get_argument(i);
2793     int c;
2794
2795     if (!TEST_ptr(s = OPENSSL_zalloc(sizeof(*s))))
2796         return 0;
2797     if (!test_start_file(s, testfile)) {
2798         OPENSSL_free(s);
2799         return 0;
2800     }
2801
2802     /* Read test file. */
2803     while (!BIO_eof(s->fp) && test_readstanza(s)) {
2804         if (s->numpairs == 0)
2805             continue;
2806         if (!file_test_run(s))
2807             s->errors++;
2808         s->numtests++;
2809         test_clearstanza(s);
2810     }
2811     test_end_file(s);
2812     c = s->errors;
2813     OPENSSL_free(s);
2814
2815     return c == 0;
2816 }
2817
2818
2819 int setup_tests(void)
2820 {
2821     int n = test_get_argument_count();
2822
2823     if (!TEST_ptr(ctx = BN_CTX_new()))
2824         return 0;
2825
2826     if (n == 0) {
2827         ADD_TEST(test_sub);
2828         ADD_TEST(test_div_recip);
2829         ADD_ALL_TESTS(test_signed_mod_replace_ab, OSSL_NELEM(signed_mod_tests));
2830         ADD_ALL_TESTS(test_signed_mod_replace_ba, OSSL_NELEM(signed_mod_tests));
2831         ADD_TEST(test_mod);
2832         ADD_TEST(test_modexp_mont5);
2833         ADD_TEST(test_kronecker);
2834         ADD_TEST(test_rand);
2835         ADD_TEST(test_bn2padded);
2836         ADD_TEST(test_dec2bn);
2837         ADD_TEST(test_hex2bn);
2838         ADD_TEST(test_asc2bn);
2839         ADD_ALL_TESTS(test_mpi, (int)OSSL_NELEM(kMPITests));
2840         ADD_TEST(test_negzero);
2841         ADD_TEST(test_badmod);
2842         ADD_TEST(test_expmodzero);
2843         ADD_TEST(test_expmodone);
2844         ADD_ALL_TESTS(test_smallprime, 16);
2845         ADD_ALL_TESTS(test_smallsafeprime, 16);
2846         ADD_TEST(test_swap);
2847         ADD_TEST(test_ctx_consttime_flag);
2848 #ifndef OPENSSL_NO_EC2M
2849         ADD_TEST(test_gf2m_add);
2850         ADD_TEST(test_gf2m_mod);
2851         ADD_TEST(test_gf2m_mul);
2852         ADD_TEST(test_gf2m_sqr);
2853         ADD_TEST(test_gf2m_modinv);
2854         ADD_TEST(test_gf2m_moddiv);
2855         ADD_TEST(test_gf2m_modexp);
2856         ADD_TEST(test_gf2m_modsqrt);
2857         ADD_TEST(test_gf2m_modsolvequad);
2858 #endif
2859         ADD_ALL_TESTS(test_is_prime, (int)OSSL_NELEM(primes));
2860         ADD_ALL_TESTS(test_not_prime, (int)OSSL_NELEM(not_primes));
2861         ADD_TEST(test_gcd_prime);
2862         ADD_ALL_TESTS(test_mod_exp, (int)OSSL_NELEM(ModExpTests));
2863         ADD_ALL_TESTS(test_mod_exp_consttime, (int)OSSL_NELEM(ModExpTests));
2864     } else {
2865         ADD_ALL_TESTS(run_file_tests, n);
2866     }
2867     return 1;
2868 }
2869
2870 void cleanup_tests(void)
2871 {
2872     BN_CTX_free(ctx);
2873 }