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