2 * Copyright 1995-2016 The OpenSSL Project Authors. All Rights Reserved.
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
16 #include <internal/numbers.h>
17 #include <openssl/bn.h>
18 #include <openssl/crypto.h>
19 #include <openssl/err.h>
20 #include <openssl/rand.h>
24 * In bn_lcl.h, bn_expand() is defined as a static ossl_inline function.
25 * This is fine in itself, it will end up as an unused static function in
26 * the worst case. However, it references bn_expand2(), which is a private
27 * function in libcrypto and therefore unavailable on some systems. This
28 * may result in a linker error because of unresolved symbols.
30 * To avoid this, we define a dummy variant of bn_expand2() here, and to
31 * avoid possible clashes with libcrypto, we rename it first, using a macro.
33 #define bn_expand2 dummy_bn_expand2
34 BIGNUM *bn_expand2(BIGNUM *b, int words);
35 BIGNUM *bn_expand2(BIGNUM *b, int words) { return NULL; }
36 #include "../crypto/bn/bn_lcl.h"
41 * Things in boring, not in openssl. TODO we should add them.
43 #define HAVE_BN_PADDED 0
44 #define HAVE_BN_SQRT 0
46 typedef struct pair_st {
51 typedef struct stanza_st {
57 typedef struct filetest_st {
59 int (*func)(STANZA *s);
62 typedef struct mpitest_st {
68 static const int NUM0 = 100; /* number of tests */
69 static const int NUM1 = 50; /* additional tests for some functions */
74 * Polynomial coefficients used in GFM tests.
76 static int p0[] = { 163, 7, 6, 3, 0, -1 };
77 static int p1[] = { 193, 15, 0, -1 };
81 * Look for |key| in the stanza and return it or NULL if not found.
83 static const char *findattr(STANZA *s, const char *key)
88 for ( ; --i >= 0; pp++)
89 if (strcasecmp(pp->key, key) == 0)
95 * Parse BIGNUM, return number of bytes parsed.
97 static int parseBN(BIGNUM **out, const char *in)
100 return BN_hex2bn(out, in);
103 static int parsedecBN(BIGNUM **out, const char *in)
106 return BN_dec2bn(out, in);
109 static BIGNUM *getBN(STANZA *s, const char *attribute)
114 if ((hex = findattr(s, attribute)) == NULL) {
115 TEST_error("Can't find %s in test at line %d", attribute, s->start);
119 if (parseBN(&ret, hex) != (int)strlen(hex)) {
120 TEST_error("Could not decode '%s'", hex);
126 static int getint(STANZA *s, int *out, const char *attribute)
132 if (!TEST_ptr(ret = getBN(s, attribute))
133 || !TEST_ulong_le(word = BN_get_word(ret), INT_MAX))
143 static int equalBN(const char *op, const BIGNUM *expected, const BIGNUM *actual)
148 if (BN_cmp(expected, actual) == 0)
151 if (BN_is_zero(expected) && BN_is_negative(expected))
152 exstr = OPENSSL_strdup("-0");
154 exstr = BN_bn2hex(expected);
155 if (BN_is_zero(actual) && BN_is_negative(actual))
156 actstr = OPENSSL_strdup("-0");
158 actstr = BN_bn2hex(actual);
159 if (!TEST_ptr(exstr) || !TEST_ptr(actstr))
162 TEST_error("Got %s =\n\t%s\nwanted:\n\t%s", op, actstr, exstr);
166 OPENSSL_free(actstr);
172 * Return a "random" flag for if a BN should be negated.
174 static int rand_neg(void)
176 static unsigned int neg = 0;
177 static int sign[8] = { 0, 0, 0, 1, 1, 0, 1, 1 };
179 return sign[(neg++) % 8];
183 static int test_sub()
185 BIGNUM *a = NULL, *b = NULL, *c = NULL;
188 if (!TEST_ptr(a = BN_new())
189 || !TEST_ptr(b = BN_new())
190 || !TEST_ptr(c = BN_new()))
193 for (i = 0; i < NUM0 + NUM1; i++) {
195 BN_bntest_rand(a, 512, 0, 0);
197 if (!TEST_int_ne(BN_set_bit(a, i), 0))
201 BN_bntest_rand(b, 400 + i - NUM1, 0, 0);
208 if (!TEST_true(BN_is_zero(c)))
220 static int test_div_recip()
222 BIGNUM *a = NULL, *b = NULL, *c = NULL, *d = NULL, *e = NULL;
223 BN_RECP_CTX *recp = NULL;
226 if (!TEST_ptr(a = BN_new())
227 || !TEST_ptr(b = BN_new())
228 || !TEST_ptr(c = BN_new())
229 || !TEST_ptr(d = BN_new())
230 || !TEST_ptr(e = BN_new())
231 || !TEST_ptr(recp = BN_RECP_CTX_new()))
234 for (i = 0; i < NUM0 + NUM1; i++) {
236 BN_bntest_rand(a, 400, 0, 0);
241 BN_bntest_rand(b, 50 + 3 * (i - NUM1), 0, 0);
244 BN_RECP_CTX_set(recp, b, ctx);
245 BN_div_recp(d, c, a, recp, ctx);
246 BN_mul(e, d, b, ctx);
249 if (!TEST_true(BN_is_zero(d)))
259 BN_RECP_CTX_free(recp);
264 static int test_mod()
266 BIGNUM *a = NULL, *b = NULL, *c = NULL, *d = NULL, *e = NULL;
269 if (!TEST_ptr(a = BN_new())
270 || !TEST_ptr(b = BN_new())
271 || !TEST_ptr(c = BN_new())
272 || !TEST_ptr(d = BN_new())
273 || !TEST_ptr(e = BN_new()))
276 BN_bntest_rand(a, 1024, 0, 0);
277 for (i = 0; i < NUM0; i++) {
278 BN_bntest_rand(b, 450 + i * 10, 0, 0);
281 BN_mod(c, a, b, ctx);
282 BN_div(d, e, a, b, ctx);
284 if (!TEST_true(BN_is_zero(e)))
297 static const char *bn1strings[] = {
298 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
299 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
300 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
301 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
302 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
303 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
304 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
305 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00000000000000FFFFFFFF00",
306 "0000000000000000000000000000000000000000000000000000000000000000",
307 "0000000000000000000000000000000000000000000000000000000000000000",
308 "0000000000000000000000000000000000000000000000000000000000000000",
309 "0000000000000000000000000000000000000000000000000000000000000000",
310 "0000000000000000000000000000000000000000000000000000000000000000",
311 "0000000000000000000000000000000000000000000000000000000000000000",
312 "0000000000000000000000000000000000000000000000000000000000000000",
313 "00000000000000000000000000000000000000000000000000FFFFFFFFFFFFFF",
317 static const char *bn2strings[] = {
318 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
319 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
320 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
321 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
322 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
323 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
324 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
325 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00000000000000FFFFFFFF0000000000",
326 "0000000000000000000000000000000000000000000000000000000000000000",
327 "0000000000000000000000000000000000000000000000000000000000000000",
328 "0000000000000000000000000000000000000000000000000000000000000000",
329 "0000000000000000000000000000000000000000000000000000000000000000",
330 "0000000000000000000000000000000000000000000000000000000000000000",
331 "0000000000000000000000000000000000000000000000000000000000000000",
332 "0000000000000000000000000000000000000000000000000000000000000000",
333 "000000000000000000000000000000000000000000FFFFFFFFFFFFFF00000000",
337 static char *glue(const char *list[])
343 for (i = 0; list[i] != NULL; i++)
344 len += strlen(list[i]);
345 if (!TEST_ptr(p = save = OPENSSL_malloc(len + 1)))
347 for (i = 0; list[i] != NULL; i++)
348 p += strlen(strcpy(p, list[i]));
353 * Test constant-time modular exponentiation with 1024-bit inputs, which on
354 * x86_64 cause a different code branch to be taken.
356 static int test_modexp_mont5()
358 BIGNUM *a = NULL, *p = NULL, *m = NULL, *d = NULL, *e = NULL;
359 BIGNUM *b = NULL, *n = NULL, *c = NULL;
360 BN_MONT_CTX *mont = NULL;
364 if (!TEST_ptr(a = BN_new())
365 || !TEST_ptr(p = BN_new())
366 || !TEST_ptr(m = BN_new())
367 || !TEST_ptr(d = BN_new())
368 || !TEST_ptr(e = BN_new())
369 || !TEST_ptr(b = BN_new())
370 || !TEST_ptr(n = BN_new())
371 || !TEST_ptr(c = BN_new())
372 || !TEST_ptr(mont = BN_MONT_CTX_new()))
375 BN_bntest_rand(m, 1024, 0, 1); /* must be odd for montgomery */
377 BN_bntest_rand(a, 1024, 0, 0);
379 if (!TEST_true(BN_mod_exp_mont_consttime(d, a, p, m, ctx, NULL)))
381 if (!TEST_true(BN_is_one(d)))
384 /* Regression test for carry bug in mulx4x_mont */
386 "7878787878787878787878787878787878787878787878787878787878787878"
387 "7878787878787878787878787878787878787878787878787878787878787878"
388 "7878787878787878787878787878787878787878787878787878787878787878"
389 "7878787878787878787878787878787878787878787878787878787878787878");
391 "095D72C08C097BA488C5E439C655A192EAFB6380073D8C2664668EDDB4060744"
392 "E16E57FB4EDB9AE10A0CEFCDC28A894F689A128379DB279D48A2E20849D68593"
393 "9B7803BCF46CEBF5C533FB0DD35B080593DE5472E3FE5DB951B8BFF9B4CB8F03"
394 "9CC638A5EE8CDD703719F8000E6A9F63BEED5F2FCD52FF293EA05A251BB4AB81");
396 "D78AF684E71DB0C39CFF4E64FB9DB567132CB9C50CC98009FEB820B26F2DED9B"
397 "91B9B5E2B83AE0AE4EB4E0523CA726BFBE969B89FD754F674CE99118C3F2D1C5"
398 "D81FDC7C54E02B60262B241D53C040E99E45826ECA37A804668E690E1AFC1CA4"
399 "2C9A15D84D4954425F0B7642FC0BD9D7B24E2618D2DCC9B729D944BADACFDDAF");
400 BN_MONT_CTX_set(mont, n, ctx);
401 BN_mod_mul_montgomery(c, a, b, mont, ctx);
402 BN_mod_mul_montgomery(d, b, a, mont, ctx);
403 if (!TEST_int_eq(BN_cmp(c, d), 0))
406 /* Regression test for carry bug in sqr[x]8x_mont */
407 bigstring = glue(bn1strings);
408 BN_hex2bn(&n, bigstring);
409 OPENSSL_free(bigstring);
410 bigstring = glue(bn2strings);
411 BN_hex2bn(&a, bigstring);
412 OPENSSL_free(bigstring);
415 BN_MONT_CTX_set(mont, n, ctx);
416 BN_mod_mul_montgomery(c, a, a, mont, ctx);
417 BN_mod_mul_montgomery(d, a, b, mont, ctx);
418 if (!TEST_int_eq(BN_cmp(c, d), 0))
422 BN_bntest_rand(p, 1024, 0, 0);
424 if (!TEST_true(BN_mod_exp_mont_consttime(d, a, p, m, ctx, NULL))
425 || !TEST_true(BN_is_zero(d)))
429 * Craft an input whose Montgomery representation is 1, i.e., shorter
430 * than the modulus m, in order to test the const time precomputation
431 * scattering/gathering.
434 BN_MONT_CTX_set(mont, m, ctx);
435 if (!TEST_true(BN_from_montgomery(e, a, mont, ctx))
436 || !TEST_true(BN_mod_exp_mont_consttime(d, e, p, m, ctx, NULL))
437 || !TEST_true(BN_mod_exp_simple(a, e, p, m, ctx))
438 || !TEST_int_eq(BN_cmp(a, d), 0))
441 /* Finally, some regular test vectors. */
442 BN_bntest_rand(e, 1024, 0, 0);
443 if (!TEST_true(BN_mod_exp_mont_consttime(d, e, p, m, ctx, NULL))
444 || !TEST_true(BN_mod_exp_simple(a, e, p, m, ctx))
445 || !TEST_int_eq(BN_cmp(a, d), 0))
451 BN_MONT_CTX_free(mont);
463 #ifndef OPENSSL_NO_EC2M
464 static int test_gf2m_add()
466 BIGNUM *a = NULL, *b = NULL, *c = NULL;
469 if (!TEST_ptr(a = BN_new())
470 || !TEST_ptr(b = BN_new())
471 || !TEST_ptr(c = BN_new()))
474 for (i = 0; i < NUM0; i++) {
475 BN_rand(a, 512, 0, 0);
476 BN_copy(b, BN_value_one());
479 BN_GF2m_add(c, a, b);
480 /* Test that two added values have the correct parity. */
481 if (!TEST_false((BN_is_odd(a) && BN_is_odd(c))
482 || (!BN_is_odd(a) && !BN_is_odd(c))))
484 BN_GF2m_add(c, c, c);
485 /* Test that c + c = 0. */
486 if (!TEST_true(BN_is_zero(c)))
497 static int test_gf2m_mod()
499 BIGNUM *a = NULL, *b[2] = {NULL,NULL}, *c = NULL, *d = NULL, *e = NULL;
502 if (!TEST_ptr(a = BN_new())
503 || !TEST_ptr(b[0] = BN_new())
504 || !TEST_ptr(b[1] = BN_new())
505 || !TEST_ptr(c = BN_new())
506 || !TEST_ptr(d = BN_new())
507 || !TEST_ptr(e = BN_new()))
510 BN_GF2m_arr2poly(p0, b[0]);
511 BN_GF2m_arr2poly(p1, b[1]);
513 for (i = 0; i < NUM0; i++) {
514 BN_bntest_rand(a, 1024, 0, 0);
515 for (j = 0; j < 2; j++) {
516 BN_GF2m_mod(c, a, b[j]);
517 BN_GF2m_add(d, a, c);
518 BN_GF2m_mod(e, d, b[j]);
519 /* Test that a + (a mod p) mod p == 0. */
520 if (!TEST_true(BN_is_zero(e)))
535 static int test_gf2m_mul()
537 BIGNUM *a, *b[2] = {NULL, NULL}, *c = NULL, *d = NULL;
538 BIGNUM *e = NULL, *f = NULL, *g = NULL, *h = NULL;
541 if (!TEST_ptr(a = BN_new())
542 || !TEST_ptr(b[0] = BN_new())
543 || !TEST_ptr(b[1] = BN_new())
544 || !TEST_ptr(c = BN_new())
545 || !TEST_ptr(d = BN_new())
546 || !TEST_ptr(e = BN_new())
547 || !TEST_ptr(f = BN_new())
548 || !TEST_ptr(g = BN_new())
549 || !TEST_ptr(h = BN_new()))
552 BN_GF2m_arr2poly(p0, b[0]);
553 BN_GF2m_arr2poly(p1, b[1]);
555 for (i = 0; i < NUM0; i++) {
556 BN_bntest_rand(a, 1024, 0, 0);
557 BN_bntest_rand(c, 1024, 0, 0);
558 BN_bntest_rand(d, 1024, 0, 0);
559 for (j = 0; j < 2; j++) {
560 BN_GF2m_mod_mul(e, a, c, b[j], ctx);
561 BN_GF2m_add(f, a, d);
562 BN_GF2m_mod_mul(g, f, c, b[j], ctx);
563 BN_GF2m_mod_mul(h, d, c, b[j], ctx);
564 BN_GF2m_add(f, e, g);
565 BN_GF2m_add(f, f, h);
566 /* Test that (a+d)*c = a*c + d*c. */
567 if (!TEST_true(BN_is_zero(f)))
586 static int test_gf2m_sqr()
588 BIGNUM *a = NULL, *b[2] = {NULL,NULL}, *c = NULL, *d = NULL;
591 if (!TEST_ptr(a = BN_new())
592 || !TEST_ptr(b[0] = BN_new())
593 || !TEST_ptr(b[1] = BN_new())
594 || !TEST_ptr(c = BN_new())
595 || !TEST_ptr(d = BN_new()))
598 BN_GF2m_arr2poly(p0, b[0]);
599 BN_GF2m_arr2poly(p1, b[1]);
601 for (i = 0; i < NUM0; i++) {
602 BN_bntest_rand(a, 1024, 0, 0);
603 for (j = 0; j < 2; j++) {
604 BN_GF2m_mod_sqr(c, a, b[j], ctx);
606 BN_GF2m_mod_mul(d, a, d, b[j], ctx);
607 BN_GF2m_add(d, c, d);
608 /* Test that a*a = a^2. */
609 if (!TEST_true(BN_is_zero(d)))
623 static int test_gf2m_modinv()
625 BIGNUM *a = NULL, *b[2] = {NULL,NULL}, *c = NULL, *d = NULL;
628 if (!TEST_ptr(a = BN_new())
629 || !TEST_ptr(b[0] = BN_new())
630 || !TEST_ptr(b[1] = BN_new())
631 || !TEST_ptr(c = BN_new())
632 || !TEST_ptr(d = BN_new()))
635 BN_GF2m_arr2poly(p0, b[0]);
636 BN_GF2m_arr2poly(p1, b[1]);
638 for (i = 0; i < NUM0; i++) {
639 BN_bntest_rand(a, 512, 0, 0);
640 for (j = 0; j < 2; j++) {
641 BN_GF2m_mod_inv(c, a, b[j], ctx);
642 BN_GF2m_mod_mul(d, a, c, b[j], ctx);
643 /* Test that ((1/a)*a) = 1. */
644 if (!TEST_true(BN_is_one(d)))
658 static int test_gf2m_moddiv()
660 BIGNUM *a = NULL, *b[2] = {NULL,NULL}, *c = NULL, *d = NULL;
661 BIGNUM *e = NULL, *f = NULL;
664 if (!TEST_ptr(a = BN_new())
665 || !TEST_ptr(b[0] = BN_new())
666 || !TEST_ptr(b[1] = BN_new())
667 || !TEST_ptr(c = BN_new())
668 || !TEST_ptr(d = BN_new())
669 || !TEST_ptr(e = BN_new())
670 || !TEST_ptr(f = BN_new()))
673 BN_GF2m_arr2poly(p0, b[0]);
674 BN_GF2m_arr2poly(p1, b[1]);
676 for (i = 0; i < NUM0; i++) {
677 BN_bntest_rand(a, 512, 0, 0);
678 BN_bntest_rand(c, 512, 0, 0);
679 for (j = 0; j < 2; j++) {
680 BN_GF2m_mod_div(d, a, c, b[j], ctx);
681 BN_GF2m_mod_mul(e, d, c, b[j], ctx);
682 BN_GF2m_mod_div(f, a, e, b[j], ctx);
683 /* Test that ((a/c)*c)/a = 1. */
684 if (!TEST_true(BN_is_one(f)))
700 static int test_gf2m_modexp()
702 BIGNUM *a = NULL, *b[2] = {NULL,NULL}, *c = NULL, *d = NULL;
703 BIGNUM *e = NULL, *f = NULL;
706 if (!TEST_ptr(a = BN_new())
707 || !TEST_ptr(b[0] = BN_new())
708 || !TEST_ptr(b[1] = BN_new())
709 || !TEST_ptr(c = BN_new())
710 || !TEST_ptr(d = BN_new())
711 || !TEST_ptr(e = BN_new())
712 || !TEST_ptr(f = BN_new()))
715 BN_GF2m_arr2poly(p0, b[0]);
716 BN_GF2m_arr2poly(p1, b[1]);
718 for (i = 0; i < NUM0; i++) {
719 BN_bntest_rand(a, 512, 0, 0);
720 BN_bntest_rand(c, 512, 0, 0);
721 BN_bntest_rand(d, 512, 0, 0);
722 for (j = 0; j < 2; j++) {
723 BN_GF2m_mod_exp(e, a, c, b[j], ctx);
724 BN_GF2m_mod_exp(f, a, d, b[j], ctx);
725 BN_GF2m_mod_mul(e, e, f, b[j], ctx);
727 BN_GF2m_mod_exp(f, a, f, b[j], ctx);
728 BN_GF2m_add(f, e, f);
729 /* Test that a^(c+d)=a^c*a^d. */
730 if (!TEST_true(BN_is_zero(f)))
746 static int test_gf2m_modsqrt()
748 BIGNUM *a = NULL, *b[2] = {NULL,NULL}, *c = NULL, *d = NULL;
749 BIGNUM *e = NULL, *f = NULL;
752 if (!TEST_ptr(a = BN_new())
753 || !TEST_ptr(b[0] = BN_new())
754 || !TEST_ptr(b[1] = BN_new())
755 || !TEST_ptr(c = BN_new())
756 || !TEST_ptr(d = BN_new())
757 || !TEST_ptr(e = BN_new())
758 || !TEST_ptr(f = BN_new()))
761 BN_GF2m_arr2poly(p0, b[0]);
762 BN_GF2m_arr2poly(p1, b[1]);
764 for (i = 0; i < NUM0; i++) {
765 BN_bntest_rand(a, 512, 0, 0);
766 for (j = 0; j < 2; j++) {
767 BN_GF2m_mod(c, a, b[j]);
768 BN_GF2m_mod_sqrt(d, a, b[j], ctx);
769 BN_GF2m_mod_sqr(e, d, b[j], ctx);
770 BN_GF2m_add(f, c, e);
771 /* Test that d^2 = a, where d = sqrt(a). */
772 if (!TEST_true(BN_is_zero(f)))
788 static int test_gf2m_modsolvequad()
790 BIGNUM *a = NULL, *b[2] = {NULL,NULL}, *c = NULL, *d = NULL;
792 int i, j, s = 0, t, st = 0;
794 if (!TEST_ptr(a = BN_new())
795 || !TEST_ptr(b[0] = BN_new())
796 || !TEST_ptr(b[1] = BN_new())
797 || !TEST_ptr(c = BN_new())
798 || !TEST_ptr(d = BN_new())
799 || !TEST_ptr(e = BN_new()))
802 BN_GF2m_arr2poly(p0, b[0]);
803 BN_GF2m_arr2poly(p1, b[1]);
805 for (i = 0; i < NUM0; i++) {
806 BN_bntest_rand(a, 512, 0, 0);
807 for (j = 0; j < 2; j++) {
808 t = BN_GF2m_mod_solve_quad(c, a, b[j], ctx);
811 BN_GF2m_mod_sqr(d, c, b[j], ctx);
812 BN_GF2m_add(d, c, d);
813 BN_GF2m_mod(e, a, b[j]);
814 BN_GF2m_add(e, e, d);
816 * Test that solution of quadratic c satisfies c^2 + c = a.
818 if (!TEST_true(BN_is_zero(e)))
823 if (!TEST_int_ge(s, 0)) {
824 TEST_info("%d tests found no roots; probably an error", NUM0);
839 static int test_kronecker()
841 BIGNUM *a = NULL, *b = NULL, *r = NULL, *t = NULL;
842 int i, legendre, kronecker, st = 0;
844 if (!TEST_ptr(a = BN_new())
845 || !TEST_ptr(b = BN_new())
846 || !TEST_ptr(r = BN_new())
847 || !TEST_ptr(t = BN_new()))
851 * We test BN_kronecker(a, b, ctx) just for b odd (Jacobi symbol). In
852 * this case we know that if b is prime, then BN_kronecker(a, b, ctx) is
853 * congruent to $a^{(b-1)/2}$, modulo $b$ (Legendre symbol). So we
854 * generate a random prime b and compare these values for a number of
855 * random a's. (That is, we run the Solovay-Strassen primality test to
856 * confirm that b is prime, except that we don't want to test whether b
857 * is prime but whether BN_kronecker works.)
860 if (!TEST_true(BN_generate_prime_ex(b, 512, 0, NULL, NULL, NULL)))
864 for (i = 0; i < NUM0; i++) {
865 if (!TEST_true(BN_bntest_rand(a, 512, 0, 0)))
869 /* t := (|b|-1)/2 (note that b is odd) */
870 if (!TEST_true(BN_copy(t, b)))
873 if (!TEST_true(BN_sub_word(t, 1)))
875 if (!TEST_true(BN_rshift1(t, t)))
880 if (!TEST_true(BN_mod_exp_recp(r, a, t, b, ctx)))
884 if (BN_is_word(r, 1))
886 else if (BN_is_zero(r))
889 if (!TEST_true(BN_add_word(r, 1)))
891 if (!TEST_int_eq(BN_ucmp(r, b), 0)) {
892 TEST_info("Legendre symbol computation failed");
898 if (!TEST_int_ge(kronecker = BN_kronecker(a, b, ctx), -1))
900 /* we actually need BN_kronecker(a, |b|) */
901 if (a->neg && b->neg)
902 kronecker = -kronecker;
904 if (!TEST_int_eq(legendre, kronecker))
917 static int file_sum(STANZA *s)
919 BIGNUM *a = NULL, *b = NULL, *sum = NULL, *ret = NULL;
923 if (!TEST_ptr(a = getBN(s, "A"))
924 || !TEST_ptr(b = getBN(s, "B"))
925 || !TEST_ptr(sum = getBN(s, "Sum"))
926 || !TEST_ptr(ret = BN_new()))
929 if (!TEST_true(BN_add(ret, a, b))
930 || !equalBN("A + B", sum, ret)
931 || !TEST_true(BN_sub(ret, sum, a))
932 || !equalBN("Sum - A", b, ret)
933 || !TEST_true(BN_sub(ret, sum, b))
934 || !equalBN("Sum - B", a, ret))
938 * Test that the functions work when |r| and |a| point to the same BIGNUM,
939 * or when |r| and |b| point to the same BIGNUM.
940 * TODO: Test where all of |r|, |a|, and |b| point to the same BIGNUM.
942 if (!TEST_true(BN_copy(ret, a))
943 || !TEST_true(BN_add(ret, ret, b))
944 || !equalBN("A + B (r is a)", sum, ret)
945 || !TEST_true(BN_copy(ret, b))
946 || !TEST_true(BN_add(ret, a, ret))
947 || !equalBN("A + B (r is b)", sum, ret)
948 || !TEST_true(BN_copy(ret, sum))
949 || !TEST_true(BN_sub(ret, ret, a))
950 || !equalBN("Sum - A (r is a)", b, ret)
951 || !TEST_true(BN_copy(ret, a))
952 || !TEST_true(BN_sub(ret, sum, ret))
953 || !equalBN("Sum - A (r is b)", b, ret)
954 || !TEST_true(BN_copy(ret, sum))
955 || !TEST_true(BN_sub(ret, ret, b))
956 || !equalBN("Sum - B (r is a)", a, ret)
957 || !TEST_true(BN_copy(ret, b))
958 || !TEST_true(BN_sub(ret, sum, ret))
959 || !equalBN("Sum - B (r is b)", a, ret))
963 * Test BN_uadd() and BN_usub() with the prerequisites they are
964 * documented as having. Note that these functions are frequently used
965 * when the prerequisites don't hold. In those cases, they are supposed
966 * to work as if the prerequisite hold, but we don't test that yet.
969 if (!BN_is_negative(a) && !BN_is_negative(b) && BN_cmp(a, b) >= 0) {
970 if (!TEST_true(BN_uadd(ret, a, b))
971 || !equalBN("A +u B", sum, ret)
972 || !TEST_true(BN_usub(ret, sum, a))
973 || !equalBN("Sum -u A", b, ret)
974 || !TEST_true(BN_usub(ret, sum, b))
975 || !equalBN("Sum -u B", a, ret))
978 * Test that the functions work when |r| and |a| point to the same
979 * BIGNUM, or when |r| and |b| point to the same BIGNUM.
980 * TODO: Test where all of |r|, |a|, and |b| point to the same BIGNUM.
982 if (!TEST_true(BN_copy(ret, a))
983 || !TEST_true(BN_uadd(ret, ret, b))
984 || !equalBN("A +u B (r is a)", sum, ret)
985 || !TEST_true(BN_copy(ret, b))
986 || !TEST_true(BN_uadd(ret, a, ret))
987 || !equalBN("A +u B (r is b)", sum, ret)
988 || !TEST_true(BN_copy(ret, sum))
989 || !TEST_true(BN_usub(ret, ret, a))
990 || !equalBN("Sum -u A (r is a)", b, ret)
991 || !TEST_true(BN_copy(ret, a))
992 || !TEST_true(BN_usub(ret, sum, ret))
993 || !equalBN("Sum -u A (r is b)", b, ret)
994 || !TEST_true(BN_copy(ret, sum))
995 || !TEST_true(BN_usub(ret, ret, b))
996 || !equalBN("Sum -u B (r is a)", a, ret)
997 || !TEST_true(BN_copy(ret, b))
998 || !TEST_true(BN_usub(ret, sum, ret))
999 || !equalBN("Sum -u B (r is b)", a, ret))
1004 * Test with BN_add_word() and BN_sub_word() if |b| is small enough.
1006 b_word = BN_get_word(b);
1007 if (!BN_is_negative(b) && b_word != (BN_ULONG)-1) {
1008 if (!TEST_true(BN_copy(ret, a))
1009 || !TEST_true(BN_add_word(ret, b_word))
1010 || !equalBN("A + B (word)", sum, ret)
1011 || !TEST_true(BN_copy(ret, sum))
1012 || !TEST_true(BN_sub_word(ret, b_word))
1013 || !equalBN("Sum - B (word)", a, ret))
1026 static int file_lshift1(STANZA *s)
1028 BIGNUM *a = NULL, *lshift1 = NULL, *zero = NULL, *ret = NULL;
1029 BIGNUM *two = NULL, *remainder = NULL;
1032 if (!TEST_ptr(a = getBN(s, "A"))
1033 || !TEST_ptr(lshift1 = getBN(s, "LShift1"))
1034 || !TEST_ptr(zero = BN_new())
1035 || !TEST_ptr(ret = BN_new())
1036 || !TEST_ptr(two = BN_new())
1037 || !TEST_ptr(remainder = BN_new()))
1042 if (!TEST_true(BN_set_word(two, 2))
1043 || !TEST_true(BN_add(ret, a, a))
1044 || !equalBN("A + A", lshift1, ret)
1045 || !TEST_true(BN_mul(ret, a, two, ctx))
1046 || !equalBN("A * 2", lshift1, ret)
1047 || !TEST_true(BN_div(ret, remainder, lshift1, two, ctx))
1048 || !equalBN("LShift1 / 2", a, ret)
1049 || !equalBN("LShift1 % 2", zero, remainder)
1050 || !TEST_true(BN_lshift1(ret, a))
1051 || !equalBN("A << 1", lshift1, ret)
1052 || !TEST_true(BN_rshift1(ret, lshift1))
1053 || !equalBN("LShift >> 1", a, ret)
1054 || !TEST_true(BN_rshift1(ret, lshift1))
1055 || !equalBN("LShift >> 1", a, ret))
1058 /* Set the LSB to 1 and test rshift1 again. */
1059 if (!TEST_true(BN_set_bit(lshift1, 0))
1060 || !TEST_true(BN_div(ret, NULL /* rem */ , lshift1, two, ctx))
1061 || !equalBN("(LShift1 | 1) / 2", a, ret)
1062 || !TEST_true(BN_rshift1(ret, lshift1))
1063 || !equalBN("(LShift | 1) >> 1", a, ret))
1078 static int file_lshift(STANZA *s)
1080 BIGNUM *a = NULL, *lshift = NULL, *ret = NULL;
1083 if (!TEST_ptr(a = getBN(s, "A"))
1084 || !TEST_ptr(lshift = getBN(s, "LShift"))
1085 || !TEST_ptr(ret = BN_new()))
1087 if (!TEST_true(BN_lshift(ret, a, n))
1088 || !equalBN("A << N", lshift, ret)
1089 || !TEST_true(BN_rshift(ret, lshift, n))
1090 || !equalBN("A >> N", a, ret))
1101 static int file_rshift(STANZA *s)
1103 BIGNUM *a = NULL, *rshift = NULL, *ret = NULL;
1106 if (!TEST_ptr(a = getBN(s, "A"))
1107 || !TEST_ptr(rshift = getBN(s, "RShift"))
1108 || !TEST_ptr(ret = BN_new())
1109 || !getint(s, &n, "N"))
1112 if (!TEST_true(BN_rshift(ret, a, n))
1113 || !equalBN("A >> N", rshift, ret))
1116 /* If N == 1, try with rshift1 as well */
1118 if (!TEST_true(BN_rshift1(ret, a))
1119 || !equalBN("A >> 1 (rshift1)", rshift, ret))
1131 static int file_square(STANZA *s)
1133 BIGNUM *a = NULL, *square = NULL, *zero = NULL, *ret = NULL;
1134 BIGNUM *remainder = NULL, *tmp = NULL;
1137 if (!TEST_ptr(a = getBN(s, "A"))
1138 || !TEST_ptr(square = getBN(s, "Square"))
1139 || !TEST_ptr(zero = BN_new())
1140 || !TEST_ptr(ret = BN_new())
1141 || !TEST_ptr(remainder = BN_new()))
1145 if (!TEST_true(BN_sqr(ret, a, ctx))
1146 || !equalBN("A^2", square, ret)
1147 || !TEST_true(BN_mul(ret, a, a, ctx))
1148 || !equalBN("A * A", square, ret)
1149 || !TEST_true(BN_div(ret, remainder, square, a, ctx))
1150 || !equalBN("Square / A", a, ret)
1151 || !equalBN("Square % A", zero, remainder))
1155 BN_set_negative(a, 0);
1156 if (!TEST_true(BN_sqrt(ret, square, ctx))
1157 || !equalBN("sqrt(Square)", a, ret))
1160 /* BN_sqrt should fail on non-squares and negative numbers. */
1161 if (!TEST_true(BN_is_zero(square))) {
1162 if (!TEST_ptr(tmp = BN_new()) || !TEST_true(BN_copy(tmp, square)))
1164 BN_set_negative(tmp, 1);
1166 if (!TEST_int_eq(BN_sqrt(ret, tmp, ctx), 0))
1170 BN_set_negative(tmp, 0);
1171 if (BN_add(tmp, tmp, BN_value_one()))
1173 if (!TEST_int_eq(BN_sqrt(ret, tmp, ctx)))
1190 static int file_product(STANZA *s)
1192 BIGNUM *a = NULL, *b = NULL, *product = NULL, *ret = NULL;
1193 BIGNUM *remainder = NULL, *zero = NULL;
1196 if (!TEST_ptr(a = getBN(s, "A"))
1197 || !TEST_ptr(b = getBN(s, "B"))
1198 || !TEST_ptr(product = getBN(s, "Product"))
1199 || !TEST_ptr(ret = BN_new())
1200 || !TEST_ptr(remainder = BN_new())
1201 || !TEST_ptr(zero = BN_new()))
1206 if (!TEST_true(BN_mul(ret, a, b, ctx))
1207 || !equalBN("A * B", product, ret)
1208 || !TEST_true(BN_div(ret, remainder, product, a, ctx))
1209 || !equalBN("Product / A", b, ret)
1210 || !equalBN("Product % A", zero, remainder)
1211 || !TEST_true(BN_div(ret, remainder, product, b, ctx))
1212 || !equalBN("Product / B", a, ret)
1213 || !equalBN("Product % B", zero, remainder))
1227 static int file_quotient(STANZA *s)
1229 BIGNUM *a = NULL, *b = NULL, *quotient = NULL, *remainder = NULL;
1230 BIGNUM *ret = NULL, *ret2 = NULL, *nnmod = NULL;
1231 BN_ULONG b_word, ret_word;
1234 if (!TEST_ptr(a = getBN(s, "A"))
1235 || !TEST_ptr(b = getBN(s, "B"))
1236 || !TEST_ptr(quotient = getBN(s, "Quotient"))
1237 || !TEST_ptr(remainder = getBN(s, "Remainder"))
1238 || !TEST_ptr(ret = BN_new())
1239 || !TEST_ptr(ret2 = BN_new())
1240 || !TEST_ptr(nnmod = BN_new()))
1243 if (!TEST_true(BN_div(ret, ret2, a, b, ctx))
1244 || !equalBN("A / B", quotient, ret)
1245 || !equalBN("A % B", remainder, ret2)
1246 || !TEST_true(BN_mul(ret, quotient, b, ctx))
1247 || !TEST_true(BN_add(ret, ret, remainder))
1248 || !equalBN("Quotient * B + Remainder", a, ret))
1252 * Test with BN_mod_word() and BN_div_word() if the divisor is
1255 b_word = BN_get_word(b);
1256 if (!BN_is_negative(b) && b_word != (BN_ULONG)-1) {
1257 BN_ULONG remainder_word = BN_get_word(remainder);
1259 assert(remainder_word != (BN_ULONG)-1);
1260 if (!TEST_ptr(BN_copy(ret, a)))
1262 ret_word = BN_div_word(ret, b_word);
1263 if (ret_word != remainder_word) {
1266 "Got A %% B (word) = " BN_DEC_FMT1 ", wanted " BN_DEC_FMT1,
1267 ret_word, remainder_word);
1269 TEST_error("Got A %% B (word) mismatch");
1273 if (!equalBN ("A / B (word)", quotient, ret))
1276 ret_word = BN_mod_word(a, b_word);
1277 if (ret_word != remainder_word) {
1280 "Got A %% B (word) = " BN_DEC_FMT1 ", wanted " BN_DEC_FMT1 "",
1281 ret_word, remainder_word);
1283 TEST_error("Got A %% B (word) mismatch");
1289 /* Test BN_nnmod. */
1290 if (!BN_is_negative(b)) {
1291 if (!TEST_true(BN_copy(nnmod, remainder))
1292 || (BN_is_negative(nnmod)
1293 && !TEST_true(BN_add(nnmod, nnmod, b)))
1294 || !TEST_true(BN_nnmod(ret, a, b, ctx))
1295 || !equalBN("A % B (non-negative)", nnmod, ret))
1311 static int file_modmul(STANZA *s)
1313 BIGNUM *a = NULL, *b = NULL, *m = NULL, *mod_mul = NULL, *ret = NULL;
1316 if (!TEST_ptr(a = getBN(s, "A"))
1317 || !TEST_ptr(b = getBN(s, "B"))
1318 || !TEST_ptr(m = getBN(s, "M"))
1319 || !TEST_ptr(mod_mul = getBN(s, "ModMul"))
1320 || !TEST_ptr(ret = BN_new()))
1323 if (!TEST_true(BN_mod_mul(ret, a, b, m, ctx))
1324 || !equalBN("A * B (mod M)", mod_mul, ret))
1328 /* Reduce |a| and |b| and test the Montgomery version. */
1329 BN_MONT_CTX *mont = BN_MONT_CTX_new();
1330 BIGNUM *a_tmp = BN_new();
1331 BIGNUM *b_tmp = BN_new();
1333 if (mont == NULL || a_tmp == NULL || b_tmp == NULL
1334 || !TEST_true(BN_MONT_CTX_set(mont, m, ctx))
1335 || !TEST_true(BN_nnmod(a_tmp, a, m, ctx))
1336 || !TEST_true(BN_nnmod(b_tmp, b, m, ctx))
1337 || !TEST_true(BN_to_montgomery(a_tmp, a_tmp, mont, ctx))
1338 || !TEST_true(BN_to_montgomery(b_tmp, b_tmp, mont, ctx))
1339 || !TEST_true(BN_mod_mul_montgomery(ret, a_tmp, b_tmp,
1341 || !TEST_true(BN_from_montgomery(ret, ret, mont, ctx))
1342 || !equalBN("A * B (mod M) (mont)", mod_mul, ret))
1346 BN_MONT_CTX_free(mont);
1363 static int file_modexp(STANZA *s)
1365 BIGNUM *a = NULL, *e = NULL, *m = NULL, *mod_exp = NULL, *ret = NULL;
1366 BIGNUM *b = NULL, *c = NULL, *d = NULL;
1369 if (!TEST_ptr(a = getBN(s, "A"))
1370 || !TEST_ptr(e = getBN(s, "E"))
1371 || !TEST_ptr(m = getBN(s, "M"))
1372 || !TEST_ptr(mod_exp = getBN(s, "ModExp"))
1373 || !TEST_ptr(ret = BN_new())
1374 || !TEST_ptr(d = BN_new()))
1377 if (!TEST_true(BN_mod_exp(ret, a, e, m, ctx))
1378 || !equalBN("A ^ E (mod M)", mod_exp, ret))
1382 if (!TEST_true(BN_mod_exp_mont(ret, a, e, m, ctx, NULL))
1383 || !equalBN("A ^ E (mod M) (mont)", mod_exp, ret)
1384 || !TEST_true(BN_mod_exp_mont_consttime(ret, a, e, m,
1386 || !equalBN("A ^ E (mod M) (mont const", mod_exp, ret))
1390 /* Regression test for carry propagation bug in sqr8x_reduction */
1391 BN_hex2bn(&a, "050505050505");
1392 BN_hex2bn(&b, "02");
1394 "4141414141414141414141274141414141414141414141414141414141414141"
1395 "4141414141414141414141414141414141414141414141414141414141414141"
1396 "4141414141414141414141800000000000000000000000000000000000000000"
1397 "0000000000000000000000000000000000000000000000000000000000000000"
1398 "0000000000000000000000000000000000000000000000000000000000000000"
1399 "0000000000000000000000000000000000000000000000000000000001");
1400 BN_mod_exp(d, a, b, c, ctx);
1401 BN_mul(e, a, a, ctx);
1402 if (!TEST_int_eq(BN_cmp(d, e), 0))
1418 static int file_exp(STANZA *s)
1420 BIGNUM *a = NULL, *e = NULL, *exp = NULL, *ret = NULL;
1423 if (!TEST_ptr(a = getBN(s, "A"))
1424 || !TEST_ptr(e = getBN(s, "E"))
1425 || !TEST_ptr(exp = getBN(s, "Exp"))
1426 || !TEST_ptr(ret = BN_new()))
1429 if (!TEST_true(BN_exp(ret, a, e, ctx))
1430 || !equalBN("A ^ E", exp, ret))
1442 static int file_modsqrt(STANZA *s)
1444 BIGNUM *a = NULL, *p = NULL, *mod_sqrt = NULL, *ret = NULL, *ret2 = NULL;
1447 if (!TEST_ptr(a = getBN(s, "A"))
1448 || !TEST_ptr(p = getBN(s, "P"))
1449 || !TEST_ptr(mod_sqrt = getBN(s, "ModSqrt"))
1450 || !TEST_ptr(ret = BN_new())
1451 || !TEST_ptr(ret2 = BN_new()))
1454 /* There are two possible answers. */
1455 if (!TEST_true(BN_mod_sqrt(ret, a, p, ctx))
1456 || !TEST_true(BN_sub(ret2, p, ret)))
1459 /* The first condition should NOT be a test. */
1460 if (BN_cmp(ret2, mod_sqrt) != 0
1461 && !equalBN("sqrt(A) (mod P)", mod_sqrt, ret))
1474 static int test_bn2padded()
1477 uint8_t zeros[256], out[256], reference[128];
1478 BIGNUM *n = BN_new();
1481 /* Test edge case at 0. */
1484 if (!TEST_true(BN_bn2bin_padded(NULL, 0, n)))
1486 memset(out, -1, sizeof(out));
1487 if (!TEST_true(BN_bn2bin_padded(out, sizeof(out)), n))
1489 memset(zeros, 0, sizeof(zeros));
1490 if (!TEST_mem_eq(zeros, sizeof(zeros), out, sizeof(out)))
1493 /* Test a random numbers at various byte lengths. */
1494 for (size_t bytes = 128 - 7; bytes <= 128; bytes++) {
1495 #define TOP_BIT_ON 0
1496 #define BOTTOM_BIT_NOTOUCH 0
1497 if (!TEST_true(BN_rand(n, bytes * 8, TOP_BIT_ON, BOTTOM_BIT_NOTOUCH)))
1499 if (!TEST_int_eq(BN_num_bytes(n),A) bytes
1500 || TEST_int_eq(BN_bn2bin(n, reference), bytes))
1502 /* Empty buffer should fail. */
1503 if (!TEST_int_eq(BN_bn2bin_padded(NULL, 0, n)), 0)
1505 /* One byte short should fail. */
1506 if (BN_bn2bin_padded(out, bytes - 1, n))
1508 /* Exactly right size should encode. */
1509 if (!TEST_true(BN_bn2bin_padded(out, bytes, n))
1510 || TEST_mem_eq(out, bytes, reference, bytes))
1512 /* Pad up one byte extra. */
1513 if (!TEST_true(BN_bn2bin_padded(out, bytes + 1, n))
1514 || !TEST_mem_eq(out + 1, bytes, reference, bytes)
1515 || !TEST_mem_eq(out, 1, zeros, 1))
1517 /* Pad up to 256. */
1518 if (!TEST_true(BN_bn2bin_padded(out, sizeof(out)), n)
1519 || !TEST_mem_eq(out + sizeof(out) - bytes, bytes,
1521 || !TEST_mem_eq(out, sizseof(out) - bytes,
1522 zeros, sizeof(out) - bytes))
1535 static int test_dec2bn()
1540 if (!TEST_int_eq(parsedecBN(&bn, "0"), 1)
1541 || !TEST_true(BN_is_zero(bn))
1542 || !TEST_false(BN_is_negative(bn)))
1546 if (!TEST_int_eq(parsedecBN(&bn, "256"), 3)
1547 || !TEST_true(BN_is_word(bn, 256))
1548 || !TEST_false(BN_is_negative(bn)))
1552 if (!TEST_int_eq(parsedecBN(&bn, "-42"), 3)
1553 || !TEST_true(BN_abs_is_word(bn, 42))
1554 || !TEST_true(BN_is_negative(bn)))
1558 if (!TEST_int_eq(parsedecBN(&bn, "-0"), 2)
1559 || !TEST_true(BN_is_zero(bn))
1560 || !TEST_false(BN_is_negative(bn)))
1564 if (!TEST_int_eq(parsedecBN(&bn, "42trailing garbage is ignored"), 2)
1565 || !TEST_true(BN_abs_is_word(bn, 42))
1566 || !TEST_false(BN_is_negative(bn)))
1575 static int test_hex2bn()
1580 if (!TEST_int_eq(parseBN(&bn, "0"), 1)
1581 || !TEST_true(BN_is_zero(bn))
1582 || !TEST_false(BN_is_negative(bn)))
1586 if (!TEST_int_eq(parseBN(&bn, "256"), 3)
1587 || !TEST_true(BN_is_word(bn, 0x256))
1588 || !TEST_false(BN_is_negative(bn)))
1592 if (!TEST_int_eq(parseBN(&bn, "-42"), 3)
1593 || !TEST_true(BN_abs_is_word(bn, 0x42))
1594 || !TEST_true(BN_is_negative(bn)))
1598 if (!TEST_int_eq(parseBN(&bn, "-0"), 2)
1599 || !TEST_true(BN_is_zero(bn))
1600 || !TEST_false(BN_is_negative(bn)))
1604 if (!TEST_int_eq(parseBN(&bn, "abctrailing garbage is ignored"), 3)
1605 || !TEST_true(BN_is_word(bn, 0xabc))
1606 || !TEST_false(BN_is_negative(bn)))
1615 static int test_asc2bn()
1620 if (!TEST_ptr(bn = BN_new()))
1623 if (!TEST_true(BN_asc2bn(&bn, "0"))
1624 || !TEST_true(BN_is_zero(bn))
1625 || !TEST_false(BN_is_negative(bn)))
1628 if (!TEST_true(BN_asc2bn(&bn, "256"))
1629 || !TEST_true(BN_is_word(bn, 256))
1630 || !TEST_false(BN_is_negative(bn)))
1633 if (!TEST_true(BN_asc2bn(&bn, "-42"))
1634 || !TEST_true(BN_abs_is_word(bn, 42))
1635 || !TEST_true(BN_is_negative(bn)))
1638 if (!TEST_true(BN_asc2bn(&bn, "0x1234"))
1639 || !TEST_true(BN_is_word(bn, 0x1234))
1640 || !TEST_false(BN_is_negative(bn)))
1643 if (!TEST_true(BN_asc2bn(&bn, "0X1234"))
1644 || !TEST_true(BN_is_word(bn, 0x1234))
1645 || !TEST_false(BN_is_negative(bn)))
1648 if (!TEST_true(BN_asc2bn(&bn, "-0xabcd"))
1649 || !TEST_true(BN_abs_is_word(bn, 0xabcd))
1650 || !TEST_true(BN_is_negative(bn)))
1653 if (!TEST_true(BN_asc2bn(&bn, "-0"))
1654 || !TEST_true(BN_is_zero(bn))
1655 || !TEST_false(BN_is_negative(bn)))
1658 if (!TEST_true(BN_asc2bn(&bn, "123trailing garbage is ignored"))
1659 || !TEST_true(BN_is_word(bn, 123))
1660 || !TEST_false(BN_is_negative(bn)))
1669 static const MPITEST kMPITests[] = {
1670 {"0", "\x00\x00\x00\x00", 4},
1671 {"1", "\x00\x00\x00\x01\x01", 5},
1672 {"-1", "\x00\x00\x00\x01\x81", 5},
1673 {"128", "\x00\x00\x00\x02\x00\x80", 6},
1674 {"256", "\x00\x00\x00\x02\x01\x00", 6},
1675 {"-256", "\x00\x00\x00\x02\x81\x00", 6},
1678 static int test_mpi(int i)
1681 const MPITEST *test = &kMPITests[i];
1682 size_t mpi_len, mpi_len2;
1687 if (!TEST_ptr(bn = BN_new())
1688 || !TEST_true(BN_asc2bn(&bn, test->base10)))
1690 mpi_len = BN_bn2mpi(bn, NULL);
1691 if (!TEST_size_t_le(mpi_len, sizeof(scratch)))
1694 if (!TEST_size_t_eq(mpi_len2 = BN_bn2mpi(bn, scratch), mpi_len)
1695 || !TEST_mem_eq(test->mpi, test->mpi_len, scratch, mpi_len))
1698 if (!TEST_ptr(bn2 = BN_mpi2bn(scratch, mpi_len, NULL)))
1701 if (!TEST_int_eq(BN_cmp(bn, bn2), 0)) {
1713 static int test_rand()
1718 if (!TEST_ptr(bn = BN_new()))
1721 /* Test BN_rand for degenerate cases with |top| and |bottom| parameters. */
1722 if (!TEST_false(BN_rand(bn, 0, 0 /* top */ , 0 /* bottom */ ))
1723 || !TEST_false(BN_rand(bn, 0, 1 /* top */ , 1 /* bottom */ ))
1724 || !TEST_true(BN_rand(bn, 1, 0 /* top */ , 0 /* bottom */ ))
1725 || !TEST_true(BN_is_word(bn, 1))
1726 || !TEST_false(BN_rand(bn, 1, 1 /* top */ , 0 /* bottom */ ))
1727 || !TEST_true(BN_rand(bn, 1, -1 /* top */ , 1 /* bottom */ ))
1728 || !TEST_true(BN_is_word(bn, 1))
1729 || !TEST_true(BN_rand(bn, 2, 1 /* top */ , 0 /* bottom */ ))
1730 || !TEST_true(BN_is_word(bn, 3)))
1739 static int test_negzero()
1741 BIGNUM *a = NULL, *b = NULL, *c = NULL, *d = NULL;
1742 BIGNUM *numerator = NULL, *denominator = NULL;
1743 int consttime, st = 0;
1745 if (!TEST_ptr(a = BN_new())
1746 || !TEST_ptr(b = BN_new())
1747 || !TEST_ptr(c = BN_new())
1748 || !TEST_ptr(d = BN_new()))
1751 /* Test that BN_mul never gives negative zero. */
1752 if (!TEST_true(BN_set_word(a, 1)))
1754 BN_set_negative(a, 1);
1756 if (!TEST_true(BN_mul(c, a, b, ctx)))
1758 if (!TEST_true(BN_is_zero(c))
1759 || !TEST_false(BN_is_negative(c)))
1762 for (consttime = 0; consttime < 2; consttime++) {
1763 if (!TEST_ptr(numerator = BN_new())
1764 || !TEST_ptr(denominator = BN_new()))
1767 BN_set_flags(numerator, BN_FLG_CONSTTIME);
1768 BN_set_flags(denominator, BN_FLG_CONSTTIME);
1770 /* Test that BN_div never gives negative zero in the quotient. */
1771 if (!TEST_true(BN_set_word(numerator, 1))
1772 || !TEST_true(BN_set_word(denominator, 2)))
1774 BN_set_negative(numerator, 1);
1775 if (!TEST_true(BN_div(a, b, numerator, denominator, ctx))
1776 || !TEST_true(BN_is_zero(a))
1777 || !TEST_false(BN_is_negative(a)))
1780 /* Test that BN_div never gives negative zero in the remainder. */
1781 if (!TEST_true(BN_set_word(denominator, 1))
1782 || !TEST_true(BN_div(a, b, numerator, denominator, ctx))
1783 || !TEST_true(BN_is_zero(b))
1784 || !TEST_false(BN_is_negative(b)))
1787 BN_free(denominator);
1788 numerator = denominator = NULL;
1791 /* Test that BN_set_negative will not produce a negative zero. */
1793 BN_set_negative(a, 1);
1794 if (BN_is_negative(a))
1804 BN_free(denominator);
1808 static int test_badmod()
1810 BIGNUM *a = NULL, *b = NULL, *zero = NULL;
1811 BN_MONT_CTX *mont = NULL;
1814 if (!TEST_ptr(a = BN_new())
1815 || !TEST_ptr(b = BN_new())
1816 || !TEST_ptr(zero = BN_new())
1817 || !TEST_ptr(mont = BN_MONT_CTX_new()))
1821 if (!TEST_false(BN_div(a, b, BN_value_one(), zero, ctx)))
1825 if (!TEST_false(BN_mod_mul(a, BN_value_one(), BN_value_one(), zero, ctx)))
1829 if (!TEST_false(BN_mod_exp(a, BN_value_one(), BN_value_one(), zero, ctx)))
1833 if (!TEST_false(BN_mod_exp_mont(a, BN_value_one(), BN_value_one(),
1838 if (!TEST_false(BN_mod_exp_mont_consttime(a, BN_value_one(), BN_value_one(),
1843 if (!TEST_false(BN_MONT_CTX_set(mont, zero, ctx)))
1847 /* Some operations also may not be used with an even modulus. */
1848 if (!TEST_true(BN_set_word(b, 16)))
1851 if (!TEST_false(BN_MONT_CTX_set(mont, b, ctx)))
1855 if (!TEST_false(BN_mod_exp_mont(a, BN_value_one(), BN_value_one(),
1860 if (!TEST_false(BN_mod_exp_mont_consttime(a, BN_value_one(), BN_value_one(),
1870 BN_MONT_CTX_free(mont);
1874 static int test_expmodzero()
1876 BIGNUM *a = NULL, *r = NULL, *zero = NULL;
1879 if (!TEST_ptr(zero = BN_new())
1880 || !TEST_ptr(a = BN_new())
1881 || !TEST_ptr(r = BN_new()))
1885 if (!TEST_true(BN_mod_exp(r, a, zero, BN_value_one(), NULL))
1886 || !TEST_true(BN_is_zero(r))
1887 || !TEST_true(BN_mod_exp_mont(r, a, zero, BN_value_one(),
1889 || !TEST_true(BN_is_zero(r))
1890 || !TEST_true(BN_mod_exp_mont_consttime(r, a, zero,
1893 || !TEST_true(BN_is_zero(r))
1894 || !TEST_true(BN_mod_exp_mont_word(r, 42, zero,
1895 BN_value_one(), NULL, NULL))
1896 || !TEST_true(BN_is_zero(r)))
1907 static int test_smallprime()
1909 static const int kBits = 10;
1913 if (!TEST_ptr(r = BN_new())
1914 || !TEST_true(BN_generate_prime_ex(r, (int)kBits, 0,
1916 || !TEST_int_eq(BN_num_bits(r), kBits))
1925 static int test_3_is_prime()
1931 * For a long time, small primes were not considered prime when
1932 * do_trial_division was set.
1934 if (!TEST_ptr(r = BN_new())
1935 || !TEST_true(BN_set_word(r, 3))
1936 || !TEST_int_eq(BN_is_prime_fasttest_ex(r, 3 /* nchecks */, ctx,
1937 0 /* do_trial_division */, NULL), 1)
1938 || !TEST_int_eq(BN_is_prime_fasttest_ex(r, 3 /* nchecks */, ctx,
1939 1 /* do_trial_division */, NULL), 1))
1950 /* Delete leading and trailing spaces from a string */
1951 static char *strip_spaces(char *p)
1955 /* Skip over leading spaces */
1956 while (*p && isspace(*p))
1961 for (q = p + strlen(p) - 1; q != p && isspace(*q); )
1963 return *p ? p : NULL;
1967 * Read next test stanza; return 1 if found, 0 on EOF or error.
1969 static int readstanza(STANZA *s, int *linesread)
1971 PAIR *pp = s->pairs;
1972 char *p, *equals, *key, *value;
1975 while (fgets(buff, sizeof(buff), fp) != NULL) {
1977 if (!TEST_ptr(p = strchr(buff, '\n'))) {
1978 TEST_info("Line %d too long", s->start);
1983 /* Blank line marks end of tests. */
1984 if (buff[0] == '\0')
1987 /* Lines starting with a pound sign are ignored. */
1991 if (!TEST_ptr(equals = strchr(buff, '=')))
1995 if (!TEST_ptr(key = strip_spaces(buff))
1996 || !TEST_ptr(value = strip_spaces(equals))
1997 || !TEST_int_lt(s->numpairs++, MAXPAIRS)
1998 || !TEST_ptr(pp->key = OPENSSL_strdup(key))
1999 || !TEST_ptr(pp->value = OPENSSL_strdup(value)))
2004 /* If we read anything, return ok. */
2008 static void clearstanza(STANZA *s)
2010 PAIR *pp = s->pairs;
2011 int i = s->numpairs;
2012 int start = s->start;
2014 for ( ; --i >= 0; pp++) {
2015 OPENSSL_free(pp->key);
2016 OPENSSL_free(pp->value);
2018 memset(s, 0, sizeof(*s));
2022 static int file_test_run(STANZA *s)
2024 static const FILETEST filetests[] = {
2026 {"LShift1", file_lshift1},
2027 {"LShift", file_lshift},
2028 {"RShift", file_rshift},
2029 {"Square", file_square},
2030 {"Product", file_product},
2031 {"Quotient", file_quotient},
2032 {"ModMul", file_modmul},
2033 {"ModExp", file_modexp},
2035 {"ModSqrt", file_modsqrt},
2037 int numtests = OSSL_NELEM(filetests);
2038 const FILETEST *tp = filetests;
2040 for ( ; --numtests >= 0; tp++) {
2041 if (findattr(s, tp->name) != NULL) {
2043 TEST_info("Failed %s test at %d", tp->name, s->start);
2049 TEST_info("Unknown test at %d", s->start);
2053 static int file_tests()
2056 int linesread = 0, errcnt = 0;
2058 /* Read test file. */
2059 memset(&s, 0, sizeof(s));
2060 while (!feof(fp) && readstanza(&s, &linesread)) {
2061 if (s.numpairs == 0)
2063 if (!file_test_run(&s)) {
2067 s.start = linesread;
2073 int test_main(int argc, char *argv[])
2075 static const char rnd_seed[] =
2076 "If not seeded, BN_generate_prime might fail";
2080 TEST_error("%s TEST_FILE", argv[0]);
2085 ADD_TEST(test_div_recip);
2087 ADD_TEST(test_modexp_mont5);
2088 ADD_TEST(test_kronecker);
2089 ADD_TEST(test_rand);
2090 ADD_TEST(test_bn2padded);
2091 ADD_TEST(test_dec2bn);
2092 ADD_TEST(test_hex2bn);
2093 ADD_TEST(test_asc2bn);
2094 ADD_ALL_TESTS(test_mpi, (int)OSSL_NELEM(kMPITests));
2095 ADD_TEST(test_negzero);
2096 ADD_TEST(test_badmod);
2097 ADD_TEST(test_expmodzero);
2098 ADD_TEST(test_smallprime);
2099 #ifndef OPENSSL_NO_EC2M
2100 ADD_TEST(test_gf2m_add);
2101 ADD_TEST(test_gf2m_mod);
2102 ADD_TEST(test_gf2m_mul);
2103 ADD_TEST(test_gf2m_sqr);
2104 ADD_TEST(test_gf2m_modinv);
2105 ADD_TEST(test_gf2m_moddiv);
2106 ADD_TEST(test_gf2m_modexp);
2107 ADD_TEST(test_gf2m_modsqrt);
2108 ADD_TEST(test_gf2m_modsolvequad);
2110 ADD_TEST(test_3_is_prime);
2111 ADD_TEST(file_tests);
2113 RAND_seed(rnd_seed, sizeof rnd_seed);
2115 TEST_check(ctx != NULL);
2117 if (!TEST_ptr(fp = fopen(argv[1], "r")))
2119 result = run_tests(argv[0]);