/*

* Copyright 1995-2021 The OpenSSL Project Authors. All Rights Reserved.

*

* Licensed under the Apache License 2.0 (the "License"). You may not use

* this file except in compliance with the License. You can obtain a copy

* in the file LICENSE in the source distribution or at

* https://www.openssl.org/source/license.html

*/

#include <assert.h>

#include <errno.h>

#include <stdio.h>

#include <string.h>

#ifdef __TANDEM

# include <strings.h> /* strcasecmp */

#endif

#include <ctype.h>

#include <openssl/bn.h>

#include <openssl/crypto.h>

#include <openssl/err.h>

#include <openssl/rand.h>

#include "internal/nelem.h"

#include "internal/numbers.h"

#include "testutil.h"

#ifdef OPENSSL_SYS_WINDOWS

# define strcasecmp _stricmp

#endif

/*

* Things in boring, not in openssl.

*/

#define HAVE_BN_SQRT 0

typedef struct filetest_st {

const char *name;

int (*func)(STANZA *s);

} FILETEST;

typedef struct mpitest_st {

const char *base10;

const char *mpi;

size_t mpi_len;

} MPITEST;

static const int NUM0 = 100; /* number of tests */

static const int NUM1 = 50; /* additional tests for some functions */

static BN_CTX *ctx;

/*

* Polynomial coefficients used in GFM tests.

*/

#ifndef OPENSSL_NO_EC2M

static int p0[] = { 163, 7, 6, 3, 0, -1 };

static int p1[] = { 193, 15, 0, -1 };

#endif

/*

* Look for |key| in the stanza and return it or NULL if not found.

*/

static const char *findattr(STANZA *s, const char *key)

{

int i = s->numpairs;

PAIR *pp = s->pairs;

for ( ; --i >= 0; pp++)

if (strcasecmp(pp->key, key) == 0)

return pp->value;

return NULL;

}

/*

* Parse BIGNUM from sparse hex-strings, return |BN_hex2bn| result.

*/

static int parse_bigBN(BIGNUM **out, const char *bn_strings[])

{

char *bigstring = glue_strings(bn_strings, NULL);

int ret = BN_hex2bn(out, bigstring);

OPENSSL_free(bigstring);

return ret;

}

/*

* Parse BIGNUM, return number of bytes parsed.

*/

static int parseBN(BIGNUM **out, const char *in)

{

*out = NULL;

return BN_hex2bn(out, in);

}

static int parsedecBN(BIGNUM **out, const char *in)

{

*out = NULL;

return BN_dec2bn(out, in);

}

static BIGNUM *getBN(STANZA *s, const char *attribute)

{

const char *hex;

BIGNUM *ret = NULL;

if ((hex = findattr(s, attribute)) == NULL) {

TEST_error("%s:%d: Can't find %s", s->test_file, s->start, attribute);

return NULL;

}

if (parseBN(&ret, hex) != (int)strlen(hex)) {

TEST_error("Could not decode '%s'", hex);

return NULL;

}

return ret;

}

static int getint(STANZA *s, int *out, const char *attribute)

{

BIGNUM *ret;

BN_ULONG word;

int st = 0;

if (!TEST_ptr(ret = getBN(s, attribute))

|| !TEST_ulong_le(word = BN_get_word(ret), INT_MAX))

goto err;

*out = (int)word;

st = 1;

err:

BN_free(ret);

return st;

}

static int equalBN(const char *op, const BIGNUM *expected, const BIGNUM *actual)

{

if (BN_cmp(expected, actual) == 0)

return 1;

TEST_error("unexpected %s value", op);

TEST_BN_eq(expected, actual);

return 0;

}

/*

* Return a "random" flag for if a BN should be negated.

*/

static int rand_neg(void)

{

static unsigned int neg = 0;

static int sign[8] = { 0, 0, 0, 1, 1, 0, 1, 1 };

return sign[(neg++) % 8];

}

static int test_swap(void)

{

BIGNUM *a = NULL, *b = NULL, *c = NULL, *d = NULL;

int top, cond, st = 0;

if (!TEST_ptr(a = BN_new())

|| !TEST_ptr(b = BN_new())

|| !TEST_ptr(c = BN_new())

|| !TEST_ptr(d = BN_new()))

goto err;

if (!(TEST_true(BN_bntest_rand(a, 1024, 1, 0))

&& TEST_true(BN_bntest_rand(b, 1024, 1, 0))

&& TEST_ptr(BN_copy(c, a))

&& TEST_ptr(BN_copy(d, b))))

goto err;

top = BN_num_bits(a) / BN_BITS2;

/* regular swap */

BN_swap(a, b);

if (!equalBN("swap", a, d)

|| !equalBN("swap", b, c))

goto err;

/* conditional swap: true */

cond = 1;

BN_consttime_swap(cond, a, b, top);

if (!equalBN("cswap true", a, c)

|| !equalBN("cswap true", b, d))

goto err;

/* conditional swap: false */

cond = 0;

BN_consttime_swap(cond, a, b, top);

if (!equalBN("cswap false", a, c)

|| !equalBN("cswap false", b, d))

goto err;

/* same tests but checking flag swap */

BN_set_flags(a, BN_FLG_CONSTTIME);

BN_swap(a, b);

if (!equalBN("swap, flags", a, d)

|| !equalBN("swap, flags", b, c)

|| !TEST_true(BN_get_flags(b, BN_FLG_CONSTTIME))

|| !TEST_false(BN_get_flags(a, BN_FLG_CONSTTIME)))

goto err;

cond = 1;

BN_consttime_swap(cond, a, b, top);

if (!equalBN("cswap true, flags", a, c)

|| !equalBN("cswap true, flags", b, d)

|| !TEST_true(BN_get_flags(a, BN_FLG_CONSTTIME))

|| !TEST_false(BN_get_flags(b, BN_FLG_CONSTTIME)))

goto err;

cond = 0;

BN_consttime_swap(cond, a, b, top);

if (!equalBN("cswap false, flags", a, c)

|| !equalBN("cswap false, flags", b, d)

|| !TEST_true(BN_get_flags(a, BN_FLG_CONSTTIME))

|| !TEST_false(BN_get_flags(b, BN_FLG_CONSTTIME)))

goto err;

st = 1;

err:

BN_free(a);

BN_free(b);

BN_free(c);

BN_free(d);

return st;

}

static int test_sub(void)

{

BIGNUM *a = NULL, *b = NULL, *c = NULL;

int i, st = 0;

if (!TEST_ptr(a = BN_new())

|| !TEST_ptr(b = BN_new())

|| !TEST_ptr(c = BN_new()))

goto err;

for (i = 0; i < NUM0 + NUM1; i++) {

if (i < NUM1) {

if (!(TEST_true(BN_bntest_rand(a, 512, 0, 0)))

&& TEST_ptr(BN_copy(b, a))

&& TEST_int_ne(BN_set_bit(a, i), 0)

&& TEST_true(BN_add_word(b, i)))

goto err;

} else {

if (!TEST_true(BN_bntest_rand(b, 400 + i - NUM1, 0, 0)))

goto err;

BN_set_negative(a, rand_neg());

BN_set_negative(b, rand_neg());

}

if (!(TEST_true(BN_sub(c, a, b))

&& TEST_true(BN_add(c, c, b))

&& TEST_true(BN_sub(c, c, a))

&& TEST_BN_eq_zero(c)))

goto err;

}

st = 1;

err:

BN_free(a);

BN_free(b);

BN_free(c);

return st;

}

static int test_div_recip(void)

{

BIGNUM *a = NULL, *b = NULL, *c = NULL, *d = NULL, *e = NULL;

BN_RECP_CTX *recp = NULL;

int st = 0, i;

if (!TEST_ptr(a = BN_new())

|| !TEST_ptr(b = BN_new())

|| !TEST_ptr(c = BN_new())

|| !TEST_ptr(d = BN_new())

|| !TEST_ptr(e = BN_new())

|| !TEST_ptr(recp = BN_RECP_CTX_new()))

goto err;

for (i = 0; i < NUM0 + NUM1; i++) {

if (i < NUM1) {

if (!(TEST_true(BN_bntest_rand(a, 400, 0, 0))

&& TEST_ptr(BN_copy(b, a))

&& TEST_true(BN_lshift(a, a, i))

&& TEST_true(BN_add_word(a, i))))

goto err;

} else {

if (!(TEST_true(BN_bntest_rand(b, 50 + 3 * (i - NUM1), 0, 0))))

goto err;

}

BN_set_negative(a, rand_neg());

BN_set_negative(b, rand_neg());

if (!(TEST_true(BN_RECP_CTX_set(recp, b, ctx))

&& TEST_true(BN_div_recp(d, c, a, recp, ctx))

&& TEST_true(BN_mul(e, d, b, ctx))

&& TEST_true(BN_add(d, e, c))

&& TEST_true(BN_sub(d, d, a))

&& TEST_BN_eq_zero(d)))

goto err;

}

st = 1;

err:

BN_free(a);

BN_free(b);

BN_free(c);

BN_free(d);

BN_free(e);

BN_RECP_CTX_free(recp);

return st;

}

static struct {

int n, divisor, result, remainder;

} signed_mod_tests[] = {

{ 10, 3, 3, 1 },

{ -10, 3, -3, -1 },

{ 10, -3, -3, 1 },

{ -10, -3, 3, -1 },

};

static BIGNUM *set_signed_bn(int value)

{

BIGNUM *bn = BN_new();

if (bn == NULL)

return NULL;

if (!BN_set_word(bn, value < 0 ? -value : value)) {

BN_free(bn);

return NULL;

}

BN_set_negative(bn, value < 0);

return bn;

}

static int test_signed_mod_replace_ab(int n)

{

BIGNUM *a = NULL, *b = NULL, *c = NULL, *d = NULL;

int st = 0;

if (!TEST_ptr(a = set_signed_bn(signed_mod_tests[n].n))

|| !TEST_ptr(b = set_signed_bn(signed_mod_tests[n].divisor))

|| !TEST_ptr(c = set_signed_bn(signed_mod_tests[n].result))

|| !TEST_ptr(d = set_signed_bn(signed_mod_tests[n].remainder)))

goto err;

if (TEST_true(BN_div(a, b, a, b, ctx))

&& TEST_BN_eq(a, c)

&& TEST_BN_eq(b, d))

st = 1;

err:

BN_free(a);

BN_free(b);

BN_free(c);

BN_free(d);

return st;

}

static int test_signed_mod_replace_ba(int n)

{

BIGNUM *a = NULL, *b = NULL, *c = NULL, *d = NULL;

int st = 0;

if (!TEST_ptr(a = set_signed_bn(signed_mod_tests[n].n))

|| !TEST_ptr(b = set_signed_bn(signed_mod_tests[n].divisor))

|| !TEST_ptr(c = set_signed_bn(signed_mod_tests[n].result))

|| !TEST_ptr(d = set_signed_bn(signed_mod_tests[n].remainder)))

goto err;

if (TEST_true(BN_div(b, a, a, b, ctx))

&& TEST_BN_eq(b, c)

&& TEST_BN_eq(a, d))

st = 1;

err:

BN_free(a);

BN_free(b);

BN_free(c);

BN_free(d);

return st;

}

static int test_mod(void)

{

BIGNUM *a = NULL, *b = NULL, *c = NULL, *d = NULL, *e = NULL;

int st = 0, i;

if (!TEST_ptr(a = BN_new())

|| !TEST_ptr(b = BN_new())

|| !TEST_ptr(c = BN_new())

|| !TEST_ptr(d = BN_new())

|| !TEST_ptr(e = BN_new()))

goto err;

if (!(TEST_true(BN_bntest_rand(a, 1024, 0, 0))))

goto err;

for (i = 0; i < NUM0; i++) {

if (!(TEST_true(BN_bntest_rand(b, 450 + i * 10, 0, 0))))

goto err;

BN_set_negative(a, rand_neg());

BN_set_negative(b, rand_neg());

if (!(TEST_true(BN_mod(c, a, b, ctx))

&& TEST_true(BN_div(d, e, a, b, ctx))

&& TEST_BN_eq(e, c)

&& TEST_true(BN_mul(c, d, b, ctx))

&& TEST_true(BN_add(d, c, e))

&& TEST_BN_eq(d, a)))

goto err;

}

st = 1;

err:

BN_free(a);

BN_free(b);

BN_free(c);

BN_free(d);

BN_free(e);

return st;

}

static const char *bn1strings[] = {

"FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",

"FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",

"FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",

"FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",

"FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",

"FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",

"FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",

"FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00000000000000FFFFFFFF00",

"0000000000000000000000000000000000000000000000000000000000000000",

"0000000000000000000000000000000000000000000000000000000000000000",

"0000000000000000000000000000000000000000000000000000000000000000",

"0000000000000000000000000000000000000000000000000000000000000000",

"0000000000000000000000000000000000000000000000000000000000000000",

"0000000000000000000000000000000000000000000000000000000000000000",

"0000000000000000000000000000000000000000000000000000000000000000",

"00000000000000000000000000000000000000000000000000FFFFFFFFFFFFFF",

NULL

};

static const char *bn2strings[] = {

"FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",

"FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",

"FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",

"FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",

"FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",

"FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",

"FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",

"FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00000000000000FFFFFFFF0000000000",

"0000000000000000000000000000000000000000000000000000000000000000",

"0000000000000000000000000000000000000000000000000000000000000000",

"0000000000000000000000000000000000000000000000000000000000000000",

"0000000000000000000000000000000000000000000000000000000000000000",

"0000000000000000000000000000000000000000000000000000000000000000",

"0000000000000000000000000000000000000000000000000000000000000000",

"0000000000000000000000000000000000000000000000000000000000000000",

"000000000000000000000000000000000000000000FFFFFFFFFFFFFF00000000",

NULL

};

/*

* Test constant-time modular exponentiation with 1024-bit inputs, which on

* x86_64 cause a different code branch to be taken.

*/

static int test_modexp_mont5(void)

{

BIGNUM *a = NULL, *p = NULL, *m = NULL, *d = NULL, *e = NULL;

BIGNUM *b = NULL, *n = NULL, *c = NULL;

BN_MONT_CTX *mont = NULL;

int st = 0;

if (!TEST_ptr(a = BN_new())

|| !TEST_ptr(p = BN_new())

|| !TEST_ptr(m = BN_new())

|| !TEST_ptr(d = BN_new())

|| !TEST_ptr(e = BN_new())

|| !TEST_ptr(b = BN_new())

|| !TEST_ptr(n = BN_new())

|| !TEST_ptr(c = BN_new())

|| !TEST_ptr(mont = BN_MONT_CTX_new()))

goto err;

/* must be odd for montgomery */

if (!(TEST_true(BN_bntest_rand(m, 1024, 0, 1))

/* Zero exponent */

&& TEST_true(BN_bntest_rand(a, 1024, 0, 0))))

goto err;

BN_zero(p);

if (!TEST_true(BN_mod_exp_mont_consttime(d, a, p, m, ctx, NULL)))

goto err;

if (!TEST_BN_eq_one(d))

goto err;

/* Regression test for carry bug in mulx4x_mont */

if (!(TEST_true(BN_hex2bn(&a,

"7878787878787878787878787878787878787878787878787878787878787878"

"7878787878787878787878787878787878787878787878787878787878787878"

"7878787878787878787878787878787878787878787878787878787878787878"

"7878787878787878787878787878787878787878787878787878787878787878"))

&& TEST_true(BN_hex2bn(&b,

"095D72C08C097BA488C5E439C655A192EAFB6380073D8C2664668EDDB4060744"

"E16E57FB4EDB9AE10A0CEFCDC28A894F689A128379DB279D48A2E20849D68593"

"9B7803BCF46CEBF5C533FB0DD35B080593DE5472E3FE5DB951B8BFF9B4CB8F03"

"9CC638A5EE8CDD703719F8000E6A9F63BEED5F2FCD52FF293EA05A251BB4AB81"))

&& TEST_true(BN_hex2bn(&n,

"D78AF684E71DB0C39CFF4E64FB9DB567132CB9C50CC98009FEB820B26F2DED9B"

"91B9B5E2B83AE0AE4EB4E0523CA726BFBE969B89FD754F674CE99118C3F2D1C5"

"D81FDC7C54E02B60262B241D53C040E99E45826ECA37A804668E690E1AFC1CA4"

"2C9A15D84D4954425F0B7642FC0BD9D7B24E2618D2DCC9B729D944BADACFDDAF"))))

goto err;

if (!(TEST_true(BN_MONT_CTX_set(mont, n, ctx))

&& TEST_true(BN_mod_mul_montgomery(c, a, b, mont, ctx))

&& TEST_true(BN_mod_mul_montgomery(d, b, a, mont, ctx))

&& TEST_BN_eq(c, d)))

goto err;

/* Regression test for carry bug in sqr[x]8x_mont */

if (!(TEST_true(parse_bigBN(&n, bn1strings))

&& TEST_true(parse_bigBN(&a, bn2strings))))

goto err;

BN_free(b);

if (!(TEST_ptr(b = BN_dup(a))

&& TEST_true(BN_MONT_CTX_set(mont, n, ctx))

&& TEST_true(BN_mod_mul_montgomery(c, a, a, mont, ctx))

&& TEST_true(BN_mod_mul_montgomery(d, a, b, mont, ctx))

&& TEST_BN_eq(c, d)))

goto err;

/* Regression test for carry bug in bn_sqrx8x_internal */

{

static const char *ahex[] = {

"FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",

"FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",

"FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",

"FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",

"FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF8FFEADBCFC4DAE7FFF908E92820306B",

"9544D954000000006C0000000000000000000000000000000000000000000000",

"00000000000000000000FF030202FFFFF8FFEBDBCFC4DAE7FFF908E92820306B",

"9544D954000000006C000000FF0302030000000000FFFFFFFFFFFFFFFFFFFFFF",

"FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF01FC00FF02FFFFFFFF",

"00FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00FCFD",

"FCFFFFFFFFFF000000000000000000FF0302030000000000FFFFFFFFFFFFFFFF",

"FF00FCFDFDFF030202FF00000000FFFFFFFFFFFFFFFFFF00FCFDFCFFFFFFFFFF",

NULL

};

static const char *nhex[] = {

"FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",

"FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",

"FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",

"FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",

"FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF8F8F8F8000000",

"00000010000000006C0000000000000000000000000000000000000000000000",

"00000000000000000000000000000000000000FFFFFFFFFFFFF8F8F8F8000000",

"00000010000000006C000000000000000000000000FFFFFFFFFFFFFFFFFFFFFF",

"FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",

"00FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",

"FFFFFFFFFFFF000000000000000000000000000000000000FFFFFFFFFFFFFFFF",

"FFFFFFFFFFFFFFFFFFFF00000000FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",

NULL

};

if (!(TEST_true(parse_bigBN(&a, ahex))

&& TEST_true(parse_bigBN(&n, nhex))))

goto err;

}

BN_free(b);

if (!(TEST_ptr(b = BN_dup(a))

&& TEST_true(BN_MONT_CTX_set(mont, n, ctx))))

goto err;

if (!TEST_true(BN_mod_mul_montgomery(c, a, a, mont, ctx))

|| !TEST_true(BN_mod_mul_montgomery(d, a, b, mont, ctx))

|| !TEST_BN_eq(c, d))

goto err;

/* Regression test for bug in BN_from_montgomery_word */

if (!(TEST_true(BN_hex2bn(&a,

"FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"

"FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"

"FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"))

&& TEST_true(BN_hex2bn(&n,

"FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"

"FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"))

&& TEST_true(BN_MONT_CTX_set(mont, n, ctx))

&& TEST_false(BN_mod_mul_montgomery(d, a, a, mont, ctx))))

goto err;

/* Regression test for bug in rsaz_1024_mul_avx2 */

if (!(TEST_true(BN_hex2bn(&a,

"FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"

"FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"

"FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"

"FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF2020202020DF"))

&& TEST_true(BN_hex2bn(&b,

"2020202020202020202020202020202020202020202020202020202020202020"

"2020202020202020202020202020202020202020202020202020202020202020"

"20202020202020FF202020202020202020202020202020202020202020202020"

"2020202020202020202020202020202020202020202020202020202020202020"))

&& TEST_true(BN_hex2bn(&n,

"FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"

"FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"

"FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"

"FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF2020202020FF"))

&& TEST_true(BN_MONT_CTX_set(mont, n, ctx))

&& TEST_true(BN_mod_exp_mont_consttime(c, a, b, n, ctx, mont))

&& TEST_true(BN_mod_exp_mont(d, a, b, n, ctx, mont))

&& TEST_BN_eq(c, d)))

goto err;

/*

* rsaz_1024_mul_avx2 expects fully-reduced inputs.

* BN_mod_exp_mont_consttime should reduce the input first.

*/

if (!(TEST_true(BN_hex2bn(&a,

"FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"

"FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"

"FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"

"FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF2020202020DF"))

&& TEST_true(BN_hex2bn(&b,

"1FA53F26F8811C58BE0357897AA5E165693230BC9DF5F01DFA6A2D59229EC69D"

"9DE6A89C36E3B6957B22D6FAAD5A3C73AE587B710DBE92E83D3A9A3339A085CB"

"B58F508CA4F837924BB52CC1698B7FDC2FD74362456A595A5B58E38E38E38E38"

"E38E38E38E38E38E38E38E38E38E38E38E38E38E38E38E38E38E38E38E38E38E"))

&& TEST_true(BN_hex2bn(&n,

"FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"

"FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"

"FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"

"FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF2020202020DF"))

&& TEST_true(BN_MONT_CTX_set(mont, n, ctx))

&& TEST_true(BN_mod_exp_mont_consttime(c, a, b, n, ctx, mont))))

goto err;

BN_zero(d);

if (!TEST_BN_eq(c, d))

goto err;

/*

* Regression test for overflow bug in bn_sqr_comba4/8 for

* mips-linux-gnu and mipsel-linux-gnu 32bit targets.

*/

{

static const char *ehex[] = {

"95564994a96c45954227b845a1e99cb939d5a1da99ee91acc962396ae999a9ee",

"38603790448f2f7694c242a875f0cad0aae658eba085f312d2febbbd128dd2b5",

"8f7d1149f03724215d704344d0d62c587ae3c5939cba4b9b5f3dc5e8e911ef9a",

"5ce1a5a749a4989d0d8368f6e1f8cdf3a362a6c97fb02047ff152b480a4ad985",

"2d45efdf0770542992afca6a0590d52930434bba96017afbc9f99e112950a8b1",

"a359473ec376f329bdae6a19f503be6d4be7393c4e43468831234e27e3838680",

"b949390d2e416a3f9759e5349ab4c253f6f29f819a6fe4cbfd27ada34903300e",

"da021f62839f5878a36f1bc3085375b00fd5fa3e68d316c0fdace87a97558465",

NULL};

static const char *phex[] = {

"f95dc0f980fbd22e90caa5a387cc4a369f3f830d50dd321c40db8c09a7e1a241",

"a536e096622d3280c0c1ba849c1f4a79bf490f60006d081e8cf69960189f0d31",

"2cd9e17073a3fba7881b21474a13b334116cb2f5dbf3189a6de3515d0840f053",

"c776d3982d391b6d04d642dda5cc6d1640174c09875addb70595658f89efb439",

"dc6fbd55f903aadd307982d3f659207f265e1ec6271b274521b7a5e28e8fd7a5",

"5df089292820477802a43cf5b6b94e999e8c9944ddebb0d0e95a60f88cb7e813",

"ba110d20e1024774107dd02949031864923b3cb8c3f7250d6d1287b0a40db6a4",

"7bd5a469518eb65aa207ddc47d8c6e5fc8e0c105be8fc1d4b57b2e27540471d5",

NULL};

static const char *mhex[] = {

"fef15d5ce4625f1bccfbba49fc8439c72bf8202af039a2259678941b60bb4a8f",

"2987e965d58fd8cf86a856674d519763d0e1211cc9f8596971050d56d9b35db3",

"785866cfbca17cfdbed6060be3629d894f924a89fdc1efc624f80d41a22f1900",

"9503fcc3824ef62ccb9208430c26f2d8ceb2c63488ec4c07437aa4c96c43dd8b",

"9289ed00a712ff66ee195dc71f5e4ead02172b63c543d69baf495f5fd63ba7bc",

"c633bd309c016e37736da92129d0b053d4ab28d21ad7d8b6fab2a8bbdc8ee647",

"d2fbcf2cf426cf892e6f5639e0252993965dfb73ccd277407014ea784aaa280c",

"b7b03972bc8b0baa72360bdb44b82415b86b2f260f877791cd33ba8f2d65229b",

NULL};

if (!TEST_true(parse_bigBN(&e, ehex))

|| !TEST_true(parse_bigBN(&p, phex))

|| !TEST_true(parse_bigBN(&m, mhex))

|| !TEST_true(BN_mod_exp_mont_consttime(d, e, p, m, ctx, NULL))

|| !TEST_true(BN_mod_exp_simple(a, e, p, m, ctx))

|| !TEST_BN_eq(a, d))

goto err;

}

/* Zero input */

if (!TEST_true(BN_bntest_rand(p, 1024, 0, 0)))

goto err;

BN_zero(a);

if (!TEST_true(BN_mod_exp_mont_consttime(d, a, p, m, ctx, NULL))

|| !TEST_BN_eq_zero(d))

goto err;

/*

* Craft an input whose Montgomery representation is 1, i.e., shorter

* than the modulus m, in order to test the const time precomputation

* scattering/gathering.

*/

if (!(TEST_true(BN_one(a))

&& TEST_true(BN_MONT_CTX_set(mont, m, ctx))))

goto err;

if (!TEST_true(BN_from_montgomery(e, a, mont, ctx))

|| !TEST_true(BN_mod_exp_mont_consttime(d, e, p, m, ctx, NULL))

|| !TEST_true(BN_mod_exp_simple(a, e, p, m, ctx))

|| !TEST_BN_eq(a, d))

goto err;

/* Finally, some regular test vectors. */

if (!(TEST_true(BN_bntest_rand(e, 1024, 0, 0))

&& TEST_true(BN_mod_exp_mont_consttime(d, e, p, m, ctx, NULL))

&& TEST_true(BN_mod_exp_simple(a, e, p, m, ctx))

&& TEST_BN_eq(a, d)))

goto err;

st = 1;

err:

BN_MONT_CTX_free(mont);

BN_free(a);

BN_free(p);

BN_free(m);

BN_free(d);

BN_free(e);

BN_free(b);

BN_free(n);

BN_free(c);

return st;

}

#ifndef OPENSSL_NO_EC2M

static int test_gf2m_add(void)

{

BIGNUM *a = NULL, *b = NULL, *c = NULL;

int i, st = 0;

if (!TEST_ptr(a = BN_new())

|| !TEST_ptr(b = BN_new())

|| !TEST_ptr(c = BN_new()))

goto err;

for (i = 0; i < NUM0; i++) {

if (!(TEST_true(BN_rand(a, 512, 0, 0))

&& TEST_ptr(BN_copy(b, BN_value_one()))))

goto err;

BN_set_negative(a, rand_neg());

BN_set_negative(b, rand_neg());

if (!(TEST_true(BN_GF2m_add(c, a, b))

/* Test that two added values have the correct parity. */

&& TEST_false((BN_is_odd(a) && BN_is_odd(c))

|| (!BN_is_odd(a) && !BN_is_odd(c)))))

goto err;

if (!(TEST_true(BN_GF2m_add(c, c, c))

/* Test that c + c = 0. */

&& TEST_BN_eq_zero(c)))

goto err;

}

st = 1;

err:

BN_free(a);

BN_free(b);

BN_free(c);

return st;

}

static int test_gf2m_mod(void)

{

BIGNUM *a = NULL, *b[2] = {NULL,NULL}, *c = NULL, *d = NULL, *e = NULL;

int i, j, st = 0;

if (!TEST_ptr(a = BN_new())

|| !TEST_ptr(b[0] = BN_new())

|| !TEST_ptr(b[1] = BN_new())

|| !TEST_ptr(c = BN_new())

|| !TEST_ptr(d = BN_new())

|| !TEST_ptr(e = BN_new()))

goto err;

if (!(TEST_true(BN_GF2m_arr2poly(p0, b[0]))

&& TEST_true(BN_GF2m_arr2poly(p1, b[1]))))

goto err;

for (i = 0; i < NUM0; i++) {

if (!TEST_true(BN_bntest_rand(a, 1024, 0, 0)))

goto err;

for (j = 0; j < 2; j++) {

if (!(TEST_true(BN_GF2m_mod(c, a, b[j]))

&& TEST_true(BN_GF2m_add(d, a, c))

&& TEST_true(BN_GF2m_mod(e, d, b[j]))

/* Test that a + (a mod p) mod p == 0. */

&& TEST_BN_eq_zero(e)))

goto err;

}

}

st = 1;

err:

BN_free(a);

BN_free(b[0]);

BN_free(b[1]);

BN_free(c);

BN_free(d);

BN_free(e);

return st;

}

static int test_gf2m_mul(void)

{

BIGNUM *a, *b[2] = {NULL, NULL}, *c = NULL, *d = NULL;

BIGNUM *e = NULL, *f = NULL, *g = NULL, *h = NULL;

int i, j, st = 0;

if (!TEST_ptr(a = BN_new())

|| !TEST_ptr(b[0] = BN_new())

|| !TEST_ptr(b[1] = BN_new())

|| !TEST_ptr(c = BN_new())

|| !TEST_ptr(d = BN_new())

|| !TEST_ptr(e = BN_new())

|| !TEST_ptr(f = BN_new())

|| !TEST_ptr(g = BN_new())

|| !TEST_ptr(h = BN_new()))

goto err;

if (!(TEST_true(BN_GF2m_arr2poly(p0, b[0]))

&& TEST_true(BN_GF2m_arr2poly(p1, b[1]))))

goto err;

for (i = 0; i < NUM0; i++) {

if (!(TEST_true(BN_bntest_rand(a, 1024, 0, 0))

&& TEST_true(BN_bntest_rand(c, 1024, 0, 0))

&& TEST_true(BN_bntest_rand(d, 1024, 0, 0))))

goto err;

for (j = 0; j < 2; j++) {

if (!(TEST_true(BN_GF2m_mod_mul(e, a, c, b[j], ctx))

&& TEST_true(BN_GF2m_add(f, a, d))

&& TEST_true(BN_GF2m_mod_mul(g, f, c, b[j], ctx))

&& TEST_true(BN_GF2m_mod_mul(h, d, c, b[j], ctx))

&& TEST_true(BN_GF2m_add(f, e, g))

&& TEST_true(BN_GF2m_add(f, f, h))

/* Test that (a+d)*c = a*c + d*c. */

&& TEST_BN_eq_zero(f)))

goto err;

}

}

st = 1;

err:

BN_free(a);

BN_free(b[0]);

BN_free(b[1]);

BN_free(c);

BN_free(d);

BN_free(e);

BN_free(f);

BN_free(g);

BN_free(h);

return st;

}

static int test_gf2m_sqr(void)

{

BIGNUM *a = NULL, *b[2] = {NULL,NULL}, *c = NULL, *d = NULL;

int i, j, st = 0;

if (!TEST_ptr(a = BN_new())

|| !TEST_ptr(b[0] = BN_new())

|| !TEST_ptr(b[1] = BN_new())

|| !TEST_ptr(c = BN_new())

|| !TEST_ptr(d = BN_new()))

goto err;

if (!(TEST_true(BN_GF2m_arr2poly(p0, b[0]))

&& TEST_true(BN_GF2m_arr2poly(p1, b[1]))))

goto err;

for (i = 0; i < NUM0; i++) {

if (!TEST_true(BN_bntest_rand(a, 1024, 0, 0)))

goto err;

for (j = 0; j < 2; j++) {

if (!(TEST_true(BN_GF2m_mod_sqr(c, a, b[j], ctx))

&& TEST_true(BN_copy(d, a))

&& TEST_true(BN_GF2m_mod_mul(d, a, d, b[j], ctx))

&& TEST_true(BN_GF2m_add(d, c, d))

/* Test that a*a = a^2. */

&& TEST_BN_eq_zero(d)))

goto err;

}

}

st = 1;

err:

BN_free(a);

BN_free(b[0]);

BN_free(b[1]);

BN_free(c);

BN_free(d);

return st;

}

static int test_gf2m_modinv(void)

{

BIGNUM *a = NULL, *b[2] = {NULL,NULL}, *c = NULL, *d = NULL;

int i, j, st = 0;

if (!TEST_ptr(a = BN_new())

|| !TEST_ptr(b[0] = BN_new())

|| !TEST_ptr(b[1] = BN_new())

|| !TEST_ptr(c = BN_new())

|| !TEST_ptr(d = BN_new()))

goto err;

if (!(TEST_true(BN_GF2m_arr2poly(p0, b[0]))

&& TEST_true(BN_GF2m_arr2poly(p1, b[1]))))

goto err;

for (i = 0; i < NUM0; i++) {

if (!TEST_true(BN_bntest_rand(a, 512, 0, 0)))

goto err;

for (j = 0; j < 2; j++) {

if (!(TEST_true(BN_GF2m_mod_inv(c, a, b[j], ctx))

&& TEST_true(BN_GF2m_mod_mul(d, a, c, b[j], ctx))

/* Test that ((1/a)*a) = 1. */

&& TEST_BN_eq_one(d)))

goto err;

}

}

st = 1;

err:

BN_free(a);

BN_free(b[0]);

BN_free(b[1]);

BN_free(c);

BN_free(d);

return st;

}

static int test_gf2m_moddiv(void)

{

BIGNUM *a = NULL, *b[2] = {NULL,NULL}, *c = NULL, *d = NULL;

BIGNUM *e = NULL, *f = NULL;

int i, j, st = 0;

if (!TEST_ptr(a = BN_new())

|| !TEST_ptr(b[0] = BN_new())

|| !TEST_ptr(b[1] = BN_new())

|| !TEST_ptr(c = BN_new())

|| !TEST_ptr(d = BN_new())

|| !TEST_ptr(e = BN_new())

|| !TEST_ptr(f = BN_new()))

goto err;

if (!(TEST_true(BN_GF2m_arr2poly(p0, b[0]))

&& TEST_true(BN_GF2m_arr2poly(p1, b[1]))))

goto err;

for (i = 0; i < NUM0; i++) {

if (!(TEST_true(BN_bntest_rand(a, 512, 0, 0))

&& TEST_true(BN_bntest_rand(c, 512, 0, 0))))

goto err;

for (j = 0; j < 2; j++) {

if (!(TEST_true(BN_GF2m_mod_div(d, a, c, b[j], ctx))

&& TEST_true(BN_GF2m_mod_mul(e, d, c, b[j], ctx))

&& TEST_true(BN_GF2m_mod_div(f, a, e, b[j], ctx))

/* Test that ((a/c)*c)/a = 1. */

&& TEST_BN_eq_one(f)))

goto err;

}

}

st = 1;

err:

BN_free(a);

BN_free(b[0]);

BN_free(b[1]);

BN_free(c);

BN_free(d);

BN_free(e);

BN_free(f);

return st;

}

static int test_gf2m_modexp(void)

{

BIGNUM *a = NULL, *b[2] = {NULL,NULL}, *c = NULL, *d = NULL;

BIGNUM *e = NULL, *f = NULL;

int i, j, st = 0;

if (!TEST_ptr(a = BN_new())

|| !TEST_ptr(b[0] = BN_new())

|| !TEST_ptr(b[1] = BN_new())

|| !TEST_ptr(c = BN_new())

|| !TEST_ptr(d = BN_new())

|| !TEST_ptr(e = BN_new())

|| !TEST_ptr(f = BN_new()))

goto err;

if (!(TEST_true(BN_GF2m_arr2poly(p0, b[0]))

&& TEST_true(BN_GF2m_arr2poly(p1, b[1]))))

goto err;

for (i = 0; i < NUM0; i++) {

if (!(TEST_true(BN_bntest_rand(a, 512, 0, 0))

&& TEST_true(BN_bntest_rand(c, 512, 0, 0))

&& TEST_true(BN_bntest_rand(d, 512, 0, 0))))

goto err;

for (j = 0; j < 2; j++) {

if (!(TEST_true(BN_GF2m_mod_exp(e, a, c, b[j], ctx))

&& TEST_true(BN_GF2m_mod_exp(f, a, d, b[j], ctx))

&& TEST_true(BN_GF2m_mod_mul(e, e, f, b[j], ctx))

&& TEST_true(BN_add(f, c, d))

&& TEST_true(BN_GF2m_mod_exp(f, a, f, b[j], ctx))

&& TEST_true(BN_GF2m_add(f, e, f))