bntest.c@ 106165

最後變更在這個檔案從106165是 104078,由 vboxsync 提交於 8 月前
openssl-3.1.5: Applied and adjusted our OpenSSL changes to 3.1.4. bugref:10638
檔案大小: 98.9 KB

行
1	/*
2	* Copyright 1995-2022 The OpenSSL Project Authors. All Rights Reserved.
3	*
4	* Licensed under the Apache License 2.0 (the "License"). You may not use
5	* this file except in compliance with the License. You can obtain a copy
6	* in the file LICENSE in the source distribution or at
7	* https://www.openssl.org/source/license.html
8	*/
9	#include <assert.h>
10	#include <errno.h>
11	#include <stdio.h>
12	#include <string.h>
13	#include <ctype.h>
14
15	#include <openssl/bn.h>
16	#include <openssl/crypto.h>
17	#include <openssl/err.h>
18	#include <openssl/rand.h>
19	#include "internal/nelem.h"
20	#include "internal/numbers.h"
21	#include "testutil.h"
22
23	/*
24	* Things in boring, not in openssl.
25	*/
26	#define HAVE_BN_SQRT 0
27
28	typedef struct filetest_st {
29	const char *name;
30	int (func)(STANZA s);
31	} FILETEST;
32
33	typedef struct mpitest_st {
34	const char *base10;
35	const char *mpi;
36	size_t mpi_len;
37	} MPITEST;
38
39	static const int NUM0 = 100; /* number of tests */
40	static const int NUM1 = 50; /* additional tests for some functions */
41	static 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	/* Test that a non-sensical, too small value causes a failure */
911	if (!TEST_true(BN_one(b[0])))
912	goto err;
913	if (!TEST_true(BN_bntest_rand(a, 512, 0, 0)))
914	goto err;
915	if (!TEST_false(BN_GF2m_mod_inv(c, a, b[0], ctx)))
916	goto err;
917
918	if (!(TEST_true(BN_GF2m_arr2poly(p0, b[0]))
919	&& TEST_true(BN_GF2m_arr2poly(p1, b[1]))))
920	goto err;
921
922	for (i = 0; i < NUM0; i++) {
923	if (!TEST_true(BN_bntest_rand(a, 512, 0, 0)))
924	goto err;
925	for (j = 0; j < 2; j++) {
926	if (!(TEST_true(BN_GF2m_mod_inv(c, a, b[j], ctx))
927	&& TEST_true(BN_GF2m_mod_mul(d, a, c, b[j], ctx))
928	/* Test that ((1/a)a) = 1. /
929	&& TEST_BN_eq_one(d)))
930	goto err;
931	}
932	}
933	st = 1;
934	err:
935	BN_free(a);
936	BN_free(b[0]);
937	BN_free(b[1]);
938	BN_free(c);
939	BN_free(d);
940	return st;
941	}
942
943	static int test_gf2m_moddiv(void)
944	{
945	BIGNUM a = NULL, b[2] = {NULL,NULL}, c = NULL, d = NULL;
946	BIGNUM e = NULL, f = NULL;
947	int i, j, st = 0;
948
949	if (!TEST_ptr(a = BN_new())
950	\|\| !TEST_ptr(b[0] = BN_new())
951	\|\| !TEST_ptr(b[1] = BN_new())
952	\|\| !TEST_ptr(c = BN_new())
953	\|\| !TEST_ptr(d = BN_new())
954	\|\| !TEST_ptr(e = BN_new())
955	\|\| !TEST_ptr(f = BN_new()))
956	goto err;
957
958	if (!(TEST_true(BN_GF2m_arr2poly(p0, b[0]))
959	&& TEST_true(BN_GF2m_arr2poly(p1, b[1]))))
960	goto err;
961
962	for (i = 0; i < NUM0; i++) {
963	if (!(TEST_true(BN_bntest_rand(a, 512, 0, 0))
964	&& TEST_true(BN_bntest_rand(c, 512, 0, 0))))
965	goto err;
966	for (j = 0; j < 2; j++) {
967	if (!(TEST_true(BN_GF2m_mod_div(d, a, c, b[j], ctx))
968	&& TEST_true(BN_GF2m_mod_mul(e, d, c, b[j], ctx))
969	&& TEST_true(BN_GF2m_mod_div(f, a, e, b[j], ctx))
970	/* Test that ((a/c)c)/a = 1. /
971	&& TEST_BN_eq_one(f)))
972	goto err;
973	}
974	}
975	st = 1;
976	err:
977	BN_free(a);
978	BN_free(b[0]);
979	BN_free(b[1]);
980	BN_free(c);
981	BN_free(d);
982	BN_free(e);
983	BN_free(f);
984	return st;
985	}
986
987	static int test_gf2m_modexp(void)
988	{
989	BIGNUM a = NULL, b[2] = {NULL,NULL}, c = NULL, d = NULL;
990	BIGNUM e = NULL, f = NULL;
991	int i, j, st = 0;
992
993	if (!TEST_ptr(a = BN_new())
994	\|\| !TEST_ptr(b[0] = BN_new())
995	\|\| !TEST_ptr(b[1] = BN_new())
996	\|\| !TEST_ptr(c = BN_new())
997	\|\| !TEST_ptr(d = BN_new())
998	\|\| !TEST_ptr(e = BN_new())
999	\|\| !TEST_ptr(f = BN_new()))
1000	goto err;
1001
1002	if (!(TEST_true(BN_GF2m_arr2poly(p0, b[0]))
1003	&& TEST_true(BN_GF2m_arr2poly(p1, b[1]))))
1004	goto err;
1005
1006	for (i = 0; i < NUM0; i++) {
1007	if (!(TEST_true(BN_bntest_rand(a, 512, 0, 0))
1008	&& TEST_true(BN_bntest_rand(c, 512, 0, 0))
1009	&& TEST_true(BN_bntest_rand(d, 512, 0, 0))))
1010	goto err;
1011	for (j = 0; j < 2; j++) {
1012	if (!(TEST_true(BN_GF2m_mod_exp(e, a, c, b[j], ctx))
1013	&& TEST_true(BN_GF2m_mod_exp(f, a, d, b[j], ctx))
1014	&& TEST_true(BN_GF2m_mod_mul(e, e, f, b[j], ctx))
1015	&& TEST_true(BN_add(f, c, d))
1016	&& TEST_true(BN_GF2m_mod_exp(f, a, f, b[j], ctx))
1017	&& TEST_true(BN_GF2m_add(f, e, f))
1018	/* Test that a^(c+d)=a^ca^d. /
1019	&& TEST_BN_eq_zero(f)))
1020	goto err;
1021	}
1022	}
1023	st = 1;
1024	err:
1025	BN_free(a);
1026	BN_free(b[0]);
1027	BN_free(b[1]);
1028	BN_free(c);
1029	BN_free(d);
1030	BN_free(e);
1031	BN_free(f);
1032	return st;
1033	}
1034
1035	static int test_gf2m_modsqrt(void)
1036	{
1037	BIGNUM a = NULL, b[2] = {NULL,NULL}, c = NULL, d = NULL;
1038	BIGNUM e = NULL, f = NULL;
1039	int i, j, st = 0;
1040
1041	if (!TEST_ptr(a = BN_new())
1042	\|\| !TEST_ptr(b[0] = BN_new())
1043	\|\| !TEST_ptr(b[1] = BN_new())
1044	\|\| !TEST_ptr(c = BN_new())
1045	\|\| !TEST_ptr(d = BN_new())
1046	\|\| !TEST_ptr(e = BN_new())
1047	\|\| !TEST_ptr(f = BN_new()))
1048	goto err;
1049
1050	if (!(TEST_true(BN_GF2m_arr2poly(p0, b[0]))
1051	&& TEST_true(BN_GF2m_arr2poly(p1, b[1]))))
1052	goto err;
1053
1054	for (i = 0; i < NUM0; i++) {
1055	if (!TEST_true(BN_bntest_rand(a, 512, 0, 0)))
1056	goto err;
1057
1058	for (j = 0; j < 2; j++) {
1059	if (!(TEST_true(BN_GF2m_mod(c, a, b[j]))
1060	&& TEST_true(BN_GF2m_mod_sqrt(d, a, b[j], ctx))
1061	&& TEST_true(BN_GF2m_mod_sqr(e, d, b[j], ctx))
1062	&& TEST_true(BN_GF2m_add(f, c, e))
1063	/* Test that d^2 = a, where d = sqrt(a). */
1064	&& TEST_BN_eq_zero(f)))
1065	goto err;
1066	}
1067	}
1068	st = 1;
1069	err:
1070	BN_free(a);
1071	BN_free(b[0]);
1072	BN_free(b[1]);
1073	BN_free(c);
1074	BN_free(d);
1075	BN_free(e);
1076	BN_free(f);
1077	return st;
1078	}
1079
1080	static int test_gf2m_modsolvequad(void)
1081	{
1082	BIGNUM a = NULL, b[2] = {NULL,NULL}, c = NULL, d = NULL;
1083	BIGNUM *e = NULL;
1084	int i, j, s = 0, t, st = 0;
1085
1086	if (!TEST_ptr(a = BN_new())
1087	\|\| !TEST_ptr(b[0] = BN_new())
1088	\|\| !TEST_ptr(b[1] = BN_new())
1089	\|\| !TEST_ptr(c = BN_new())
1090	\|\| !TEST_ptr(d = BN_new())
1091	\|\| !TEST_ptr(e = BN_new()))
1092	goto err;
1093
1094	if (!(TEST_true(BN_GF2m_arr2poly(p0, b[0]))
1095	&& TEST_true(BN_GF2m_arr2poly(p1, b[1]))))
1096	goto err;
1097
1098	for (i = 0; i < NUM0; i++) {
1099	if (!TEST_true(BN_bntest_rand(a, 512, 0, 0)))
1100	goto err;
1101	for (j = 0; j < 2; j++) {
1102	t = BN_GF2m_mod_solve_quad(c, a, b[j], ctx);
1103	if (t) {
1104	s++;
1105	if (!(TEST_true(BN_GF2m_mod_sqr(d, c, b[j], ctx))
1106	&& TEST_true(BN_GF2m_add(d, c, d))
1107	&& TEST_true(BN_GF2m_mod(e, a, b[j]))
1108	&& TEST_true(BN_GF2m_add(e, e, d))
1109	/*
1110	* Test that solution of quadratic c
1111	* satisfies c^2 + c = a.
1112	*/
1113	&& TEST_BN_eq_zero(e)))
1114	goto err;
1115	}
1116	}
1117	}
1118	if (!TEST_int_ge(s, 0)) {
1119	TEST_info("%d tests found no roots; probably an error", NUM0);
1120	goto err;
1121	}
1122	st = 1;
1123	err:
1124	BN_free(a);
1125	BN_free(b[0]);
1126	BN_free(b[1]);
1127	BN_free(c);
1128	BN_free(d);
1129	BN_free(e);
1130	return st;
1131	}
1132	#endif
1133
1134	static int test_kronecker(void)
1135	{
1136	BIGNUM a = NULL, b = NULL, r = NULL, t = NULL;
1137	int i, legendre, kronecker, st = 0;
1138
1139	if (!TEST_ptr(a = BN_new())
1140	\|\| !TEST_ptr(b = BN_new())
1141	\|\| !TEST_ptr(r = BN_new())
1142	\|\| !TEST_ptr(t = BN_new()))
1143	goto err;
1144
1145	/*
1146	* We test BN_kronecker(a, b, ctx) just for b odd (Jacobi symbol). In
1147	* this case we know that if b is prime, then BN_kronecker(a, b, ctx) is
1148	* congruent to $a^{(b-1)/2}$, modulo $b$ (Legendre symbol). So we
1149	* generate a random prime b and compare these values for a number of
1150	* random a's. (That is, we run the Solovay-Strassen primality test to
1151	* confirm that b is prime, except that we don't want to test whether b
1152	* is prime but whether BN_kronecker works.)
1153	*/
1154
1155	if (!TEST_true(BN_generate_prime_ex(b, 512, 0, NULL, NULL, NULL)))
1156	goto err;
1157	BN_set_negative(b, rand_neg());
1158
1159	for (i = 0; i < NUM0; i++) {
1160	if (!TEST_true(BN_bntest_rand(a, 512, 0, 0)))
1161	goto err;
1162	BN_set_negative(a, rand_neg());
1163
1164	/* t := (\|b\|-1)/2 (note that b is odd) */
1165	if (!TEST_true(BN_copy(t, b)))
1166	goto err;
1167	BN_set_negative(t, 0);
1168	if (!TEST_true(BN_sub_word(t, 1)))
1169	goto err;
1170	if (!TEST_true(BN_rshift1(t, t)))
1171	goto err;
1172	/* r := a^t mod b */
1173	BN_set_negative(b, 0);
1174
1175	if (!TEST_true(BN_mod_exp_recp(r, a, t, b, ctx)))
1176	goto err;
1177	BN_set_negative(b, 1);
1178
1179	if (BN_is_word(r, 1))
1180	legendre = 1;
1181	else if (BN_is_zero(r))
1182	legendre = 0;
1183	else {
1184	if (!TEST_true(BN_add_word(r, 1)))
1185	goto err;
1186	if (!TEST_int_eq(BN_ucmp(r, b), 0)) {
1187	TEST_info("Legendre symbol computation failed");
1188	goto err;
1189	}
1190	legendre = -1;
1191	}
1192
1193	if (!TEST_int_ge(kronecker = BN_kronecker(a, b, ctx), -1))
1194	goto err;
1195	/* we actually need BN_kronecker(a, \|b\|) */
1196	if (BN_is_negative(a) && BN_is_negative(b))
1197	kronecker = -kronecker;
1198
1199	if (!TEST_int_eq(legendre, kronecker))
1200	goto err;
1201	}
1202
1203	st = 1;
1204	err:
1205	BN_free(a);
1206	BN_free(b);
1207	BN_free(r);
1208	BN_free(t);
1209	return st;
1210	}
1211
1212	static int file_sum(STANZA *s)
1213	{
1214	BIGNUM a = NULL, b = NULL, sum = NULL, ret = NULL;
1215	BN_ULONG b_word;
1216	int st = 0;
1217
1218	if (!TEST_ptr(a = getBN(s, "A"))
1219	\|\| !TEST_ptr(b = getBN(s, "B"))
1220	\|\| !TEST_ptr(sum = getBN(s, "Sum"))
1221	\|\| !TEST_ptr(ret = BN_new()))
1222	goto err;
1223
1224	if (!TEST_true(BN_add(ret, a, b))
1225	\|\| !equalBN("A + B", sum, ret)
1226	\|\| !TEST_true(BN_sub(ret, sum, a))
1227	\|\| !equalBN("Sum - A", b, ret)
1228	\|\| !TEST_true(BN_sub(ret, sum, b))
1229	\|\| !equalBN("Sum - B", a, ret))
1230	goto err;
1231
1232	/*
1233	* Test that the functions work when \|r\| and \|a\| point to the same BIGNUM,
1234	* or when \|r\| and \|b\| point to the same BIGNUM.
1235	* There is no test for all of \|r\|, \|a\|, and \|b\| pointint to the same BIGNUM.
1236	*/
1237	if (!TEST_true(BN_copy(ret, a))
1238	\|\| !TEST_true(BN_add(ret, ret, b))
1239	\|\| !equalBN("A + B (r is a)", sum, ret)
1240	\|\| !TEST_true(BN_copy(ret, b))
1241	\|\| !TEST_true(BN_add(ret, a, ret))
1242	\|\| !equalBN("A + B (r is b)", sum, ret)
1243	\|\| !TEST_true(BN_copy(ret, sum))
1244	\|\| !TEST_true(BN_sub(ret, ret, a))
1245	\|\| !equalBN("Sum - A (r is a)", b, ret)
1246	\|\| !TEST_true(BN_copy(ret, a))
1247	\|\| !TEST_true(BN_sub(ret, sum, ret))
1248	\|\| !equalBN("Sum - A (r is b)", b, ret)
1249	\|\| !TEST_true(BN_copy(ret, sum))
1250	\|\| !TEST_true(BN_sub(ret, ret, b))
1251	\|\| !equalBN("Sum - B (r is a)", a, ret)
1252	\|\| !TEST_true(BN_copy(ret, b))
1253	\|\| !TEST_true(BN_sub(ret, sum, ret))
1254	\|\| !equalBN("Sum - B (r is b)", a, ret))
1255	goto err;
1256
1257	/*
1258	* Test BN_uadd() and BN_usub() with the prerequisites they are
1259	* documented as having. Note that these functions are frequently used
1260	* when the prerequisites don't hold. In those cases, they are supposed
1261	* to work as if the prerequisite hold, but we don't test that yet.
1262	*/
1263	if (!BN_is_negative(a) && !BN_is_negative(b) && BN_cmp(a, b) >= 0) {
1264	if (!TEST_true(BN_uadd(ret, a, b))
1265	\|\| !equalBN("A +u B", sum, ret)
1266	\|\| !TEST_true(BN_usub(ret, sum, a))
1267	\|\| !equalBN("Sum -u A", b, ret)
1268	\|\| !TEST_true(BN_usub(ret, sum, b))
1269	\|\| !equalBN("Sum -u B", a, ret))
1270	goto err;
1271	/*
1272	* Test that the functions work when \|r\| and \|a\| point to the same
1273	* BIGNUM, or when \|r\| and \|b\| point to the same BIGNUM.
1274	* There is no test for all of \|r\|, \|a\|, and \|b\| pointint to the same
1275	* BIGNUM.
1276	*/
1277	if (!TEST_true(BN_copy(ret, a))
1278	\|\| !TEST_true(BN_uadd(ret, ret, b))
1279	\|\| !equalBN("A +u B (r is a)", sum, ret)
1280	\|\| !TEST_true(BN_copy(ret, b))
1281	\|\| !TEST_true(BN_uadd(ret, a, ret))
1282	\|\| !equalBN("A +u B (r is b)", sum, ret)
1283	\|\| !TEST_true(BN_copy(ret, sum))
1284	\|\| !TEST_true(BN_usub(ret, ret, a))
1285	\|\| !equalBN("Sum -u A (r is a)", b, ret)
1286	\|\| !TEST_true(BN_copy(ret, a))
1287	\|\| !TEST_true(BN_usub(ret, sum, ret))
1288	\|\| !equalBN("Sum -u A (r is b)", b, ret)
1289	\|\| !TEST_true(BN_copy(ret, sum))
1290	\|\| !TEST_true(BN_usub(ret, ret, b))
1291	\|\| !equalBN("Sum -u B (r is a)", a, ret)
1292	\|\| !TEST_true(BN_copy(ret, b))
1293	\|\| !TEST_true(BN_usub(ret, sum, ret))
1294	\|\| !equalBN("Sum -u B (r is b)", a, ret))
1295	goto err;
1296	}
1297
1298	/*
1299	* Test with BN_add_word() and BN_sub_word() if \|b\| is small enough.
1300	*/
1301	b_word = BN_get_word(b);
1302	if (!BN_is_negative(b) && b_word != (BN_ULONG)-1) {
1303	if (!TEST_true(BN_copy(ret, a))
1304	\|\| !TEST_true(BN_add_word(ret, b_word))
1305	\|\| !equalBN("A + B (word)", sum, ret)
1306	\|\| !TEST_true(BN_copy(ret, sum))
1307	\|\| !TEST_true(BN_sub_word(ret, b_word))
1308	\|\| !equalBN("Sum - B (word)", a, ret))
1309	goto err;
1310	}
1311	st = 1;
1312
1313	err:
1314	BN_free(a);
1315	BN_free(b);
1316	BN_free(sum);
1317	BN_free(ret);
1318	return st;
1319	}
1320
1321	static int file_lshift1(STANZA *s)
1322	{
1323	BIGNUM a = NULL, lshift1 = NULL, zero = NULL, ret = NULL;
1324	BIGNUM two = NULL, remainder = NULL;
1325	int st = 0;
1326
1327	if (!TEST_ptr(a = getBN(s, "A"))
1328	\|\| !TEST_ptr(lshift1 = getBN(s, "LShift1"))
1329	\|\| !TEST_ptr(zero = BN_new())
1330	\|\| !TEST_ptr(ret = BN_new())
1331	\|\| !TEST_ptr(two = BN_new())
1332	\|\| !TEST_ptr(remainder = BN_new()))
1333	goto err;
1334
1335	BN_zero(zero);
1336
1337	if (!TEST_true(BN_set_word(two, 2))
1338	\|\| !TEST_true(BN_add(ret, a, a))
1339	\|\| !equalBN("A + A", lshift1, ret)
1340	\|\| !TEST_true(BN_mul(ret, a, two, ctx))
1341	\|\| !equalBN("A * 2", lshift1, ret)
1342	\|\| !TEST_true(BN_div(ret, remainder, lshift1, two, ctx))
1343	\|\| !equalBN("LShift1 / 2", a, ret)
1344	\|\| !equalBN("LShift1 % 2", zero, remainder)
1345	\|\| !TEST_true(BN_lshift1(ret, a))
1346	\|\| !equalBN("A << 1", lshift1, ret)
1347	\|\| !TEST_true(BN_rshift1(ret, lshift1))
1348	\|\| !equalBN("LShift >> 1", a, ret)
1349	\|\| !TEST_true(BN_rshift1(ret, lshift1))
1350	\|\| !equalBN("LShift >> 1", a, ret))
1351	goto err;
1352
1353	/* Set the LSB to 1 and test rshift1 again. */
1354	if (!TEST_true(BN_set_bit(lshift1, 0))
1355	\|\| !TEST_true(BN_div(ret, NULL /* rem */ , lshift1, two, ctx))
1356	\|\| !equalBN("(LShift1 \| 1) / 2", a, ret)
1357	\|\| !TEST_true(BN_rshift1(ret, lshift1))
1358	\|\| !equalBN("(LShift \| 1) >> 1", a, ret))
1359	goto err;
1360
1361	st = 1;
1362	err:
1363	BN_free(a);
1364	BN_free(lshift1);
1365	BN_free(zero);
1366	BN_free(ret);
1367	BN_free(two);
1368	BN_free(remainder);
1369
1370	return st;
1371	}
1372
1373	static int file_lshift(STANZA *s)
1374	{
1375	BIGNUM a = NULL, lshift = NULL, *ret = NULL;
1376	int n = 0, st = 0;
1377
1378	if (!TEST_ptr(a = getBN(s, "A"))
1379	\|\| !TEST_ptr(lshift = getBN(s, "LShift"))
1380	\|\| !TEST_ptr(ret = BN_new())
1381	\|\| !getint(s, &n, "N"))
1382	goto err;
1383
1384	if (!TEST_true(BN_lshift(ret, a, n))
1385	\|\| !equalBN("A << N", lshift, ret)
1386	\|\| !TEST_true(BN_rshift(ret, lshift, n))
1387	\|\| !equalBN("A >> N", a, ret))
1388	goto err;
1389
1390	st = 1;
1391	err:
1392	BN_free(a);
1393	BN_free(lshift);
1394	BN_free(ret);
1395	return st;
1396	}
1397
1398	static int file_rshift(STANZA *s)
1399	{
1400	BIGNUM a = NULL, rshift = NULL, *ret = NULL;
1401	int n = 0, st = 0;
1402
1403	if (!TEST_ptr(a = getBN(s, "A"))
1404	\|\| !TEST_ptr(rshift = getBN(s, "RShift"))
1405	\|\| !TEST_ptr(ret = BN_new())
1406	\|\| !getint(s, &n, "N"))
1407	goto err;
1408
1409	if (!TEST_true(BN_rshift(ret, a, n))
1410	\|\| !equalBN("A >> N", rshift, ret))
1411	goto err;
1412
1413	/* If N == 1, try with rshift1 as well */
1414	if (n == 1) {
1415	if (!TEST_true(BN_rshift1(ret, a))
1416	\|\| !equalBN("A >> 1 (rshift1)", rshift, ret))
1417	goto err;
1418	}
1419	st = 1;
1420
1421	err:
1422	BN_free(a);
1423	BN_free(rshift);
1424	BN_free(ret);
1425	return st;
1426	}
1427
1428	static int file_square(STANZA *s)
1429	{
1430	BIGNUM a = NULL, square = NULL, zero = NULL, ret = NULL;
1431	BIGNUM remainder = NULL, tmp = NULL;
1432	int st = 0;
1433
1434	if (!TEST_ptr(a = getBN(s, "A"))
1435	\|\| !TEST_ptr(square = getBN(s, "Square"))
1436	\|\| !TEST_ptr(zero = BN_new())
1437	\|\| !TEST_ptr(ret = BN_new())
1438	\|\| !TEST_ptr(remainder = BN_new()))
1439	goto err;
1440
1441	BN_zero(zero);
1442	if (!TEST_true(BN_sqr(ret, a, ctx))
1443	\|\| !equalBN("A^2", square, ret)
1444	\|\| !TEST_true(BN_mul(ret, a, a, ctx))
1445	\|\| !equalBN("A * A", square, ret)
1446	\|\| !TEST_true(BN_div(ret, remainder, square, a, ctx))
1447	\|\| !equalBN("Square / A", a, ret)
1448	\|\| !equalBN("Square % A", zero, remainder))
1449	goto err;
1450
1451	#if HAVE_BN_SQRT
1452	BN_set_negative(a, 0);
1453	if (!TEST_true(BN_sqrt(ret, square, ctx))
1454	\|\| !equalBN("sqrt(Square)", a, ret))
1455	goto err;
1456
1457	/* BN_sqrt should fail on non-squares and negative numbers. */
1458	if (!TEST_BN_eq_zero(square)) {
1459	if (!TEST_ptr(tmp = BN_new())
1460	\|\| !TEST_true(BN_copy(tmp, square)))
1461	goto err;
1462	BN_set_negative(tmp, 1);
1463
1464	if (!TEST_int_eq(BN_sqrt(ret, tmp, ctx), 0))
1465	goto err;
1466	ERR_clear_error();
1467
1468	BN_set_negative(tmp, 0);
1469	if (BN_add(tmp, tmp, BN_value_one()))
1470	goto err;
1471	if (!TEST_int_eq(BN_sqrt(ret, tmp, ctx)))
1472	goto err;
1473	ERR_clear_error();
1474	}
1475	#endif
1476
1477	st = 1;
1478	err:
1479	BN_free(a);
1480	BN_free(square);
1481	BN_free(zero);
1482	BN_free(ret);
1483	BN_free(remainder);
1484	BN_free(tmp);
1485	return st;
1486	}
1487
1488	static int file_product(STANZA *s)
1489	{
1490	BIGNUM a = NULL, b = NULL, product = NULL, ret = NULL;
1491	BIGNUM remainder = NULL, zero = NULL;
1492	int st = 0;
1493
1494	if (!TEST_ptr(a = getBN(s, "A"))
1495	\|\| !TEST_ptr(b = getBN(s, "B"))
1496	\|\| !TEST_ptr(product = getBN(s, "Product"))
1497	\|\| !TEST_ptr(ret = BN_new())
1498	\|\| !TEST_ptr(remainder = BN_new())
1499	\|\| !TEST_ptr(zero = BN_new()))
1500	goto err;
1501
1502	BN_zero(zero);
1503
1504	if (!TEST_true(BN_mul(ret, a, b, ctx))
1505	\|\| !equalBN("A * B", product, ret)
1506	\|\| !TEST_true(BN_div(ret, remainder, product, a, ctx))
1507	\|\| !equalBN("Product / A", b, ret)
1508	\|\| !equalBN("Product % A", zero, remainder)
1509	\|\| !TEST_true(BN_div(ret, remainder, product, b, ctx))
1510	\|\| !equalBN("Product / B", a, ret)
1511	\|\| !equalBN("Product % B", zero, remainder))
1512	goto err;
1513
1514	st = 1;
1515	err:
1516	BN_free(a);
1517	BN_free(b);
1518	BN_free(product);
1519	BN_free(ret);
1520	BN_free(remainder);
1521	BN_free(zero);
1522	return st;
1523	}
1524
1525	static int file_quotient(STANZA *s)
1526	{
1527	BIGNUM a = NULL, b = NULL, quotient = NULL, remainder = NULL;
1528	BIGNUM ret = NULL, ret2 = NULL, *nnmod = NULL;
1529	BN_ULONG b_word, ret_word;
1530	int st = 0;
1531
1532	if (!TEST_ptr(a = getBN(s, "A"))
1533	\|\| !TEST_ptr(b = getBN(s, "B"))
1534	\|\| !TEST_ptr(quotient = getBN(s, "Quotient"))
1535	\|\| !TEST_ptr(remainder = getBN(s, "Remainder"))
1536	\|\| !TEST_ptr(ret = BN_new())
1537	\|\| !TEST_ptr(ret2 = BN_new())
1538	\|\| !TEST_ptr(nnmod = BN_new()))
1539	goto err;
1540
1541	if (!TEST_true(BN_div(ret, ret2, a, b, ctx))
1542	\|\| !equalBN("A / B", quotient, ret)
1543	\|\| !equalBN("A % B", remainder, ret2)
1544	\|\| !TEST_true(BN_mul(ret, quotient, b, ctx))
1545	\|\| !TEST_true(BN_add(ret, ret, remainder))
1546	\|\| !equalBN("Quotient * B + Remainder", a, ret))
1547	goto err;
1548
1549	/*
1550	* Test with BN_mod_word() and BN_div_word() if the divisor is
1551	* small enough.
1552	*/
1553	b_word = BN_get_word(b);
1554	if (!BN_is_negative(b) && b_word != (BN_ULONG)-1) {
1555	BN_ULONG remainder_word = BN_get_word(remainder);
1556
1557	assert(remainder_word != (BN_ULONG)-1);
1558	if (!TEST_ptr(BN_copy(ret, a)))
1559	goto err;
1560	ret_word = BN_div_word(ret, b_word);
1561	if (ret_word != remainder_word) {
1562	#ifdef BN_DEC_FMT1
1563	TEST_error(
1564	"Got A %% B (word) = " BN_DEC_FMT1 ", wanted " BN_DEC_FMT1,
1565	ret_word, remainder_word);
1566	#else
1567	TEST_error("Got A %% B (word) mismatch");
1568	#endif
1569	goto err;
1570	}
1571	if (!equalBN ("A / B (word)", quotient, ret))
1572	goto err;
1573
1574	ret_word = BN_mod_word(a, b_word);
1575	if (ret_word != remainder_word) {
1576	#ifdef BN_DEC_FMT1
1577	TEST_error(
1578	"Got A %% B (word) = " BN_DEC_FMT1 ", wanted " BN_DEC_FMT1 "",
1579	ret_word, remainder_word);
1580	#else
1581	TEST_error("Got A %% B (word) mismatch");
1582	#endif
1583	goto err;
1584	}
1585	}
1586
1587	/* Test BN_nnmod. */
1588	if (!BN_is_negative(b)) {
1589	if (!TEST_true(BN_copy(nnmod, remainder))
1590	\|\| (BN_is_negative(nnmod)
1591	&& !TEST_true(BN_add(nnmod, nnmod, b)))
1592	\|\| !TEST_true(BN_nnmod(ret, a, b, ctx))
1593	\|\| !equalBN("A % B (non-negative)", nnmod, ret))
1594	goto err;
1595	}
1596
1597	st = 1;
1598	err:
1599	BN_free(a);
1600	BN_free(b);
1601	BN_free(quotient);
1602	BN_free(remainder);
1603	BN_free(ret);
1604	BN_free(ret2);
1605	BN_free(nnmod);
1606	return st;
1607	}
1608
1609	static int file_modmul(STANZA *s)
1610	{
1611	BIGNUM a = NULL, b = NULL, m = NULL, mod_mul = NULL, *ret = NULL;
1612	int st = 0;
1613
1614	if (!TEST_ptr(a = getBN(s, "A"))
1615	\|\| !TEST_ptr(b = getBN(s, "B"))
1616	\|\| !TEST_ptr(m = getBN(s, "M"))
1617	\|\| !TEST_ptr(mod_mul = getBN(s, "ModMul"))
1618	\|\| !TEST_ptr(ret = BN_new()))
1619	goto err;
1620
1621	if (!TEST_true(BN_mod_mul(ret, a, b, m, ctx))
1622	\|\| !equalBN("A * B (mod M)", mod_mul, ret))
1623	goto err;
1624
1625	if (BN_is_odd(m)) {
1626	/* Reduce \|a\| and \|b\| and test the Montgomery version. */
1627	BN_MONT_CTX *mont = BN_MONT_CTX_new();
1628	BIGNUM *a_tmp = BN_new();
1629	BIGNUM *b_tmp = BN_new();
1630
1631	if (mont == NULL \|\| a_tmp == NULL \|\| b_tmp == NULL
1632	\|\| !TEST_true(BN_MONT_CTX_set(mont, m, ctx))
1633	\|\| !TEST_true(BN_nnmod(a_tmp, a, m, ctx))
1634	\|\| !TEST_true(BN_nnmod(b_tmp, b, m, ctx))
1635	\|\| !TEST_true(BN_to_montgomery(a_tmp, a_tmp, mont, ctx))
1636	\|\| !TEST_true(BN_to_montgomery(b_tmp, b_tmp, mont, ctx))
1637	\|\| !TEST_true(BN_mod_mul_montgomery(ret, a_tmp, b_tmp,
1638	mont, ctx))
1639	\|\| !TEST_true(BN_from_montgomery(ret, ret, mont, ctx))
1640	\|\| !equalBN("A * B (mod M) (mont)", mod_mul, ret))
1641	st = 0;
1642	else
1643	st = 1;
1644	BN_MONT_CTX_free(mont);
1645	BN_free(a_tmp);
1646	BN_free(b_tmp);
1647	if (st == 0)
1648	goto err;
1649	}
1650
1651	st = 1;
1652	err:
1653	BN_free(a);
1654	BN_free(b);
1655	BN_free(m);
1656	BN_free(mod_mul);
1657	BN_free(ret);
1658	return st;
1659	}
1660
1661	static int file_modexp(STANZA *s)
1662	{
1663	BIGNUM a = NULL, e = NULL, m = NULL, mod_exp = NULL, *ret = NULL;
1664	BIGNUM b = NULL, c = NULL, *d = NULL;
1665	int st = 0;
1666
1667	if (!TEST_ptr(a = getBN(s, "A"))
1668	\|\| !TEST_ptr(e = getBN(s, "E"))
1669	\|\| !TEST_ptr(m = getBN(s, "M"))
1670	\|\| !TEST_ptr(mod_exp = getBN(s, "ModExp"))
1671	\|\| !TEST_ptr(ret = BN_new())
1672	\|\| !TEST_ptr(d = BN_new()))
1673	goto err;
1674
1675	if (!TEST_true(BN_mod_exp(ret, a, e, m, ctx))
1676	\|\| !equalBN("A ^ E (mod M)", mod_exp, ret))
1677	goto err;
1678
1679	if (BN_is_odd(m)) {
1680	if (!TEST_true(BN_mod_exp_mont(ret, a, e, m, ctx, NULL))
1681	\|\| !equalBN("A ^ E (mod M) (mont)", mod_exp, ret)
1682	\|\| !TEST_true(BN_mod_exp_mont_consttime(ret, a, e, m,
1683	ctx, NULL))
1684	\|\| !equalBN("A ^ E (mod M) (mont const", mod_exp, ret))
1685	goto err;
1686	}
1687
1688	/* Regression test for carry propagation bug in sqr8x_reduction */
1689	BN_hex2bn(&a, "050505050505");
1690	BN_hex2bn(&b, "02");
1691	BN_hex2bn(&c,
1692	"4141414141414141414141274141414141414141414141414141414141414141"
1693	"4141414141414141414141414141414141414141414141414141414141414141"
1694	"4141414141414141414141800000000000000000000000000000000000000000"
1695	"0000000000000000000000000000000000000000000000000000000000000000"
1696	"0000000000000000000000000000000000000000000000000000000000000000"
1697	"0000000000000000000000000000000000000000000000000000000001");
1698	if (!TEST_true(BN_mod_exp(d, a, b, c, ctx))
1699	\|\| !TEST_true(BN_mul(e, a, a, ctx))
1700	\|\| !TEST_BN_eq(d, e))
1701	goto err;
1702
1703	st = 1;
1704	err:
1705	BN_free(a);
1706	BN_free(b);
1707	BN_free(c);
1708	BN_free(d);
1709	BN_free(e);
1710	BN_free(m);
1711	BN_free(mod_exp);
1712	BN_free(ret);
1713	return st;
1714	}
1715
1716	static int file_exp(STANZA *s)
1717	{
1718	BIGNUM a = NULL, e = NULL, exp = NULL, ret = NULL;
1719	int st = 0;
1720
1721	if (!TEST_ptr(a = getBN(s, "A"))
1722	\|\| !TEST_ptr(e = getBN(s, "E"))
1723	\|\| !TEST_ptr(exp = getBN(s, "Exp"))
1724	\|\| !TEST_ptr(ret = BN_new()))
1725	goto err;
1726
1727	if (!TEST_true(BN_exp(ret, a, e, ctx))
1728	\|\| !equalBN("A ^ E", exp, ret))
1729	goto err;
1730
1731	st = 1;
1732	err:
1733	BN_free(a);
1734	BN_free(e);
1735	BN_free(exp);
1736	BN_free(ret);
1737	return st;
1738	}
1739
1740	static int file_modsqrt(STANZA *s)
1741	{
1742	BIGNUM a = NULL, p = NULL, mod_sqrt = NULL, ret = NULL, *ret2 = NULL;
1743	int st = 0;
1744
1745	if (!TEST_ptr(a = getBN(s, "A"))
1746	\|\| !TEST_ptr(p = getBN(s, "P"))
1747	\|\| !TEST_ptr(mod_sqrt = getBN(s, "ModSqrt"))
1748	\|\| !TEST_ptr(ret = BN_new())
1749	\|\| !TEST_ptr(ret2 = BN_new()))
1750	goto err;
1751
1752	if (BN_is_negative(mod_sqrt)) {
1753	/* A negative testcase */
1754	if (!TEST_ptr_null(BN_mod_sqrt(ret, a, p, ctx)))
1755	goto err;
1756
1757	st = 1;
1758	goto err;
1759	}
1760
1761	/* There are two possible answers. */
1762	if (!TEST_ptr(BN_mod_sqrt(ret, a, p, ctx))
1763	\|\| !TEST_true(BN_sub(ret2, p, ret)))
1764	goto err;
1765
1766	/* The first condition should NOT be a test. */
1767	if (BN_cmp(ret2, mod_sqrt) != 0
1768	&& !equalBN("sqrt(A) (mod P)", mod_sqrt, ret))
1769	goto err;
1770
1771	st = 1;
1772	err:
1773	BN_free(a);
1774	BN_free(p);
1775	BN_free(mod_sqrt);
1776	BN_free(ret);
1777	BN_free(ret2);
1778	return st;
1779	}
1780
1781	static int file_gcd(STANZA *s)
1782	{
1783	BIGNUM a = NULL, b = NULL, gcd = NULL, ret = NULL;
1784	int st = 0;
1785
1786	if (!TEST_ptr(a = getBN(s, "A"))
1787	\|\| !TEST_ptr(b = getBN(s, "B"))
1788	\|\| !TEST_ptr(gcd = getBN(s, "GCD"))
1789	\|\| !TEST_ptr(ret = BN_new()))
1790	goto err;
1791
1792	if (!TEST_true(BN_gcd(ret, a, b, ctx))
1793	\|\| !equalBN("gcd(A,B)", gcd, ret))
1794	goto err;
1795
1796	st = 1;
1797	err:
1798	BN_free(a);
1799	BN_free(b);
1800	BN_free(gcd);
1801	BN_free(ret);
1802	return st;
1803	}
1804
1805	static int test_bn2padded(void)
1806	{
1807	uint8_t zeros[256], out[256], reference[128];
1808	size_t bytes;
1809	BIGNUM *n;
1810	int st = 0;
1811
1812	/* Test edge case at 0. */
1813	if (!TEST_ptr((n = BN_new())))
1814	goto err;
1815	if (!TEST_int_eq(BN_bn2binpad(n, NULL, 0), 0))
1816	goto err;
1817	memset(out, -1, sizeof(out));
1818	if (!TEST_int_eq(BN_bn2binpad(n, out, sizeof(out)), sizeof(out)))
1819	goto err;
1820	memset(zeros, 0, sizeof(zeros));
1821	if (!TEST_mem_eq(zeros, sizeof(zeros), out, sizeof(out)))
1822	goto err;
1823
1824	/* Test a random numbers at various byte lengths. */
1825	for (bytes = 128 - 7; bytes <= 128; bytes++) {
1826	# define TOP_BIT_ON 0
1827	# define BOTTOM_BIT_NOTOUCH 0
1828	if (!TEST_true(BN_rand(n, bytes * 8, TOP_BIT_ON, BOTTOM_BIT_NOTOUCH)))
1829	goto err;
1830	if (!TEST_int_eq(BN_num_bytes(n), bytes)
1831	\|\| !TEST_int_eq(BN_bn2bin(n, reference), bytes))
1832	goto err;
1833	/* Empty buffer should fail. */
1834	if (!TEST_int_eq(BN_bn2binpad(n, NULL, 0), -1))
1835	goto err;
1836	/* One byte short should fail. */
1837	if (!TEST_int_eq(BN_bn2binpad(n, out, bytes - 1), -1))
1838	goto err;
1839	/* Exactly right size should encode. */
1840	if (!TEST_int_eq(BN_bn2binpad(n, out, bytes), bytes)
1841	\|\| !TEST_mem_eq(out, bytes, reference, bytes))
1842	goto err;
1843	/* Pad up one byte extra. */
1844	if (!TEST_int_eq(BN_bn2binpad(n, out, bytes + 1), bytes + 1)
1845	\|\| !TEST_mem_eq(out + 1, bytes, reference, bytes)
1846	\|\| !TEST_mem_eq(out, 1, zeros, 1))
1847	goto err;
1848	/* Pad up to 256. */
1849	if (!TEST_int_eq(BN_bn2binpad(n, out, sizeof(out)), sizeof(out))
1850	\|\| !TEST_mem_eq(out + sizeof(out) - bytes, bytes,
1851	reference, bytes)
1852	\|\| !TEST_mem_eq(out, sizeof(out) - bytes,
1853	zeros, sizeof(out) - bytes))
1854	goto err;
1855	}
1856
1857	st = 1;
1858	err:
1859	BN_free(n);
1860	return st;
1861	}
1862
1863	static int test_dec2bn(void)
1864	{
1865	BIGNUM *bn = NULL;
1866	int st = 0;
1867
1868	if (!TEST_int_eq(parsedecBN(&bn, "0"), 1)
1869	\|\| !TEST_BN_eq_word(bn, 0)
1870	\|\| !TEST_BN_eq_zero(bn)
1871	\|\| !TEST_BN_le_zero(bn)
1872	\|\| !TEST_BN_ge_zero(bn)
1873	\|\| !TEST_BN_even(bn))
1874	goto err;
1875	BN_free(bn);
1876	bn = NULL;
1877
1878	if (!TEST_int_eq(parsedecBN(&bn, "256"), 3)
1879	\|\| !TEST_BN_eq_word(bn, 256)
1880	\|\| !TEST_BN_ge_zero(bn)
1881	\|\| !TEST_BN_gt_zero(bn)
1882	\|\| !TEST_BN_ne_zero(bn)
1883	\|\| !TEST_BN_even(bn))
1884	goto err;
1885	BN_free(bn);
1886	bn = NULL;
1887
1888	if (!TEST_int_eq(parsedecBN(&bn, "-42"), 3)
1889	\|\| !TEST_BN_abs_eq_word(bn, 42)
1890	\|\| !TEST_BN_lt_zero(bn)
1891	\|\| !TEST_BN_le_zero(bn)
1892	\|\| !TEST_BN_ne_zero(bn)
1893	\|\| !TEST_BN_even(bn))
1894	goto err;
1895	BN_free(bn);
1896	bn = NULL;
1897
1898	if (!TEST_int_eq(parsedecBN(&bn, "1"), 1)
1899	\|\| !TEST_BN_eq_word(bn, 1)
1900	\|\| !TEST_BN_ne_zero(bn)
1901	\|\| !TEST_BN_gt_zero(bn)
1902	\|\| !TEST_BN_ge_zero(bn)
1903	\|\| !TEST_BN_eq_one(bn)
1904	\|\| !TEST_BN_odd(bn))
1905	goto err;
1906	BN_free(bn);
1907	bn = NULL;
1908
1909	if (!TEST_int_eq(parsedecBN(&bn, "-0"), 2)
1910	\|\| !TEST_BN_eq_zero(bn)
1911	\|\| !TEST_BN_ge_zero(bn)
1912	\|\| !TEST_BN_le_zero(bn)
1913	\|\| !TEST_BN_even(bn))
1914	goto err;
1915	BN_free(bn);
1916	bn = NULL;
1917
1918	if (!TEST_int_eq(parsedecBN(&bn, "42trailing garbage is ignored"), 2)
1919	\|\| !TEST_BN_abs_eq_word(bn, 42)
1920	\|\| !TEST_BN_ge_zero(bn)
1921	\|\| !TEST_BN_gt_zero(bn)
1922	\|\| !TEST_BN_ne_zero(bn)
1923	\|\| !TEST_BN_even(bn))
1924	goto err;
1925
1926	st = 1;
1927	err:
1928	BN_free(bn);
1929	return st;
1930	}
1931
1932	static int test_hex2bn(void)
1933	{
1934	BIGNUM *bn = NULL;
1935	int st = 0;
1936
1937	if (!TEST_int_eq(parseBN(&bn, "0"), 1)
1938	\|\| !TEST_BN_eq_zero(bn)
1939	\|\| !TEST_BN_ge_zero(bn)
1940	\|\| !TEST_BN_even(bn))
1941	goto err;
1942	BN_free(bn);
1943	bn = NULL;
1944
1945	if (!TEST_int_eq(parseBN(&bn, "256"), 3)
1946	\|\| !TEST_BN_eq_word(bn, 0x256)
1947	\|\| !TEST_BN_ge_zero(bn)
1948	\|\| !TEST_BN_gt_zero(bn)
1949	\|\| !TEST_BN_ne_zero(bn)
1950	\|\| !TEST_BN_even(bn))
1951	goto err;
1952	BN_free(bn);
1953	bn = NULL;
1954
1955	if (!TEST_int_eq(parseBN(&bn, "-42"), 3)
1956	\|\| !TEST_BN_abs_eq_word(bn, 0x42)
1957	\|\| !TEST_BN_lt_zero(bn)
1958	\|\| !TEST_BN_le_zero(bn)
1959	\|\| !TEST_BN_ne_zero(bn)
1960	\|\| !TEST_BN_even(bn))
1961	goto err;
1962	BN_free(bn);
1963	bn = NULL;
1964
1965	if (!TEST_int_eq(parseBN(&bn, "cb"), 2)
1966	\|\| !TEST_BN_eq_word(bn, 0xCB)
1967	\|\| !TEST_BN_ge_zero(bn)
1968	\|\| !TEST_BN_gt_zero(bn)
1969	\|\| !TEST_BN_ne_zero(bn)
1970	\|\| !TEST_BN_odd(bn))
1971	goto err;
1972	BN_free(bn);
1973	bn = NULL;
1974
1975	if (!TEST_int_eq(parseBN(&bn, "-0"), 2)
1976	\|\| !TEST_BN_eq_zero(bn)
1977	\|\| !TEST_BN_ge_zero(bn)
1978	\|\| !TEST_BN_le_zero(bn)
1979	\|\| !TEST_BN_even(bn))
1980	goto err;
1981	BN_free(bn);
1982	bn = NULL;
1983
1984	if (!TEST_int_eq(parseBN(&bn, "abctrailing garbage is ignored"), 3)
1985	\|\| !TEST_BN_eq_word(bn, 0xabc)
1986	\|\| !TEST_BN_ge_zero(bn)
1987	\|\| !TEST_BN_gt_zero(bn)
1988	\|\| !TEST_BN_ne_zero(bn)
1989	\|\| !TEST_BN_even(bn))
1990	goto err;
1991	st = 1;
1992
1993	err:
1994	BN_free(bn);
1995	return st;
1996	}
1997
1998	static int test_asc2bn(void)
1999	{
2000	BIGNUM *bn = NULL;
2001	int st = 0;
2002
2003	if (!TEST_ptr(bn = BN_new()))
2004	goto err;
2005
2006	if (!TEST_true(BN_asc2bn(&bn, "0"))
2007	\|\| !TEST_BN_eq_zero(bn)
2008	\|\| !TEST_BN_ge_zero(bn))
2009	goto err;
2010
2011	if (!TEST_true(BN_asc2bn(&bn, "256"))
2012	\|\| !TEST_BN_eq_word(bn, 256)
2013	\|\| !TEST_BN_ge_zero(bn))
2014	goto err;
2015
2016	if (!TEST_true(BN_asc2bn(&bn, "-42"))
2017	\|\| !TEST_BN_abs_eq_word(bn, 42)
2018	\|\| !TEST_BN_lt_zero(bn))
2019	goto err;
2020
2021	if (!TEST_true(BN_asc2bn(&bn, "0x1234"))
2022	\|\| !TEST_BN_eq_word(bn, 0x1234)
2023	\|\| !TEST_BN_ge_zero(bn))
2024	goto err;
2025
2026	if (!TEST_true(BN_asc2bn(&bn, "0X1234"))
2027	\|\| !TEST_BN_eq_word(bn, 0x1234)
2028	\|\| !TEST_BN_ge_zero(bn))
2029	goto err;
2030
2031	if (!TEST_true(BN_asc2bn(&bn, "-0xabcd"))
2032	\|\| !TEST_BN_abs_eq_word(bn, 0xabcd)
2033	\|\| !TEST_BN_lt_zero(bn))
2034	goto err;
2035
2036	if (!TEST_true(BN_asc2bn(&bn, "-0"))
2037	\|\| !TEST_BN_eq_zero(bn)
2038	\|\| !TEST_BN_ge_zero(bn))
2039	goto err;
2040
2041	if (!TEST_true(BN_asc2bn(&bn, "123trailing garbage is ignored"))
2042	\|\| !TEST_BN_eq_word(bn, 123)
2043	\|\| !TEST_BN_ge_zero(bn))
2044	goto err;
2045
2046	st = 1;
2047	err:
2048	BN_free(bn);
2049	return st;
2050	}
2051
2052	static const MPITEST kMPITests[] = {
2053	{"0", "\x00\x00\x00\x00", 4},
2054	{"1", "\x00\x00\x00\x01\x01", 5},
2055	{"-1", "\x00\x00\x00\x01\x81", 5},
2056	{"128", "\x00\x00\x00\x02\x00\x80", 6},
2057	{"256", "\x00\x00\x00\x02\x01\x00", 6},
2058	{"-256", "\x00\x00\x00\x02\x81\x00", 6},
2059	};
2060
2061	static int test_mpi(int i)
2062	{
2063	uint8_t scratch[8];
2064	const MPITEST *test = &kMPITests[i];
2065	size_t mpi_len, mpi_len2;
2066	BIGNUM *bn = NULL;
2067	BIGNUM *bn2 = NULL;
2068	int st = 0;
2069
2070	if (!TEST_ptr(bn = BN_new())
2071	\|\| !TEST_true(BN_asc2bn(&bn, test->base10)))
2072	goto err;
2073	mpi_len = BN_bn2mpi(bn, NULL);
2074	if (!TEST_size_t_le(mpi_len, sizeof(scratch)))
2075	goto err;
2076
2077	if (!TEST_size_t_eq(mpi_len2 = BN_bn2mpi(bn, scratch), mpi_len)
2078	\|\| !TEST_mem_eq(test->mpi, test->mpi_len, scratch, mpi_len))
2079	goto err;
2080
2081	if (!TEST_ptr(bn2 = BN_mpi2bn(scratch, mpi_len, NULL)))
2082	goto err;
2083
2084	if (!TEST_BN_eq(bn, bn2)) {
2085	BN_free(bn2);
2086	goto err;
2087	}
2088	BN_free(bn2);
2089
2090	st = 1;
2091	err:
2092	BN_free(bn);
2093	return st;
2094	}
2095
2096	static int test_rand(void)
2097	{
2098	BIGNUM *bn = NULL;
2099	int st = 0;
2100
2101	if (!TEST_ptr(bn = BN_new()))
2102	return 0;
2103
2104	/* Test BN_rand for degenerate cases with \|top\| and \|bottom\| parameters. */
2105	if (!TEST_false(BN_rand(bn, 0, 0 /* top / , 0 / bottom */ ))
2106	\|\| !TEST_false(BN_rand(bn, 0, 1 /* top / , 1 / bottom */ ))
2107	\|\| !TEST_true(BN_rand(bn, 1, 0 /* top / , 0 / bottom */ ))
2108	\|\| !TEST_BN_eq_one(bn)
2109	\|\| !TEST_false(BN_rand(bn, 1, 1 /* top / , 0 / bottom */ ))
2110	\|\| !TEST_true(BN_rand(bn, 1, -1 /* top / , 1 / bottom */ ))
2111	\|\| !TEST_BN_eq_one(bn)
2112	\|\| !TEST_true(BN_rand(bn, 2, 1 /* top / , 0 / bottom */ ))
2113	\|\| !TEST_BN_eq_word(bn, 3))
2114	goto err;
2115
2116	st = 1;
2117	err:
2118	BN_free(bn);
2119	return st;
2120	}
2121
2122	/*
2123	* Run some statistical tests to provide a degree confidence that the
2124	* BN_rand_range() function works as expected. The test cases and
2125	* critical values are generated by the bn_rand_range script.
2126	*
2127	* Each individual test is a Chi^2 goodness of fit for a specified number
2128	* of samples and range. The samples are assumed to be independent and
2129	* that they are from a discrete uniform distribution.
2130	*
2131	* Some of these individual tests are expected to fail, the success/failure
2132	* of each is an independent Bernoulli trial. The number of such successes
2133	* will form a binomial distribution. The count of the successes is compared
2134	* against a precomputed critical value to determine the overall outcome.
2135	*/
2136	struct rand_range_case {
2137	unsigned int range;
2138	unsigned int iterations;
2139	double critical;
2140	};
2141
2142	#include "bn_rand_range.h"
2143
2144	static int test_rand_range_single(size_t n)
2145	{
2146	const unsigned int range = rand_range_cases[n].range;
2147	const unsigned int iterations = rand_range_cases[n].iterations;
2148	const double critical = rand_range_cases[n].critical;
2149	const double expected = iterations / (double)range;
2150	double sum = 0;
2151	BIGNUM rng = NULL, val = NULL;
2152	size_t *counts;
2153	unsigned int i, v;
2154	int res = 0;
2155
2156	if (!TEST_ptr(counts = OPENSSL_zalloc(sizeof(counts) range))
2157	\|\| !TEST_ptr(rng = BN_new())
2158	\|\| !TEST_ptr(val = BN_new())
2159	\|\| !TEST_true(BN_set_word(rng, range)))
2160	goto err;
2161	for (i = 0; i < iterations; i++) {
2162	if (!TEST_true(BN_rand_range(val, rng))
2163	\|\| !TEST_uint_lt(v = (unsigned int)BN_get_word(val), range))
2164	goto err;
2165	counts[v]++;
2166	}
2167
2168	for (i = 0; i < range; i++) {
2169	const double delta = counts[i] - expected;
2170	sum += delta * delta;
2171	}
2172	sum /= expected;
2173
2174	if (sum > critical) {
2175	TEST_info("Chi^2 test negative %.4f > %4.f", sum, critical);
2176	TEST_note("test case %zu range %u iterations %u", n + 1, range,
2177	iterations);
2178	goto err;
2179	}
2180
2181	res = 1;
2182	err:
2183	BN_free(rng);
2184	BN_free(val);
2185	OPENSSL_free(counts);
2186	return res;
2187	}
2188
2189	static int test_rand_range(void)
2190	{
2191	int n_success = 0;
2192	size_t i;
2193
2194	for (i = 0; i < OSSL_NELEM(rand_range_cases); i++)
2195	n_success += test_rand_range_single(i);
2196	if (TEST_int_ge(n_success, binomial_critical))
2197	return 1;
2198	TEST_note("This test is expected to fail by chance 0.01%% of the time.");
2199	return 0;
2200	}
2201
2202	static int test_negzero(void)
2203	{
2204	BIGNUM a = NULL, b = NULL, c = NULL, d = NULL;
2205	BIGNUM numerator = NULL, denominator = NULL;
2206	int consttime, st = 0;
2207
2208	if (!TEST_ptr(a = BN_new())
2209	\|\| !TEST_ptr(b = BN_new())
2210	\|\| !TEST_ptr(c = BN_new())
2211	\|\| !TEST_ptr(d = BN_new()))
2212	goto err;
2213
2214	/* Test that BN_mul never gives negative zero. */
2215	if (!TEST_true(BN_set_word(a, 1)))
2216	goto err;
2217	BN_set_negative(a, 1);
2218	BN_zero(b);
2219	if (!TEST_true(BN_mul(c, a, b, ctx)))
2220	goto err;
2221	if (!TEST_BN_eq_zero(c)
2222	\|\| !TEST_BN_ge_zero(c))
2223	goto err;
2224
2225	for (consttime = 0; consttime < 2; consttime++) {
2226	if (!TEST_ptr(numerator = BN_new())
2227	\|\| !TEST_ptr(denominator = BN_new()))
2228	goto err;
2229	if (consttime) {
2230	BN_set_flags(numerator, BN_FLG_CONSTTIME);
2231	BN_set_flags(denominator, BN_FLG_CONSTTIME);
2232	}
2233	/* Test that BN_div never gives negative zero in the quotient. */
2234	if (!TEST_true(BN_set_word(numerator, 1))
2235	\|\| !TEST_true(BN_set_word(denominator, 2)))
2236	goto err;
2237	BN_set_negative(numerator, 1);
2238	if (!TEST_true(BN_div(a, b, numerator, denominator, ctx))
2239	\|\| !TEST_BN_eq_zero(a)
2240	\|\| !TEST_BN_ge_zero(a))
2241	goto err;
2242
2243	/* Test that BN_div never gives negative zero in the remainder. */
2244	if (!TEST_true(BN_set_word(denominator, 1))
2245	\|\| !TEST_true(BN_div(a, b, numerator, denominator, ctx))
2246	\|\| !TEST_BN_eq_zero(b)
2247	\|\| !TEST_BN_ge_zero(b))
2248	goto err;
2249	BN_free(numerator);
2250	BN_free(denominator);
2251	numerator = denominator = NULL;
2252	}
2253
2254	/* Test that BN_set_negative will not produce a negative zero. */
2255	BN_zero(a);
2256	BN_set_negative(a, 1);
2257	if (BN_is_negative(a))
2258	goto err;
2259	st = 1;
2260
2261	err:
2262	BN_free(a);
2263	BN_free(b);
2264	BN_free(c);
2265	BN_free(d);
2266	BN_free(numerator);
2267	BN_free(denominator);
2268	return st;
2269	}
2270
2271	static int test_badmod(void)
2272	{
2273	BIGNUM a = NULL, b = NULL, *zero = NULL;
2274	BN_MONT_CTX *mont = NULL;
2275	int st = 0;
2276
2277	if (!TEST_ptr(a = BN_new())
2278	\|\| !TEST_ptr(b = BN_new())
2279	\|\| !TEST_ptr(zero = BN_new())
2280	\|\| !TEST_ptr(mont = BN_MONT_CTX_new()))
2281	goto err;
2282	BN_zero(zero);
2283
2284	if (!TEST_false(BN_div(a, b, BN_value_one(), zero, ctx)))
2285	goto err;
2286	ERR_clear_error();
2287
2288	if (!TEST_false(BN_mod_mul(a, BN_value_one(), BN_value_one(), zero, ctx)))
2289	goto err;
2290	ERR_clear_error();
2291
2292	if (!TEST_false(BN_mod_exp(a, BN_value_one(), BN_value_one(), zero, ctx)))
2293	goto err;
2294	ERR_clear_error();
2295
2296	if (!TEST_false(BN_mod_exp_mont(a, BN_value_one(), BN_value_one(),
2297	zero, ctx, NULL)))
2298	goto err;
2299	ERR_clear_error();
2300
2301	if (!TEST_false(BN_mod_exp_mont_consttime(a, BN_value_one(), BN_value_one(),
2302	zero, ctx, NULL)))
2303	goto err;
2304	ERR_clear_error();
2305
2306	if (!TEST_false(BN_MONT_CTX_set(mont, zero, ctx)))
2307	goto err;
2308	ERR_clear_error();
2309
2310	/* Some operations also may not be used with an even modulus. */
2311	if (!TEST_true(BN_set_word(b, 16)))
2312	goto err;
2313
2314	if (!TEST_false(BN_MONT_CTX_set(mont, b, ctx)))
2315	goto err;
2316	ERR_clear_error();
2317
2318	if (!TEST_false(BN_mod_exp_mont(a, BN_value_one(), BN_value_one(),
2319	b, ctx, NULL)))
2320	goto err;
2321	ERR_clear_error();
2322
2323	if (!TEST_false(BN_mod_exp_mont_consttime(a, BN_value_one(), BN_value_one(),
2324	b, ctx, NULL)))
2325	goto err;
2326	ERR_clear_error();
2327
2328	st = 1;
2329	err:
2330	BN_free(a);
2331	BN_free(b);
2332	BN_free(zero);
2333	BN_MONT_CTX_free(mont);
2334	return st;
2335	}
2336
2337	static int test_expmodzero(void)
2338	{
2339	BIGNUM a = NULL, r = NULL, *zero = NULL;
2340	int st = 0;
2341
2342	if (!TEST_ptr(zero = BN_new())
2343	\|\| !TEST_ptr(a = BN_new())
2344	\|\| !TEST_ptr(r = BN_new()))
2345	goto err;
2346	BN_zero(zero);
2347
2348	if (!TEST_true(BN_mod_exp(r, a, zero, BN_value_one(), NULL))
2349	\|\| !TEST_BN_eq_zero(r)
2350	\|\| !TEST_true(BN_mod_exp_mont(r, a, zero, BN_value_one(),
2351	NULL, NULL))
2352	\|\| !TEST_BN_eq_zero(r)
2353	\|\| !TEST_true(BN_mod_exp_mont_consttime(r, a, zero,
2354	BN_value_one(),
2355	NULL, NULL))
2356	\|\| !TEST_BN_eq_zero(r)
2357	\|\| !TEST_true(BN_mod_exp_mont_word(r, 42, zero,
2358	BN_value_one(), NULL, NULL))
2359	\|\| !TEST_BN_eq_zero(r))
2360	goto err;
2361
2362	st = 1;
2363	err:
2364	BN_free(zero);
2365	BN_free(a);
2366	BN_free(r);
2367	return st;
2368	}
2369
2370	static int test_expmodone(void)
2371	{
2372	int ret = 0, i;
2373	BIGNUM *r = BN_new();
2374	BIGNUM *a = BN_new();
2375	BIGNUM *p = BN_new();
2376	BIGNUM *m = BN_new();
2377
2378	if (!TEST_ptr(r)
2379	\|\| !TEST_ptr(a)
2380	\|\| !TEST_ptr(p)
2381	\|\| !TEST_ptr(p)
2382	\|\| !TEST_ptr(m)
2383	\|\| !TEST_true(BN_set_word(a, 1))
2384	\|\| !TEST_true(BN_set_word(p, 0))
2385	\|\| !TEST_true(BN_set_word(m, 1)))
2386	goto err;
2387
2388	/* Calculate r = 1 ^ 0 mod 1, and check the result is always 0 */
2389	for (i = 0; i < 2; i++) {
2390	if (!TEST_true(BN_mod_exp(r, a, p, m, NULL))
2391	\|\| !TEST_BN_eq_zero(r)
2392	\|\| !TEST_true(BN_mod_exp_mont(r, a, p, m, NULL, NULL))
2393	\|\| !TEST_BN_eq_zero(r)
2394	\|\| !TEST_true(BN_mod_exp_mont_consttime(r, a, p, m, NULL, NULL))
2395	\|\| !TEST_BN_eq_zero(r)
2396	\|\| !TEST_true(BN_mod_exp_mont_word(r, 1, p, m, NULL, NULL))
2397	\|\| !TEST_BN_eq_zero(r)
2398	\|\| !TEST_true(BN_mod_exp_simple(r, a, p, m, NULL))
2399	\|\| !TEST_BN_eq_zero(r)
2400	\|\| !TEST_true(BN_mod_exp_recp(r, a, p, m, NULL))
2401	\|\| !TEST_BN_eq_zero(r))
2402	goto err;
2403	/* Repeat for r = 1 ^ 0 mod -1 */
2404	if (i == 0)
2405	BN_set_negative(m, 1);
2406	}
2407
2408	ret = 1;
2409	err:
2410	BN_free(r);
2411	BN_free(a);
2412	BN_free(p);
2413	BN_free(m);
2414	return ret;
2415	}
2416
2417	static int test_smallprime(int kBits)
2418	{
2419	BIGNUM *r;
2420	int st = 0;
2421
2422	if (!TEST_ptr(r = BN_new()))
2423	goto err;
2424
2425	if (kBits <= 1) {
2426	if (!TEST_false(BN_generate_prime_ex(r, kBits, 0,
2427	NULL, NULL, NULL)))
2428	goto err;
2429	} else {
2430	if (!TEST_true(BN_generate_prime_ex(r, kBits, 0,
2431	NULL, NULL, NULL))
2432	\|\| !TEST_int_eq(BN_num_bits(r), kBits))
2433	goto err;
2434	}
2435
2436	st = 1;
2437	err:
2438	BN_free(r);
2439	return st;
2440	}
2441
2442	static int test_smallsafeprime(int kBits)
2443	{
2444	BIGNUM *r;
2445	int st = 0;
2446
2447	if (!TEST_ptr(r = BN_new()))
2448	goto err;
2449
2450	if (kBits <= 5 && kBits != 3) {
2451	if (!TEST_false(BN_generate_prime_ex(r, kBits, 1,
2452	NULL, NULL, NULL)))
2453	goto err;
2454	} else {
2455	if (!TEST_true(BN_generate_prime_ex(r, kBits, 1,
2456	NULL, NULL, NULL))
2457	\|\| !TEST_int_eq(BN_num_bits(r), kBits))
2458	goto err;
2459	}
2460
2461	st = 1;
2462	err:
2463	BN_free(r);
2464	return st;
2465	}
2466
2467	static int primes[] = { 2, 3, 5, 7, 17863 };
2468
2469	static int test_is_prime(int i)
2470	{
2471	int ret = 0;
2472	BIGNUM *r = NULL;
2473	int trial;
2474
2475	if (!TEST_ptr(r = BN_new()))
2476	goto err;
2477
2478	for (trial = 0; trial <= 1; ++trial) {
2479	if (!TEST_true(BN_set_word(r, primes[i]))
2480	\|\| !TEST_int_eq(BN_check_prime(r, ctx, NULL),
2481	1))
2482	goto err;
2483	}
2484
2485	ret = 1;
2486	err:
2487	BN_free(r);
2488	return ret;
2489	}
2490
2491	static int not_primes[] = { -1, 0, 1, 4 };
2492
2493	static int test_not_prime(int i)
2494	{
2495	int ret = 0;
2496	BIGNUM *r = NULL;
2497	int trial;
2498
2499	if (!TEST_ptr(r = BN_new()))
2500	goto err;
2501
2502	for (trial = 0; trial <= 1; ++trial) {
2503	if (!TEST_true(BN_set_word(r, not_primes[i]))
2504	\|\| !TEST_false(BN_check_prime(r, ctx, NULL)))
2505	goto err;
2506	}
2507
2508	ret = 1;
2509	err:
2510	BN_free(r);
2511	return ret;
2512	}
2513
2514	static int test_ctx_set_ct_flag(BN_CTX *c)
2515	{
2516	int st = 0;
2517	size_t i;
2518	BIGNUM *b[15];
2519
2520	BN_CTX_start(c);
2521	for (i = 0; i < OSSL_NELEM(b); i++) {
2522	if (!TEST_ptr(b[i] = BN_CTX_get(c)))
2523	goto err;
2524	if (i % 2 == 1)
2525	BN_set_flags(b[i], BN_FLG_CONSTTIME);
2526	}
2527
2528	st = 1;
2529	err:
2530	BN_CTX_end(c);
2531	return st;
2532	}
2533
2534	static int test_ctx_check_ct_flag(BN_CTX *c)
2535	{
2536	int st = 0;
2537	size_t i;
2538	BIGNUM *b[30];
2539
2540	BN_CTX_start(c);
2541	for (i = 0; i < OSSL_NELEM(b); i++) {
2542	if (!TEST_ptr(b[i] = BN_CTX_get(c)))
2543	goto err;
2544	if (!TEST_false(BN_get_flags(b[i], BN_FLG_CONSTTIME)))
2545	goto err;
2546	}
2547
2548	st = 1;
2549	err:
2550	BN_CTX_end(c);
2551	return st;
2552	}
2553
2554	static int test_ctx_consttime_flag(void)
2555	{
2556	/*-
2557	* The constant-time flag should not "leak" among BN_CTX frames:
2558	*
2559	* - test_ctx_set_ct_flag() starts a frame in the given BN_CTX and
2560	* sets the BN_FLG_CONSTTIME flag on some of the BIGNUMs obtained
2561	* from the frame before ending it.
2562	* - test_ctx_check_ct_flag() then starts a new frame and gets a
2563	* number of BIGNUMs from it. In absence of leaks, none of the
2564	* BIGNUMs in the new frame should have BN_FLG_CONSTTIME set.
2565	*
2566	* In actual BN_CTX usage inside libcrypto the leak could happen at
2567	* any depth level in the BN_CTX stack, with varying results
2568	* depending on the patterns of sibling trees of nested function
2569	* calls sharing the same BN_CTX object, and the effect of
2570	* unintended BN_FLG_CONSTTIME on the called BN_* functions.
2571	*
2572	* This simple unit test abstracts away this complexity and verifies
2573	* that the leak does not happen between two sibling functions
2574	* sharing the same BN_CTX object at the same level of nesting.
2575	*
2576	*/
2577	BN_CTX *nctx = NULL;
2578	BN_CTX *sctx = NULL;
2579	size_t i = 0;
2580	int st = 0;
2581
2582	if (!TEST_ptr(nctx = BN_CTX_new())
2583	\|\| !TEST_ptr(sctx = BN_CTX_secure_new()))
2584	goto err;
2585
2586	for (i = 0; i < 2; i++) {
2587	BN_CTX *c = i == 0 ? nctx : sctx;
2588	if (!TEST_true(test_ctx_set_ct_flag(c))
2589	\|\| !TEST_true(test_ctx_check_ct_flag(c)))
2590	goto err;
2591	}
2592
2593	st = 1;
2594	err:
2595	BN_CTX_free(nctx);
2596	BN_CTX_free(sctx);
2597	return st;
2598	}
2599
2600	static int test_coprime(void)
2601	{
2602	BIGNUM a = NULL, b = NULL;
2603	int ret = 0;
2604
2605	ret = TEST_ptr(a = BN_new())
2606	&& TEST_ptr(b = BN_new())
2607	&& TEST_true(BN_set_word(a, 66))
2608	&& TEST_true(BN_set_word(b, 99))
2609	&& TEST_int_eq(BN_are_coprime(a, b, ctx), 0)
2610	&& TEST_int_eq(BN_are_coprime(b, a, ctx), 0)
2611	&& TEST_true(BN_set_word(a, 67))
2612	&& TEST_int_eq(BN_are_coprime(a, b, ctx), 1)
2613	&& TEST_int_eq(BN_are_coprime(b, a, ctx), 1);
2614	BN_free(a);
2615	BN_free(b);
2616	return ret;
2617	}
2618
2619	static int test_gcd_prime(void)
2620	{
2621	BIGNUM a = NULL, b = NULL, *gcd = NULL;
2622	int i, st = 0;
2623
2624	if (!TEST_ptr(a = BN_new())
2625	\|\| !TEST_ptr(b = BN_new())
2626	\|\| !TEST_ptr(gcd = BN_new()))
2627	goto err;
2628
2629	if (!TEST_true(BN_generate_prime_ex(a, 1024, 0, NULL, NULL, NULL)))
2630	goto err;
2631	for (i = 0; i < NUM_PRIME_TESTS; i++) {
2632	if (!TEST_true(BN_generate_prime_ex(b, 1024, 0,
2633	NULL, NULL, NULL))
2634	\|\| !TEST_true(BN_gcd(gcd, a, b, ctx))
2635	\|\| !TEST_true(BN_is_one(gcd))
2636	\|\| !TEST_true(BN_are_coprime(a, b, ctx)))
2637	goto err;
2638	}
2639
2640	st = 1;
2641	err:
2642	BN_free(a);
2643	BN_free(b);
2644	BN_free(gcd);
2645	return st;
2646	}
2647
2648	typedef struct mod_exp_test_st
2649	{
2650	const char *base;
2651	const char *exp;
2652	const char *mod;
2653	const char *res;
2654	} MOD_EXP_TEST;
2655
2656	static const MOD_EXP_TEST ModExpTests[] = {
2657	/* original test vectors for rsaz_512_sqr bug, by OSS-Fuzz */
2658	{
2659	"1166180238001879113042182292626169621106255558914000595999312084"
2660	"4627946820899490684928760491249738643524880720584249698100907201"
2661	"002086675047927600340800371",
2662	"8000000000000000000000000000000000000000000000000000000000000000"
2663	"0000000000000000000000000000000000000000000000000000000000000000"
2664	"00000000",
2665	"1340780792684523720980737645613191762604395855615117867483316354"
2666	"3294276330515137663421134775482798690129946803802212663956180562"
2667	"088664022929883876655300863",
2668	"8243904058268085430037326628480645845409758077568738532059032482"
2669	"8294114415890603594730158120426756266457928475330450251339773498"
2670	"26758407619521544102068438"
2671	},
2672	{
2673	"4974270041410803822078866696159586946995877618987010219312844726"
2674	"0284386121835740784990869050050504348861513337232530490826340663"
2675	"197278031692737429054",
2676	"4974270041410803822078866696159586946995877428188754995041148539"
2677	"1663243362592271353668158565195557417149981094324650322556843202"
2678	"946445882670777892608",
2679	"1340780716511420227215592830971452482815377482627251725537099028"
2680	"4429769497230131760206012644403029349547320953206103351725462999"
2681	"947509743623340557059752191",
2682	"5296244594780707015616522701706118082963369547253192207884519362"
2683	"1767869984947542695665420219028522815539559194793619684334900442"
2684	"49304558011362360473525933"
2685	},
2686	/* test vectors for rsaz_512_srq bug, with rcx/rbx=1 */
2687	{ /* between first and second iteration */
2688	"5148719036160389201525610950887605325980251964889646556085286545"
2689	"3931548809178823413169359635978762036512397113080988070677858033"
2690	"36463909753993540214027190",
2691	"6703903964971298549787012499102923063739682910296196688861780721"
2692	"8608820150367734884009371490834517138450159290932430254268769414"
2693	"05973284973216824503042158",
2694	"6703903964971298549787012499102923063739682910296196688861780721"
2695	"8608820150367734884009371490834517138450159290932430254268769414"
2696	"05973284973216824503042159",
2697	"1"
2698	},
2699	{ /* between second and third iteration */
2700	"8908340854353752577419678771330460827942371434853054158622636544"
2701	"8151360109722890949471912566649465436296659601091730745087014189"
2702	"2672764191218875181826063",
2703	"6703903964971298549787012499102923063739682910296196688861780721"
2704	"8608820150367734884009371490834517138450159290932430254268769414"
2705	"05973284973216824503042158",
2706	"6703903964971298549787012499102923063739682910296196688861780721"
2707	"8608820150367734884009371490834517138450159290932430254268769414"
2708	"05973284973216824503042159",
2709	"1"
2710	},
2711	{ /* between third and fourth iteration */
2712	"3427446396505596330634350984901719674479522569002785244080234738"
2713	"4288743635435746136297299366444548736533053717416735379073185344"
2714	"26985272974404612945608761",
2715	"6703903964971298549787012499102923063739682910296196688861780721"
2716	"8608820150367734884009371490834517138450159290932430254268769414"
2717	"05973284973216824503042158",
2718	"6703903964971298549787012499102923063739682910296196688861780721"
2719	"8608820150367734884009371490834517138450159290932430254268769414"
2720	"05973284973216824503042159",
2721	"1"
2722	},
2723	{ /* between fourth and fifth iteration */
2724	"3472743044917564564078857826111874560045331237315597383869652985"
2725	"6919870028890895988478351133601517365908445058405433832718206902"
2726	"4088133164805266956353542",
2727	"6703903964971298549787012499102923063739682910296196688861780721"
2728	"8608820150367734884009371490834517138450159290932430254268769414"
2729	"05973284973216824503042158",
2730	"6703903964971298549787012499102923063739682910296196688861780721"
2731	"8608820150367734884009371490834517138450159290932430254268769414"
2732	"05973284973216824503042159",
2733	"1"
2734	},
2735	{ /* between fifth and sixth iteration */
2736	"3608632990153469264412378349742339216742409743898601587274768025"
2737	"0110772032985643555192767717344946174122842255204082586753499651"
2738	"14483434992887431333675068",
2739	"6703903964971298549787012499102923063739682910296196688861780721"
2740	"8608820150367734884009371490834517138450159290932430254268769414"
2741	"05973284973216824503042158",
2742	"6703903964971298549787012499102923063739682910296196688861780721"
2743	"8608820150367734884009371490834517138450159290932430254268769414"
2744	"05973284973216824503042159",
2745	"1"
2746	},
2747	{ /* between sixth and seventh iteration */
2748	"8455374370234070242910508226941981520235709767260723212165264877"
2749	"8689064388017521524568434328264431772644802567028663962962025746"
2750	"9283458217850119569539086",
2751	"6703903964971298549787012499102923063739682910296196688861780721"
2752	"8608820150367734884009371490834517138450159290932430254268769414"
2753	"05973284973216824503042158",
2754	"6703903964971298549787012499102923063739682910296196688861780721"
2755	"8608820150367734884009371490834517138450159290932430254268769414"
2756	"05973284973216824503042159",
2757	"1"
2758	},
2759	{ /* between seventh and eighth iteration */
2760	"5155371529688532178421209781159131443543419764974688878527112131"
2761	"7446518205609427412336183157918981038066636807317733319323257603"
2762	"04416292040754017461076359",
2763	"1005585594745694782468051874865438459560952436544429503329267108"
2764	"2791323022555160232601405723625177570767523893639864538140315412"
2765	"108959927459825236754563832",
2766	"1005585594745694782468051874865438459560952436544429503329267108"
2767	"2791323022555160232601405723625177570767523893639864538140315412"
2768	"108959927459825236754563833",
2769	"1"
2770	},
2771	/* test vectors for rsaz_512_srq bug, with rcx/rbx=2 */
2772	{ /* between first and second iteration */
2773	"3155666506033786929967309937640790361084670559125912405342594979"
2774	"4345142818528956285490897841406338022378565972533508820577760065"
2775	"58494345853302083699912572",
2776	"6703903964971298549787012499102923063739682910296196688861780721"
2777	"8608820150367734884009371490834517138450159290932430254268769414"
2778	"05973284973216824503042158",
2779	"6703903964971298549787012499102923063739682910296196688861780721"
2780	"8608820150367734884009371490834517138450159290932430254268769414"
2781	"05973284973216824503042159",
2782	"1"
2783	},
2784	{ /* between second and third iteration */
2785	"3789819583801342198190405714582958759005991915505282362397087750"
2786	"4213544724644823098843135685133927198668818185338794377239590049"
2787	"41019388529192775771488319",
2788	"6703903964971298549787012499102923063739682910296196688861780721"
2789	"8608820150367734884009371490834517138450159290932430254268769414"
2790	"05973284973216824503042158",
2791	"6703903964971298549787012499102923063739682910296196688861780721"
2792	"8608820150367734884009371490834517138450159290932430254268769414"
2793	"05973284973216824503042159",
2794	"1"
2795	},
2796	{ /* between third and forth iteration */
2797	"4695752552040706867080542538786056470322165281761525158189220280"
2798	"4025547447667484759200742764246905647644662050122968912279199065"
2799	"48065034299166336940507214",
2800	"6703903964971298549787012499102923063739682910296196688861780721"
2801	"8608820150367734884009371490834517138450159290932430254268769414"
2802	"05973284973216824503042158",
2803	"6703903964971298549787012499102923063739682910296196688861780721"
2804	"8608820150367734884009371490834517138450159290932430254268769414"
2805	"05973284973216824503042159",
2806	"1"
2807	},
2808	{ /* between forth and fifth iteration */
2809	"2159140240970485794188159431017382878636879856244045329971239574"
2810	"8919691133560661162828034323196457386059819832804593989740268964"
2811	"74502911811812651475927076",
2812	"6703903964971298549787012499102923063739682910296196688861780721"
2813	"8608820150367734884009371490834517138450159290932430254268769414"
2814	"05973284973216824503042158",
2815	"6703903964971298549787012499102923063739682910296196688861780721"
2816	"8608820150367734884009371490834517138450159290932430254268769414"
2817	"05973284973216824503042159",
2818	"1"
2819	},
2820	{ /* between fifth and sixth iteration */
2821	"5239312332984325668414624633307915097111691815000872662334695514"
2822	"5436533521392362443557163429336808208137221322444780490437871903"
2823	"99972784701334569424519255",
2824	"6703903964971298549787012499102923063739682910296196688861780721"
2825	"8608820150367734884009371490834517138450159290932430254268769414"
2826	"05973284973216824503042158",
2827	"6703903964971298549787012499102923063739682910296196688861780721"
2828	"8608820150367734884009371490834517138450159290932430254268769414"
2829	"05973284973216824503042159",
2830	"1"
2831	},
2832	{ /* between sixth and seventh iteration */
2833	"1977953647322612860406858017869125467496941904523063466791308891"
2834	"1172796739058531929470539758361774569875505293428856181093904091"
2835	"33788264851714311303725089",
2836	"6703903964971298549787012499102923063739682910296196688861780721"
2837	"8608820150367734884009371490834517138450159290932430254268769414"
2838	"05973284973216824503042158",
2839	"6703903964971298549787012499102923063739682910296196688861780721"
2840	"8608820150367734884009371490834517138450159290932430254268769414"
2841	"05973284973216824503042159",
2842	"1"
2843	},
2844	{ /* between seventh and eighth iteration */
2845	"6456987954117763835533395796948878140715006860263624787492985786"
2846	"8514630216966738305923915688821526449499763719943997120302368211"
2847	"04813318117996225041943964",
2848	"1340780792994259709957402499820584612747936582059239337772356144"
2849	"3721764030073546976801874298166903427690031858186486050853753882"
2850	"811946551499689575296532556",
2851	"1340780792994259709957402499820584612747936582059239337772356144"
2852	"3721764030073546976801874298166903427690031858186486050853753882"
2853	"811946551499689575296532557",
2854	"1"
2855	}
2856	};
2857
2858	static int test_mod_exp(int i)
2859	{
2860	const MOD_EXP_TEST *test = &ModExpTests[i];
2861	int res = 0;
2862	BIGNUM* result = NULL;
2863	BIGNUM base = NULL, exponent = NULL, *modulo = NULL;
2864	char *s = NULL;
2865
2866	if (!TEST_ptr(result = BN_new())
2867	\|\| !TEST_true(BN_dec2bn(&base, test->base))
2868	\|\| !TEST_true(BN_dec2bn(&exponent, test->exp))
2869	\|\| !TEST_true(BN_dec2bn(&modulo, test->mod)))
2870	goto err;
2871
2872	if (!TEST_int_eq(BN_mod_exp(result, base, exponent, modulo, ctx), 1))
2873	goto err;
2874
2875	if (!TEST_ptr(s = BN_bn2dec(result)))
2876	goto err;
2877
2878	if (!TEST_mem_eq(s, strlen(s), test->res, strlen(test->res)))
2879	goto err;
2880
2881	res = 1;
2882
2883	err:
2884	OPENSSL_free(s);
2885	BN_free(result);
2886	BN_free(base);
2887	BN_free(exponent);
2888	BN_free(modulo);
2889	return res;
2890	}
2891
2892	static int test_mod_exp_consttime(int i)
2893	{
2894	const MOD_EXP_TEST *test = &ModExpTests[i];
2895	int res = 0;
2896	BIGNUM* result = NULL;
2897	BIGNUM base = NULL, exponent = NULL, *modulo = NULL;
2898	char *s = NULL;
2899
2900	if (!TEST_ptr(result = BN_new())
2901	\|\| !TEST_true(BN_dec2bn(&base, test->base))
2902	\|\| !TEST_true(BN_dec2bn(&exponent, test->exp))
2903	\|\| !TEST_true(BN_dec2bn(&modulo, test->mod)))
2904	goto err;
2905
2906	BN_set_flags(base, BN_FLG_CONSTTIME);
2907	BN_set_flags(exponent, BN_FLG_CONSTTIME);
2908	BN_set_flags(modulo, BN_FLG_CONSTTIME);
2909
2910	if (!TEST_int_eq(BN_mod_exp(result, base, exponent, modulo, ctx), 1))
2911	goto err;
2912
2913	if (!TEST_ptr(s = BN_bn2dec(result)))
2914	goto err;
2915
2916	if (!TEST_mem_eq(s, strlen(s), test->res, strlen(test->res)))
2917	goto err;
2918
2919	res = 1;
2920
2921	err:
2922	OPENSSL_free(s);
2923	BN_free(result);
2924	BN_free(base);
2925	BN_free(exponent);
2926	BN_free(modulo);
2927	return res;
2928	}
2929
2930	/*
2931	* Regression test to ensure BN_mod_exp2_mont fails safely if argument m is
2932	* zero.
2933	*/
2934	static int test_mod_exp2_mont(void)
2935	{
2936	int res = 0;
2937	BIGNUM *exp_result = NULL;
2938	BIGNUM exp_a1 = NULL, exp_p1 = NULL, exp_a2 = NULL, exp_p2 = NULL,
2939	*exp_m = NULL;
2940
2941	if (!TEST_ptr(exp_result = BN_new())
2942	\|\| !TEST_ptr(exp_a1 = BN_new())
2943	\|\| !TEST_ptr(exp_p1 = BN_new())
2944	\|\| !TEST_ptr(exp_a2 = BN_new())
2945	\|\| !TEST_ptr(exp_p2 = BN_new())
2946	\|\| !TEST_ptr(exp_m = BN_new()))
2947	goto err;
2948
2949	if (!TEST_true(BN_one(exp_a1))
2950	\|\| !TEST_true(BN_one(exp_p1))
2951	\|\| !TEST_true(BN_one(exp_a2))
2952	\|\| !TEST_true(BN_one(exp_p2)))
2953	goto err;
2954
2955	BN_zero(exp_m);
2956
2957	/* input of 0 is even, so must fail */
2958	if (!TEST_int_eq(BN_mod_exp2_mont(exp_result, exp_a1, exp_p1, exp_a2,
2959	exp_p2, exp_m, ctx, NULL), 0))
2960	goto err;
2961
2962	res = 1;
2963
2964	err:
2965	BN_free(exp_result);
2966	BN_free(exp_a1);
2967	BN_free(exp_p1);
2968	BN_free(exp_a2);
2969	BN_free(exp_p2);
2970	BN_free(exp_m);
2971	return res;
2972	}
2973
2974	static int test_mod_inverse(void)
2975	{
2976	int res = 0;
2977	char *str = NULL;
2978	BIGNUM *a = NULL;
2979	BIGNUM *b = NULL;
2980	BIGNUM *r = NULL;
2981
2982	if (!TEST_true(BN_dec2bn(&a, "5193817943")))
2983	goto err;
2984	if (!TEST_true(BN_dec2bn(&b, "3259122431")))
2985	goto err;
2986	if (!TEST_ptr(r = BN_new()))
2987	goto err;
2988	if (!TEST_ptr_eq(BN_mod_inverse(r, a, b, ctx), r))
2989	goto err;
2990	if (!TEST_ptr_ne(str = BN_bn2dec(r), NULL))
2991	goto err;
2992	if (!TEST_int_eq(strcmp(str, "2609653924"), 0))
2993	goto err;
2994
2995	/* Note that this aliases the result with the modulus. */
2996	if (!TEST_ptr_null(BN_mod_inverse(b, a, b, ctx)))
2997	goto err;
2998
2999	res = 1;
3000
3001	err:
3002	BN_free(a);
3003	BN_free(b);
3004	BN_free(r);
3005	OPENSSL_free(str);
3006	return res;
3007	}
3008
3009	static int test_mod_exp_alias(int idx)
3010	{
3011	int res = 0;
3012	char *str = NULL;
3013	BIGNUM *a = NULL;
3014	BIGNUM *b = NULL;
3015	BIGNUM *c = NULL;
3016	BIGNUM *r = NULL;
3017
3018	if (!TEST_true(BN_dec2bn(&a, "15")))
3019	goto err;
3020	if (!TEST_true(BN_dec2bn(&b, "10")))
3021	goto err;
3022	if (!TEST_true(BN_dec2bn(&c, "39")))
3023	goto err;
3024	if (!TEST_ptr(r = BN_new()))
3025	goto err;
3026
3027	if (!TEST_int_eq((idx == 0 ? BN_mod_exp_simple
3028	: BN_mod_exp_recp)(r, a, b, c, ctx), 1))
3029	goto err;
3030	if (!TEST_ptr_ne(str = BN_bn2dec(r), NULL))
3031	goto err;
3032	if (!TEST_str_eq(str, "36"))
3033	goto err;
3034
3035	OPENSSL_free(str);
3036	str = NULL;
3037
3038	BN_copy(r, b);
3039
3040	/* Aliasing with exponent must work. */
3041	if (!TEST_int_eq((idx == 0 ? BN_mod_exp_simple
3042	: BN_mod_exp_recp)(r, a, r, c, ctx), 1))
3043	goto err;
3044	if (!TEST_ptr_ne(str = BN_bn2dec(r), NULL))
3045	goto err;
3046	if (!TEST_str_eq(str, "36"))
3047	goto err;
3048
3049	OPENSSL_free(str);
3050	str = NULL;
3051
3052	/* Aliasing with modulus should return failure for the simple call. */
3053	if (idx == 0) {
3054	if (!TEST_int_eq(BN_mod_exp_simple(c, a, b, c, ctx), 0))
3055	goto err;
3056	} else {
3057	if (!TEST_int_eq(BN_mod_exp_recp(c, a, b, c, ctx), 1))
3058	goto err;
3059	if (!TEST_ptr_ne(str = BN_bn2dec(c), NULL))
3060	goto err;
3061	if (!TEST_str_eq(str, "36"))
3062	goto err;
3063	}
3064
3065	res = 1;
3066
3067	err:
3068	BN_free(a);
3069	BN_free(b);
3070	BN_free(c);
3071	BN_free(r);
3072	OPENSSL_free(str);
3073	return res;
3074	}
3075
3076	static int file_test_run(STANZA *s)
3077	{
3078	static const FILETEST filetests[] = {
3079	{"Sum", file_sum},
3080	{"LShift1", file_lshift1},
3081	{"LShift", file_lshift},
3082	{"RShift", file_rshift},
3083	{"Square", file_square},
3084	{"Product", file_product},
3085	{"Quotient", file_quotient},
3086	{"ModMul", file_modmul},
3087	{"ModExp", file_modexp},
3088	{"Exp", file_exp},
3089	{"ModSqrt", file_modsqrt},
3090	{"GCD", file_gcd},
3091	};
3092	int numtests = OSSL_NELEM(filetests);
3093	const FILETEST *tp = filetests;
3094
3095	for ( ; --numtests >= 0; tp++) {
3096	if (findattr(s, tp->name) != NULL) {
3097	if (!tp->func(s)) {
3098	TEST_info("%s:%d: Failed %s test",
3099	s->test_file, s->start, tp->name);
3100	return 0;
3101	}
3102	return 1;
3103	}
3104	}
3105	TEST_info("%s:%d: Unknown test", s->test_file, s->start);
3106	return 0;
3107	}
3108
3109	static int run_file_tests(int i)
3110	{
3111	STANZA *s = NULL;
3112	char *testfile = test_get_argument(i);
3113	int c;
3114
3115	if (!TEST_ptr(s = OPENSSL_zalloc(sizeof(*s))))
3116	return 0;
3117	if (!test_start_file(s, testfile)) {
3118	OPENSSL_free(s);
3119	return 0;
3120	}
3121
3122	/* Read test file. */
3123	while (!BIO_eof(s->fp) && test_readstanza(s)) {
3124	if (s->numpairs == 0)
3125	continue;
3126	if (!file_test_run(s))
3127	s->errors++;
3128	s->numtests++;
3129	test_clearstanza(s);
3130	}
3131	test_end_file(s);
3132	c = s->errors;
3133	OPENSSL_free(s);
3134
3135	return c == 0;
3136	}
3137
3138	typedef enum OPTION_choice {
3139	OPT_ERR = -1,
3140	OPT_EOF = 0,
3141	OPT_STOCHASTIC_TESTS,
3142	OPT_TEST_ENUM
3143	} OPTION_CHOICE;
3144
3145	const OPTIONS *test_get_options(void)
3146	{
3147	static const OPTIONS test_options[] = {
3148	OPT_TEST_OPTIONS_WITH_EXTRA_USAGE("[file...]\n"),
3149	{ "stochastic", OPT_STOCHASTIC_TESTS, '-', "Run stochastic tests" },
3150	{ OPT_HELP_STR, 1, '-',
3151	"file\tFile to run tests on. Normal tests are not run\n" },
3152	{ NULL }
3153	};
3154	return test_options;
3155	}
3156
3157	int setup_tests(void)
3158	{
3159	OPTION_CHOICE o;
3160	int n, stochastic = 0;
3161
3162	while ((o = opt_next()) != OPT_EOF) {
3163	switch (o) {
3164	case OPT_STOCHASTIC_TESTS:
3165	stochastic = 1;
3166	break;
3167	case OPT_TEST_CASES:
3168	break;
3169	default:
3170	case OPT_ERR:
3171	return 0;
3172	}
3173	}
3174	n = test_get_argument_count();
3175
3176	if (!TEST_ptr(ctx = BN_CTX_new()))
3177	return 0;
3178
3179	if (n == 0) {
3180	ADD_TEST(test_sub);
3181	ADD_TEST(test_div_recip);
3182	ADD_ALL_TESTS(test_signed_mod_replace_ab, OSSL_NELEM(signed_mod_tests));
3183	ADD_ALL_TESTS(test_signed_mod_replace_ba, OSSL_NELEM(signed_mod_tests));
3184	ADD_TEST(test_mod);
3185	ADD_TEST(test_mod_inverse);
3186	ADD_ALL_TESTS(test_mod_exp_alias, 2);
3187	ADD_TEST(test_modexp_mont5);
3188	ADD_TEST(test_kronecker);
3189	ADD_TEST(test_rand);
3190	ADD_TEST(test_bn2padded);
3191	ADD_TEST(test_dec2bn);
3192	ADD_TEST(test_hex2bn);
3193	ADD_TEST(test_asc2bn);
3194	ADD_ALL_TESTS(test_mpi, (int)OSSL_NELEM(kMPITests));
3195	ADD_TEST(test_negzero);
3196	ADD_TEST(test_badmod);
3197	ADD_TEST(test_expmodzero);
3198	ADD_TEST(test_expmodone);
3199	ADD_ALL_TESTS(test_smallprime, 16);
3200	ADD_ALL_TESTS(test_smallsafeprime, 16);
3201	ADD_TEST(test_swap);
3202	ADD_TEST(test_ctx_consttime_flag);
3203	#ifndef OPENSSL_NO_EC2M
3204	ADD_TEST(test_gf2m_add);
3205	ADD_TEST(test_gf2m_mod);
3206	ADD_TEST(test_gf2m_mul);
3207	ADD_TEST(test_gf2m_sqr);
3208	ADD_TEST(test_gf2m_modinv);
3209	ADD_TEST(test_gf2m_moddiv);
3210	ADD_TEST(test_gf2m_modexp);
3211	ADD_TEST(test_gf2m_modsqrt);
3212	ADD_TEST(test_gf2m_modsolvequad);
3213	#endif
3214	ADD_ALL_TESTS(test_is_prime, (int)OSSL_NELEM(primes));
3215	ADD_ALL_TESTS(test_not_prime, (int)OSSL_NELEM(not_primes));
3216	ADD_TEST(test_gcd_prime);
3217	ADD_TEST(test_coprime);
3218	ADD_ALL_TESTS(test_mod_exp, (int)OSSL_NELEM(ModExpTests));
3219	ADD_ALL_TESTS(test_mod_exp_consttime, (int)OSSL_NELEM(ModExpTests));
3220	ADD_TEST(test_mod_exp2_mont);
3221	if (stochastic)
3222	ADD_TEST(test_rand_range);
3223	} else {
3224	ADD_ALL_TESTS(run_file_tests, n);
3225	}
3226	return 1;
3227	}
3228
3229	void cleanup_tests(void)
3230	{
3231	BN_CTX_free(ctx);
3232	}

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

source: vbox/trunk/src/libs/openssl-3.1.7/test/bntest.c@ 106165

以其他格式下載: