bntest.c@ 95218

Last change on this file since 95218 was 94404, checked in by vboxsync, 3 years ago
libs/openssl: Update to 3.0.2 and switch to it, bugref:10128
File size: 95.3 KB

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

Note: See TracBrowser for help on using the repository browser.

source: vbox/trunk/src/libs/openssl-3.0.3/test/bntest.c@ 95218

Download in other formats: