Blame - ap/lib/libssl/openssl-1.1.1o/test/bntest.c - T106_DC

blob: 9273e865668f173afaf3ffe629fb39c05e398912 [file] [log] [blame]

lh	9ed821d	2023-04-07 01:36:19 -0700	[diff] [blame]	1	/*
				2	* Copyright 1995-2022 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	/*
				631	* Regression test for overflow bug in bn_sqr_comba4/8 for
				632	* mips-linux-gnu and mipsel-linux-gnu 32bit targets.
				633	*/
				634	{
				635	static const char *ehex[] = {
				636	"95564994a96c45954227b845a1e99cb939d5a1da99ee91acc962396ae999a9ee",
				637	"38603790448f2f7694c242a875f0cad0aae658eba085f312d2febbbd128dd2b5",
				638	"8f7d1149f03724215d704344d0d62c587ae3c5939cba4b9b5f3dc5e8e911ef9a",
				639	"5ce1a5a749a4989d0d8368f6e1f8cdf3a362a6c97fb02047ff152b480a4ad985",
				640	"2d45efdf0770542992afca6a0590d52930434bba96017afbc9f99e112950a8b1",
				641	"a359473ec376f329bdae6a19f503be6d4be7393c4e43468831234e27e3838680",
				642	"b949390d2e416a3f9759e5349ab4c253f6f29f819a6fe4cbfd27ada34903300e",
				643	"da021f62839f5878a36f1bc3085375b00fd5fa3e68d316c0fdace87a97558465",
				644	NULL};
				645	static const char *phex[] = {
				646	"f95dc0f980fbd22e90caa5a387cc4a369f3f830d50dd321c40db8c09a7e1a241",
				647	"a536e096622d3280c0c1ba849c1f4a79bf490f60006d081e8cf69960189f0d31",
				648	"2cd9e17073a3fba7881b21474a13b334116cb2f5dbf3189a6de3515d0840f053",
				649	"c776d3982d391b6d04d642dda5cc6d1640174c09875addb70595658f89efb439",
				650	"dc6fbd55f903aadd307982d3f659207f265e1ec6271b274521b7a5e28e8fd7a5",
				651	"5df089292820477802a43cf5b6b94e999e8c9944ddebb0d0e95a60f88cb7e813",
				652	"ba110d20e1024774107dd02949031864923b3cb8c3f7250d6d1287b0a40db6a4",
				653	"7bd5a469518eb65aa207ddc47d8c6e5fc8e0c105be8fc1d4b57b2e27540471d5",
				654	NULL};
				655	static const char *mhex[] = {
				656	"fef15d5ce4625f1bccfbba49fc8439c72bf8202af039a2259678941b60bb4a8f",
				657	"2987e965d58fd8cf86a856674d519763d0e1211cc9f8596971050d56d9b35db3",
				658	"785866cfbca17cfdbed6060be3629d894f924a89fdc1efc624f80d41a22f1900",
				659	"9503fcc3824ef62ccb9208430c26f2d8ceb2c63488ec4c07437aa4c96c43dd8b",
				660	"9289ed00a712ff66ee195dc71f5e4ead02172b63c543d69baf495f5fd63ba7bc",
				661	"c633bd309c016e37736da92129d0b053d4ab28d21ad7d8b6fab2a8bbdc8ee647",
				662	"d2fbcf2cf426cf892e6f5639e0252993965dfb73ccd277407014ea784aaa280c",
				663	"b7b03972bc8b0baa72360bdb44b82415b86b2f260f877791cd33ba8f2d65229b",
				664	NULL};
				665
				666	if (!TEST_true(parse_bigBN(&e, ehex))
				667	\|\| !TEST_true(parse_bigBN(&p, phex))
				668	\|\| !TEST_true(parse_bigBN(&m, mhex))
				669	\|\| !TEST_true(BN_mod_exp_mont_consttime(d, e, p, m, ctx, NULL))
				670	\|\| !TEST_true(BN_mod_exp_simple(a, e, p, m, ctx))
				671	\|\| !TEST_BN_eq(a, d))
				672	goto err;
				673	}
				674
				675	/* Zero input */
				676	if (!TEST_true(BN_bntest_rand(p, 1024, 0, 0)))
				677	goto err;
				678	BN_zero(a);
				679	if (!TEST_true(BN_mod_exp_mont_consttime(d, a, p, m, ctx, NULL))
				680	\|\| !TEST_BN_eq_zero(d))
				681	goto err;
				682
				683	/*
				684	* Craft an input whose Montgomery representation is 1, i.e., shorter
				685	* than the modulus m, in order to test the const time precomputation
				686	* scattering/gathering.
				687	*/
				688	if (!(TEST_true(BN_one(a))
				689	&& TEST_true(BN_MONT_CTX_set(mont, m, ctx))))
				690	goto err;
				691	if (!TEST_true(BN_from_montgomery(e, a, mont, ctx))
				692	\|\| !TEST_true(BN_mod_exp_mont_consttime(d, e, p, m, ctx, NULL))
				693	\|\| !TEST_true(BN_mod_exp_simple(a, e, p, m, ctx))
				694	\|\| !TEST_BN_eq(a, d))
				695	goto err;
				696
				697	/* Finally, some regular test vectors. */
				698	if (!(TEST_true(BN_bntest_rand(e, 1024, 0, 0))
				699	&& TEST_true(BN_mod_exp_mont_consttime(d, e, p, m, ctx, NULL))
				700	&& TEST_true(BN_mod_exp_simple(a, e, p, m, ctx))
				701	&& TEST_BN_eq(a, d)))
				702	goto err;
				703
				704	st = 1;
				705
				706	err:
				707	BN_MONT_CTX_free(mont);
				708	BN_free(a);
				709	BN_free(p);
				710	BN_free(m);
				711	BN_free(d);
				712	BN_free(e);
				713	BN_free(b);
				714	BN_free(n);
				715	BN_free(c);
				716	return st;
				717	}
				718
				719	#ifndef OPENSSL_NO_EC2M
				720	static int test_gf2m_add(void)
				721	{
				722	BIGNUM a = NULL, b = NULL, *c = NULL;
				723	int i, st = 0;
				724
				725	if (!TEST_ptr(a = BN_new())
				726	\|\| !TEST_ptr(b = BN_new())
				727	\|\| !TEST_ptr(c = BN_new()))
				728	goto err;
				729
				730	for (i = 0; i < NUM0; i++) {
				731	if (!(TEST_true(BN_rand(a, 512, 0, 0))
				732	&& TEST_ptr(BN_copy(b, BN_value_one()))))
				733	goto err;
				734	BN_set_negative(a, rand_neg());
				735	BN_set_negative(b, rand_neg());
				736	if (!(TEST_true(BN_GF2m_add(c, a, b))
				737	/* Test that two added values have the correct parity. */
				738	&& TEST_false((BN_is_odd(a) && BN_is_odd(c))
				739	\|\| (!BN_is_odd(a) && !BN_is_odd(c)))))
				740	goto err;
				741	if (!(TEST_true(BN_GF2m_add(c, c, c))
				742	/* Test that c + c = 0. */
				743	&& TEST_BN_eq_zero(c)))
				744	goto err;
				745	}
				746	st = 1;
				747	err:
				748	BN_free(a);
				749	BN_free(b);
				750	BN_free(c);
				751	return st;
				752	}
				753
				754	static int test_gf2m_mod(void)
				755	{
				756	BIGNUM a = NULL, b[2] = {NULL,NULL}, c = NULL, d = NULL, *e = NULL;
				757	int i, j, st = 0;
				758
				759	if (!TEST_ptr(a = BN_new())
				760	\|\| !TEST_ptr(b[0] = BN_new())
				761	\|\| !TEST_ptr(b[1] = BN_new())
				762	\|\| !TEST_ptr(c = BN_new())
				763	\|\| !TEST_ptr(d = BN_new())
				764	\|\| !TEST_ptr(e = BN_new()))
				765	goto err;
				766
				767	if (!(TEST_true(BN_GF2m_arr2poly(p0, b[0]))
				768	&& TEST_true(BN_GF2m_arr2poly(p1, b[1]))))
				769	goto err;
				770
				771	for (i = 0; i < NUM0; i++) {
				772	if (!TEST_true(BN_bntest_rand(a, 1024, 0, 0)))
				773	goto err;
				774	for (j = 0; j < 2; j++) {
				775	if (!(TEST_true(BN_GF2m_mod(c, a, b[j]))
				776	&& TEST_true(BN_GF2m_add(d, a, c))
				777	&& TEST_true(BN_GF2m_mod(e, d, b[j]))
				778	/* Test that a + (a mod p) mod p == 0. */
				779	&& TEST_BN_eq_zero(e)))
				780	goto err;
				781	}
				782	}
				783	st = 1;
				784	err:
				785	BN_free(a);
				786	BN_free(b[0]);
				787	BN_free(b[1]);
				788	BN_free(c);
				789	BN_free(d);
				790	BN_free(e);
				791	return st;
				792	}
				793
				794	static int test_gf2m_mul(void)
				795	{
				796	BIGNUM a, b[2] = {NULL, NULL}, c = NULL, d = NULL;
				797	BIGNUM e = NULL, f = NULL, g = NULL, h = NULL;
				798	int i, j, st = 0;
				799
				800	if (!TEST_ptr(a = BN_new())
				801	\|\| !TEST_ptr(b[0] = BN_new())
				802	\|\| !TEST_ptr(b[1] = BN_new())
				803	\|\| !TEST_ptr(c = BN_new())
				804	\|\| !TEST_ptr(d = BN_new())
				805	\|\| !TEST_ptr(e = BN_new())
				806	\|\| !TEST_ptr(f = BN_new())
				807	\|\| !TEST_ptr(g = BN_new())
				808	\|\| !TEST_ptr(h = BN_new()))
				809	goto err;
				810
				811	if (!(TEST_true(BN_GF2m_arr2poly(p0, b[0]))
				812	&& TEST_true(BN_GF2m_arr2poly(p1, b[1]))))
				813	goto err;
				814
				815	for (i = 0; i < NUM0; i++) {
				816	if (!(TEST_true(BN_bntest_rand(a, 1024, 0, 0))
				817	&& TEST_true(BN_bntest_rand(c, 1024, 0, 0))
				818	&& TEST_true(BN_bntest_rand(d, 1024, 0, 0))))
				819	goto err;
				820	for (j = 0; j < 2; j++) {
				821	if (!(TEST_true(BN_GF2m_mod_mul(e, a, c, b[j], ctx))
				822	&& TEST_true(BN_GF2m_add(f, a, d))
				823	&& TEST_true(BN_GF2m_mod_mul(g, f, c, b[j], ctx))
				824	&& TEST_true(BN_GF2m_mod_mul(h, d, c, b[j], ctx))
				825	&& TEST_true(BN_GF2m_add(f, e, g))
				826	&& TEST_true(BN_GF2m_add(f, f, h))
				827	/* Test that (a+d)c = ac + dc. /
				828	&& TEST_BN_eq_zero(f)))
				829	goto err;
				830	}
				831	}
				832	st = 1;
				833
				834	err:
				835	BN_free(a);
				836	BN_free(b[0]);
				837	BN_free(b[1]);
				838	BN_free(c);
				839	BN_free(d);
				840	BN_free(e);
				841	BN_free(f);
				842	BN_free(g);
				843	BN_free(h);
				844	return st;
				845	}
				846
				847	static int test_gf2m_sqr(void)
				848	{
				849	BIGNUM a = NULL, b[2] = {NULL,NULL}, c = NULL, d = NULL;
				850	int i, j, st = 0;
				851
				852	if (!TEST_ptr(a = BN_new())
				853	\|\| !TEST_ptr(b[0] = BN_new())
				854	\|\| !TEST_ptr(b[1] = BN_new())
				855	\|\| !TEST_ptr(c = BN_new())
				856	\|\| !TEST_ptr(d = BN_new()))
				857	goto err;
				858
				859	if (!(TEST_true(BN_GF2m_arr2poly(p0, b[0]))
				860	&& TEST_true(BN_GF2m_arr2poly(p1, b[1]))))
				861	goto err;
				862
				863	for (i = 0; i < NUM0; i++) {
				864	if (!TEST_true(BN_bntest_rand(a, 1024, 0, 0)))
				865	goto err;
				866	for (j = 0; j < 2; j++) {
				867	if (!(TEST_true(BN_GF2m_mod_sqr(c, a, b[j], ctx))
				868	&& TEST_true(BN_copy(d, a))
				869	&& TEST_true(BN_GF2m_mod_mul(d, a, d, b[j], ctx))
				870	&& TEST_true(BN_GF2m_add(d, c, d))
				871	/* Test that aa = a^2. /
				872	&& TEST_BN_eq_zero(d)))
				873	goto err;
				874	}
				875	}
				876	st = 1;
				877	err:
				878	BN_free(a);
				879	BN_free(b[0]);
				880	BN_free(b[1]);
				881	BN_free(c);
				882	BN_free(d);
				883	return st;
				884	}
				885
				886	static int test_gf2m_modinv(void)
				887	{
				888	BIGNUM a = NULL, b[2] = {NULL,NULL}, c = NULL, d = NULL;
				889	int i, j, st = 0;
				890
				891	if (!TEST_ptr(a = BN_new())
				892	\|\| !TEST_ptr(b[0] = BN_new())
				893	\|\| !TEST_ptr(b[1] = BN_new())
				894	\|\| !TEST_ptr(c = BN_new())
				895	\|\| !TEST_ptr(d = BN_new()))
				896	goto err;
				897
				898	if (!(TEST_true(BN_GF2m_arr2poly(p0, b[0]))
				899	&& TEST_true(BN_GF2m_arr2poly(p1, b[1]))))
				900	goto err;
				901
				902	for (i = 0; i < NUM0; i++) {
				903	if (!TEST_true(BN_bntest_rand(a, 512, 0, 0)))
				904	goto err;
				905	for (j = 0; j < 2; j++) {
				906	if (!(TEST_true(BN_GF2m_mod_inv(c, a, b[j], ctx))
				907	&& TEST_true(BN_GF2m_mod_mul(d, a, c, b[j], ctx))
				908	/* Test that ((1/a)a) = 1. /
				909	&& TEST_BN_eq_one(d)))
				910	goto err;
				911	}
				912	}
				913	st = 1;
				914	err:
				915	BN_free(a);
				916	BN_free(b[0]);
				917	BN_free(b[1]);
				918	BN_free(c);
				919	BN_free(d);
				920	return st;
				921	}
				922
				923	static int test_gf2m_moddiv(void)
				924	{
				925	BIGNUM a = NULL, b[2] = {NULL,NULL}, c = NULL, d = NULL;
				926	BIGNUM e = NULL, f = NULL;
				927	int i, j, st = 0;
				928
				929	if (!TEST_ptr(a = BN_new())
				930	\|\| !TEST_ptr(b[0] = BN_new())
				931	\|\| !TEST_ptr(b[1] = BN_new())
				932	\|\| !TEST_ptr(c = BN_new())
				933	\|\| !TEST_ptr(d = BN_new())
				934	\|\| !TEST_ptr(e = BN_new())
				935	\|\| !TEST_ptr(f = BN_new()))
				936	goto err;
				937
				938	if (!(TEST_true(BN_GF2m_arr2poly(p0, b[0]))
				939	&& TEST_true(BN_GF2m_arr2poly(p1, b[1]))))
				940	goto err;
				941
				942	for (i = 0; i < NUM0; i++) {
				943	if (!(TEST_true(BN_bntest_rand(a, 512, 0, 0))
				944	&& TEST_true(BN_bntest_rand(c, 512, 0, 0))))
				945	goto err;
				946	for (j = 0; j < 2; j++) {
				947	if (!(TEST_true(BN_GF2m_mod_div(d, a, c, b[j], ctx))
				948	&& TEST_true(BN_GF2m_mod_mul(e, d, c, b[j], ctx))
				949	&& TEST_true(BN_GF2m_mod_div(f, a, e, b[j], ctx))
				950	/* Test that ((a/c)c)/a = 1. /
				951	&& TEST_BN_eq_one(f)))
				952	goto err;
				953	}
				954	}
				955	st = 1;
				956	err:
				957	BN_free(a);
				958	BN_free(b[0]);
				959	BN_free(b[1]);
				960	BN_free(c);
				961	BN_free(d);
				962	BN_free(e);
				963	BN_free(f);
				964	return st;
				965	}
				966
				967	static int test_gf2m_modexp(void)
				968	{
				969	BIGNUM a = NULL, b[2] = {NULL,NULL}, c = NULL, d = NULL;
				970	BIGNUM e = NULL, f = NULL;
				971	int i, j, st = 0;
				972
				973	if (!TEST_ptr(a = BN_new())
				974	\|\| !TEST_ptr(b[0] = BN_new())
				975	\|\| !TEST_ptr(b[1] = BN_new())
				976	\|\| !TEST_ptr(c = BN_new())
				977	\|\| !TEST_ptr(d = BN_new())
				978	\|\| !TEST_ptr(e = BN_new())
				979	\|\| !TEST_ptr(f = BN_new()))
				980	goto err;
				981
				982	if (!(TEST_true(BN_GF2m_arr2poly(p0, b[0]))
				983	&& TEST_true(BN_GF2m_arr2poly(p1, b[1]))))
				984	goto err;
				985
				986	for (i = 0; i < NUM0; i++) {
				987	if (!(TEST_true(BN_bntest_rand(a, 512, 0, 0))
				988	&& TEST_true(BN_bntest_rand(c, 512, 0, 0))
				989	&& TEST_true(BN_bntest_rand(d, 512, 0, 0))))
				990	goto err;
				991	for (j = 0; j < 2; j++) {
				992	if (!(TEST_true(BN_GF2m_mod_exp(e, a, c, b[j], ctx))
				993	&& TEST_true(BN_GF2m_mod_exp(f, a, d, b[j], ctx))
				994	&& TEST_true(BN_GF2m_mod_mul(e, e, f, b[j], ctx))
				995	&& TEST_true(BN_add(f, c, d))
				996	&& TEST_true(BN_GF2m_mod_exp(f, a, f, b[j], ctx))
				997	&& TEST_true(BN_GF2m_add(f, e, f))
				998	/* Test that a^(c+d)=a^ca^d. /
				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_modsqrt(void)
				1016	{
				1017	BIGNUM a = NULL, b[2] = {NULL,NULL}, c = NULL, d = NULL;
				1018	BIGNUM e = NULL, f = NULL;
				1019	int i, j, 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	\|\| !TEST_ptr(f = BN_new()))
				1028	goto err;
				1029
				1030	if (!(TEST_true(BN_GF2m_arr2poly(p0, b[0]))
				1031	&& TEST_true(BN_GF2m_arr2poly(p1, b[1]))))
				1032	goto err;
				1033
				1034	for (i = 0; i < NUM0; i++) {
				1035	if (!TEST_true(BN_bntest_rand(a, 512, 0, 0)))
				1036	goto err;
				1037
				1038	for (j = 0; j < 2; j++) {
				1039	if (!(TEST_true(BN_GF2m_mod(c, a, b[j]))
				1040	&& TEST_true(BN_GF2m_mod_sqrt(d, a, b[j], ctx))
				1041	&& TEST_true(BN_GF2m_mod_sqr(e, d, b[j], ctx))
				1042	&& TEST_true(BN_GF2m_add(f, c, e))
				1043	/* Test that d^2 = a, where d = sqrt(a). */
				1044	&& TEST_BN_eq_zero(f)))
				1045	goto err;
				1046	}
				1047	}
				1048	st = 1;
				1049	err:
				1050	BN_free(a);
				1051	BN_free(b[0]);
				1052	BN_free(b[1]);
				1053	BN_free(c);
				1054	BN_free(d);
				1055	BN_free(e);
				1056	BN_free(f);
				1057	return st;
				1058	}
				1059
				1060	static int test_gf2m_modsolvequad(void)
				1061	{
				1062	BIGNUM a = NULL, b[2] = {NULL,NULL}, c = NULL, d = NULL;
				1063	BIGNUM *e = NULL;
				1064	int i, j, s = 0, t, st = 0;
				1065
				1066	if (!TEST_ptr(a = BN_new())
				1067	\|\| !TEST_ptr(b[0] = BN_new())
				1068	\|\| !TEST_ptr(b[1] = BN_new())
				1069	\|\| !TEST_ptr(c = BN_new())
				1070	\|\| !TEST_ptr(d = BN_new())
				1071	\|\| !TEST_ptr(e = BN_new()))
				1072	goto err;
				1073
				1074	if (!(TEST_true(BN_GF2m_arr2poly(p0, b[0]))
				1075	&& TEST_true(BN_GF2m_arr2poly(p1, b[1]))))
				1076	goto err;
				1077
				1078	for (i = 0; i < NUM0; i++) {
				1079	if (!TEST_true(BN_bntest_rand(a, 512, 0, 0)))
				1080	goto err;
				1081	for (j = 0; j < 2; j++) {
				1082	t = BN_GF2m_mod_solve_quad(c, a, b[j], ctx);
				1083	if (t) {
				1084	s++;
				1085	if (!(TEST_true(BN_GF2m_mod_sqr(d, c, b[j], ctx))
				1086	&& TEST_true(BN_GF2m_add(d, c, d))
				1087	&& TEST_true(BN_GF2m_mod(e, a, b[j]))
				1088	&& TEST_true(BN_GF2m_add(e, e, d))
				1089	/*
				1090	* Test that solution of quadratic c
				1091	* satisfies c^2 + c = a.
				1092	*/
				1093	&& TEST_BN_eq_zero(e)))
				1094	goto err;
				1095	}
				1096	}
				1097	}
				1098	if (!TEST_int_ge(s, 0)) {
				1099	TEST_info("%d tests found no roots; probably an error", NUM0);
				1100	goto err;
				1101	}
				1102	st = 1;
				1103	err:
				1104	BN_free(a);
				1105	BN_free(b[0]);
				1106	BN_free(b[1]);
				1107	BN_free(c);
				1108	BN_free(d);
				1109	BN_free(e);
				1110	return st;
				1111	}
				1112	#endif
				1113
				1114	static int test_kronecker(void)
				1115	{
				1116	BIGNUM a = NULL, b = NULL, r = NULL, t = NULL;
				1117	int i, legendre, kronecker, st = 0;
				1118
				1119	if (!TEST_ptr(a = BN_new())
				1120	\|\| !TEST_ptr(b = BN_new())
				1121	\|\| !TEST_ptr(r = BN_new())
				1122	\|\| !TEST_ptr(t = BN_new()))
				1123	goto err;
				1124
				1125	/*
				1126	* We test BN_kronecker(a, b, ctx) just for b odd (Jacobi symbol). In
				1127	* this case we know that if b is prime, then BN_kronecker(a, b, ctx) is
				1128	* congruent to $a^{(b-1)/2}$, modulo $b$ (Legendre symbol). So we
				1129	* generate a random prime b and compare these values for a number of
				1130	* random a's. (That is, we run the Solovay-Strassen primality test to
				1131	* confirm that b is prime, except that we don't want to test whether b
				1132	* is prime but whether BN_kronecker works.)
				1133	*/
				1134
				1135	if (!TEST_true(BN_generate_prime_ex(b, 512, 0, NULL, NULL, NULL)))
				1136	goto err;
				1137	BN_set_negative(b, rand_neg());
				1138
				1139	for (i = 0; i < NUM0; i++) {
				1140	if (!TEST_true(BN_bntest_rand(a, 512, 0, 0)))
				1141	goto err;
				1142	BN_set_negative(a, rand_neg());
				1143
				1144	/* t := (\|b\|-1)/2 (note that b is odd) */
				1145	if (!TEST_true(BN_copy(t, b)))
				1146	goto err;
				1147	BN_set_negative(t, 0);
				1148	if (!TEST_true(BN_sub_word(t, 1)))
				1149	goto err;
				1150	if (!TEST_true(BN_rshift1(t, t)))
				1151	goto err;
				1152	/* r := a^t mod b */
				1153	BN_set_negative(b, 0);
				1154
				1155	if (!TEST_true(BN_mod_exp_recp(r, a, t, b, ctx)))
				1156	goto err;
				1157	BN_set_negative(b, 1);
				1158
				1159	if (BN_is_word(r, 1))
				1160	legendre = 1;
				1161	else if (BN_is_zero(r))
				1162	legendre = 0;
				1163	else {
				1164	if (!TEST_true(BN_add_word(r, 1)))
				1165	goto err;
				1166	if (!TEST_int_eq(BN_ucmp(r, b), 0)) {
				1167	TEST_info("Legendre symbol computation failed");
				1168	goto err;
				1169	}
				1170	legendre = -1;
				1171	}
				1172
				1173	if (!TEST_int_ge(kronecker = BN_kronecker(a, b, ctx), -1))
				1174	goto err;
				1175	/* we actually need BN_kronecker(a, \|b\|) */
				1176	if (BN_is_negative(a) && BN_is_negative(b))
				1177	kronecker = -kronecker;
				1178
				1179	if (!TEST_int_eq(legendre, kronecker))
				1180	goto err;
				1181	}
				1182
				1183	st = 1;
				1184	err:
				1185	BN_free(a);
				1186	BN_free(b);
				1187	BN_free(r);
				1188	BN_free(t);
				1189	return st;
				1190	}
				1191
				1192	static int file_sum(STANZA *s)
				1193	{
				1194	BIGNUM a = NULL, b = NULL, sum = NULL, ret = NULL;
				1195	BN_ULONG b_word;
				1196	int st = 0;
				1197
				1198	if (!TEST_ptr(a = getBN(s, "A"))
				1199	\|\| !TEST_ptr(b = getBN(s, "B"))
				1200	\|\| !TEST_ptr(sum = getBN(s, "Sum"))
				1201	\|\| !TEST_ptr(ret = BN_new()))
				1202	goto err;
				1203
				1204	if (!TEST_true(BN_add(ret, a, b))
				1205	\|\| !equalBN("A + B", sum, ret)
				1206	\|\| !TEST_true(BN_sub(ret, sum, a))
				1207	\|\| !equalBN("Sum - A", b, ret)
				1208	\|\| !TEST_true(BN_sub(ret, sum, b))
				1209	\|\| !equalBN("Sum - B", a, ret))
				1210	goto err;
				1211
				1212	/*
				1213	* Test that the functions work when \|r\| and \|a\| point to the same BIGNUM,
				1214	* or when \|r\| and \|b\| point to the same BIGNUM.
				1215	* TODO: Test where all of \|r\|, \|a\|, and \|b\| point to the same BIGNUM.
				1216	*/
				1217	if (!TEST_true(BN_copy(ret, a))
				1218	\|\| !TEST_true(BN_add(ret, ret, b))
				1219	\|\| !equalBN("A + B (r is a)", sum, ret)
				1220	\|\| !TEST_true(BN_copy(ret, b))
				1221	\|\| !TEST_true(BN_add(ret, a, ret))
				1222	\|\| !equalBN("A + B (r is b)", sum, ret)
				1223	\|\| !TEST_true(BN_copy(ret, sum))
				1224	\|\| !TEST_true(BN_sub(ret, ret, a))
				1225	\|\| !equalBN("Sum - A (r is a)", b, ret)
				1226	\|\| !TEST_true(BN_copy(ret, a))
				1227	\|\| !TEST_true(BN_sub(ret, sum, ret))
				1228	\|\| !equalBN("Sum - A (r is b)", b, ret)
				1229	\|\| !TEST_true(BN_copy(ret, sum))
				1230	\|\| !TEST_true(BN_sub(ret, ret, b))
				1231	\|\| !equalBN("Sum - B (r is a)", a, ret)
				1232	\|\| !TEST_true(BN_copy(ret, b))
				1233	\|\| !TEST_true(BN_sub(ret, sum, ret))
				1234	\|\| !equalBN("Sum - B (r is b)", a, ret))
				1235	goto err;
				1236
				1237	/*
				1238	* Test BN_uadd() and BN_usub() with the prerequisites they are
				1239	* documented as having. Note that these functions are frequently used
				1240	* when the prerequisites don't hold. In those cases, they are supposed
				1241	* to work as if the prerequisite hold, but we don't test that yet.
				1242	* TODO: test that.
				1243	*/
				1244	if (!BN_is_negative(a) && !BN_is_negative(b) && BN_cmp(a, b) >= 0) {
				1245	if (!TEST_true(BN_uadd(ret, a, b))
				1246	\|\| !equalBN("A +u B", sum, ret)
				1247	\|\| !TEST_true(BN_usub(ret, sum, a))
				1248	\|\| !equalBN("Sum -u A", b, ret)
				1249	\|\| !TEST_true(BN_usub(ret, sum, b))
				1250	\|\| !equalBN("Sum -u B", a, ret))
				1251	goto err;
				1252	/*
				1253	* Test that the functions work when \|r\| and \|a\| point to the same
				1254	* BIGNUM, or when \|r\| and \|b\| point to the same BIGNUM.
				1255	* TODO: Test where all of \|r\|, \|a\|, and \|b\| point to the same BIGNUM.
				1256	*/
				1257	if (!TEST_true(BN_copy(ret, a))
				1258	\|\| !TEST_true(BN_uadd(ret, ret, b))
				1259	\|\| !equalBN("A +u B (r is a)", sum, ret)
				1260	\|\| !TEST_true(BN_copy(ret, b))
				1261	\|\| !TEST_true(BN_uadd(ret, a, ret))
				1262	\|\| !equalBN("A +u B (r is b)", sum, ret)
				1263	\|\| !TEST_true(BN_copy(ret, sum))
				1264	\|\| !TEST_true(BN_usub(ret, ret, a))
				1265	\|\| !equalBN("Sum -u A (r is a)", b, ret)
				1266	\|\| !TEST_true(BN_copy(ret, a))
				1267	\|\| !TEST_true(BN_usub(ret, sum, ret))
				1268	\|\| !equalBN("Sum -u A (r is b)", b, ret)
				1269	\|\| !TEST_true(BN_copy(ret, sum))
				1270	\|\| !TEST_true(BN_usub(ret, ret, b))
				1271	\|\| !equalBN("Sum -u B (r is a)", a, ret)
				1272	\|\| !TEST_true(BN_copy(ret, b))
				1273	\|\| !TEST_true(BN_usub(ret, sum, ret))
				1274	\|\| !equalBN("Sum -u B (r is b)", a, ret))
				1275	goto err;
				1276	}
				1277
				1278	/*
				1279	* Test with BN_add_word() and BN_sub_word() if \|b\| is small enough.
				1280	*/
				1281	b_word = BN_get_word(b);
				1282	if (!BN_is_negative(b) && b_word != (BN_ULONG)-1) {
				1283	if (!TEST_true(BN_copy(ret, a))
				1284	\|\| !TEST_true(BN_add_word(ret, b_word))
				1285	\|\| !equalBN("A + B (word)", sum, ret)
				1286	\|\| !TEST_true(BN_copy(ret, sum))
				1287	\|\| !TEST_true(BN_sub_word(ret, b_word))
				1288	\|\| !equalBN("Sum - B (word)", a, ret))
				1289	goto err;
				1290	}
				1291	st = 1;
				1292
				1293	err:
				1294	BN_free(a);
				1295	BN_free(b);
				1296	BN_free(sum);
				1297	BN_free(ret);
				1298	return st;
				1299	}
				1300
				1301	static int file_lshift1(STANZA *s)
				1302	{
				1303	BIGNUM a = NULL, lshift1 = NULL, zero = NULL, ret = NULL;
				1304	BIGNUM two = NULL, remainder = NULL;
				1305	int st = 0;
				1306
				1307	if (!TEST_ptr(a = getBN(s, "A"))
				1308	\|\| !TEST_ptr(lshift1 = getBN(s, "LShift1"))
				1309	\|\| !TEST_ptr(zero = BN_new())
				1310	\|\| !TEST_ptr(ret = BN_new())
				1311	\|\| !TEST_ptr(two = BN_new())
				1312	\|\| !TEST_ptr(remainder = BN_new()))
				1313	goto err;
				1314
				1315	BN_zero(zero);
				1316
				1317	if (!TEST_true(BN_set_word(two, 2))
				1318	\|\| !TEST_true(BN_add(ret, a, a))
				1319	\|\| !equalBN("A + A", lshift1, ret)
				1320	\|\| !TEST_true(BN_mul(ret, a, two, ctx))
				1321	\|\| !equalBN("A * 2", lshift1, ret)
				1322	\|\| !TEST_true(BN_div(ret, remainder, lshift1, two, ctx))
				1323	\|\| !equalBN("LShift1 / 2", a, ret)
				1324	\|\| !equalBN("LShift1 % 2", zero, remainder)
				1325	\|\| !TEST_true(BN_lshift1(ret, a))
				1326	\|\| !equalBN("A << 1", lshift1, ret)
				1327	\|\| !TEST_true(BN_rshift1(ret, lshift1))
				1328	\|\| !equalBN("LShift >> 1", a, ret)
				1329	\|\| !TEST_true(BN_rshift1(ret, lshift1))
				1330	\|\| !equalBN("LShift >> 1", a, ret))
				1331	goto err;
				1332
				1333	/* Set the LSB to 1 and test rshift1 again. */
				1334	if (!TEST_true(BN_set_bit(lshift1, 0))
				1335	\|\| !TEST_true(BN_div(ret, NULL /* rem */ , lshift1, two, ctx))
				1336	\|\| !equalBN("(LShift1 \| 1) / 2", a, ret)
				1337	\|\| !TEST_true(BN_rshift1(ret, lshift1))
				1338	\|\| !equalBN("(LShift \| 1) >> 1", a, ret))
				1339	goto err;
				1340
				1341	st = 1;
				1342	err:
				1343	BN_free(a);
				1344	BN_free(lshift1);
				1345	BN_free(zero);
				1346	BN_free(ret);
				1347	BN_free(two);
				1348	BN_free(remainder);
				1349
				1350	return st;
				1351	}
				1352
				1353	static int file_lshift(STANZA *s)
				1354	{
				1355	BIGNUM a = NULL, lshift = NULL, *ret = NULL;
				1356	int n = 0, st = 0;
				1357
				1358	if (!TEST_ptr(a = getBN(s, "A"))
				1359	\|\| !TEST_ptr(lshift = getBN(s, "LShift"))
				1360	\|\| !TEST_ptr(ret = BN_new())
				1361	\|\| !getint(s, &n, "N"))
				1362	goto err;
				1363
				1364	if (!TEST_true(BN_lshift(ret, a, n))
				1365	\|\| !equalBN("A << N", lshift, ret)
				1366	\|\| !TEST_true(BN_rshift(ret, lshift, n))
				1367	\|\| !equalBN("A >> N", a, ret))
				1368	goto err;
				1369
				1370	st = 1;
				1371	err:
				1372	BN_free(a);
				1373	BN_free(lshift);
				1374	BN_free(ret);
				1375	return st;
				1376	}
				1377
				1378	static int file_rshift(STANZA *s)
				1379	{
				1380	BIGNUM a = NULL, rshift = NULL, *ret = NULL;
				1381	int n = 0, st = 0;
				1382
				1383	if (!TEST_ptr(a = getBN(s, "A"))
				1384	\|\| !TEST_ptr(rshift = getBN(s, "RShift"))
				1385	\|\| !TEST_ptr(ret = BN_new())
				1386	\|\| !getint(s, &n, "N"))
				1387	goto err;
				1388
				1389	if (!TEST_true(BN_rshift(ret, a, n))
				1390	\|\| !equalBN("A >> N", rshift, ret))
				1391	goto err;
				1392
				1393	/* If N == 1, try with rshift1 as well */
				1394	if (n == 1) {
				1395	if (!TEST_true(BN_rshift1(ret, a))
				1396	\|\| !equalBN("A >> 1 (rshift1)", rshift, ret))
				1397	goto err;
				1398	}
				1399	st = 1;
				1400
				1401	err:
				1402	BN_free(a);
				1403	BN_free(rshift);
				1404	BN_free(ret);
				1405	return st;
				1406	}
				1407
				1408	static int file_square(STANZA *s)
				1409	{
				1410	BIGNUM a = NULL, square = NULL, zero = NULL, ret = NULL;
				1411	BIGNUM remainder = NULL, tmp = NULL;
				1412	int st = 0;
				1413
				1414	if (!TEST_ptr(a = getBN(s, "A"))
				1415	\|\| !TEST_ptr(square = getBN(s, "Square"))
				1416	\|\| !TEST_ptr(zero = BN_new())
				1417	\|\| !TEST_ptr(ret = BN_new())
				1418	\|\| !TEST_ptr(remainder = BN_new()))
				1419	goto err;
				1420
				1421	BN_zero(zero);
				1422	if (!TEST_true(BN_sqr(ret, a, ctx))
				1423	\|\| !equalBN("A^2", square, ret)
				1424	\|\| !TEST_true(BN_mul(ret, a, a, ctx))
				1425	\|\| !equalBN("A * A", square, ret)
				1426	\|\| !TEST_true(BN_div(ret, remainder, square, a, ctx))
				1427	\|\| !equalBN("Square / A", a, ret)
				1428	\|\| !equalBN("Square % A", zero, remainder))
				1429	goto err;
				1430
				1431	#if HAVE_BN_SQRT
				1432	BN_set_negative(a, 0);
				1433	if (!TEST_true(BN_sqrt(ret, square, ctx))
				1434	\|\| !equalBN("sqrt(Square)", a, ret))
				1435	goto err;
				1436
				1437	/* BN_sqrt should fail on non-squares and negative numbers. */
				1438	if (!TEST_BN_eq_zero(square)) {
				1439	if (!TEST_ptr(tmp = BN_new())
				1440	\|\| !TEST_true(BN_copy(tmp, square)))
				1441	goto err;
				1442	BN_set_negative(tmp, 1);
				1443
				1444	if (!TEST_int_eq(BN_sqrt(ret, tmp, ctx), 0))
				1445	goto err;
				1446	ERR_clear_error();
				1447
				1448	BN_set_negative(tmp, 0);
				1449	if (BN_add(tmp, tmp, BN_value_one()))
				1450	goto err;
				1451	if (!TEST_int_eq(BN_sqrt(ret, tmp, ctx)))
				1452	goto err;
				1453	ERR_clear_error();
				1454	}
				1455	#endif
				1456
				1457	st = 1;
				1458	err:
				1459	BN_free(a);
				1460	BN_free(square);
				1461	BN_free(zero);
				1462	BN_free(ret);
				1463	BN_free(remainder);
				1464	BN_free(tmp);
				1465	return st;
				1466	}
				1467
				1468	static int file_product(STANZA *s)
				1469	{
				1470	BIGNUM a = NULL, b = NULL, product = NULL, ret = NULL;
				1471	BIGNUM remainder = NULL, zero = NULL;
				1472	int st = 0;
				1473
				1474	if (!TEST_ptr(a = getBN(s, "A"))
				1475	\|\| !TEST_ptr(b = getBN(s, "B"))
				1476	\|\| !TEST_ptr(product = getBN(s, "Product"))
				1477	\|\| !TEST_ptr(ret = BN_new())
				1478	\|\| !TEST_ptr(remainder = BN_new())
				1479	\|\| !TEST_ptr(zero = BN_new()))
				1480	goto err;
				1481
				1482	BN_zero(zero);
				1483
				1484	if (!TEST_true(BN_mul(ret, a, b, ctx))
				1485	\|\| !equalBN("A * B", product, ret)
				1486	\|\| !TEST_true(BN_div(ret, remainder, product, a, ctx))
				1487	\|\| !equalBN("Product / A", b, ret)
				1488	\|\| !equalBN("Product % A", zero, remainder)
				1489	\|\| !TEST_true(BN_div(ret, remainder, product, b, ctx))
				1490	\|\| !equalBN("Product / B", a, ret)
				1491	\|\| !equalBN("Product % B", zero, remainder))
				1492	goto err;
				1493
				1494	st = 1;
				1495	err:
				1496	BN_free(a);
				1497	BN_free(b);
				1498	BN_free(product);
				1499	BN_free(ret);
				1500	BN_free(remainder);
				1501	BN_free(zero);
				1502	return st;
				1503	}
				1504
				1505	static int file_quotient(STANZA *s)
				1506	{
				1507	BIGNUM a = NULL, b = NULL, quotient = NULL, remainder = NULL;
				1508	BIGNUM ret = NULL, ret2 = NULL, *nnmod = NULL;
				1509	BN_ULONG b_word, ret_word;
				1510	int st = 0;
				1511
				1512	if (!TEST_ptr(a = getBN(s, "A"))
				1513	\|\| !TEST_ptr(b = getBN(s, "B"))
				1514	\|\| !TEST_ptr(quotient = getBN(s, "Quotient"))
				1515	\|\| !TEST_ptr(remainder = getBN(s, "Remainder"))
				1516	\|\| !TEST_ptr(ret = BN_new())
				1517	\|\| !TEST_ptr(ret2 = BN_new())
				1518	\|\| !TEST_ptr(nnmod = BN_new()))
				1519	goto err;
				1520
				1521	if (!TEST_true(BN_div(ret, ret2, a, b, ctx))
				1522	\|\| !equalBN("A / B", quotient, ret)
				1523	\|\| !equalBN("A % B", remainder, ret2)
				1524	\|\| !TEST_true(BN_mul(ret, quotient, b, ctx))
				1525	\|\| !TEST_true(BN_add(ret, ret, remainder))
				1526	\|\| !equalBN("Quotient * B + Remainder", a, ret))
				1527	goto err;
				1528
				1529	/*
				1530	* Test with BN_mod_word() and BN_div_word() if the divisor is
				1531	* small enough.
				1532	*/
				1533	b_word = BN_get_word(b);
				1534	if (!BN_is_negative(b) && b_word != (BN_ULONG)-1) {
				1535	BN_ULONG remainder_word = BN_get_word(remainder);
				1536
				1537	assert(remainder_word != (BN_ULONG)-1);
				1538	if (!TEST_ptr(BN_copy(ret, a)))
				1539	goto err;
				1540	ret_word = BN_div_word(ret, b_word);
				1541	if (ret_word != remainder_word) {
				1542	#ifdef BN_DEC_FMT1
				1543	TEST_error(
				1544	"Got A %% B (word) = " BN_DEC_FMT1 ", wanted " BN_DEC_FMT1,
				1545	ret_word, remainder_word);
				1546	#else
				1547	TEST_error("Got A %% B (word) mismatch");
				1548	#endif
				1549	goto err;
				1550	}
				1551	if (!equalBN ("A / B (word)", quotient, ret))
				1552	goto err;
				1553
				1554	ret_word = BN_mod_word(a, b_word);
				1555	if (ret_word != remainder_word) {
				1556	#ifdef BN_DEC_FMT1
				1557	TEST_error(
				1558	"Got A %% B (word) = " BN_DEC_FMT1 ", wanted " BN_DEC_FMT1 "",
				1559	ret_word, remainder_word);
				1560	#else
				1561	TEST_error("Got A %% B (word) mismatch");
				1562	#endif
				1563	goto err;
				1564	}
				1565	}
				1566
				1567	/* Test BN_nnmod. */
				1568	if (!BN_is_negative(b)) {
				1569	if (!TEST_true(BN_copy(nnmod, remainder))
				1570	\|\| (BN_is_negative(nnmod)
				1571	&& !TEST_true(BN_add(nnmod, nnmod, b)))
				1572	\|\| !TEST_true(BN_nnmod(ret, a, b, ctx))
				1573	\|\| !equalBN("A % B (non-negative)", nnmod, ret))
				1574	goto err;
				1575	}
				1576
				1577	st = 1;
				1578	err:
				1579	BN_free(a);
				1580	BN_free(b);
				1581	BN_free(quotient);
				1582	BN_free(remainder);
				1583	BN_free(ret);
				1584	BN_free(ret2);
				1585	BN_free(nnmod);
				1586	return st;
				1587	}
				1588
				1589	static int file_modmul(STANZA *s)
				1590	{
				1591	BIGNUM a = NULL, b = NULL, m = NULL, mod_mul = NULL, *ret = NULL;
				1592	int st = 0;
				1593
				1594	if (!TEST_ptr(a = getBN(s, "A"))
				1595	\|\| !TEST_ptr(b = getBN(s, "B"))
				1596	\|\| !TEST_ptr(m = getBN(s, "M"))
				1597	\|\| !TEST_ptr(mod_mul = getBN(s, "ModMul"))
				1598	\|\| !TEST_ptr(ret = BN_new()))
				1599	goto err;
				1600
				1601	if (!TEST_true(BN_mod_mul(ret, a, b, m, ctx))
				1602	\|\| !equalBN("A * B (mod M)", mod_mul, ret))
				1603	goto err;
				1604
				1605	if (BN_is_odd(m)) {
				1606	/* Reduce \|a\| and \|b\| and test the Montgomery version. */
				1607	BN_MONT_CTX *mont = BN_MONT_CTX_new();
				1608	BIGNUM *a_tmp = BN_new();
				1609	BIGNUM *b_tmp = BN_new();
				1610
				1611	if (mont == NULL \|\| a_tmp == NULL \|\| b_tmp == NULL
				1612	\|\| !TEST_true(BN_MONT_CTX_set(mont, m, ctx))
				1613	\|\| !TEST_true(BN_nnmod(a_tmp, a, m, ctx))
				1614	\|\| !TEST_true(BN_nnmod(b_tmp, b, m, ctx))
				1615	\|\| !TEST_true(BN_to_montgomery(a_tmp, a_tmp, mont, ctx))
				1616	\|\| !TEST_true(BN_to_montgomery(b_tmp, b_tmp, mont, ctx))
				1617	\|\| !TEST_true(BN_mod_mul_montgomery(ret, a_tmp, b_tmp,
				1618	mont, ctx))
				1619	\|\| !TEST_true(BN_from_montgomery(ret, ret, mont, ctx))
				1620	\|\| !equalBN("A * B (mod M) (mont)", mod_mul, ret))
				1621	st = 0;
				1622	else
				1623	st = 1;
				1624	BN_MONT_CTX_free(mont);
				1625	BN_free(a_tmp);
				1626	BN_free(b_tmp);
				1627	if (st == 0)
				1628	goto err;
				1629	}
				1630
				1631	st = 1;
				1632	err:
				1633	BN_free(a);
				1634	BN_free(b);
				1635	BN_free(m);
				1636	BN_free(mod_mul);
				1637	BN_free(ret);
				1638	return st;
				1639	}
				1640
				1641	static int file_modexp(STANZA *s)
				1642	{
				1643	BIGNUM a = NULL, e = NULL, m = NULL, mod_exp = NULL, *ret = NULL;
				1644	BIGNUM b = NULL, c = NULL, *d = NULL;
				1645	int st = 0;
				1646
				1647	if (!TEST_ptr(a = getBN(s, "A"))
				1648	\|\| !TEST_ptr(e = getBN(s, "E"))
				1649	\|\| !TEST_ptr(m = getBN(s, "M"))
				1650	\|\| !TEST_ptr(mod_exp = getBN(s, "ModExp"))
				1651	\|\| !TEST_ptr(ret = BN_new())
				1652	\|\| !TEST_ptr(d = BN_new()))
				1653	goto err;
				1654
				1655	if (!TEST_true(BN_mod_exp(ret, a, e, m, ctx))
				1656	\|\| !equalBN("A ^ E (mod M)", mod_exp, ret))
				1657	goto err;
				1658
				1659	if (BN_is_odd(m)) {
				1660	if (!TEST_true(BN_mod_exp_mont(ret, a, e, m, ctx, NULL))
				1661	\|\| !equalBN("A ^ E (mod M) (mont)", mod_exp, ret)
				1662	\|\| !TEST_true(BN_mod_exp_mont_consttime(ret, a, e, m,
				1663	ctx, NULL))
				1664	\|\| !equalBN("A ^ E (mod M) (mont const", mod_exp, ret))
				1665	goto err;
				1666	}
				1667
				1668	/* Regression test for carry propagation bug in sqr8x_reduction */
				1669	BN_hex2bn(&a, "050505050505");
				1670	BN_hex2bn(&b, "02");
				1671	BN_hex2bn(&c,
				1672	"4141414141414141414141274141414141414141414141414141414141414141"
				1673	"4141414141414141414141414141414141414141414141414141414141414141"
				1674	"4141414141414141414141800000000000000000000000000000000000000000"
				1675	"0000000000000000000000000000000000000000000000000000000000000000"
				1676	"0000000000000000000000000000000000000000000000000000000000000000"
				1677	"0000000000000000000000000000000000000000000000000000000001");
				1678	if (!TEST_true(BN_mod_exp(d, a, b, c, ctx))
				1679	\|\| !TEST_true(BN_mul(e, a, a, ctx))
				1680	\|\| !TEST_BN_eq(d, e))
				1681	goto err;
				1682
				1683	st = 1;
				1684	err:
				1685	BN_free(a);
				1686	BN_free(b);
				1687	BN_free(c);
				1688	BN_free(d);
				1689	BN_free(e);
				1690	BN_free(m);
				1691	BN_free(mod_exp);
				1692	BN_free(ret);
				1693	return st;
				1694	}
				1695
				1696	static int file_exp(STANZA *s)
				1697	{
				1698	BIGNUM a = NULL, e = NULL, exp = NULL, ret = NULL;
				1699	int st = 0;
				1700
				1701	if (!TEST_ptr(a = getBN(s, "A"))
				1702	\|\| !TEST_ptr(e = getBN(s, "E"))
				1703	\|\| !TEST_ptr(exp = getBN(s, "Exp"))
				1704	\|\| !TEST_ptr(ret = BN_new()))
				1705	goto err;
				1706
				1707	if (!TEST_true(BN_exp(ret, a, e, ctx))
				1708	\|\| !equalBN("A ^ E", exp, ret))
				1709	goto err;
				1710
				1711	st = 1;
				1712	err:
				1713	BN_free(a);
				1714	BN_free(e);
				1715	BN_free(exp);
				1716	BN_free(ret);
				1717	return st;
				1718	}
				1719
				1720	static int file_modsqrt(STANZA *s)
				1721	{
				1722	BIGNUM a = NULL, p = NULL, mod_sqrt = NULL, ret = NULL, *ret2 = NULL;
				1723	int st = 0;
				1724
				1725	if (!TEST_ptr(a = getBN(s, "A"))
				1726	\|\| !TEST_ptr(p = getBN(s, "P"))
				1727	\|\| !TEST_ptr(mod_sqrt = getBN(s, "ModSqrt"))
				1728	\|\| !TEST_ptr(ret = BN_new())
				1729	\|\| !TEST_ptr(ret2 = BN_new()))
				1730	goto err;
				1731
				1732	if (BN_is_negative(mod_sqrt)) {
				1733	/* A negative testcase */
				1734	if (!TEST_ptr_null(BN_mod_sqrt(ret, a, p, ctx)))
				1735	goto err;
				1736
				1737	st = 1;
				1738	goto err;
				1739	}
				1740
				1741	/* There are two possible answers. */
				1742	if (!TEST_ptr(BN_mod_sqrt(ret, a, p, ctx))
				1743	\|\| !TEST_true(BN_sub(ret2, p, ret)))
				1744	goto err;
				1745
				1746	/* The first condition should NOT be a test. */
				1747	if (BN_cmp(ret2, mod_sqrt) != 0
				1748	&& !equalBN("sqrt(A) (mod P)", mod_sqrt, ret))
				1749	goto err;
				1750
				1751	st = 1;
				1752	err:
				1753	BN_free(a);
				1754	BN_free(p);
				1755	BN_free(mod_sqrt);
				1756	BN_free(ret);
				1757	BN_free(ret2);
				1758	return st;
				1759	}
				1760
				1761	static int file_gcd(STANZA *s)
				1762	{
				1763	BIGNUM a = NULL, b = NULL, gcd = NULL, ret = NULL;
				1764	int st = 0;
				1765
				1766	if (!TEST_ptr(a = getBN(s, "A"))
				1767	\|\| !TEST_ptr(b = getBN(s, "B"))
				1768	\|\| !TEST_ptr(gcd = getBN(s, "GCD"))
				1769	\|\| !TEST_ptr(ret = BN_new()))
				1770	goto err;
				1771
				1772	if (!TEST_true(BN_gcd(ret, a, b, ctx))
				1773	\|\| !equalBN("gcd(A,B)", gcd, ret))
				1774	goto err;
				1775
				1776	st = 1;
				1777	err:
				1778	BN_free(a);
				1779	BN_free(b);
				1780	BN_free(gcd);
				1781	BN_free(ret);
				1782	return st;
				1783	}
				1784
				1785	static int test_bn2padded(void)
				1786	{
				1787	uint8_t zeros[256], out[256], reference[128];
				1788	size_t bytes;
				1789	BIGNUM *n;
				1790	int st = 0;
				1791
				1792	/* Test edge case at 0. */
				1793	if (!TEST_ptr((n = BN_new())))
				1794	goto err;
				1795	if (!TEST_int_eq(BN_bn2binpad(n, NULL, 0), 0))
				1796	goto err;
				1797	memset(out, -1, sizeof(out));
				1798	if (!TEST_int_eq(BN_bn2binpad(n, out, sizeof(out)), sizeof(out)))
				1799	goto err;
				1800	memset(zeros, 0, sizeof(zeros));
				1801	if (!TEST_mem_eq(zeros, sizeof(zeros), out, sizeof(out)))
				1802	goto err;
				1803
				1804	/* Test a random numbers at various byte lengths. */
				1805	for (bytes = 128 - 7; bytes <= 128; bytes++) {
				1806	# define TOP_BIT_ON 0
				1807	# define BOTTOM_BIT_NOTOUCH 0
				1808	if (!TEST_true(BN_rand(n, bytes * 8, TOP_BIT_ON, BOTTOM_BIT_NOTOUCH)))
				1809	goto err;
				1810	if (!TEST_int_eq(BN_num_bytes(n), bytes)
				1811	\|\| !TEST_int_eq(BN_bn2bin(n, reference), bytes))
				1812	goto err;
				1813	/* Empty buffer should fail. */
				1814	if (!TEST_int_eq(BN_bn2binpad(n, NULL, 0), -1))
				1815	goto err;
				1816	/* One byte short should fail. */
				1817	if (!TEST_int_eq(BN_bn2binpad(n, out, bytes - 1), -1))
				1818	goto err;
				1819	/* Exactly right size should encode. */
				1820	if (!TEST_int_eq(BN_bn2binpad(n, out, bytes), bytes)
				1821	\|\| !TEST_mem_eq(out, bytes, reference, bytes))
				1822	goto err;
				1823	/* Pad up one byte extra. */
				1824	if (!TEST_int_eq(BN_bn2binpad(n, out, bytes + 1), bytes + 1)
				1825	\|\| !TEST_mem_eq(out + 1, bytes, reference, bytes)
				1826	\|\| !TEST_mem_eq(out, 1, zeros, 1))
				1827	goto err;
				1828	/* Pad up to 256. */
				1829	if (!TEST_int_eq(BN_bn2binpad(n, out, sizeof(out)), sizeof(out))
				1830	\|\| !TEST_mem_eq(out + sizeof(out) - bytes, bytes,
				1831	reference, bytes)
				1832	\|\| !TEST_mem_eq(out, sizeof(out) - bytes,
				1833	zeros, sizeof(out) - bytes))
				1834	goto err;
				1835	}
				1836
				1837	st = 1;
				1838	err:
				1839	BN_free(n);
				1840	return st;
				1841	}
				1842
				1843	static int test_dec2bn(void)
				1844	{
				1845	BIGNUM *bn = NULL;
				1846	int st = 0;
				1847
				1848	if (!TEST_int_eq(parsedecBN(&bn, "0"), 1)
				1849	\|\| !TEST_BN_eq_word(bn, 0)
				1850	\|\| !TEST_BN_eq_zero(bn)
				1851	\|\| !TEST_BN_le_zero(bn)
				1852	\|\| !TEST_BN_ge_zero(bn)
				1853	\|\| !TEST_BN_even(bn))
				1854	goto err;
				1855	BN_free(bn);
				1856	bn = NULL;
				1857
				1858	if (!TEST_int_eq(parsedecBN(&bn, "256"), 3)
				1859	\|\| !TEST_BN_eq_word(bn, 256)
				1860	\|\| !TEST_BN_ge_zero(bn)
				1861	\|\| !TEST_BN_gt_zero(bn)
				1862	\|\| !TEST_BN_ne_zero(bn)
				1863	\|\| !TEST_BN_even(bn))
				1864	goto err;
				1865	BN_free(bn);
				1866	bn = NULL;
				1867
				1868	if (!TEST_int_eq(parsedecBN(&bn, "-42"), 3)
				1869	\|\| !TEST_BN_abs_eq_word(bn, 42)
				1870	\|\| !TEST_BN_lt_zero(bn)
				1871	\|\| !TEST_BN_le_zero(bn)
				1872	\|\| !TEST_BN_ne_zero(bn)
				1873	\|\| !TEST_BN_even(bn))
				1874	goto err;
				1875	BN_free(bn);
				1876	bn = NULL;
				1877
				1878	if (!TEST_int_eq(parsedecBN(&bn, "1"), 1)
				1879	\|\| !TEST_BN_eq_word(bn, 1)
				1880	\|\| !TEST_BN_ne_zero(bn)
				1881	\|\| !TEST_BN_gt_zero(bn)
				1882	\|\| !TEST_BN_ge_zero(bn)
				1883	\|\| !TEST_BN_eq_one(bn)
				1884	\|\| !TEST_BN_odd(bn))
				1885	goto err;
				1886	BN_free(bn);
				1887	bn = NULL;
				1888
				1889	if (!TEST_int_eq(parsedecBN(&bn, "-0"), 2)
				1890	\|\| !TEST_BN_eq_zero(bn)
				1891	\|\| !TEST_BN_ge_zero(bn)
				1892	\|\| !TEST_BN_le_zero(bn)
				1893	\|\| !TEST_BN_even(bn))
				1894	goto err;
				1895	BN_free(bn);
				1896	bn = NULL;
				1897
				1898	if (!TEST_int_eq(parsedecBN(&bn, "42trailing garbage is ignored"), 2)
				1899	\|\| !TEST_BN_abs_eq_word(bn, 42)
				1900	\|\| !TEST_BN_ge_zero(bn)
				1901	\|\| !TEST_BN_gt_zero(bn)
				1902	\|\| !TEST_BN_ne_zero(bn)
				1903	\|\| !TEST_BN_even(bn))
				1904	goto err;
				1905
				1906	st = 1;
				1907	err:
				1908	BN_free(bn);
				1909	return st;
				1910	}
				1911
				1912	static int test_hex2bn(void)
				1913	{
				1914	BIGNUM *bn = NULL;
				1915	int st = 0;
				1916
				1917	if (!TEST_int_eq(parseBN(&bn, "0"), 1)
				1918	\|\| !TEST_BN_eq_zero(bn)
				1919	\|\| !TEST_BN_ge_zero(bn)
				1920	\|\| !TEST_BN_even(bn))
				1921	goto err;
				1922	BN_free(bn);
				1923	bn = NULL;
				1924
				1925	if (!TEST_int_eq(parseBN(&bn, "256"), 3)
				1926	\|\| !TEST_BN_eq_word(bn, 0x256)
				1927	\|\| !TEST_BN_ge_zero(bn)
				1928	\|\| !TEST_BN_gt_zero(bn)
				1929	\|\| !TEST_BN_ne_zero(bn)
				1930	\|\| !TEST_BN_even(bn))
				1931	goto err;
				1932	BN_free(bn);
				1933	bn = NULL;
				1934
				1935	if (!TEST_int_eq(parseBN(&bn, "-42"), 3)
				1936	\|\| !TEST_BN_abs_eq_word(bn, 0x42)
				1937	\|\| !TEST_BN_lt_zero(bn)
				1938	\|\| !TEST_BN_le_zero(bn)
				1939	\|\| !TEST_BN_ne_zero(bn)
				1940	\|\| !TEST_BN_even(bn))
				1941	goto err;
				1942	BN_free(bn);
				1943	bn = NULL;
				1944
				1945	if (!TEST_int_eq(parseBN(&bn, "cb"), 2)
				1946	\|\| !TEST_BN_eq_word(bn, 0xCB)
				1947	\|\| !TEST_BN_ge_zero(bn)
				1948	\|\| !TEST_BN_gt_zero(bn)
				1949	\|\| !TEST_BN_ne_zero(bn)
				1950	\|\| !TEST_BN_odd(bn))
				1951	goto err;
				1952	BN_free(bn);
				1953	bn = NULL;
				1954
				1955	if (!TEST_int_eq(parseBN(&bn, "-0"), 2)
				1956	\|\| !TEST_BN_eq_zero(bn)
				1957	\|\| !TEST_BN_ge_zero(bn)
				1958	\|\| !TEST_BN_le_zero(bn)
				1959	\|\| !TEST_BN_even(bn))
				1960	goto err;
				1961	BN_free(bn);
				1962	bn = NULL;
				1963
				1964	if (!TEST_int_eq(parseBN(&bn, "abctrailing garbage is ignored"), 3)
				1965	\|\| !TEST_BN_eq_word(bn, 0xabc)
				1966	\|\| !TEST_BN_ge_zero(bn)
				1967	\|\| !TEST_BN_gt_zero(bn)
				1968	\|\| !TEST_BN_ne_zero(bn)
				1969	\|\| !TEST_BN_even(bn))
				1970	goto err;
				1971	st = 1;
				1972
				1973	err:
				1974	BN_free(bn);
				1975	return st;
				1976	}
				1977
				1978	static int test_asc2bn(void)
				1979	{
				1980	BIGNUM *bn = NULL;
				1981	int st = 0;
				1982
				1983	if (!TEST_ptr(bn = BN_new()))
				1984	goto err;
				1985
				1986	if (!TEST_true(BN_asc2bn(&bn, "0"))
				1987	\|\| !TEST_BN_eq_zero(bn)
				1988	\|\| !TEST_BN_ge_zero(bn))
				1989	goto err;
				1990
				1991	if (!TEST_true(BN_asc2bn(&bn, "256"))
				1992	\|\| !TEST_BN_eq_word(bn, 256)
				1993	\|\| !TEST_BN_ge_zero(bn))
				1994	goto err;
				1995
				1996	if (!TEST_true(BN_asc2bn(&bn, "-42"))
				1997	\|\| !TEST_BN_abs_eq_word(bn, 42)
				1998	\|\| !TEST_BN_lt_zero(bn))
				1999	goto err;
				2000
				2001	if (!TEST_true(BN_asc2bn(&bn, "0x1234"))
				2002	\|\| !TEST_BN_eq_word(bn, 0x1234)
				2003	\|\| !TEST_BN_ge_zero(bn))
				2004	goto err;
				2005
				2006	if (!TEST_true(BN_asc2bn(&bn, "0X1234"))
				2007	\|\| !TEST_BN_eq_word(bn, 0x1234)
				2008	\|\| !TEST_BN_ge_zero(bn))
				2009	goto err;
				2010
				2011	if (!TEST_true(BN_asc2bn(&bn, "-0xabcd"))
				2012	\|\| !TEST_BN_abs_eq_word(bn, 0xabcd)
				2013	\|\| !TEST_BN_lt_zero(bn))
				2014	goto err;
				2015
				2016	if (!TEST_true(BN_asc2bn(&bn, "-0"))
				2017	\|\| !TEST_BN_eq_zero(bn)
				2018	\|\| !TEST_BN_ge_zero(bn))
				2019	goto err;
				2020
				2021	if (!TEST_true(BN_asc2bn(&bn, "123trailing garbage is ignored"))
				2022	\|\| !TEST_BN_eq_word(bn, 123)
				2023	\|\| !TEST_BN_ge_zero(bn))
				2024	goto err;
				2025
				2026	st = 1;
				2027	err:
				2028	BN_free(bn);
				2029	return st;
				2030	}
				2031
				2032	static const MPITEST kMPITests[] = {
				2033	{"0", "\x00\x00\x00\x00", 4},
				2034	{"1", "\x00\x00\x00\x01\x01", 5},
				2035	{"-1", "\x00\x00\x00\x01\x81", 5},
				2036	{"128", "\x00\x00\x00\x02\x00\x80", 6},
				2037	{"256", "\x00\x00\x00\x02\x01\x00", 6},
				2038	{"-256", "\x00\x00\x00\x02\x81\x00", 6},
				2039	};
				2040
				2041	static int test_mpi(int i)
				2042	{
				2043	uint8_t scratch[8];
				2044	const MPITEST *test = &kMPITests[i];
				2045	size_t mpi_len, mpi_len2;
				2046	BIGNUM *bn = NULL;
				2047	BIGNUM *bn2 = NULL;
				2048	int st = 0;
				2049
				2050	if (!TEST_ptr(bn = BN_new())
				2051	\|\| !TEST_true(BN_asc2bn(&bn, test->base10)))
				2052	goto err;
				2053	mpi_len = BN_bn2mpi(bn, NULL);
				2054	if (!TEST_size_t_le(mpi_len, sizeof(scratch)))
				2055	goto err;
				2056
				2057	if (!TEST_size_t_eq(mpi_len2 = BN_bn2mpi(bn, scratch), mpi_len)
				2058	\|\| !TEST_mem_eq(test->mpi, test->mpi_len, scratch, mpi_len))
				2059	goto err;
				2060
				2061	if (!TEST_ptr(bn2 = BN_mpi2bn(scratch, mpi_len, NULL)))
				2062	goto err;
				2063
				2064	if (!TEST_BN_eq(bn, bn2)) {
				2065	BN_free(bn2);
				2066	goto err;
				2067	}
				2068	BN_free(bn2);
				2069
				2070	st = 1;
				2071	err:
				2072	BN_free(bn);
				2073	return st;
				2074	}
				2075
				2076	static int test_rand(void)
				2077	{
				2078	BIGNUM *bn = NULL;
				2079	int st = 0;
				2080
				2081	if (!TEST_ptr(bn = BN_new()))
				2082	return 0;
				2083
				2084	/* Test BN_rand for degenerate cases with \|top\| and \|bottom\| parameters. */
				2085	if (!TEST_false(BN_rand(bn, 0, 0 /* top / , 0 / bottom */ ))
				2086	\|\| !TEST_false(BN_rand(bn, 0, 1 /* top / , 1 / bottom */ ))
				2087	\|\| !TEST_true(BN_rand(bn, 1, 0 /* top / , 0 / bottom */ ))
				2088	\|\| !TEST_BN_eq_one(bn)
				2089	\|\| !TEST_false(BN_rand(bn, 1, 1 /* top / , 0 / bottom */ ))
				2090	\|\| !TEST_true(BN_rand(bn, 1, -1 /* top / , 1 / bottom */ ))
				2091	\|\| !TEST_BN_eq_one(bn)
				2092	\|\| !TEST_true(BN_rand(bn, 2, 1 /* top / , 0 / bottom */ ))
				2093	\|\| !TEST_BN_eq_word(bn, 3))
				2094	goto err;
				2095
				2096	st = 1;
				2097	err:
				2098	BN_free(bn);
				2099	return st;
				2100	}
				2101
				2102	static int test_negzero(void)
				2103	{
				2104	BIGNUM a = NULL, b = NULL, c = NULL, d = NULL;
				2105	BIGNUM numerator = NULL, denominator = NULL;
				2106	int consttime, st = 0;
				2107
				2108	if (!TEST_ptr(a = BN_new())
				2109	\|\| !TEST_ptr(b = BN_new())
				2110	\|\| !TEST_ptr(c = BN_new())
				2111	\|\| !TEST_ptr(d = BN_new()))
				2112	goto err;
				2113
				2114	/* Test that BN_mul never gives negative zero. */
				2115	if (!TEST_true(BN_set_word(a, 1)))
				2116	goto err;
				2117	BN_set_negative(a, 1);
				2118	BN_zero(b);
				2119	if (!TEST_true(BN_mul(c, a, b, ctx)))
				2120	goto err;
				2121	if (!TEST_BN_eq_zero(c)
				2122	\|\| !TEST_BN_ge_zero(c))
				2123	goto err;
				2124
				2125	for (consttime = 0; consttime < 2; consttime++) {
				2126	if (!TEST_ptr(numerator = BN_new())
				2127	\|\| !TEST_ptr(denominator = BN_new()))
				2128	goto err;
				2129	if (consttime) {
				2130	BN_set_flags(numerator, BN_FLG_CONSTTIME);
				2131	BN_set_flags(denominator, BN_FLG_CONSTTIME);
				2132	}
				2133	/* Test that BN_div never gives negative zero in the quotient. */
				2134	if (!TEST_true(BN_set_word(numerator, 1))
				2135	\|\| !TEST_true(BN_set_word(denominator, 2)))
				2136	goto err;
				2137	BN_set_negative(numerator, 1);
				2138	if (!TEST_true(BN_div(a, b, numerator, denominator, ctx))
				2139	\|\| !TEST_BN_eq_zero(a)
				2140	\|\| !TEST_BN_ge_zero(a))
				2141	goto err;
				2142
				2143	/* Test that BN_div never gives negative zero in the remainder. */
				2144	if (!TEST_true(BN_set_word(denominator, 1))
				2145	\|\| !TEST_true(BN_div(a, b, numerator, denominator, ctx))
				2146	\|\| !TEST_BN_eq_zero(b)
				2147	\|\| !TEST_BN_ge_zero(b))
				2148	goto err;
				2149	BN_free(numerator);
				2150	BN_free(denominator);
				2151	numerator = denominator = NULL;
				2152	}
				2153
				2154	/* Test that BN_set_negative will not produce a negative zero. */
				2155	BN_zero(a);
				2156	BN_set_negative(a, 1);
				2157	if (BN_is_negative(a))
				2158	goto err;
				2159	st = 1;
				2160
				2161	err:
				2162	BN_free(a);
				2163	BN_free(b);
				2164	BN_free(c);
				2165	BN_free(d);
				2166	BN_free(numerator);
				2167	BN_free(denominator);
				2168	return st;
				2169	}
				2170
				2171	static int test_badmod(void)
				2172	{
				2173	BIGNUM a = NULL, b = NULL, *zero = NULL;
				2174	BN_MONT_CTX *mont = NULL;
				2175	int st = 0;
				2176
				2177	if (!TEST_ptr(a = BN_new())
				2178	\|\| !TEST_ptr(b = BN_new())
				2179	\|\| !TEST_ptr(zero = BN_new())
				2180	\|\| !TEST_ptr(mont = BN_MONT_CTX_new()))
				2181	goto err;
				2182	BN_zero(zero);
				2183
				2184	if (!TEST_false(BN_div(a, b, BN_value_one(), zero, ctx)))
				2185	goto err;
				2186	ERR_clear_error();
				2187
				2188	if (!TEST_false(BN_mod_mul(a, BN_value_one(), BN_value_one(), zero, ctx)))
				2189	goto err;
				2190	ERR_clear_error();
				2191
				2192	if (!TEST_false(BN_mod_exp(a, BN_value_one(), BN_value_one(), zero, ctx)))
				2193	goto err;
				2194	ERR_clear_error();
				2195
				2196	if (!TEST_false(BN_mod_exp_mont(a, BN_value_one(), BN_value_one(),
				2197	zero, ctx, NULL)))
				2198	goto err;
				2199	ERR_clear_error();
				2200
				2201	if (!TEST_false(BN_mod_exp_mont_consttime(a, BN_value_one(), BN_value_one(),
				2202	zero, ctx, NULL)))
				2203	goto err;
				2204	ERR_clear_error();
				2205
				2206	if (!TEST_false(BN_MONT_CTX_set(mont, zero, ctx)))
				2207	goto err;
				2208	ERR_clear_error();
				2209
				2210	/* Some operations also may not be used with an even modulus. */
				2211	if (!TEST_true(BN_set_word(b, 16)))
				2212	goto err;
				2213
				2214	if (!TEST_false(BN_MONT_CTX_set(mont, b, ctx)))
				2215	goto err;
				2216	ERR_clear_error();
				2217
				2218	if (!TEST_false(BN_mod_exp_mont(a, BN_value_one(), BN_value_one(),
				2219	b, ctx, NULL)))
				2220	goto err;
				2221	ERR_clear_error();
				2222
				2223	if (!TEST_false(BN_mod_exp_mont_consttime(a, BN_value_one(), BN_value_one(),
				2224	b, ctx, NULL)))
				2225	goto err;
				2226	ERR_clear_error();
				2227
				2228	st = 1;
				2229	err:
				2230	BN_free(a);
				2231	BN_free(b);
				2232	BN_free(zero);
				2233	BN_MONT_CTX_free(mont);
				2234	return st;
				2235	}
				2236
				2237	static int test_expmodzero(void)
				2238	{
				2239	BIGNUM a = NULL, r = NULL, *zero = NULL;
				2240	int st = 0;
				2241
				2242	if (!TEST_ptr(zero = BN_new())
				2243	\|\| !TEST_ptr(a = BN_new())
				2244	\|\| !TEST_ptr(r = BN_new()))
				2245	goto err;
				2246	BN_zero(zero);
				2247
				2248	if (!TEST_true(BN_mod_exp(r, a, zero, BN_value_one(), NULL))
				2249	\|\| !TEST_BN_eq_zero(r)
				2250	\|\| !TEST_true(BN_mod_exp_mont(r, a, zero, BN_value_one(),
				2251	NULL, NULL))
				2252	\|\| !TEST_BN_eq_zero(r)
				2253	\|\| !TEST_true(BN_mod_exp_mont_consttime(r, a, zero,
				2254	BN_value_one(),
				2255	NULL, NULL))
				2256	\|\| !TEST_BN_eq_zero(r)
				2257	\|\| !TEST_true(BN_mod_exp_mont_word(r, 42, zero,
				2258	BN_value_one(), NULL, NULL))
				2259	\|\| !TEST_BN_eq_zero(r))
				2260	goto err;
				2261
				2262	st = 1;
				2263	err:
				2264	BN_free(zero);
				2265	BN_free(a);
				2266	BN_free(r);
				2267	return st;
				2268	}
				2269
				2270	static int test_expmodone(void)
				2271	{
				2272	int ret = 0, i;
				2273	BIGNUM *r = BN_new();
				2274	BIGNUM *a = BN_new();
				2275	BIGNUM *p = BN_new();
				2276	BIGNUM *m = BN_new();
				2277
				2278	if (!TEST_ptr(r)
				2279	\|\| !TEST_ptr(a)
				2280	\|\| !TEST_ptr(p)
				2281	\|\| !TEST_ptr(p)
				2282	\|\| !TEST_ptr(m)
				2283	\|\| !TEST_true(BN_set_word(a, 1))
				2284	\|\| !TEST_true(BN_set_word(p, 0))
				2285	\|\| !TEST_true(BN_set_word(m, 1)))
				2286	goto err;
				2287
				2288	/* Calculate r = 1 ^ 0 mod 1, and check the result is always 0 */
				2289	for (i = 0; i < 2; i++) {
				2290	if (!TEST_true(BN_mod_exp(r, a, p, m, NULL))
				2291	\|\| !TEST_BN_eq_zero(r)
				2292	\|\| !TEST_true(BN_mod_exp_mont(r, a, p, m, NULL, NULL))
				2293	\|\| !TEST_BN_eq_zero(r)
				2294	\|\| !TEST_true(BN_mod_exp_mont_consttime(r, a, p, m, NULL, NULL))
				2295	\|\| !TEST_BN_eq_zero(r)
				2296	\|\| !TEST_true(BN_mod_exp_mont_word(r, 1, p, m, NULL, NULL))
				2297	\|\| !TEST_BN_eq_zero(r)
				2298	\|\| !TEST_true(BN_mod_exp_simple(r, a, p, m, NULL))
				2299	\|\| !TEST_BN_eq_zero(r)
				2300	\|\| !TEST_true(BN_mod_exp_recp(r, a, p, m, NULL))
				2301	\|\| !TEST_BN_eq_zero(r))
				2302	goto err;
				2303	/* Repeat for r = 1 ^ 0 mod -1 */
				2304	if (i == 0)
				2305	BN_set_negative(m, 1);
				2306	}
				2307
				2308	ret = 1;
				2309	err:
				2310	BN_free(r);
				2311	BN_free(a);
				2312	BN_free(p);
				2313	BN_free(m);
				2314	return ret;
				2315	}
				2316
				2317	static int test_smallprime(int kBits)
				2318	{
				2319	BIGNUM *r;
				2320	int st = 0;
				2321
				2322	if (!TEST_ptr(r = BN_new()))
				2323	goto err;
				2324
				2325	if (kBits <= 1) {
				2326	if (!TEST_false(BN_generate_prime_ex(r, kBits, 0,
				2327	NULL, NULL, NULL)))
				2328	goto err;
				2329	} else {
				2330	if (!TEST_true(BN_generate_prime_ex(r, kBits, 0,
				2331	NULL, NULL, NULL))
				2332	\|\| !TEST_int_eq(BN_num_bits(r), kBits))
				2333	goto err;
				2334	}
				2335
				2336	st = 1;
				2337	err:
				2338	BN_free(r);
				2339	return st;
				2340	}
				2341
				2342	static int test_smallsafeprime(int kBits)
				2343	{
				2344	BIGNUM *r;
				2345	int st = 0;
				2346
				2347	if (!TEST_ptr(r = BN_new()))
				2348	goto err;
				2349
				2350	if (kBits <= 5 && kBits != 3) {
				2351	if (!TEST_false(BN_generate_prime_ex(r, kBits, 1,
				2352	NULL, NULL, NULL)))
				2353	goto err;
				2354	} else {
				2355	if (!TEST_true(BN_generate_prime_ex(r, kBits, 1,
				2356	NULL, NULL, NULL))
				2357	\|\| !TEST_int_eq(BN_num_bits(r), kBits))
				2358	goto err;
				2359	}
				2360
				2361	st = 1;
				2362	err:
				2363	BN_free(r);
				2364	return st;
				2365	}
				2366
				2367	static int primes[] = { 2, 3, 5, 7, 17863 };
				2368
				2369	static int test_is_prime(int i)
				2370	{
				2371	int ret = 0;
				2372	BIGNUM *r = NULL;
				2373	int trial;
				2374
				2375	if (!TEST_ptr(r = BN_new()))
				2376	goto err;
				2377
				2378	for (trial = 0; trial <= 1; ++trial) {
				2379	if (!TEST_true(BN_set_word(r, primes[i]))
				2380	\|\| !TEST_int_eq(BN_is_prime_fasttest_ex(r, 1, ctx, trial, NULL),
				2381	1))
				2382	goto err;
				2383	}
				2384
				2385	ret = 1;
				2386	err:
				2387	BN_free(r);
				2388	return ret;
				2389	}
				2390
				2391	static int not_primes[] = { -1, 0, 1, 4 };
				2392
				2393	static int test_not_prime(int i)
				2394	{
				2395	int ret = 0;
				2396	BIGNUM *r = NULL;
				2397	int trial;
				2398
				2399	if (!TEST_ptr(r = BN_new()))
				2400	goto err;
				2401
				2402	for (trial = 0; trial <= 1; ++trial) {
				2403	if (!TEST_true(BN_set_word(r, not_primes[i]))
				2404	\|\| !TEST_false(BN_is_prime_fasttest_ex(r, 1, ctx, trial, NULL)))
				2405	goto err;
				2406	}
				2407
				2408	ret = 1;
				2409	err:
				2410	BN_free(r);
				2411	return ret;
				2412	}
				2413
				2414	static int test_ctx_set_ct_flag(BN_CTX *c)
				2415	{
				2416	int st = 0;
				2417	size_t i;
				2418	BIGNUM *b[15];
				2419
				2420	BN_CTX_start(c);
				2421	for (i = 0; i < OSSL_NELEM(b); i++) {
				2422	if (!TEST_ptr(b[i] = BN_CTX_get(c)))
				2423	goto err;
				2424	if (i % 2 == 1)
				2425	BN_set_flags(b[i], BN_FLG_CONSTTIME);
				2426	}
				2427
				2428	st = 1;
				2429	err:
				2430	BN_CTX_end(c);
				2431	return st;
				2432	}
				2433
				2434	static int test_ctx_check_ct_flag(BN_CTX *c)
				2435	{
				2436	int st = 0;
				2437	size_t i;
				2438	BIGNUM *b[30];
				2439
				2440	BN_CTX_start(c);
				2441	for (i = 0; i < OSSL_NELEM(b); i++) {
				2442	if (!TEST_ptr(b[i] = BN_CTX_get(c)))
				2443	goto err;
				2444	if (!TEST_false(BN_get_flags(b[i], BN_FLG_CONSTTIME)))
				2445	goto err;
				2446	}
				2447
				2448	st = 1;
				2449	err:
				2450	BN_CTX_end(c);
				2451	return st;
				2452	}
				2453
				2454	static int test_ctx_consttime_flag(void)
				2455	{
				2456	/*-
				2457	* The constant-time flag should not "leak" among BN_CTX frames:
				2458	*
				2459	* - test_ctx_set_ct_flag() starts a frame in the given BN_CTX and
				2460	* sets the BN_FLG_CONSTTIME flag on some of the BIGNUMs obtained
				2461	* from the frame before ending it.
				2462	* - test_ctx_check_ct_flag() then starts a new frame and gets a
				2463	* number of BIGNUMs from it. In absence of leaks, none of the
				2464	* BIGNUMs in the new frame should have BN_FLG_CONSTTIME set.
				2465	*
				2466	* In actual BN_CTX usage inside libcrypto the leak could happen at
				2467	* any depth level in the BN_CTX stack, with varying results
				2468	* depending on the patterns of sibling trees of nested function
				2469	* calls sharing the same BN_CTX object, and the effect of
				2470	* unintended BN_FLG_CONSTTIME on the called BN_* functions.
				2471	*
				2472	* This simple unit test abstracts away this complexity and verifies
				2473	* that the leak does not happen between two sibling functions
				2474	* sharing the same BN_CTX object at the same level of nesting.
				2475	*
				2476	*/
				2477	BN_CTX *nctx = NULL;
				2478	BN_CTX *sctx = NULL;
				2479	size_t i = 0;
				2480	int st = 0;
				2481
				2482	if (!TEST_ptr(nctx = BN_CTX_new())
				2483	\|\| !TEST_ptr(sctx = BN_CTX_secure_new()))
				2484	goto err;
				2485
				2486	for (i = 0; i < 2; i++) {
				2487	BN_CTX *c = i == 0 ? nctx : sctx;
				2488	if (!TEST_true(test_ctx_set_ct_flag(c))
				2489	\|\| !TEST_true(test_ctx_check_ct_flag(c)))
				2490	goto err;
				2491	}
				2492
				2493	st = 1;
				2494	err:
				2495	BN_CTX_free(nctx);
				2496	BN_CTX_free(sctx);
				2497	return st;
				2498	}
				2499
				2500	static int test_gcd_prime(void)
				2501	{
				2502	BIGNUM a = NULL, b = NULL, *gcd = NULL;
				2503	int i, st = 0;
				2504
				2505	if (!TEST_ptr(a = BN_new())
				2506	\|\| !TEST_ptr(b = BN_new())
				2507	\|\| !TEST_ptr(gcd = BN_new()))
				2508	goto err;
				2509
				2510	if (!TEST_true(BN_generate_prime_ex(a, 1024, 0, NULL, NULL, NULL)))
				2511	goto err;
				2512	for (i = 0; i < NUM0; i++) {
				2513	if (!TEST_true(BN_generate_prime_ex(b, 1024, 0,
				2514	NULL, NULL, NULL))
				2515	\|\| !TEST_true(BN_gcd(gcd, a, b, ctx))
				2516	\|\| !TEST_true(BN_is_one(gcd)))
				2517	goto err;
				2518	}
				2519
				2520	st = 1;
				2521	err:
				2522	BN_free(a);
				2523	BN_free(b);
				2524	BN_free(gcd);
				2525	return st;
				2526	}
				2527
				2528	typedef struct mod_exp_test_st
				2529	{
				2530	const char *base;
				2531	const char *exp;
				2532	const char *mod;
				2533	const char *res;
				2534	} MOD_EXP_TEST;
				2535
				2536	static const MOD_EXP_TEST ModExpTests[] = {
				2537	/* original test vectors for rsaz_512_sqr bug, by OSS-Fuzz */
				2538	{
				2539	"1166180238001879113042182292626169621106255558914000595999312084"
				2540	"4627946820899490684928760491249738643524880720584249698100907201"
				2541	"002086675047927600340800371",
				2542	"8000000000000000000000000000000000000000000000000000000000000000"
				2543	"0000000000000000000000000000000000000000000000000000000000000000"
				2544	"00000000",
				2545	"1340780792684523720980737645613191762604395855615117867483316354"
				2546	"3294276330515137663421134775482798690129946803802212663956180562"
				2547	"088664022929883876655300863",
				2548	"8243904058268085430037326628480645845409758077568738532059032482"
				2549	"8294114415890603594730158120426756266457928475330450251339773498"
				2550	"26758407619521544102068438"
				2551	},
				2552	{
				2553	"4974270041410803822078866696159586946995877618987010219312844726"
				2554	"0284386121835740784990869050050504348861513337232530490826340663"
				2555	"197278031692737429054",
				2556	"4974270041410803822078866696159586946995877428188754995041148539"
				2557	"1663243362592271353668158565195557417149981094324650322556843202"
				2558	"946445882670777892608",
				2559	"1340780716511420227215592830971452482815377482627251725537099028"
				2560	"4429769497230131760206012644403029349547320953206103351725462999"
				2561	"947509743623340557059752191",
				2562	"5296244594780707015616522701706118082963369547253192207884519362"
				2563	"1767869984947542695665420219028522815539559194793619684334900442"
				2564	"49304558011362360473525933"
				2565	},
				2566	/* test vectors for rsaz_512_srq bug, with rcx/rbx=1 */
				2567	{ /* between first and second iteration */
				2568	"5148719036160389201525610950887605325980251964889646556085286545"
				2569	"3931548809178823413169359635978762036512397113080988070677858033"
				2570	"36463909753993540214027190",
				2571	"6703903964971298549787012499102923063739682910296196688861780721"
				2572	"8608820150367734884009371490834517138450159290932430254268769414"
				2573	"05973284973216824503042158",
				2574	"6703903964971298549787012499102923063739682910296196688861780721"
				2575	"8608820150367734884009371490834517138450159290932430254268769414"
				2576	"05973284973216824503042159",
				2577	"1"
				2578	},
				2579	{ /* between second and third iteration */
				2580	"8908340854353752577419678771330460827942371434853054158622636544"
				2581	"8151360109722890949471912566649465436296659601091730745087014189"
				2582	"2672764191218875181826063",
				2583	"6703903964971298549787012499102923063739682910296196688861780721"
				2584	"8608820150367734884009371490834517138450159290932430254268769414"
				2585	"05973284973216824503042158",
				2586	"6703903964971298549787012499102923063739682910296196688861780721"
				2587	"8608820150367734884009371490834517138450159290932430254268769414"
				2588	"05973284973216824503042159",
				2589	"1"
				2590	},
				2591	{ /* between third and fourth iteration */
				2592	"3427446396505596330634350984901719674479522569002785244080234738"
				2593	"4288743635435746136297299366444548736533053717416735379073185344"
				2594	"26985272974404612945608761",
				2595	"6703903964971298549787012499102923063739682910296196688861780721"
				2596	"8608820150367734884009371490834517138450159290932430254268769414"
				2597	"05973284973216824503042158",
				2598	"6703903964971298549787012499102923063739682910296196688861780721"
				2599	"8608820150367734884009371490834517138450159290932430254268769414"
				2600	"05973284973216824503042159",
				2601	"1"
				2602	},
				2603	{ /* between fourth and fifth iteration */
				2604	"3472743044917564564078857826111874560045331237315597383869652985"
				2605	"6919870028890895988478351133601517365908445058405433832718206902"
				2606	"4088133164805266956353542",
				2607	"6703903964971298549787012499102923063739682910296196688861780721"
				2608	"8608820150367734884009371490834517138450159290932430254268769414"
				2609	"05973284973216824503042158",
				2610	"6703903964971298549787012499102923063739682910296196688861780721"
				2611	"8608820150367734884009371490834517138450159290932430254268769414"
				2612	"05973284973216824503042159",
				2613	"1"
				2614	},
				2615	{ /* between fifth and sixth iteration */
				2616	"3608632990153469264412378349742339216742409743898601587274768025"
				2617	"0110772032985643555192767717344946174122842255204082586753499651"
				2618	"14483434992887431333675068",
				2619	"6703903964971298549787012499102923063739682910296196688861780721"
				2620	"8608820150367734884009371490834517138450159290932430254268769414"
				2621	"05973284973216824503042158",
				2622	"6703903964971298549787012499102923063739682910296196688861780721"
				2623	"8608820150367734884009371490834517138450159290932430254268769414"
				2624	"05973284973216824503042159",
				2625	"1"
				2626	},
				2627	{ /* between sixth and seventh iteration */
				2628	"8455374370234070242910508226941981520235709767260723212165264877"
				2629	"8689064388017521524568434328264431772644802567028663962962025746"
				2630	"9283458217850119569539086",
				2631	"6703903964971298549787012499102923063739682910296196688861780721"
				2632	"8608820150367734884009371490834517138450159290932430254268769414"
				2633	"05973284973216824503042158",
				2634	"6703903964971298549787012499102923063739682910296196688861780721"
				2635	"8608820150367734884009371490834517138450159290932430254268769414"
				2636	"05973284973216824503042159",
				2637	"1"
				2638	},
				2639	{ /* between seventh and eighth iteration */
				2640	"5155371529688532178421209781159131443543419764974688878527112131"
				2641	"7446518205609427412336183157918981038066636807317733319323257603"
				2642	"04416292040754017461076359",
				2643	"1005585594745694782468051874865438459560952436544429503329267108"
				2644	"2791323022555160232601405723625177570767523893639864538140315412"
				2645	"108959927459825236754563832",
				2646	"1005585594745694782468051874865438459560952436544429503329267108"
				2647	"2791323022555160232601405723625177570767523893639864538140315412"
				2648	"108959927459825236754563833",
				2649	"1"
				2650	},
				2651	/* test vectors for rsaz_512_srq bug, with rcx/rbx=2 */
				2652	{ /* between first and second iteration */
				2653	"3155666506033786929967309937640790361084670559125912405342594979"
				2654	"4345142818528956285490897841406338022378565972533508820577760065"
				2655	"58494345853302083699912572",
				2656	"6703903964971298549787012499102923063739682910296196688861780721"
				2657	"8608820150367734884009371490834517138450159290932430254268769414"
				2658	"05973284973216824503042158",
				2659	"6703903964971298549787012499102923063739682910296196688861780721"
				2660	"8608820150367734884009371490834517138450159290932430254268769414"
				2661	"05973284973216824503042159",
				2662	"1"
				2663	},
				2664	{ /* between second and third iteration */
				2665	"3789819583801342198190405714582958759005991915505282362397087750"
				2666	"4213544724644823098843135685133927198668818185338794377239590049"
				2667	"41019388529192775771488319",
				2668	"6703903964971298549787012499102923063739682910296196688861780721"
				2669	"8608820150367734884009371490834517138450159290932430254268769414"
				2670	"05973284973216824503042158",
				2671	"6703903964971298549787012499102923063739682910296196688861780721"
				2672	"8608820150367734884009371490834517138450159290932430254268769414"
				2673	"05973284973216824503042159",
				2674	"1"
				2675	},
				2676	{ /* between third and forth iteration */
				2677	"4695752552040706867080542538786056470322165281761525158189220280"
				2678	"4025547447667484759200742764246905647644662050122968912279199065"
				2679	"48065034299166336940507214",
				2680	"6703903964971298549787012499102923063739682910296196688861780721"
				2681	"8608820150367734884009371490834517138450159290932430254268769414"
				2682	"05973284973216824503042158",
				2683	"6703903964971298549787012499102923063739682910296196688861780721"
				2684	"8608820150367734884009371490834517138450159290932430254268769414"
				2685	"05973284973216824503042159",
				2686	"1"
				2687	},
				2688	{ /* between forth and fifth iteration */
				2689	"2159140240970485794188159431017382878636879856244045329971239574"
				2690	"8919691133560661162828034323196457386059819832804593989740268964"
				2691	"74502911811812651475927076",
				2692	"6703903964971298549787012499102923063739682910296196688861780721"
				2693	"8608820150367734884009371490834517138450159290932430254268769414"
				2694	"05973284973216824503042158",
				2695	"6703903964971298549787012499102923063739682910296196688861780721"
				2696	"8608820150367734884009371490834517138450159290932430254268769414"
				2697	"05973284973216824503042159",
				2698	"1"
				2699	},
				2700	{ /* between fifth and sixth iteration */
				2701	"5239312332984325668414624633307915097111691815000872662334695514"
				2702	"5436533521392362443557163429336808208137221322444780490437871903"
				2703	"99972784701334569424519255",
				2704	"6703903964971298549787012499102923063739682910296196688861780721"
				2705	"8608820150367734884009371490834517138450159290932430254268769414"
				2706	"05973284973216824503042158",
				2707	"6703903964971298549787012499102923063739682910296196688861780721"
				2708	"8608820150367734884009371490834517138450159290932430254268769414"
				2709	"05973284973216824503042159",
				2710	"1"
				2711	},
				2712	{ /* between sixth and seventh iteration */
				2713	"1977953647322612860406858017869125467496941904523063466791308891"
				2714	"1172796739058531929470539758361774569875505293428856181093904091"
				2715	"33788264851714311303725089",
				2716	"6703903964971298549787012499102923063739682910296196688861780721"
				2717	"8608820150367734884009371490834517138450159290932430254268769414"
				2718	"05973284973216824503042158",
				2719	"6703903964971298549787012499102923063739682910296196688861780721"
				2720	"8608820150367734884009371490834517138450159290932430254268769414"
				2721	"05973284973216824503042159",
				2722	"1"
				2723	},
				2724	{ /* between seventh and eighth iteration */
				2725	"6456987954117763835533395796948878140715006860263624787492985786"
				2726	"8514630216966738305923915688821526449499763719943997120302368211"
				2727	"04813318117996225041943964",
				2728	"1340780792994259709957402499820584612747936582059239337772356144"
				2729	"3721764030073546976801874298166903427690031858186486050853753882"
				2730	"811946551499689575296532556",
				2731	"1340780792994259709957402499820584612747936582059239337772356144"
				2732	"3721764030073546976801874298166903427690031858186486050853753882"
				2733	"811946551499689575296532557",
				2734	"1"
				2735	}
				2736	};
				2737
				2738	static int test_mod_exp(int i)
				2739	{
				2740	const MOD_EXP_TEST *test = &ModExpTests[i];
				2741	int res = 0;
				2742	BIGNUM* result = NULL;
				2743	BIGNUM base = NULL, exponent = NULL, *modulo = NULL;
				2744	char *s = NULL;
				2745
				2746	if (!TEST_ptr(result = BN_new())
				2747	\|\| !TEST_true(BN_dec2bn(&base, test->base))
				2748	\|\| !TEST_true(BN_dec2bn(&exponent, test->exp))
				2749	\|\| !TEST_true(BN_dec2bn(&modulo, test->mod)))
				2750	goto err;
				2751
				2752	if (!TEST_int_eq(BN_mod_exp(result, base, exponent, modulo, ctx), 1))
				2753	goto err;
				2754
				2755	if (!TEST_ptr(s = BN_bn2dec(result)))
				2756	goto err;
				2757
				2758	if (!TEST_mem_eq(s, strlen(s), test->res, strlen(test->res)))
				2759	goto err;
				2760
				2761	res = 1;
				2762
				2763	err:
				2764	OPENSSL_free(s);
				2765	BN_free(result);
				2766	BN_free(base);
				2767	BN_free(exponent);
				2768	BN_free(modulo);
				2769	return res;
				2770	}
				2771
				2772	static int test_mod_exp_consttime(int i)
				2773	{
				2774	const MOD_EXP_TEST *test = &ModExpTests[i];
				2775	int res = 0;
				2776	BIGNUM* result = NULL;
				2777	BIGNUM base = NULL, exponent = NULL, *modulo = NULL;
				2778	char *s = NULL;
				2779
				2780	if (!TEST_ptr(result = BN_new())
				2781	\|\| !TEST_true(BN_dec2bn(&base, test->base))
				2782	\|\| !TEST_true(BN_dec2bn(&exponent, test->exp))
				2783	\|\| !TEST_true(BN_dec2bn(&modulo, test->mod)))
				2784	goto err;
				2785
				2786	BN_set_flags(base, BN_FLG_CONSTTIME);
				2787	BN_set_flags(exponent, BN_FLG_CONSTTIME);
				2788	BN_set_flags(modulo, BN_FLG_CONSTTIME);
				2789
				2790	if (!TEST_int_eq(BN_mod_exp(result, base, exponent, modulo, ctx), 1))
				2791	goto err;
				2792
				2793	if (!TEST_ptr(s = BN_bn2dec(result)))
				2794	goto err;
				2795
				2796	if (!TEST_mem_eq(s, strlen(s), test->res, strlen(test->res)))
				2797	goto err;
				2798
				2799	res = 1;
				2800
				2801	err:
				2802	OPENSSL_free(s);
				2803	BN_free(result);
				2804	BN_free(base);
				2805	BN_free(exponent);
				2806	BN_free(modulo);
				2807	return res;
				2808	}
				2809
				2810	/*
				2811	* Regression test to ensure BN_mod_exp2_mont fails safely if argument m is
				2812	* zero.
				2813	*/
				2814	static int test_mod_exp2_mont(void)
				2815	{
				2816	int res = 0;
				2817	BIGNUM *exp_result = NULL;
				2818	BIGNUM exp_a1 = NULL, exp_p1 = NULL, exp_a2 = NULL, exp_p2 = NULL,
				2819	*exp_m = NULL;
				2820
				2821	if (!TEST_ptr(exp_result = BN_new())
				2822	\|\| !TEST_ptr(exp_a1 = BN_new())
				2823	\|\| !TEST_ptr(exp_p1 = BN_new())
				2824	\|\| !TEST_ptr(exp_a2 = BN_new())
				2825	\|\| !TEST_ptr(exp_p2 = BN_new())
				2826	\|\| !TEST_ptr(exp_m = BN_new()))
				2827	goto err;
				2828
				2829	if (!TEST_true(BN_one(exp_a1))
				2830	\|\| !TEST_true(BN_one(exp_p1))
				2831	\|\| !TEST_true(BN_one(exp_a2))
				2832	\|\| !TEST_true(BN_one(exp_p2)))
				2833	goto err;
				2834
				2835	BN_zero(exp_m);
				2836
				2837	/* input of 0 is even, so must fail */
				2838	if (!TEST_int_eq(BN_mod_exp2_mont(exp_result, exp_a1, exp_p1, exp_a2,
				2839	exp_p2, exp_m, ctx, NULL), 0))
				2840	goto err;
				2841
				2842	res = 1;
				2843
				2844	err:
				2845	BN_free(exp_result);
				2846	BN_free(exp_a1);
				2847	BN_free(exp_p1);
				2848	BN_free(exp_a2);
				2849	BN_free(exp_p2);
				2850	BN_free(exp_m);
				2851	return res;
				2852	}
				2853
				2854	static int file_test_run(STANZA *s)
				2855	{
				2856	static const FILETEST filetests[] = {
				2857	{"Sum", file_sum},
				2858	{"LShift1", file_lshift1},
				2859	{"LShift", file_lshift},
				2860	{"RShift", file_rshift},
				2861	{"Square", file_square},
				2862	{"Product", file_product},
				2863	{"Quotient", file_quotient},
				2864	{"ModMul", file_modmul},
				2865	{"ModExp", file_modexp},
				2866	{"Exp", file_exp},
				2867	{"ModSqrt", file_modsqrt},
				2868	{"GCD", file_gcd},
				2869	};
				2870	int numtests = OSSL_NELEM(filetests);
				2871	const FILETEST *tp = filetests;
				2872
				2873	for ( ; --numtests >= 0; tp++) {
				2874	if (findattr(s, tp->name) != NULL) {
				2875	if (!tp->func(s)) {
				2876	TEST_info("%s:%d: Failed %s test",
				2877	s->test_file, s->start, tp->name);
				2878	return 0;
				2879	}
				2880	return 1;
				2881	}
				2882	}
				2883	TEST_info("%s:%d: Unknown test", s->test_file, s->start);
				2884	return 0;
				2885	}
				2886
				2887	static int run_file_tests(int i)
				2888	{
				2889	STANZA *s = NULL;
				2890	char *testfile = test_get_argument(i);
				2891	int c;
				2892
				2893	if (!TEST_ptr(s = OPENSSL_zalloc(sizeof(*s))))
				2894	return 0;
				2895	if (!test_start_file(s, testfile)) {
				2896	OPENSSL_free(s);
				2897	return 0;
				2898	}
				2899
				2900	/* Read test file. */
				2901	while (!BIO_eof(s->fp) && test_readstanza(s)) {
				2902	if (s->numpairs == 0)
				2903	continue;
				2904	if (!file_test_run(s))
				2905	s->errors++;
				2906	s->numtests++;
				2907	test_clearstanza(s);
				2908	}
				2909	test_end_file(s);
				2910	c = s->errors;
				2911	OPENSSL_free(s);
				2912
				2913	return c == 0;
				2914	}
				2915
				2916
				2917	int setup_tests(void)
				2918	{
				2919	int n = test_get_argument_count();
				2920
				2921	if (!TEST_ptr(ctx = BN_CTX_new()))
				2922	return 0;
				2923
				2924	if (n == 0) {
				2925	ADD_TEST(test_sub);
				2926	ADD_TEST(test_div_recip);
				2927	ADD_ALL_TESTS(test_signed_mod_replace_ab, OSSL_NELEM(signed_mod_tests));
				2928	ADD_ALL_TESTS(test_signed_mod_replace_ba, OSSL_NELEM(signed_mod_tests));
				2929	ADD_TEST(test_mod);
				2930	ADD_TEST(test_modexp_mont5);
				2931	ADD_TEST(test_kronecker);
				2932	ADD_TEST(test_rand);
				2933	ADD_TEST(test_bn2padded);
				2934	ADD_TEST(test_dec2bn);
				2935	ADD_TEST(test_hex2bn);
				2936	ADD_TEST(test_asc2bn);
				2937	ADD_ALL_TESTS(test_mpi, (int)OSSL_NELEM(kMPITests));
				2938	ADD_TEST(test_negzero);
				2939	ADD_TEST(test_badmod);
				2940	ADD_TEST(test_expmodzero);
				2941	ADD_TEST(test_expmodone);
				2942	ADD_ALL_TESTS(test_smallprime, 16);
				2943	ADD_ALL_TESTS(test_smallsafeprime, 16);
				2944	ADD_TEST(test_swap);
				2945	ADD_TEST(test_ctx_consttime_flag);
				2946	#ifndef OPENSSL_NO_EC2M
				2947	ADD_TEST(test_gf2m_add);
				2948	ADD_TEST(test_gf2m_mod);
				2949	ADD_TEST(test_gf2m_mul);
				2950	ADD_TEST(test_gf2m_sqr);
				2951	ADD_TEST(test_gf2m_modinv);
				2952	ADD_TEST(test_gf2m_moddiv);
				2953	ADD_TEST(test_gf2m_modexp);
				2954	ADD_TEST(test_gf2m_modsqrt);
				2955	ADD_TEST(test_gf2m_modsolvequad);
				2956	#endif
				2957	ADD_ALL_TESTS(test_is_prime, (int)OSSL_NELEM(primes));
				2958	ADD_ALL_TESTS(test_not_prime, (int)OSSL_NELEM(not_primes));
				2959	ADD_TEST(test_gcd_prime);
				2960	ADD_ALL_TESTS(test_mod_exp, (int)OSSL_NELEM(ModExpTests));
				2961	ADD_ALL_TESTS(test_mod_exp_consttime, (int)OSSL_NELEM(ModExpTests));
				2962	ADD_TEST(test_mod_exp2_mont);
				2963	} else {
				2964	ADD_ALL_TESTS(run_file_tests, n);
				2965	}
				2966	return 1;
				2967	}
				2968
				2969	void cleanup_tests(void)
				2970	{
				2971	BN_CTX_free(ctx);
				2972	}