bntest.c@ 94403

最後變更在這個檔案從94403是 94320,由 vboxsync 提交於 3 年前
libs/openssl-3.0.1: Export to OSE and fix copyright headers in Makefiles, bugref:10128
檔案大小: 94.0 KB

行
1	/*
2	* Copyright 1995-2021 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	/* There are two possible answers. */
1736	if (!TEST_true(BN_mod_sqrt(ret, a, p, ctx))
1737	\|\| !TEST_true(BN_sub(ret2, p, ret)))
1738	goto err;
1739
1740	/* The first condition should NOT be a test. */
1741	if (BN_cmp(ret2, mod_sqrt) != 0
1742	&& !equalBN("sqrt(A) (mod P)", mod_sqrt, ret))
1743	goto err;
1744
1745	st = 1;
1746	err:
1747	BN_free(a);
1748	BN_free(p);
1749	BN_free(mod_sqrt);
1750	BN_free(ret);
1751	BN_free(ret2);
1752	return st;
1753	}
1754
1755	static int file_gcd(STANZA *s)
1756	{
1757	BIGNUM a = NULL, b = NULL, gcd = NULL, ret = NULL;
1758	int st = 0;
1759
1760	if (!TEST_ptr(a = getBN(s, "A"))
1761	\|\| !TEST_ptr(b = getBN(s, "B"))
1762	\|\| !TEST_ptr(gcd = getBN(s, "GCD"))
1763	\|\| !TEST_ptr(ret = BN_new()))
1764	goto err;
1765
1766	if (!TEST_true(BN_gcd(ret, a, b, ctx))
1767	\|\| !equalBN("gcd(A,B)", gcd, ret))
1768	goto err;
1769
1770	st = 1;
1771	err:
1772	BN_free(a);
1773	BN_free(b);
1774	BN_free(gcd);
1775	BN_free(ret);
1776	return st;
1777	}
1778
1779	static int test_bn2padded(void)
1780	{
1781	uint8_t zeros[256], out[256], reference[128];
1782	size_t bytes;
1783	BIGNUM *n;
1784	int st = 0;
1785
1786	/* Test edge case at 0. */
1787	if (!TEST_ptr((n = BN_new())))
1788	goto err;
1789	if (!TEST_int_eq(BN_bn2binpad(n, NULL, 0), 0))
1790	goto err;
1791	memset(out, -1, sizeof(out));
1792	if (!TEST_int_eq(BN_bn2binpad(n, out, sizeof(out)), sizeof(out)))
1793	goto err;
1794	memset(zeros, 0, sizeof(zeros));
1795	if (!TEST_mem_eq(zeros, sizeof(zeros), out, sizeof(out)))
1796	goto err;
1797
1798	/* Test a random numbers at various byte lengths. */
1799	for (bytes = 128 - 7; bytes <= 128; bytes++) {
1800	# define TOP_BIT_ON 0
1801	# define BOTTOM_BIT_NOTOUCH 0
1802	if (!TEST_true(BN_rand(n, bytes * 8, TOP_BIT_ON, BOTTOM_BIT_NOTOUCH)))
1803	goto err;
1804	if (!TEST_int_eq(BN_num_bytes(n), bytes)
1805	\|\| !TEST_int_eq(BN_bn2bin(n, reference), bytes))
1806	goto err;
1807	/* Empty buffer should fail. */
1808	if (!TEST_int_eq(BN_bn2binpad(n, NULL, 0), -1))
1809	goto err;
1810	/* One byte short should fail. */
1811	if (!TEST_int_eq(BN_bn2binpad(n, out, bytes - 1), -1))
1812	goto err;
1813	/* Exactly right size should encode. */
1814	if (!TEST_int_eq(BN_bn2binpad(n, out, bytes), bytes)
1815	\|\| !TEST_mem_eq(out, bytes, reference, bytes))
1816	goto err;
1817	/* Pad up one byte extra. */
1818	if (!TEST_int_eq(BN_bn2binpad(n, out, bytes + 1), bytes + 1)
1819	\|\| !TEST_mem_eq(out + 1, bytes, reference, bytes)
1820	\|\| !TEST_mem_eq(out, 1, zeros, 1))
1821	goto err;
1822	/* Pad up to 256. */
1823	if (!TEST_int_eq(BN_bn2binpad(n, out, sizeof(out)), sizeof(out))
1824	\|\| !TEST_mem_eq(out + sizeof(out) - bytes, bytes,
1825	reference, bytes)
1826	\|\| !TEST_mem_eq(out, sizeof(out) - bytes,
1827	zeros, sizeof(out) - bytes))
1828	goto err;
1829	}
1830
1831	st = 1;
1832	err:
1833	BN_free(n);
1834	return st;
1835	}
1836
1837	static int test_dec2bn(void)
1838	{
1839	BIGNUM *bn = NULL;
1840	int st = 0;
1841
1842	if (!TEST_int_eq(parsedecBN(&bn, "0"), 1)
1843	\|\| !TEST_BN_eq_word(bn, 0)
1844	\|\| !TEST_BN_eq_zero(bn)
1845	\|\| !TEST_BN_le_zero(bn)
1846	\|\| !TEST_BN_ge_zero(bn)
1847	\|\| !TEST_BN_even(bn))
1848	goto err;
1849	BN_free(bn);
1850	bn = NULL;
1851
1852	if (!TEST_int_eq(parsedecBN(&bn, "256"), 3)
1853	\|\| !TEST_BN_eq_word(bn, 256)
1854	\|\| !TEST_BN_ge_zero(bn)
1855	\|\| !TEST_BN_gt_zero(bn)
1856	\|\| !TEST_BN_ne_zero(bn)
1857	\|\| !TEST_BN_even(bn))
1858	goto err;
1859	BN_free(bn);
1860	bn = NULL;
1861
1862	if (!TEST_int_eq(parsedecBN(&bn, "-42"), 3)
1863	\|\| !TEST_BN_abs_eq_word(bn, 42)
1864	\|\| !TEST_BN_lt_zero(bn)
1865	\|\| !TEST_BN_le_zero(bn)
1866	\|\| !TEST_BN_ne_zero(bn)
1867	\|\| !TEST_BN_even(bn))
1868	goto err;
1869	BN_free(bn);
1870	bn = NULL;
1871
1872	if (!TEST_int_eq(parsedecBN(&bn, "1"), 1)
1873	\|\| !TEST_BN_eq_word(bn, 1)
1874	\|\| !TEST_BN_ne_zero(bn)
1875	\|\| !TEST_BN_gt_zero(bn)
1876	\|\| !TEST_BN_ge_zero(bn)
1877	\|\| !TEST_BN_eq_one(bn)
1878	\|\| !TEST_BN_odd(bn))
1879	goto err;
1880	BN_free(bn);
1881	bn = NULL;
1882
1883	if (!TEST_int_eq(parsedecBN(&bn, "-0"), 2)
1884	\|\| !TEST_BN_eq_zero(bn)
1885	\|\| !TEST_BN_ge_zero(bn)
1886	\|\| !TEST_BN_le_zero(bn)
1887	\|\| !TEST_BN_even(bn))
1888	goto err;
1889	BN_free(bn);
1890	bn = NULL;
1891
1892	if (!TEST_int_eq(parsedecBN(&bn, "42trailing garbage is ignored"), 2)
1893	\|\| !TEST_BN_abs_eq_word(bn, 42)
1894	\|\| !TEST_BN_ge_zero(bn)
1895	\|\| !TEST_BN_gt_zero(bn)
1896	\|\| !TEST_BN_ne_zero(bn)
1897	\|\| !TEST_BN_even(bn))
1898	goto err;
1899
1900	st = 1;
1901	err:
1902	BN_free(bn);
1903	return st;
1904	}
1905
1906	static int test_hex2bn(void)
1907	{
1908	BIGNUM *bn = NULL;
1909	int st = 0;
1910
1911	if (!TEST_int_eq(parseBN(&bn, "0"), 1)
1912	\|\| !TEST_BN_eq_zero(bn)
1913	\|\| !TEST_BN_ge_zero(bn)
1914	\|\| !TEST_BN_even(bn))
1915	goto err;
1916	BN_free(bn);
1917	bn = NULL;
1918
1919	if (!TEST_int_eq(parseBN(&bn, "256"), 3)
1920	\|\| !TEST_BN_eq_word(bn, 0x256)
1921	\|\| !TEST_BN_ge_zero(bn)
1922	\|\| !TEST_BN_gt_zero(bn)
1923	\|\| !TEST_BN_ne_zero(bn)
1924	\|\| !TEST_BN_even(bn))
1925	goto err;
1926	BN_free(bn);
1927	bn = NULL;
1928
1929	if (!TEST_int_eq(parseBN(&bn, "-42"), 3)
1930	\|\| !TEST_BN_abs_eq_word(bn, 0x42)
1931	\|\| !TEST_BN_lt_zero(bn)
1932	\|\| !TEST_BN_le_zero(bn)
1933	\|\| !TEST_BN_ne_zero(bn)
1934	\|\| !TEST_BN_even(bn))
1935	goto err;
1936	BN_free(bn);
1937	bn = NULL;
1938
1939	if (!TEST_int_eq(parseBN(&bn, "cb"), 2)
1940	\|\| !TEST_BN_eq_word(bn, 0xCB)
1941	\|\| !TEST_BN_ge_zero(bn)
1942	\|\| !TEST_BN_gt_zero(bn)
1943	\|\| !TEST_BN_ne_zero(bn)
1944	\|\| !TEST_BN_odd(bn))
1945	goto err;
1946	BN_free(bn);
1947	bn = NULL;
1948
1949	if (!TEST_int_eq(parseBN(&bn, "-0"), 2)
1950	\|\| !TEST_BN_eq_zero(bn)
1951	\|\| !TEST_BN_ge_zero(bn)
1952	\|\| !TEST_BN_le_zero(bn)
1953	\|\| !TEST_BN_even(bn))
1954	goto err;
1955	BN_free(bn);
1956	bn = NULL;
1957
1958	if (!TEST_int_eq(parseBN(&bn, "abctrailing garbage is ignored"), 3)
1959	\|\| !TEST_BN_eq_word(bn, 0xabc)
1960	\|\| !TEST_BN_ge_zero(bn)
1961	\|\| !TEST_BN_gt_zero(bn)
1962	\|\| !TEST_BN_ne_zero(bn)
1963	\|\| !TEST_BN_even(bn))
1964	goto err;
1965	st = 1;
1966
1967	err:
1968	BN_free(bn);
1969	return st;
1970	}
1971
1972	static int test_asc2bn(void)
1973	{
1974	BIGNUM *bn = NULL;
1975	int st = 0;
1976
1977	if (!TEST_ptr(bn = BN_new()))
1978	goto err;
1979
1980	if (!TEST_true(BN_asc2bn(&bn, "0"))
1981	\|\| !TEST_BN_eq_zero(bn)
1982	\|\| !TEST_BN_ge_zero(bn))
1983	goto err;
1984
1985	if (!TEST_true(BN_asc2bn(&bn, "256"))
1986	\|\| !TEST_BN_eq_word(bn, 256)
1987	\|\| !TEST_BN_ge_zero(bn))
1988	goto err;
1989
1990	if (!TEST_true(BN_asc2bn(&bn, "-42"))
1991	\|\| !TEST_BN_abs_eq_word(bn, 42)
1992	\|\| !TEST_BN_lt_zero(bn))
1993	goto err;
1994
1995	if (!TEST_true(BN_asc2bn(&bn, "0x1234"))
1996	\|\| !TEST_BN_eq_word(bn, 0x1234)
1997	\|\| !TEST_BN_ge_zero(bn))
1998	goto err;
1999
2000	if (!TEST_true(BN_asc2bn(&bn, "0X1234"))
2001	\|\| !TEST_BN_eq_word(bn, 0x1234)
2002	\|\| !TEST_BN_ge_zero(bn))
2003	goto err;
2004
2005	if (!TEST_true(BN_asc2bn(&bn, "-0xabcd"))
2006	\|\| !TEST_BN_abs_eq_word(bn, 0xabcd)
2007	\|\| !TEST_BN_lt_zero(bn))
2008	goto err;
2009
2010	if (!TEST_true(BN_asc2bn(&bn, "-0"))
2011	\|\| !TEST_BN_eq_zero(bn)
2012	\|\| !TEST_BN_ge_zero(bn))
2013	goto err;
2014
2015	if (!TEST_true(BN_asc2bn(&bn, "123trailing garbage is ignored"))
2016	\|\| !TEST_BN_eq_word(bn, 123)
2017	\|\| !TEST_BN_ge_zero(bn))
2018	goto err;
2019
2020	st = 1;
2021	err:
2022	BN_free(bn);
2023	return st;
2024	}
2025
2026	static const MPITEST kMPITests[] = {
2027	{"0", "\x00\x00\x00\x00", 4},
2028	{"1", "\x00\x00\x00\x01\x01", 5},
2029	{"-1", "\x00\x00\x00\x01\x81", 5},
2030	{"128", "\x00\x00\x00\x02\x00\x80", 6},
2031	{"256", "\x00\x00\x00\x02\x01\x00", 6},
2032	{"-256", "\x00\x00\x00\x02\x81\x00", 6},
2033	};
2034
2035	static int test_mpi(int i)
2036	{
2037	uint8_t scratch[8];
2038	const MPITEST *test = &kMPITests[i];
2039	size_t mpi_len, mpi_len2;
2040	BIGNUM *bn = NULL;
2041	BIGNUM *bn2 = NULL;
2042	int st = 0;
2043
2044	if (!TEST_ptr(bn = BN_new())
2045	\|\| !TEST_true(BN_asc2bn(&bn, test->base10)))
2046	goto err;
2047	mpi_len = BN_bn2mpi(bn, NULL);
2048	if (!TEST_size_t_le(mpi_len, sizeof(scratch)))
2049	goto err;
2050
2051	if (!TEST_size_t_eq(mpi_len2 = BN_bn2mpi(bn, scratch), mpi_len)
2052	\|\| !TEST_mem_eq(test->mpi, test->mpi_len, scratch, mpi_len))
2053	goto err;
2054
2055	if (!TEST_ptr(bn2 = BN_mpi2bn(scratch, mpi_len, NULL)))
2056	goto err;
2057
2058	if (!TEST_BN_eq(bn, bn2)) {
2059	BN_free(bn2);
2060	goto err;
2061	}
2062	BN_free(bn2);
2063
2064	st = 1;
2065	err:
2066	BN_free(bn);
2067	return st;
2068	}
2069
2070	static int test_rand(void)
2071	{
2072	BIGNUM *bn = NULL;
2073	int st = 0;
2074
2075	if (!TEST_ptr(bn = BN_new()))
2076	return 0;
2077
2078	/* Test BN_rand for degenerate cases with \|top\| and \|bottom\| parameters. */
2079	if (!TEST_false(BN_rand(bn, 0, 0 /* top / , 0 / bottom */ ))
2080	\|\| !TEST_false(BN_rand(bn, 0, 1 /* top / , 1 / bottom */ ))
2081	\|\| !TEST_true(BN_rand(bn, 1, 0 /* top / , 0 / bottom */ ))
2082	\|\| !TEST_BN_eq_one(bn)
2083	\|\| !TEST_false(BN_rand(bn, 1, 1 /* top / , 0 / bottom */ ))
2084	\|\| !TEST_true(BN_rand(bn, 1, -1 /* top / , 1 / bottom */ ))
2085	\|\| !TEST_BN_eq_one(bn)
2086	\|\| !TEST_true(BN_rand(bn, 2, 1 /* top / , 0 / bottom */ ))
2087	\|\| !TEST_BN_eq_word(bn, 3))
2088	goto err;
2089
2090	st = 1;
2091	err:
2092	BN_free(bn);
2093	return st;
2094	}
2095
2096	/*
2097	* Run some statistical tests to provide a degree confidence that the
2098	* BN_rand_range() function works as expected. The test cases and
2099	* critical values are generated by the bn_rand_range script.
2100	*
2101	* Each individual test is a Chi^2 goodness of fit for a specified number
2102	* of samples and range. The samples are assumed to be independent and
2103	* that they are from a discrete uniform distribution.
2104	*
2105	* Some of these individual tests are expected to fail, the success/failure
2106	* of each is an independent Bernoulli trial. The number of such successes
2107	* will form a binomial distribution. The count of the successes is compared
2108	* against a precomputed critical value to determine the overall outcome.
2109	*/
2110	struct rand_range_case {
2111	unsigned int range;
2112	unsigned int iterations;
2113	double critical;
2114	};
2115
2116	#include "bn_rand_range.h"
2117
2118	static int test_rand_range_single(size_t n)
2119	{
2120	const unsigned int range = rand_range_cases[n].range;
2121	const unsigned int iterations = rand_range_cases[n].iterations;
2122	const double critical = rand_range_cases[n].critical;
2123	const double expected = iterations / (double)range;
2124	double sum = 0;
2125	BIGNUM rng = NULL, val = NULL;
2126	size_t *counts;
2127	unsigned int i, v;
2128	int res = 0;
2129
2130	if (!TEST_ptr(counts = OPENSSL_zalloc(sizeof(counts) range))
2131	\|\| !TEST_ptr(rng = BN_new())
2132	\|\| !TEST_ptr(val = BN_new())
2133	\|\| !TEST_true(BN_set_word(rng, range)))
2134	goto err;
2135	for (i = 0; i < iterations; i++) {
2136	if (!TEST_true(BN_rand_range(val, rng))
2137	\|\| !TEST_uint_lt(v = (unsigned int)BN_get_word(val), range))
2138	goto err;
2139	counts[v]++;
2140	}
2141
2142	for (i = 0; i < range; i++) {
2143	const double delta = counts[i] - expected;
2144	sum += delta * delta;
2145	}
2146	sum /= expected;
2147
2148	if (sum > critical) {
2149	TEST_info("Chi^2 test negative %.4f > %4.f", sum, critical);
2150	TEST_note("test case %zu range %u iterations %u", n + 1, range,
2151	iterations);
2152	goto err;
2153	}
2154
2155	res = 1;
2156	err:
2157	BN_free(rng);
2158	BN_free(val);
2159	OPENSSL_free(counts);
2160	return res;
2161	}
2162
2163	static int test_rand_range(void)
2164	{
2165	int n_success = 0;
2166	size_t i;
2167
2168	for (i = 0; i < OSSL_NELEM(rand_range_cases); i++)
2169	n_success += test_rand_range_single(i);
2170	if (TEST_int_ge(n_success, binomial_critical))
2171	return 1;
2172	TEST_note("This test is expected to fail by chance 0.01%% of the time.");
2173	return 0;
2174	}
2175
2176	static int test_negzero(void)
2177	{
2178	BIGNUM a = NULL, b = NULL, c = NULL, d = NULL;
2179	BIGNUM numerator = NULL, denominator = NULL;
2180	int consttime, st = 0;
2181
2182	if (!TEST_ptr(a = BN_new())
2183	\|\| !TEST_ptr(b = BN_new())
2184	\|\| !TEST_ptr(c = BN_new())
2185	\|\| !TEST_ptr(d = BN_new()))
2186	goto err;
2187
2188	/* Test that BN_mul never gives negative zero. */
2189	if (!TEST_true(BN_set_word(a, 1)))
2190	goto err;
2191	BN_set_negative(a, 1);
2192	BN_zero(b);
2193	if (!TEST_true(BN_mul(c, a, b, ctx)))
2194	goto err;
2195	if (!TEST_BN_eq_zero(c)
2196	\|\| !TEST_BN_ge_zero(c))
2197	goto err;
2198
2199	for (consttime = 0; consttime < 2; consttime++) {
2200	if (!TEST_ptr(numerator = BN_new())
2201	\|\| !TEST_ptr(denominator = BN_new()))
2202	goto err;
2203	if (consttime) {
2204	BN_set_flags(numerator, BN_FLG_CONSTTIME);
2205	BN_set_flags(denominator, BN_FLG_CONSTTIME);
2206	}
2207	/* Test that BN_div never gives negative zero in the quotient. */
2208	if (!TEST_true(BN_set_word(numerator, 1))
2209	\|\| !TEST_true(BN_set_word(denominator, 2)))
2210	goto err;
2211	BN_set_negative(numerator, 1);
2212	if (!TEST_true(BN_div(a, b, numerator, denominator, ctx))
2213	\|\| !TEST_BN_eq_zero(a)
2214	\|\| !TEST_BN_ge_zero(a))
2215	goto err;
2216
2217	/* Test that BN_div never gives negative zero in the remainder. */
2218	if (!TEST_true(BN_set_word(denominator, 1))
2219	\|\| !TEST_true(BN_div(a, b, numerator, denominator, ctx))
2220	\|\| !TEST_BN_eq_zero(b)
2221	\|\| !TEST_BN_ge_zero(b))
2222	goto err;
2223	BN_free(numerator);
2224	BN_free(denominator);
2225	numerator = denominator = NULL;
2226	}
2227
2228	/* Test that BN_set_negative will not produce a negative zero. */
2229	BN_zero(a);
2230	BN_set_negative(a, 1);
2231	if (BN_is_negative(a))
2232	goto err;
2233	st = 1;
2234
2235	err:
2236	BN_free(a);
2237	BN_free(b);
2238	BN_free(c);
2239	BN_free(d);
2240	BN_free(numerator);
2241	BN_free(denominator);
2242	return st;
2243	}
2244
2245	static int test_badmod(void)
2246	{
2247	BIGNUM a = NULL, b = NULL, *zero = NULL;
2248	BN_MONT_CTX *mont = NULL;
2249	int st = 0;
2250
2251	if (!TEST_ptr(a = BN_new())
2252	\|\| !TEST_ptr(b = BN_new())
2253	\|\| !TEST_ptr(zero = BN_new())
2254	\|\| !TEST_ptr(mont = BN_MONT_CTX_new()))
2255	goto err;
2256	BN_zero(zero);
2257
2258	if (!TEST_false(BN_div(a, b, BN_value_one(), zero, ctx)))
2259	goto err;
2260	ERR_clear_error();
2261
2262	if (!TEST_false(BN_mod_mul(a, BN_value_one(), BN_value_one(), zero, ctx)))
2263	goto err;
2264	ERR_clear_error();
2265
2266	if (!TEST_false(BN_mod_exp(a, BN_value_one(), BN_value_one(), zero, ctx)))
2267	goto err;
2268	ERR_clear_error();
2269
2270	if (!TEST_false(BN_mod_exp_mont(a, BN_value_one(), BN_value_one(),
2271	zero, ctx, NULL)))
2272	goto err;
2273	ERR_clear_error();
2274
2275	if (!TEST_false(BN_mod_exp_mont_consttime(a, BN_value_one(), BN_value_one(),
2276	zero, ctx, NULL)))
2277	goto err;
2278	ERR_clear_error();
2279
2280	if (!TEST_false(BN_MONT_CTX_set(mont, zero, ctx)))
2281	goto err;
2282	ERR_clear_error();
2283
2284	/* Some operations also may not be used with an even modulus. */
2285	if (!TEST_true(BN_set_word(b, 16)))
2286	goto err;
2287
2288	if (!TEST_false(BN_MONT_CTX_set(mont, b, ctx)))
2289	goto err;
2290	ERR_clear_error();
2291
2292	if (!TEST_false(BN_mod_exp_mont(a, BN_value_one(), BN_value_one(),
2293	b, ctx, NULL)))
2294	goto err;
2295	ERR_clear_error();
2296
2297	if (!TEST_false(BN_mod_exp_mont_consttime(a, BN_value_one(), BN_value_one(),
2298	b, ctx, NULL)))
2299	goto err;
2300	ERR_clear_error();
2301
2302	st = 1;
2303	err:
2304	BN_free(a);
2305	BN_free(b);
2306	BN_free(zero);
2307	BN_MONT_CTX_free(mont);
2308	return st;
2309	}
2310
2311	static int test_expmodzero(void)
2312	{
2313	BIGNUM a = NULL, r = NULL, *zero = NULL;
2314	int st = 0;
2315
2316	if (!TEST_ptr(zero = BN_new())
2317	\|\| !TEST_ptr(a = BN_new())
2318	\|\| !TEST_ptr(r = BN_new()))
2319	goto err;
2320	BN_zero(zero);
2321
2322	if (!TEST_true(BN_mod_exp(r, a, zero, BN_value_one(), NULL))
2323	\|\| !TEST_BN_eq_zero(r)
2324	\|\| !TEST_true(BN_mod_exp_mont(r, a, zero, BN_value_one(),
2325	NULL, NULL))
2326	\|\| !TEST_BN_eq_zero(r)
2327	\|\| !TEST_true(BN_mod_exp_mont_consttime(r, a, zero,
2328	BN_value_one(),
2329	NULL, NULL))
2330	\|\| !TEST_BN_eq_zero(r)
2331	\|\| !TEST_true(BN_mod_exp_mont_word(r, 42, zero,
2332	BN_value_one(), NULL, NULL))
2333	\|\| !TEST_BN_eq_zero(r))
2334	goto err;
2335
2336	st = 1;
2337	err:
2338	BN_free(zero);
2339	BN_free(a);
2340	BN_free(r);
2341	return st;
2342	}
2343
2344	static int test_expmodone(void)
2345	{
2346	int ret = 0, i;
2347	BIGNUM *r = BN_new();
2348	BIGNUM *a = BN_new();
2349	BIGNUM *p = BN_new();
2350	BIGNUM *m = BN_new();
2351
2352	if (!TEST_ptr(r)
2353	\|\| !TEST_ptr(a)
2354	\|\| !TEST_ptr(p)
2355	\|\| !TEST_ptr(p)
2356	\|\| !TEST_ptr(m)
2357	\|\| !TEST_true(BN_set_word(a, 1))
2358	\|\| !TEST_true(BN_set_word(p, 0))
2359	\|\| !TEST_true(BN_set_word(m, 1)))
2360	goto err;
2361
2362	/* Calculate r = 1 ^ 0 mod 1, and check the result is always 0 */
2363	for (i = 0; i < 2; i++) {
2364	if (!TEST_true(BN_mod_exp(r, a, p, m, NULL))
2365	\|\| !TEST_BN_eq_zero(r)
2366	\|\| !TEST_true(BN_mod_exp_mont(r, a, p, m, NULL, NULL))
2367	\|\| !TEST_BN_eq_zero(r)
2368	\|\| !TEST_true(BN_mod_exp_mont_consttime(r, a, p, m, NULL, NULL))
2369	\|\| !TEST_BN_eq_zero(r)
2370	\|\| !TEST_true(BN_mod_exp_mont_word(r, 1, p, m, NULL, NULL))
2371	\|\| !TEST_BN_eq_zero(r)
2372	\|\| !TEST_true(BN_mod_exp_simple(r, a, p, m, NULL))
2373	\|\| !TEST_BN_eq_zero(r)
2374	\|\| !TEST_true(BN_mod_exp_recp(r, a, p, m, NULL))
2375	\|\| !TEST_BN_eq_zero(r))
2376	goto err;
2377	/* Repeat for r = 1 ^ 0 mod -1 */
2378	if (i == 0)
2379	BN_set_negative(m, 1);
2380	}
2381
2382	ret = 1;
2383	err:
2384	BN_free(r);
2385	BN_free(a);
2386	BN_free(p);
2387	BN_free(m);
2388	return ret;
2389	}
2390
2391	static int test_smallprime(int kBits)
2392	{
2393	BIGNUM *r;
2394	int st = 0;
2395
2396	if (!TEST_ptr(r = BN_new()))
2397	goto err;
2398
2399	if (kBits <= 1) {
2400	if (!TEST_false(BN_generate_prime_ex(r, kBits, 0,
2401	NULL, NULL, NULL)))
2402	goto err;
2403	} else {
2404	if (!TEST_true(BN_generate_prime_ex(r, kBits, 0,
2405	NULL, NULL, NULL))
2406	\|\| !TEST_int_eq(BN_num_bits(r), kBits))
2407	goto err;
2408	}
2409
2410	st = 1;
2411	err:
2412	BN_free(r);
2413	return st;
2414	}
2415
2416	static int test_smallsafeprime(int kBits)
2417	{
2418	BIGNUM *r;
2419	int st = 0;
2420
2421	if (!TEST_ptr(r = BN_new()))
2422	goto err;
2423
2424	if (kBits <= 5 && kBits != 3) {
2425	if (!TEST_false(BN_generate_prime_ex(r, kBits, 1,
2426	NULL, NULL, NULL)))
2427	goto err;
2428	} else {
2429	if (!TEST_true(BN_generate_prime_ex(r, kBits, 1,
2430	NULL, NULL, NULL))
2431	\|\| !TEST_int_eq(BN_num_bits(r), kBits))
2432	goto err;
2433	}
2434
2435	st = 1;
2436	err:
2437	BN_free(r);
2438	return st;
2439	}
2440
2441	static int primes[] = { 2, 3, 5, 7, 17863 };
2442
2443	static int test_is_prime(int i)
2444	{
2445	int ret = 0;
2446	BIGNUM *r = NULL;
2447	int trial;
2448
2449	if (!TEST_ptr(r = BN_new()))
2450	goto err;
2451
2452	for (trial = 0; trial <= 1; ++trial) {
2453	if (!TEST_true(BN_set_word(r, primes[i]))
2454	\|\| !TEST_int_eq(BN_check_prime(r, ctx, NULL),
2455	1))
2456	goto err;
2457	}
2458
2459	ret = 1;
2460	err:
2461	BN_free(r);
2462	return ret;
2463	}
2464
2465	static int not_primes[] = { -1, 0, 1, 4 };
2466
2467	static int test_not_prime(int i)
2468	{
2469	int ret = 0;
2470	BIGNUM *r = NULL;
2471	int trial;
2472
2473	if (!TEST_ptr(r = BN_new()))
2474	goto err;
2475
2476	for (trial = 0; trial <= 1; ++trial) {
2477	if (!TEST_true(BN_set_word(r, not_primes[i]))
2478	\|\| !TEST_false(BN_check_prime(r, ctx, NULL)))
2479	goto err;
2480	}
2481
2482	ret = 1;
2483	err:
2484	BN_free(r);
2485	return ret;
2486	}
2487
2488	static int test_ctx_set_ct_flag(BN_CTX *c)
2489	{
2490	int st = 0;
2491	size_t i;
2492	BIGNUM *b[15];
2493
2494	BN_CTX_start(c);
2495	for (i = 0; i < OSSL_NELEM(b); i++) {
2496	if (!TEST_ptr(b[i] = BN_CTX_get(c)))
2497	goto err;
2498	if (i % 2 == 1)
2499	BN_set_flags(b[i], BN_FLG_CONSTTIME);
2500	}
2501
2502	st = 1;
2503	err:
2504	BN_CTX_end(c);
2505	return st;
2506	}
2507
2508	static int test_ctx_check_ct_flag(BN_CTX *c)
2509	{
2510	int st = 0;
2511	size_t i;
2512	BIGNUM *b[30];
2513
2514	BN_CTX_start(c);
2515	for (i = 0; i < OSSL_NELEM(b); i++) {
2516	if (!TEST_ptr(b[i] = BN_CTX_get(c)))
2517	goto err;
2518	if (!TEST_false(BN_get_flags(b[i], BN_FLG_CONSTTIME)))
2519	goto err;
2520	}
2521
2522	st = 1;
2523	err:
2524	BN_CTX_end(c);
2525	return st;
2526	}
2527
2528	static int test_ctx_consttime_flag(void)
2529	{
2530	/*-
2531	* The constant-time flag should not "leak" among BN_CTX frames:
2532	*
2533	* - test_ctx_set_ct_flag() starts a frame in the given BN_CTX and
2534	* sets the BN_FLG_CONSTTIME flag on some of the BIGNUMs obtained
2535	* from the frame before ending it.
2536	* - test_ctx_check_ct_flag() then starts a new frame and gets a
2537	* number of BIGNUMs from it. In absence of leaks, none of the
2538	* BIGNUMs in the new frame should have BN_FLG_CONSTTIME set.
2539	*
2540	* In actual BN_CTX usage inside libcrypto the leak could happen at
2541	* any depth level in the BN_CTX stack, with varying results
2542	* depending on the patterns of sibling trees of nested function
2543	* calls sharing the same BN_CTX object, and the effect of
2544	* unintended BN_FLG_CONSTTIME on the called BN_* functions.
2545	*
2546	* This simple unit test abstracts away this complexity and verifies
2547	* that the leak does not happen between two sibling functions
2548	* sharing the same BN_CTX object at the same level of nesting.
2549	*
2550	*/
2551	BN_CTX *nctx = NULL;
2552	BN_CTX *sctx = NULL;
2553	size_t i = 0;
2554	int st = 0;
2555
2556	if (!TEST_ptr(nctx = BN_CTX_new())
2557	\|\| !TEST_ptr(sctx = BN_CTX_secure_new()))
2558	goto err;
2559
2560	for (i = 0; i < 2; i++) {
2561	BN_CTX *c = i == 0 ? nctx : sctx;
2562	if (!TEST_true(test_ctx_set_ct_flag(c))
2563	\|\| !TEST_true(test_ctx_check_ct_flag(c)))
2564	goto err;
2565	}
2566
2567	st = 1;
2568	err:
2569	BN_CTX_free(nctx);
2570	BN_CTX_free(sctx);
2571	return st;
2572	}
2573
2574	static int test_gcd_prime(void)
2575	{
2576	BIGNUM a = NULL, b = NULL, *gcd = NULL;
2577	int i, st = 0;
2578
2579	if (!TEST_ptr(a = BN_new())
2580	\|\| !TEST_ptr(b = BN_new())
2581	\|\| !TEST_ptr(gcd = BN_new()))
2582	goto err;
2583
2584	if (!TEST_true(BN_generate_prime_ex(a, 1024, 0, NULL, NULL, NULL)))
2585	goto err;
2586	for (i = 0; i < NUM0; i++) {
2587	if (!TEST_true(BN_generate_prime_ex(b, 1024, 0,
2588	NULL, NULL, NULL))
2589	\|\| !TEST_true(BN_gcd(gcd, a, b, ctx))
2590	\|\| !TEST_true(BN_is_one(gcd)))
2591	goto err;
2592	}
2593
2594	st = 1;
2595	err:
2596	BN_free(a);
2597	BN_free(b);
2598	BN_free(gcd);
2599	return st;
2600	}
2601
2602	typedef struct mod_exp_test_st
2603	{
2604	const char *base;
2605	const char *exp;
2606	const char *mod;
2607	const char *res;
2608	} MOD_EXP_TEST;
2609
2610	static const MOD_EXP_TEST ModExpTests[] = {
2611	/* original test vectors for rsaz_512_sqr bug, by OSS-Fuzz */
2612	{
2613	"1166180238001879113042182292626169621106255558914000595999312084"
2614	"4627946820899490684928760491249738643524880720584249698100907201"
2615	"002086675047927600340800371",
2616	"8000000000000000000000000000000000000000000000000000000000000000"
2617	"0000000000000000000000000000000000000000000000000000000000000000"
2618	"00000000",
2619	"1340780792684523720980737645613191762604395855615117867483316354"
2620	"3294276330515137663421134775482798690129946803802212663956180562"
2621	"088664022929883876655300863",
2622	"8243904058268085430037326628480645845409758077568738532059032482"
2623	"8294114415890603594730158120426756266457928475330450251339773498"
2624	"26758407619521544102068438"
2625	},
2626	{
2627	"4974270041410803822078866696159586946995877618987010219312844726"
2628	"0284386121835740784990869050050504348861513337232530490826340663"
2629	"197278031692737429054",
2630	"4974270041410803822078866696159586946995877428188754995041148539"
2631	"1663243362592271353668158565195557417149981094324650322556843202"
2632	"946445882670777892608",
2633	"1340780716511420227215592830971452482815377482627251725537099028"
2634	"4429769497230131760206012644403029349547320953206103351725462999"
2635	"947509743623340557059752191",
2636	"5296244594780707015616522701706118082963369547253192207884519362"
2637	"1767869984947542695665420219028522815539559194793619684334900442"
2638	"49304558011362360473525933"
2639	},
2640	/* test vectors for rsaz_512_srq bug, with rcx/rbx=1 */
2641	{ /* between first and second iteration */
2642	"5148719036160389201525610950887605325980251964889646556085286545"
2643	"3931548809178823413169359635978762036512397113080988070677858033"
2644	"36463909753993540214027190",
2645	"6703903964971298549787012499102923063739682910296196688861780721"
2646	"8608820150367734884009371490834517138450159290932430254268769414"
2647	"05973284973216824503042158",
2648	"6703903964971298549787012499102923063739682910296196688861780721"
2649	"8608820150367734884009371490834517138450159290932430254268769414"
2650	"05973284973216824503042159",
2651	"1"
2652	},
2653	{ /* between second and third iteration */
2654	"8908340854353752577419678771330460827942371434853054158622636544"
2655	"8151360109722890949471912566649465436296659601091730745087014189"
2656	"2672764191218875181826063",
2657	"6703903964971298549787012499102923063739682910296196688861780721"
2658	"8608820150367734884009371490834517138450159290932430254268769414"
2659	"05973284973216824503042158",
2660	"6703903964971298549787012499102923063739682910296196688861780721"
2661	"8608820150367734884009371490834517138450159290932430254268769414"
2662	"05973284973216824503042159",
2663	"1"
2664	},
2665	{ /* between third and fourth iteration */
2666	"3427446396505596330634350984901719674479522569002785244080234738"
2667	"4288743635435746136297299366444548736533053717416735379073185344"
2668	"26985272974404612945608761",
2669	"6703903964971298549787012499102923063739682910296196688861780721"
2670	"8608820150367734884009371490834517138450159290932430254268769414"
2671	"05973284973216824503042158",
2672	"6703903964971298549787012499102923063739682910296196688861780721"
2673	"8608820150367734884009371490834517138450159290932430254268769414"
2674	"05973284973216824503042159",
2675	"1"
2676	},
2677	{ /* between fourth and fifth iteration */
2678	"3472743044917564564078857826111874560045331237315597383869652985"
2679	"6919870028890895988478351133601517365908445058405433832718206902"
2680	"4088133164805266956353542",
2681	"6703903964971298549787012499102923063739682910296196688861780721"
2682	"8608820150367734884009371490834517138450159290932430254268769414"
2683	"05973284973216824503042158",
2684	"6703903964971298549787012499102923063739682910296196688861780721"
2685	"8608820150367734884009371490834517138450159290932430254268769414"
2686	"05973284973216824503042159",
2687	"1"
2688	},
2689	{ /* between fifth and sixth iteration */
2690	"3608632990153469264412378349742339216742409743898601587274768025"
2691	"0110772032985643555192767717344946174122842255204082586753499651"
2692	"14483434992887431333675068",
2693	"6703903964971298549787012499102923063739682910296196688861780721"
2694	"8608820150367734884009371490834517138450159290932430254268769414"
2695	"05973284973216824503042158",
2696	"6703903964971298549787012499102923063739682910296196688861780721"
2697	"8608820150367734884009371490834517138450159290932430254268769414"
2698	"05973284973216824503042159",
2699	"1"
2700	},
2701	{ /* between sixth and seventh iteration */
2702	"8455374370234070242910508226941981520235709767260723212165264877"
2703	"8689064388017521524568434328264431772644802567028663962962025746"
2704	"9283458217850119569539086",
2705	"6703903964971298549787012499102923063739682910296196688861780721"
2706	"8608820150367734884009371490834517138450159290932430254268769414"
2707	"05973284973216824503042158",
2708	"6703903964971298549787012499102923063739682910296196688861780721"
2709	"8608820150367734884009371490834517138450159290932430254268769414"
2710	"05973284973216824503042159",
2711	"1"
2712	},
2713	{ /* between seventh and eighth iteration */
2714	"5155371529688532178421209781159131443543419764974688878527112131"
2715	"7446518205609427412336183157918981038066636807317733319323257603"
2716	"04416292040754017461076359",
2717	"1005585594745694782468051874865438459560952436544429503329267108"
2718	"2791323022555160232601405723625177570767523893639864538140315412"
2719	"108959927459825236754563832",
2720	"1005585594745694782468051874865438459560952436544429503329267108"
2721	"2791323022555160232601405723625177570767523893639864538140315412"
2722	"108959927459825236754563833",
2723	"1"
2724	},
2725	/* test vectors for rsaz_512_srq bug, with rcx/rbx=2 */
2726	{ /* between first and second iteration */
2727	"3155666506033786929967309937640790361084670559125912405342594979"
2728	"4345142818528956285490897841406338022378565972533508820577760065"
2729	"58494345853302083699912572",
2730	"6703903964971298549787012499102923063739682910296196688861780721"
2731	"8608820150367734884009371490834517138450159290932430254268769414"
2732	"05973284973216824503042158",
2733	"6703903964971298549787012499102923063739682910296196688861780721"
2734	"8608820150367734884009371490834517138450159290932430254268769414"
2735	"05973284973216824503042159",
2736	"1"
2737	},
2738	{ /* between second and third iteration */
2739	"3789819583801342198190405714582958759005991915505282362397087750"
2740	"4213544724644823098843135685133927198668818185338794377239590049"
2741	"41019388529192775771488319",
2742	"6703903964971298549787012499102923063739682910296196688861780721"
2743	"8608820150367734884009371490834517138450159290932430254268769414"
2744	"05973284973216824503042158",
2745	"6703903964971298549787012499102923063739682910296196688861780721"
2746	"8608820150367734884009371490834517138450159290932430254268769414"
2747	"05973284973216824503042159",
2748	"1"
2749	},
2750	{ /* between third and forth iteration */
2751	"4695752552040706867080542538786056470322165281761525158189220280"
2752	"4025547447667484759200742764246905647644662050122968912279199065"
2753	"48065034299166336940507214",
2754	"6703903964971298549787012499102923063739682910296196688861780721"
2755	"8608820150367734884009371490834517138450159290932430254268769414"
2756	"05973284973216824503042158",
2757	"6703903964971298549787012499102923063739682910296196688861780721"
2758	"8608820150367734884009371490834517138450159290932430254268769414"
2759	"05973284973216824503042159",
2760	"1"
2761	},
2762	{ /* between forth and fifth iteration */
2763	"2159140240970485794188159431017382878636879856244045329971239574"
2764	"8919691133560661162828034323196457386059819832804593989740268964"
2765	"74502911811812651475927076",
2766	"6703903964971298549787012499102923063739682910296196688861780721"
2767	"8608820150367734884009371490834517138450159290932430254268769414"
2768	"05973284973216824503042158",
2769	"6703903964971298549787012499102923063739682910296196688861780721"
2770	"8608820150367734884009371490834517138450159290932430254268769414"
2771	"05973284973216824503042159",
2772	"1"
2773	},
2774	{ /* between fifth and sixth iteration */
2775	"5239312332984325668414624633307915097111691815000872662334695514"
2776	"5436533521392362443557163429336808208137221322444780490437871903"
2777	"99972784701334569424519255",
2778	"6703903964971298549787012499102923063739682910296196688861780721"
2779	"8608820150367734884009371490834517138450159290932430254268769414"
2780	"05973284973216824503042158",
2781	"6703903964971298549787012499102923063739682910296196688861780721"
2782	"8608820150367734884009371490834517138450159290932430254268769414"
2783	"05973284973216824503042159",
2784	"1"
2785	},
2786	{ /* between sixth and seventh iteration */
2787	"1977953647322612860406858017869125467496941904523063466791308891"
2788	"1172796739058531929470539758361774569875505293428856181093904091"
2789	"33788264851714311303725089",
2790	"6703903964971298549787012499102923063739682910296196688861780721"
2791	"8608820150367734884009371490834517138450159290932430254268769414"
2792	"05973284973216824503042158",
2793	"6703903964971298549787012499102923063739682910296196688861780721"
2794	"8608820150367734884009371490834517138450159290932430254268769414"
2795	"05973284973216824503042159",
2796	"1"
2797	},
2798	{ /* between seventh and eighth iteration */
2799	"6456987954117763835533395796948878140715006860263624787492985786"
2800	"8514630216966738305923915688821526449499763719943997120302368211"
2801	"04813318117996225041943964",
2802	"1340780792994259709957402499820584612747936582059239337772356144"
2803	"3721764030073546976801874298166903427690031858186486050853753882"
2804	"811946551499689575296532556",
2805	"1340780792994259709957402499820584612747936582059239337772356144"
2806	"3721764030073546976801874298166903427690031858186486050853753882"
2807	"811946551499689575296532557",
2808	"1"
2809	}
2810	};
2811
2812	static int test_mod_exp(int i)
2813	{
2814	const MOD_EXP_TEST *test = &ModExpTests[i];
2815	int res = 0;
2816	BIGNUM* result = NULL;
2817	BIGNUM base = NULL, exponent = NULL, *modulo = NULL;
2818	char *s = NULL;
2819
2820	if (!TEST_ptr(result = BN_new())
2821	\|\| !TEST_true(BN_dec2bn(&base, test->base))
2822	\|\| !TEST_true(BN_dec2bn(&exponent, test->exp))
2823	\|\| !TEST_true(BN_dec2bn(&modulo, test->mod)))
2824	goto err;
2825
2826	if (!TEST_int_eq(BN_mod_exp(result, base, exponent, modulo, ctx), 1))
2827	goto err;
2828
2829	if (!TEST_ptr(s = BN_bn2dec(result)))
2830	goto err;
2831
2832	if (!TEST_mem_eq(s, strlen(s), test->res, strlen(test->res)))
2833	goto err;
2834
2835	res = 1;
2836
2837	err:
2838	OPENSSL_free(s);
2839	BN_free(result);
2840	BN_free(base);
2841	BN_free(exponent);
2842	BN_free(modulo);
2843	return res;
2844	}
2845
2846	static int test_mod_exp_consttime(int i)
2847	{
2848	const MOD_EXP_TEST *test = &ModExpTests[i];
2849	int res = 0;
2850	BIGNUM* result = NULL;
2851	BIGNUM base = NULL, exponent = NULL, *modulo = NULL;
2852	char *s = NULL;
2853
2854	if (!TEST_ptr(result = BN_new())
2855	\|\| !TEST_true(BN_dec2bn(&base, test->base))
2856	\|\| !TEST_true(BN_dec2bn(&exponent, test->exp))
2857	\|\| !TEST_true(BN_dec2bn(&modulo, test->mod)))
2858	goto err;
2859
2860	BN_set_flags(base, BN_FLG_CONSTTIME);
2861	BN_set_flags(exponent, BN_FLG_CONSTTIME);
2862	BN_set_flags(modulo, BN_FLG_CONSTTIME);
2863
2864	if (!TEST_int_eq(BN_mod_exp(result, base, exponent, modulo, ctx), 1))
2865	goto err;
2866
2867	if (!TEST_ptr(s = BN_bn2dec(result)))
2868	goto err;
2869
2870	if (!TEST_mem_eq(s, strlen(s), test->res, strlen(test->res)))
2871	goto err;
2872
2873	res = 1;
2874
2875	err:
2876	OPENSSL_free(s);
2877	BN_free(result);
2878	BN_free(base);
2879	BN_free(exponent);
2880	BN_free(modulo);
2881	return res;
2882	}
2883
2884	static int file_test_run(STANZA *s)
2885	{
2886	static const FILETEST filetests[] = {
2887	{"Sum", file_sum},
2888	{"LShift1", file_lshift1},
2889	{"LShift", file_lshift},
2890	{"RShift", file_rshift},
2891	{"Square", file_square},
2892	{"Product", file_product},
2893	{"Quotient", file_quotient},
2894	{"ModMul", file_modmul},
2895	{"ModExp", file_modexp},
2896	{"Exp", file_exp},
2897	{"ModSqrt", file_modsqrt},
2898	{"GCD", file_gcd},
2899	};
2900	int numtests = OSSL_NELEM(filetests);
2901	const FILETEST *tp = filetests;
2902
2903	for ( ; --numtests >= 0; tp++) {
2904	if (findattr(s, tp->name) != NULL) {
2905	if (!tp->func(s)) {
2906	TEST_info("%s:%d: Failed %s test",
2907	s->test_file, s->start, tp->name);
2908	return 0;
2909	}
2910	return 1;
2911	}
2912	}
2913	TEST_info("%s:%d: Unknown test", s->test_file, s->start);
2914	return 0;
2915	}
2916
2917	static int run_file_tests(int i)
2918	{
2919	STANZA *s = NULL;
2920	char *testfile = test_get_argument(i);
2921	int c;
2922
2923	if (!TEST_ptr(s = OPENSSL_zalloc(sizeof(*s))))
2924	return 0;
2925	if (!test_start_file(s, testfile)) {
2926	OPENSSL_free(s);
2927	return 0;
2928	}
2929
2930	/* Read test file. */
2931	while (!BIO_eof(s->fp) && test_readstanza(s)) {
2932	if (s->numpairs == 0)
2933	continue;
2934	if (!file_test_run(s))
2935	s->errors++;
2936	s->numtests++;
2937	test_clearstanza(s);
2938	}
2939	test_end_file(s);
2940	c = s->errors;
2941	OPENSSL_free(s);
2942
2943	return c == 0;
2944	}
2945
2946	typedef enum OPTION_choice {
2947	OPT_ERR = -1,
2948	OPT_EOF = 0,
2949	OPT_STOCHASTIC_TESTS,
2950	OPT_TEST_ENUM
2951	} OPTION_CHOICE;
2952
2953	const OPTIONS *test_get_options(void)
2954	{
2955	static const OPTIONS test_options[] = {
2956	OPT_TEST_OPTIONS_WITH_EXTRA_USAGE("[file...]\n"),
2957	{ "stochastic", OPT_STOCHASTIC_TESTS, '-', "Run stochastic tests" },
2958	{ OPT_HELP_STR, 1, '-',
2959	"file\tFile to run tests on. Normal tests are not run\n" },
2960	{ NULL }
2961	};
2962	return test_options;
2963	}
2964
2965	int setup_tests(void)
2966	{
2967	OPTION_CHOICE o;
2968	int n, stochastic = 0;
2969
2970	while ((o = opt_next()) != OPT_EOF) {
2971	switch (o) {
2972	case OPT_STOCHASTIC_TESTS:
2973	stochastic = 1;
2974	break;
2975	case OPT_TEST_CASES:
2976	break;
2977	default:
2978	case OPT_ERR:
2979	return 0;
2980	}
2981	}
2982	n = test_get_argument_count();
2983
2984	if (!TEST_ptr(ctx = BN_CTX_new()))
2985	return 0;
2986
2987	if (n == 0) {
2988	ADD_TEST(test_sub);
2989	ADD_TEST(test_div_recip);
2990	ADD_ALL_TESTS(test_signed_mod_replace_ab, OSSL_NELEM(signed_mod_tests));
2991	ADD_ALL_TESTS(test_signed_mod_replace_ba, OSSL_NELEM(signed_mod_tests));
2992	ADD_TEST(test_mod);
2993	ADD_TEST(test_modexp_mont5);
2994	ADD_TEST(test_kronecker);
2995	ADD_TEST(test_rand);
2996	ADD_TEST(test_bn2padded);
2997	ADD_TEST(test_dec2bn);
2998	ADD_TEST(test_hex2bn);
2999	ADD_TEST(test_asc2bn);
3000	ADD_ALL_TESTS(test_mpi, (int)OSSL_NELEM(kMPITests));
3001	ADD_TEST(test_negzero);
3002	ADD_TEST(test_badmod);
3003	ADD_TEST(test_expmodzero);
3004	ADD_TEST(test_expmodone);
3005	ADD_ALL_TESTS(test_smallprime, 16);
3006	ADD_ALL_TESTS(test_smallsafeprime, 16);
3007	ADD_TEST(test_swap);
3008	ADD_TEST(test_ctx_consttime_flag);
3009	#ifndef OPENSSL_NO_EC2M
3010	ADD_TEST(test_gf2m_add);
3011	ADD_TEST(test_gf2m_mod);
3012	ADD_TEST(test_gf2m_mul);
3013	ADD_TEST(test_gf2m_sqr);
3014	ADD_TEST(test_gf2m_modinv);
3015	ADD_TEST(test_gf2m_moddiv);
3016	ADD_TEST(test_gf2m_modexp);
3017	ADD_TEST(test_gf2m_modsqrt);
3018	ADD_TEST(test_gf2m_modsolvequad);
3019	#endif
3020	ADD_ALL_TESTS(test_is_prime, (int)OSSL_NELEM(primes));
3021	ADD_ALL_TESTS(test_not_prime, (int)OSSL_NELEM(not_primes));
3022	ADD_TEST(test_gcd_prime);
3023	ADD_ALL_TESTS(test_mod_exp, (int)OSSL_NELEM(ModExpTests));
3024	ADD_ALL_TESTS(test_mod_exp_consttime, (int)OSSL_NELEM(ModExpTests));
3025	if (stochastic)
3026	ADD_TEST(test_rand_range);
3027	} else {
3028	ADD_ALL_TESTS(run_file_tests, n);
3029	}
3030	return 1;
3031	}
3032
3033	void cleanup_tests(void)
3034	{
3035	BN_CTX_free(ctx);
3036	}

注意: 瀏覽 TracBrowser 來幫助您使用儲存庫瀏覽器

source: vbox/trunk/src/libs/openssl-3.0.2/test/bntest.c@ 94403

以其他格式下載: