bntest.c@ 102210

Last change on this file since 102210 was 101211, checked in by vboxsync, 15 months ago
openssl-3.1.3: Applied and adjusted our OpenSSL changes to 3.1.2. bugref:10527
File size: 96.3 KB

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

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

source: vbox/trunk/src/libs/openssl-3.1.3/test/bntest.c@ 102210

Download in other formats: