bntest.c@ 95224

最後變更在這個檔案從95224是 95219,由 vboxsync 提交於 3 年前
libs/openssl: Switched to v3.0.3, bugref:10128
檔案大小: 95.2 KB

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

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

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

以其他格式下載: