summaryrefslogtreecommitdiff
path: root/src/regress/lib/libcrypto/bn/bn_test.c
diff options
context:
space:
mode:
authortb <>2022-12-01 20:50:10 +0000
committertb <>2022-12-01 20:50:10 +0000
commit1ee4f78484654f244b792d02de8a59790eaa8d57 (patch)
tree9c919d8b5975d41dccaa87e47c91d601f9dd9857 /src/regress/lib/libcrypto/bn/bn_test.c
parent27a426a371fafd6a5de905f5335425a4f20844fb (diff)
downloadopenbsd-1ee4f78484654f244b792d02de8a59790eaa8d57.tar.gz
openbsd-1ee4f78484654f244b792d02de8a59790eaa8d57.tar.bz2
openbsd-1ee4f78484654f244b792d02de8a59790eaa8d57.zip
Flatten structure of libcrypto/bn tests
The bn tests were distributed into three subdirectories rather randomly. It's cleaner and easier to maintain if all this is in a single directory. Use consistent names for the .c files, unify handling of the tests with the exception of bn_test, which is special. Discussed with jsing
Diffstat (limited to 'src/regress/lib/libcrypto/bn/bn_test.c')
-rw-r--r--src/regress/lib/libcrypto/bn/bn_test.c2624
1 files changed, 2624 insertions, 0 deletions
diff --git a/src/regress/lib/libcrypto/bn/bn_test.c b/src/regress/lib/libcrypto/bn/bn_test.c
new file mode 100644
index 0000000000..c1feddeda1
--- /dev/null
+++ b/src/regress/lib/libcrypto/bn/bn_test.c
@@ -0,0 +1,2624 @@
1/* $OpenBSD: bn_test.c,v 1.1 2022/12/01 20:50:10 tb Exp $ */
2/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
3 * All rights reserved.
4 *
5 * This package is an SSL implementation written
6 * by Eric Young (eay@cryptsoft.com).
7 * The implementation was written so as to conform with Netscapes SSL.
8 *
9 * This library is free for commercial and non-commercial use as long as
10 * the following conditions are aheared to. The following conditions
11 * apply to all code found in this distribution, be it the RC4, RSA,
12 * lhash, DES, etc., code; not just the SSL code. The SSL documentation
13 * included with this distribution is covered by the same copyright terms
14 * except that the holder is Tim Hudson (tjh@cryptsoft.com).
15 *
16 * Copyright remains Eric Young's, and as such any Copyright notices in
17 * the code are not to be removed.
18 * If this package is used in a product, Eric Young should be given attribution
19 * as the author of the parts of the library used.
20 * This can be in the form of a textual message at program startup or
21 * in documentation (online or textual) provided with the package.
22 *
23 * Redistribution and use in source and binary forms, with or without
24 * modification, are permitted provided that the following conditions
25 * are met:
26 * 1. Redistributions of source code must retain the copyright
27 * notice, this list of conditions and the following disclaimer.
28 * 2. Redistributions in binary form must reproduce the above copyright
29 * notice, this list of conditions and the following disclaimer in the
30 * documentation and/or other materials provided with the distribution.
31 * 3. All advertising materials mentioning features or use of this software
32 * must display the following acknowledgement:
33 * "This product includes cryptographic software written by
34 * Eric Young (eay@cryptsoft.com)"
35 * The word 'cryptographic' can be left out if the rouines from the library
36 * being used are not cryptographic related :-).
37 * 4. If you include any Windows specific code (or a derivative thereof) from
38 * the apps directory (application code) you must include an acknowledgement:
39 * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)"
40 *
41 * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND
42 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
43 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
44 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
45 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
46 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
47 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
48 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
49 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
50 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
51 * SUCH DAMAGE.
52 *
53 * The licence and distribution terms for any publically available version or
54 * derivative of this code cannot be changed. i.e. this code cannot simply be
55 * copied and put under another distribution licence
56 * [including the GNU Public Licence.]
57 */
58/* ====================================================================
59 * Copyright 2002 Sun Microsystems, Inc. ALL RIGHTS RESERVED.
60 *
61 * Portions of the attached software ("Contribution") are developed by
62 * SUN MICROSYSTEMS, INC., and are contributed to the OpenSSL project.
63 *
64 * The Contribution is licensed pursuant to the Eric Young open source
65 * license provided above.
66 *
67 * The binary polynomial arithmetic software is originally written by
68 * Sheueling Chang Shantz and Douglas Stebila of Sun Microsystems Laboratories.
69 *
70 */
71
72/* Until the key-gen callbacks are modified to use newer prototypes, we allow
73 * deprecated functions for openssl-internal code */
74#ifdef OPENSSL_NO_DEPRECATED
75#undef OPENSSL_NO_DEPRECATED
76#endif
77
78#include <stdio.h>
79#include <stdlib.h>
80#include <string.h>
81
82#include <openssl/bio.h>
83#include <openssl/bn.h>
84#include <openssl/x509.h>
85#include <openssl/err.h>
86
87int BN_mod_exp_ct(BIGNUM *r, const BIGNUM *a, const BIGNUM *p,
88 const BIGNUM *m, BN_CTX *ctx);
89int BN_mod_exp_nonct(BIGNUM *r, const BIGNUM *a, const BIGNUM *p,
90 const BIGNUM *m, BN_CTX *ctx);
91int BN_mod_exp_mont_ct(BIGNUM *r, const BIGNUM *a, const BIGNUM *p,
92 const BIGNUM *m, BN_CTX *ctx, BN_MONT_CTX *m_ctx);
93int BN_mod_exp_mont_nonct(BIGNUM *r, const BIGNUM *a, const BIGNUM *p,
94 const BIGNUM *m, BN_CTX *ctx, BN_MONT_CTX *m_ctx);
95
96int BN_bntest_rand(BIGNUM *rnd, int bits, int top, int bottom);
97
98const int num0 = 100; /* number of tests */
99const int num1 = 50; /* additional tests for some functions */
100const int num2 = 5; /* number of tests for slow functions */
101
102int test_add(BIO *bp);
103int test_sub(BIO *bp);
104int test_lshift1(BIO *bp);
105int test_lshift(BIO *bp, BN_CTX *ctx, BIGNUM *a_);
106int test_rshift1(BIO *bp);
107int test_rshift(BIO *bp, BN_CTX *ctx);
108int test_div(BIO *bp, BN_CTX *ctx);
109int test_div_word(BIO *bp);
110int test_div_recp(BIO *bp, BN_CTX *ctx);
111int test_mul(BIO *bp);
112int test_sqr(BIO *bp, BN_CTX *ctx);
113int test_mont(BIO *bp, BN_CTX *ctx);
114int test_mod(BIO *bp, BN_CTX *ctx);
115int test_mod_mul(BIO *bp, BN_CTX *ctx);
116int test_mod_exp(BIO *bp, BN_CTX *ctx);
117int test_mod_exp_mont_consttime(BIO *bp, BN_CTX *ctx);
118int test_mod_exp_mont5(BIO *bp, BN_CTX *ctx);
119int test_mod_exp_sizes(BIO *bp, BN_CTX *ctx);
120int test_exp(BIO *bp, BN_CTX *ctx);
121int test_gf2m_add(BIO *bp);
122int test_gf2m_mod(BIO *bp);
123int test_gf2m_mod_mul(BIO *bp, BN_CTX *ctx);
124int test_gf2m_mod_sqr(BIO *bp, BN_CTX *ctx);
125int test_gf2m_mod_inv(BIO *bp, BN_CTX *ctx);
126int test_gf2m_mod_div(BIO *bp, BN_CTX *ctx);
127int test_gf2m_mod_exp(BIO *bp, BN_CTX *ctx);
128int test_gf2m_mod_sqrt(BIO *bp, BN_CTX *ctx);
129int test_gf2m_mod_solve_quad(BIO *bp, BN_CTX *ctx);
130int test_kron(BIO *bp, BN_CTX *ctx);
131int test_sqrt(BIO *bp, BN_CTX *ctx);
132int rand_neg(void);
133static int results = 0;
134
135static unsigned char lst[] =
136 "\xC6\x4F\x43\x04\x2A\xEA\xCA\x6E\x58\x36\x80\x5B\xE8\xC9"
137 "\x9B\x04\x5D\x48\x36\xC2\xFD\x16\xC9\x64\xF0";
138
139#define PRINT_ERROR printf("Error in %s [%s:%d]\n", __func__, __FILE__, \
140 __LINE__)
141
142#define CHECK_GOTO(a) do { \
143 if (!(a)) { \
144 PRINT_ERROR; \
145 rc = 0; \
146 goto err; \
147 } \
148} while (0)
149
150static void
151message(BIO *out, char *m)
152{
153 fprintf(stderr, "test %s\n", m);
154 BIO_puts(out, "print \"test ");
155 BIO_puts(out, m);
156 BIO_puts(out, "\\n\"\n");
157}
158
159int
160main(int argc, char *argv[])
161{
162 BN_CTX *ctx;
163 BIO *out;
164 char *outfile = NULL;
165
166 results = 0;
167
168 argc--;
169 argv++;
170 while (argc >= 1) {
171 if (strcmp(*argv, "-results") == 0)
172 results = 1;
173 else if (strcmp(*argv, "-out") == 0) {
174 if (--argc < 1)
175 break;
176 outfile= *(++argv);
177 }
178 argc--;
179 argv++;
180 }
181
182
183 ctx = BN_CTX_new();
184 if (ctx == NULL)
185 exit(1);
186
187 out = BIO_new(BIO_s_file());
188 if (out == NULL)
189 exit(1);
190 if (outfile == NULL) {
191 BIO_set_fp(out, stdout, BIO_NOCLOSE);
192 } else {
193 if (!BIO_write_filename(out, outfile)) {
194 perror(outfile);
195 exit(1);
196 }
197 }
198
199 if (!results)
200 BIO_puts(out, "obase=16\nibase=16\n");
201
202 message(out, "BN_add");
203 if (!test_add(out))
204 goto err;
205 (void)BIO_flush(out);
206
207 message(out, "BN_sub");
208 if (!test_sub(out))
209 goto err;
210 (void)BIO_flush(out);
211
212 message(out, "BN_lshift1");
213 if (!test_lshift1(out))
214 goto err;
215 (void)BIO_flush(out);
216
217 message(out, "BN_lshift (fixed)");
218 if (!test_lshift(out, ctx, BN_bin2bn(lst, sizeof(lst) - 1, NULL)))
219 goto err;
220 (void)BIO_flush(out);
221
222 message(out, "BN_lshift");
223 if (!test_lshift(out, ctx, NULL))
224 goto err;
225 (void)BIO_flush(out);
226
227 message(out, "BN_rshift1");
228 if (!test_rshift1(out))
229 goto err;
230 (void)BIO_flush(out);
231
232 message(out, "BN_rshift");
233 if (!test_rshift(out, ctx))
234 goto err;
235 (void)BIO_flush(out);
236
237 message(out, "BN_sqr");
238 if (!test_sqr(out, ctx))
239 goto err;
240 (void)BIO_flush(out);
241
242 message(out, "BN_mul");
243 if (!test_mul(out))
244 goto err;
245 (void)BIO_flush(out);
246
247 message(out, "BN_div");
248 if (!test_div(out, ctx))
249 goto err;
250 (void)BIO_flush(out);
251
252 message(out, "BN_div_word");
253 if (!test_div_word(out))
254 goto err;
255 (void)BIO_flush(out);
256
257 message(out, "BN_div_recp");
258 if (!test_div_recp(out, ctx))
259 goto err;
260 (void)BIO_flush(out);
261
262 message(out, "BN_mod");
263 if (!test_mod(out, ctx))
264 goto err;
265 (void)BIO_flush(out);
266
267 message(out, "BN_mod_mul");
268 if (!test_mod_mul(out, ctx))
269 goto err;
270 (void)BIO_flush(out);
271
272 message(out, "BN_mont");
273 if (!test_mont(out, ctx))
274 goto err;
275 (void)BIO_flush(out);
276
277 message(out, "BN_mod_exp");
278 if (!test_mod_exp(out, ctx))
279 goto err;
280 (void)BIO_flush(out);
281
282 message(out, "BN_mod_exp_mont_consttime");
283 if (!test_mod_exp_mont_consttime(out, ctx))
284 goto err;
285 (void)BIO_flush(out);
286
287 message(out, "BN_mod_exp_mont5");
288 if (!test_mod_exp_mont5(out, ctx))
289 goto err;
290 (void)BIO_flush(out);
291
292 message(out, "BN_exp");
293 if (!test_exp(out, ctx))
294 goto err;
295 (void)BIO_flush(out);
296
297 message(out, "BN_kronecker");
298 if (!test_kron(out, ctx))
299 goto err;
300 (void)BIO_flush(out);
301
302 message(out, "BN_mod_sqrt");
303 if (!test_sqrt(out, ctx))
304 goto err;
305 (void)BIO_flush(out);
306
307 message(out, "Modexp with different sizes");
308 if (!test_mod_exp_sizes(out, ctx))
309 goto err;
310 (void)BIO_flush(out);
311
312#ifndef OPENSSL_NO_EC2M
313 message(out, "BN_GF2m_add");
314 if (!test_gf2m_add(out))
315 goto err;
316 (void)BIO_flush(out);
317
318 message(out, "BN_GF2m_mod");
319 if (!test_gf2m_mod(out))
320 goto err;
321 (void)BIO_flush(out);
322
323 message(out, "BN_GF2m_mod_mul");
324 if (!test_gf2m_mod_mul(out, ctx))
325 goto err;
326 (void)BIO_flush(out);
327
328 message(out, "BN_GF2m_mod_sqr");
329 if (!test_gf2m_mod_sqr(out, ctx))
330 goto err;
331 (void)BIO_flush(out);
332
333 message(out, "BN_GF2m_mod_inv");
334 if (!test_gf2m_mod_inv(out, ctx))
335 goto err;
336 (void)BIO_flush(out);
337
338 message(out, "BN_GF2m_mod_div");
339 if (!test_gf2m_mod_div(out, ctx))
340 goto err;
341 (void)BIO_flush(out);
342
343 message(out, "BN_GF2m_mod_exp");
344 if (!test_gf2m_mod_exp(out, ctx))
345 goto err;
346 (void)BIO_flush(out);
347
348 message(out, "BN_GF2m_mod_sqrt");
349 if (!test_gf2m_mod_sqrt(out, ctx))
350 goto err;
351 (void)BIO_flush(out);
352
353 message(out, "BN_GF2m_mod_solve_quad");
354 if (!test_gf2m_mod_solve_quad(out, ctx))
355 goto err;
356 (void)BIO_flush(out);
357#endif
358 BN_CTX_free(ctx);
359 BIO_free(out);
360
361 exit(0);
362 err:
363 BIO_puts(out, "1\n"); /* make sure the Perl script fed by bc notices
364 * the failure, see test_bn in test/Makefile.ssl*/
365
366 (void)BIO_flush(out);
367 ERR_load_crypto_strings();
368 ERR_print_errors_fp(stderr);
369 exit(1);
370}
371
372int
373test_add(BIO *bp)
374{
375 BIGNUM *a = NULL, *b = NULL, *c = NULL;
376 int i;
377 int rc = 1;
378
379 if ((a = BN_new()) == NULL)
380 goto err;
381 if ((b = BN_new()) == NULL)
382 goto err;
383 if ((c = BN_new()) == NULL)
384 goto err;
385
386 CHECK_GOTO(BN_bntest_rand(a, 512, 0, 0));
387 for (i = 0; i < num0; i++) {
388 CHECK_GOTO(BN_bntest_rand(b, 450 + i, 0, 0));
389 BN_set_negative(a, rand_neg());
390 BN_set_negative(b, rand_neg());
391 CHECK_GOTO(BN_add(c, a, b));
392 if (bp != NULL) {
393 if (!results) {
394 CHECK_GOTO(BN_print(bp, a));
395 BIO_puts(bp, " + ");
396 CHECK_GOTO(BN_print(bp, b));
397 BIO_puts(bp, " - ");
398 }
399 CHECK_GOTO(BN_print(bp, c));
400 BIO_puts(bp, "\n");
401 }
402 BN_set_negative(a, !BN_is_negative(a));
403 BN_set_negative(b, !BN_is_negative(b));
404 CHECK_GOTO(BN_add(c, c, b));
405 CHECK_GOTO(BN_add(c, c, a));
406 if (!BN_is_zero(c)) {
407 fprintf(stderr, "Add test failed!\n");
408 rc = 0;
409 break;
410 }
411 }
412
413 err:
414 BN_free(a);
415 BN_free(b);
416 BN_free(c);
417
418 return rc;
419}
420
421int
422test_sub(BIO *bp)
423{
424 BIGNUM *a = NULL, *b = NULL, *c = NULL;
425 int i;
426 int rc = 1;
427
428 if ((a = BN_new()) == NULL)
429 goto err;
430 if ((b = BN_new()) == NULL)
431 goto err;
432 if ((c = BN_new()) == NULL)
433 goto err;
434
435 for (i = 0; i < num0 + num1; i++) {
436 if (i < num1) {
437 CHECK_GOTO(BN_bntest_rand(a, 512, 0, 0));
438 CHECK_GOTO(BN_copy(b, a));
439 if (BN_set_bit(a, i) == 0) {
440 rc = 0;
441 break;
442 }
443 CHECK_GOTO(BN_add_word(b, i));
444 } else {
445 CHECK_GOTO(BN_bntest_rand(b, 400 + i - num1, 0, 0));
446 BN_set_negative(a, rand_neg());
447 BN_set_negative(b, rand_neg());
448 }
449 CHECK_GOTO(BN_sub(c, a, b));
450 if (bp != NULL) {
451 if (!results) {
452 CHECK_GOTO(BN_print(bp, a));
453 BIO_puts(bp, " - ");
454 CHECK_GOTO(BN_print(bp, b));
455 BIO_puts(bp, " - ");
456 }
457 CHECK_GOTO(BN_print(bp, c));
458 BIO_puts(bp, "\n");
459 }
460 CHECK_GOTO(BN_add(c, c, b));
461 CHECK_GOTO(BN_sub(c, c, a));
462 if (!BN_is_zero(c)) {
463 fprintf(stderr, "Subtract test failed!\n");
464 rc = 0;
465 break;
466 }
467 }
468 err:
469 BN_free(a);
470 BN_free(b);
471 BN_free(c);
472 return (rc);
473}
474
475int
476test_div(BIO *bp, BN_CTX *ctx)
477{
478 BIGNUM *a = NULL, *b = NULL, *c = NULL, *d = NULL, *e = NULL;
479 int i;
480 int rc = 1;
481
482 if ((a = BN_new()) == NULL)
483 goto err;
484 if ((b = BN_new()) == NULL)
485 goto err;
486 if ((c = BN_new()) == NULL)
487 goto err;
488 if ((d = BN_new()) == NULL)
489 goto err;
490 if ((e = BN_new()) == NULL)
491 goto err;
492
493 CHECK_GOTO(BN_one(a));
494 CHECK_GOTO(BN_zero(b));
495
496 if (BN_div(d, c, a, b, ctx)) {
497 fprintf(stderr, "Division by zero succeeded!\n");
498 return (0);
499 }
500
501 for (i = 0; i < num0 + num1; i++) {
502 if (i < num1) {
503 CHECK_GOTO(BN_bntest_rand(a, 400, 0, 0));
504 CHECK_GOTO(BN_copy(b, a));
505 CHECK_GOTO(BN_lshift(a, a, i));
506 CHECK_GOTO(BN_add_word(a, i));
507 } else
508 CHECK_GOTO(BN_bntest_rand(b, 50 + 3 * (i - num1), 0, 0));
509 BN_set_negative(a, rand_neg());
510 BN_set_negative(b, rand_neg());
511 CHECK_GOTO(BN_div(d, c, a, b, ctx));
512 if (bp != NULL) {
513 if (!results) {
514 CHECK_GOTO(BN_print(bp, a));
515 BIO_puts(bp, " / ");
516 CHECK_GOTO(BN_print(bp, b));
517 BIO_puts(bp, " - ");
518 }
519 CHECK_GOTO(BN_print(bp, d));
520 BIO_puts(bp, "\n");
521
522 if (!results) {
523 CHECK_GOTO(BN_print(bp, a));
524 BIO_puts(bp, " % ");
525 CHECK_GOTO(BN_print(bp, b));
526 BIO_puts(bp, " - ");
527 }
528 CHECK_GOTO(BN_print(bp, c));
529 BIO_puts(bp, "\n");
530 }
531 CHECK_GOTO(BN_mul(e, d, b, ctx));
532 CHECK_GOTO(BN_add(d, e, c));
533 CHECK_GOTO(BN_sub(d, d, a));
534 if (!BN_is_zero(d)) {
535 fprintf(stderr, "Division test failed!\n");
536 rc = 0;
537 break;
538 }
539 }
540 err:
541 BN_free(a);
542 BN_free(b);
543 BN_free(c);
544 BN_free(d);
545 BN_free(e);
546 return (rc);
547}
548
549static void
550print_word(BIO *bp, BN_ULONG w)
551{
552#ifdef SIXTY_FOUR_BIT
553 if (sizeof(w) > sizeof(unsigned long)) {
554 unsigned long h = (unsigned long)(w >> 32), l = (unsigned long)(w);
555
556 if (h)
557 BIO_printf(bp, "%lX%08lX", h, l);
558 else
559 BIO_printf(bp, "%lX", l);
560 return;
561 }
562#endif
563 BIO_printf(bp, BN_HEX_FMT1, w);
564}
565
566int
567test_div_word(BIO *bp)
568{
569 BIGNUM *a = NULL, *b = NULL;
570 BN_ULONG r, rmod, s = 0;
571 int i;
572 int rc = 1;
573
574 if ((a = BN_new()) == NULL)
575 goto err;
576 if ((b = BN_new()) == NULL)
577 goto err;
578
579 for (i = 0; i < num0; i++) {
580 do {
581 if (!BN_bntest_rand(a, 512, -1, 0) ||
582 !BN_bntest_rand(b, BN_BITS2, -1, 0)) {
583 rc = 0;
584 break;
585 }
586 s = BN_get_word(b);
587 } while (!s);
588
589 if (!BN_copy(b, a)) {
590 rc = 0;
591 break;
592 }
593
594 rmod = BN_mod_word(b, s);
595 r = BN_div_word(b, s);
596
597 if (r == (BN_ULONG)-1 || rmod == (BN_ULONG)-1) {
598 rc = 0;
599 break;
600 }
601
602 if (rmod != r) {
603 fprintf(stderr, "Mod (word) test failed!\n");
604 rc = 0;
605 break;
606 }
607
608 if (bp != NULL) {
609 if (!results) {
610 CHECK_GOTO(BN_print(bp, a));
611 BIO_puts(bp, " / ");
612 print_word(bp, s);
613 BIO_puts(bp, " - ");
614 }
615 CHECK_GOTO(BN_print(bp, b));
616 BIO_puts(bp, "\n");
617
618 if (!results) {
619 CHECK_GOTO(BN_print(bp, a));
620 BIO_puts(bp, " % ");
621 print_word(bp, s);
622 BIO_puts(bp, " - ");
623 }
624 print_word(bp, r);
625 BIO_puts(bp, "\n");
626 }
627 CHECK_GOTO(BN_mul_word(b, s));
628 CHECK_GOTO(BN_add_word(b, r));
629 CHECK_GOTO(BN_sub(b, a, b));
630 if (!BN_is_zero(b)) {
631 fprintf(stderr, "Division (word) test failed!\n");
632 rc = 0;
633 break;
634 }
635 }
636 err:
637 BN_free(a);
638 BN_free(b);
639
640 return rc;
641}
642
643int
644test_div_recp(BIO *bp, BN_CTX *ctx)
645{
646 BIGNUM *a = NULL, *b = NULL, *c = NULL, *d = NULL, *e = NULL;
647 BN_RECP_CTX *recp = NULL;
648 int i;
649 int rc = 1;
650
651 if ((a = BN_new()) == NULL)
652 goto err;
653 if ((b = BN_new()) == NULL)
654 goto err;
655 if ((c = BN_new()) == NULL)
656 goto err;
657 if ((d = BN_new()) == NULL)
658 goto err;
659 if ((e = BN_new()) == NULL)
660 goto err;
661
662 if ((recp = BN_RECP_CTX_new()) == NULL)
663 goto err;
664
665 for (i = 0; i < num0 + num1; i++) {
666 if (i < num1) {
667 CHECK_GOTO(BN_bntest_rand(a, 400, 0, 0));
668 CHECK_GOTO(BN_copy(b, a));
669 CHECK_GOTO(BN_lshift(a, a, i));
670 CHECK_GOTO(BN_add_word(a, i));
671 } else
672 CHECK_GOTO(BN_bntest_rand(b, 50 + 3 * (i - num1), 0, 0));
673 BN_set_negative(a, rand_neg());
674 BN_set_negative(b, rand_neg());
675 CHECK_GOTO(BN_RECP_CTX_set(recp, b, ctx));
676 CHECK_GOTO(BN_div_recp(d, c, a, recp, ctx));
677 if (bp != NULL) {
678 if (!results) {
679 CHECK_GOTO(BN_print(bp, a));
680 BIO_puts(bp, " / ");
681 CHECK_GOTO(BN_print(bp, b));
682 BIO_puts(bp, " - ");
683 }
684 CHECK_GOTO(BN_print(bp, d));
685 BIO_puts(bp, "\n");
686
687 if (!results) {
688 CHECK_GOTO(BN_print(bp, a));
689 BIO_puts(bp, " % ");
690 CHECK_GOTO(BN_print(bp, b));
691 BIO_puts(bp, " - ");
692 }
693 CHECK_GOTO(BN_print(bp, c));
694 BIO_puts(bp, "\n");
695 }
696 CHECK_GOTO(BN_mul(e, d, b, ctx));
697 CHECK_GOTO(BN_add(d, e, c));
698 CHECK_GOTO(BN_sub(d, d, a));
699 if (!BN_is_zero(d)) {
700 fprintf(stderr, "Reciprocal division test failed!\n");
701 fprintf(stderr, "a=");
702 CHECK_GOTO(BN_print_fp(stderr, a));
703 fprintf(stderr, "\nb=");
704 CHECK_GOTO(BN_print_fp(stderr, b));
705 fprintf(stderr, "\n");
706 rc = 0;
707 break;
708 }
709 }
710 err:
711 BN_free(a);
712 BN_free(b);
713 BN_free(c);
714 BN_free(d);
715 BN_free(e);
716 BN_RECP_CTX_free(recp);
717 return (rc);
718}
719
720int
721test_mul(BIO *bp)
722{
723 BIGNUM *a = NULL, *b = NULL, *c = NULL, *d = NULL, *e = NULL;
724 int i;
725 int rc = 1;
726 BN_CTX *ctx;
727
728 ctx = BN_CTX_new();
729 if (ctx == NULL)
730 exit(1);
731
732 if ((a = BN_new()) == NULL)
733 goto err;
734 if ((b = BN_new()) == NULL)
735 goto err;
736 if ((c = BN_new()) == NULL)
737 goto err;
738 if ((d = BN_new()) == NULL)
739 goto err;
740 if ((e = BN_new()) == NULL)
741 goto err;
742
743 for (i = 0; i < num0 + num1; i++) {
744 if (i <= num1) {
745 CHECK_GOTO(BN_bntest_rand(a, 100, 0, 0));
746 CHECK_GOTO(BN_bntest_rand(b, 100, 0, 0));
747 } else
748 CHECK_GOTO(BN_bntest_rand(b, i - num1, 0, 0));
749 BN_set_negative(a, rand_neg());
750 BN_set_negative(b, rand_neg());
751 CHECK_GOTO(BN_mul(c, a, b, ctx));
752 if (bp != NULL) {
753 if (!results) {
754 CHECK_GOTO(BN_print(bp, a));
755 BIO_puts(bp, " * ");
756 CHECK_GOTO(BN_print(bp, b));
757 BIO_puts(bp, " - ");
758 }
759 CHECK_GOTO(BN_print(bp, c));
760 BIO_puts(bp, "\n");
761 }
762 CHECK_GOTO(BN_div(d, e, c, a, ctx));
763 CHECK_GOTO(BN_sub(d, d, b));
764 if (!BN_is_zero(d) || !BN_is_zero(e)) {
765 fprintf(stderr, "Multiplication test failed!\n");
766 rc = 0;
767 break;
768 }
769 }
770 err:
771 BN_free(a);
772 BN_free(b);
773 BN_free(c);
774 BN_free(d);
775 BN_free(e);
776 BN_CTX_free(ctx);
777 return (rc);
778}
779
780int
781test_sqr(BIO *bp, BN_CTX *ctx)
782{
783 BIGNUM *a = NULL, *c = NULL, *d = NULL, *e = NULL;
784 int i, rc = 0;
785
786 if ((a = BN_new()) == NULL)
787 goto err;
788 if ((c = BN_new()) == NULL)
789 goto err;
790 if ((d = BN_new()) == NULL)
791 goto err;
792 if ((e = BN_new()) == NULL)
793 goto err;
794
795 for (i = 0; i < num0; i++) {
796 CHECK_GOTO(BN_bntest_rand(a, 40 + i * 10, 0, 0));
797 BN_set_negative(a, rand_neg());
798 CHECK_GOTO(BN_sqr(c, a, ctx));
799 if (bp != NULL) {
800 if (!results) {
801 CHECK_GOTO(BN_print(bp, a));
802 BIO_puts(bp, " * ");
803 CHECK_GOTO(BN_print(bp, a));
804 BIO_puts(bp, " - ");
805 }
806 CHECK_GOTO(BN_print(bp, c));
807 BIO_puts(bp, "\n");
808 }
809 CHECK_GOTO(BN_div(d, e, c, a, ctx));
810 CHECK_GOTO(BN_sub(d, d, a));
811 if (!BN_is_zero(d) || !BN_is_zero(e)) {
812 fprintf(stderr, "Square test failed!\n");
813 goto err;
814 }
815 }
816
817 /* Regression test for a BN_sqr overflow bug. */
818 if (!BN_hex2bn(&a, "80000000000000008000000000000001"
819 "FFFFFFFFFFFFFFFE0000000000000000")) {
820 fprintf(stderr, "BN_hex2bn failed\n");
821 goto err;
822 }
823 CHECK_GOTO(BN_sqr(c, a, ctx));
824 if (bp != NULL) {
825 if (!results) {
826 CHECK_GOTO(BN_print(bp, a));
827 BIO_puts(bp, " * ");
828 CHECK_GOTO(BN_print(bp, a));
829 BIO_puts(bp, " - ");
830 }
831 CHECK_GOTO(BN_print(bp, c));
832 BIO_puts(bp, "\n");
833 }
834 CHECK_GOTO(BN_mul(d, a, a, ctx));
835 if (BN_cmp(c, d)) {
836 fprintf(stderr,
837 "Square test failed: BN_sqr and BN_mul produce "
838 "different results!\n");
839 goto err;
840 }
841
842 /* Regression test for a BN_sqr overflow bug. */
843 if (!BN_hex2bn(&a, "80000000000000000000000080000001"
844 "FFFFFFFE000000000000000000000000")) {
845 fprintf(stderr, "BN_hex2bn failed\n");
846 goto err;
847 }
848 CHECK_GOTO(BN_sqr(c, a, ctx));
849 if (bp != NULL) {
850 if (!results) {
851 CHECK_GOTO(BN_print(bp, a));
852 BIO_puts(bp, " * ");
853 CHECK_GOTO(BN_print(bp, a));
854 BIO_puts(bp, " - ");
855 }
856 CHECK_GOTO(BN_print(bp, c));
857 BIO_puts(bp, "\n");
858 }
859 CHECK_GOTO(BN_mul(d, a, a, ctx));
860 if (BN_cmp(c, d)) {
861 fprintf(stderr, "Square test failed: BN_sqr and BN_mul produce "
862 "different results!\n");
863 goto err;
864 }
865 rc = 1;
866 err:
867 BN_free(a);
868 BN_free(c);
869 BN_free(d);
870 BN_free(e);
871 return rc;
872}
873
874int
875test_mont(BIO *bp, BN_CTX *ctx)
876{
877 BIGNUM *a = NULL, *b = NULL, *c = NULL, *d = NULL, *A = NULL, *B = NULL;
878 BIGNUM *n = NULL;
879 int i;
880 int rc = 1;
881 BN_MONT_CTX *mont;
882
883 mont = BN_MONT_CTX_new();
884 if (mont == NULL)
885 return 0;
886
887 if ((a = BN_new()) == NULL)
888 goto err;
889 if ((b = BN_new()) == NULL)
890 goto err;
891 if ((c = BN_new()) == NULL)
892 goto err;
893 if ((d = BN_new()) == NULL)
894 goto err;
895 if ((A = BN_new()) == NULL)
896 goto err;
897 if ((B = BN_new()) == NULL)
898 goto err;
899 if ((n = BN_new()) == NULL)
900 goto err;
901
902 CHECK_GOTO(BN_zero(n));
903 if (BN_MONT_CTX_set(mont, n, ctx)) {
904 fprintf(stderr, "BN_MONT_CTX_set succeeded for zero modulus!\n");
905 return (0);
906 }
907
908 CHECK_GOTO(BN_set_word(n, 16));
909 if (BN_MONT_CTX_set(mont, n, ctx)) {
910 fprintf(stderr, "BN_MONT_CTX_set succeeded for even modulus!\n");
911 return (0);
912 }
913
914 CHECK_GOTO(BN_bntest_rand(a, 100, 0, 0));
915 CHECK_GOTO(BN_bntest_rand(b, 100, 0, 0));
916 for (i = 0; i < num2; i++) {
917 int bits = (200 * (i + 1)) / num2;
918
919 if (bits == 0)
920 continue;
921 CHECK_GOTO(BN_bntest_rand(n, bits, 0, 1));
922 CHECK_GOTO(BN_MONT_CTX_set(mont, n, ctx));
923
924 CHECK_GOTO(BN_nnmod(a, a, n, ctx));
925 CHECK_GOTO(BN_nnmod(b, b, n, ctx));
926
927 CHECK_GOTO(BN_to_montgomery(A, a, mont, ctx));
928 CHECK_GOTO(BN_to_montgomery(B, b, mont, ctx));
929
930 CHECK_GOTO(BN_mod_mul_montgomery(c, A, B, mont, ctx));
931 CHECK_GOTO(BN_from_montgomery(A, c, mont, ctx));
932 if (bp != NULL) {
933 if (!results) {
934 CHECK_GOTO(BN_print(bp, a));
935 BIO_puts(bp, " * ");
936 CHECK_GOTO(BN_print(bp, b));
937 BIO_puts(bp, " % ");
938 /* n == &mont->N */
939 CHECK_GOTO(BN_print(bp, n));
940 BIO_puts(bp, " - ");
941 }
942 CHECK_GOTO(BN_print(bp, A));
943 BIO_puts(bp, "\n");
944 }
945 CHECK_GOTO(BN_mod_mul(d, a, b, n, ctx));
946 CHECK_GOTO(BN_sub(d, d, A));
947 if (!BN_is_zero(d)) {
948 fprintf(stderr, "Montgomery multiplication test failed!\n");
949 rc = 0;
950 break;
951 }
952 }
953 err:
954 BN_MONT_CTX_free(mont);
955 BN_free(a);
956 BN_free(b);
957 BN_free(c);
958 BN_free(d);
959 BN_free(A);
960 BN_free(B);
961 BN_free(n);
962 return (rc);
963}
964
965int
966test_mod(BIO *bp, BN_CTX *ctx)
967{
968 BIGNUM *a = NULL, *b = NULL, *c = NULL, *d = NULL, *e = NULL;
969 int i;
970 int rc = 1;
971
972 if ((a = BN_new()) == NULL)
973 goto err;
974 if ((b = BN_new()) == NULL)
975 goto err;
976 if ((c = BN_new()) == NULL)
977 goto err;
978 if ((d = BN_new()) == NULL)
979 goto err;
980 if ((e = BN_new()) == NULL)
981 goto err;
982
983 CHECK_GOTO(BN_bntest_rand(a, 1024, 0, 0));
984 for (i = 0; i < num0; i++) {
985 CHECK_GOTO(BN_bntest_rand(b, 450 + i * 10, 0, 0));
986 BN_set_negative(a, rand_neg());
987 BN_set_negative(b, rand_neg());
988 CHECK_GOTO(BN_mod(c, a, b, ctx));
989 if (bp != NULL) {
990 if (!results) {
991 CHECK_GOTO(BN_print(bp, a));
992 BIO_puts(bp, " % ");
993 CHECK_GOTO(BN_print(bp, b));
994 BIO_puts(bp, " - ");
995 }
996 CHECK_GOTO(BN_print(bp, c));
997 BIO_puts(bp, "\n");
998 }
999 CHECK_GOTO(BN_div(d, e, a, b, ctx));
1000 CHECK_GOTO(BN_sub(e, e, c));
1001 if (!BN_is_zero(e)) {
1002 fprintf(stderr, "Modulo test failed!\n");
1003 rc = 0;
1004 break;
1005 }
1006 }
1007 err:
1008 BN_free(a);
1009 BN_free(b);
1010 BN_free(c);
1011 BN_free(d);
1012 BN_free(e);
1013 return (rc);
1014}
1015
1016int
1017test_mod_mul(BIO *bp, BN_CTX *ctx)
1018{
1019 BIGNUM *a = NULL, *b = NULL, *c = NULL, *d = NULL, *e = NULL;
1020 int i, j;
1021 int rc = 1;
1022
1023 if ((a = BN_new()) == NULL)
1024 goto err;
1025 if ((b = BN_new()) == NULL)
1026 goto err;
1027 if ((c = BN_new()) == NULL)
1028 goto err;
1029 if ((d = BN_new()) == NULL)
1030 goto err;
1031 if ((e = BN_new()) == NULL)
1032 goto err;
1033
1034 CHECK_GOTO(BN_one(a));
1035 CHECK_GOTO(BN_one(b));
1036 CHECK_GOTO(BN_zero(c));
1037 if (BN_mod_mul(e, a, b, c, ctx)) {
1038 fprintf(stderr, "BN_mod_mul with zero modulus succeeded!\n");
1039 return (0);
1040 }
1041
1042 for (j = 0; j < 3; j++) {
1043 CHECK_GOTO(BN_bntest_rand(c, 1024, 0, 0));
1044 for (i = 0; i < num0; i++) {
1045 CHECK_GOTO(BN_bntest_rand(a, 475 + i * 10, 0, 0));
1046 CHECK_GOTO(BN_bntest_rand(b, 425 + i * 11, 0, 0));
1047 BN_set_negative(a, rand_neg());
1048 BN_set_negative(b, rand_neg());
1049 if (!BN_mod_mul(e, a, b, c, ctx)) {
1050 unsigned long l;
1051
1052 while ((l = ERR_get_error()))
1053 fprintf(stderr, "ERROR:%s\n",
1054 ERR_error_string(l, NULL));
1055 exit(1);
1056 }
1057 if (bp != NULL) {
1058 if (!results) {
1059 CHECK_GOTO(BN_print(bp, a));
1060 BIO_puts(bp, " * ");
1061 CHECK_GOTO(BN_print(bp, b));
1062 BIO_puts(bp, " % ");
1063 CHECK_GOTO(BN_print(bp, c));
1064 if ((BN_is_negative(a) ^ BN_is_negative(b)) &&
1065 !BN_is_zero(e)) {
1066 /* If (a*b) % c is negative, c must be added
1067 * in order to obtain the normalized remainder
1068 * (new with OpenSSL 0.9.7, previous versions of
1069 * BN_mod_mul could generate negative results)
1070 */
1071 BIO_puts(bp, " + ");
1072 CHECK_GOTO(BN_print(bp, c));
1073 }
1074 BIO_puts(bp, " - ");
1075 }
1076 CHECK_GOTO(BN_print(bp, e));
1077 BIO_puts(bp, "\n");
1078 }
1079 CHECK_GOTO(BN_mul(d, a, b, ctx));
1080 CHECK_GOTO(BN_sub(d, d, e));
1081 CHECK_GOTO(BN_div(a, b, d, c, ctx));
1082 if (!BN_is_zero(b)) {
1083 fprintf(stderr, "Modulo multiply test failed!\n");
1084 ERR_print_errors_fp(stderr);
1085 rc = 0;
1086 goto err;
1087 }
1088 }
1089 }
1090 err:
1091 BN_free(a);
1092 BN_free(b);
1093 BN_free(c);
1094 BN_free(d);
1095 BN_free(e);
1096 return (rc);
1097}
1098
1099int
1100test_mod_exp(BIO *bp, BN_CTX *ctx)
1101{
1102 BIGNUM *a = NULL, *b = NULL, *c = NULL, *d = NULL, *e = NULL;
1103 int i;
1104 int rc = 1;
1105
1106 if ((a = BN_new()) == NULL)
1107 goto err;
1108 if ((b = BN_new()) == NULL)
1109 goto err;
1110 if ((c = BN_new()) == NULL)
1111 goto err;
1112 if ((d = BN_new()) == NULL)
1113 goto err;
1114 if ((e = BN_new()) == NULL)
1115 goto err;
1116
1117 CHECK_GOTO(BN_one(a));
1118 CHECK_GOTO(BN_one(b));
1119 CHECK_GOTO(BN_zero(c));
1120 if (BN_mod_exp(d, a, b, c, ctx)) {
1121 fprintf(stderr, "BN_mod_exp with zero modulus succeeded!\n");
1122 rc = 0;
1123 goto err;
1124 }
1125 if (BN_mod_exp_ct(d, a, b, c, ctx)) {
1126 fprintf(stderr, "BN_mod_exp_ct with zero modulus succeeded!\n");
1127 rc = 0;
1128 goto err;
1129 }
1130 if (BN_mod_exp_nonct(d, a, b, c, ctx)) {
1131 fprintf(stderr, "BN_mod_exp_nonct with zero modulus succeeded!\n");
1132 rc = 0;
1133 goto err;
1134 }
1135
1136 CHECK_GOTO(BN_bntest_rand(c, 30, 0, 1)); /* must be odd for montgomery */
1137 for (i = 0; i < num2; i++) {
1138 CHECK_GOTO(BN_bntest_rand(a, 20 + i * 5, 0, 0));
1139 CHECK_GOTO(BN_bntest_rand(b, 2 + i, 0, 0));
1140
1141 if (!BN_mod_exp(d, a, b, c, ctx)) {
1142 rc = 0;
1143 break;
1144 }
1145
1146 if (bp != NULL) {
1147 if (!results) {
1148 CHECK_GOTO(BN_print(bp, a));
1149 BIO_puts(bp, " ^ ");
1150 CHECK_GOTO(BN_print(bp, b));
1151 BIO_puts(bp, " % ");
1152 CHECK_GOTO(BN_print(bp, c));
1153 BIO_puts(bp, " - ");
1154 }
1155 CHECK_GOTO(BN_print(bp, d));
1156 BIO_puts(bp, "\n");
1157 }
1158 CHECK_GOTO(BN_exp(e, a, b, ctx));
1159 CHECK_GOTO(BN_sub(e, e, d));
1160 CHECK_GOTO(BN_div(a, b, e, c, ctx));
1161 if (!BN_is_zero(b)) {
1162 fprintf(stderr, "Modulo exponentiation test failed!\n");
1163 rc = 0;
1164 break;
1165 }
1166 }
1167
1168 CHECK_GOTO(BN_bntest_rand(c, 30, 0, 1)); /* must be odd for montgomery */
1169 for (i = 0; i < num2; i++) {
1170 CHECK_GOTO(BN_bntest_rand(a, 20 + i * 5, 0, 0));
1171 CHECK_GOTO(BN_bntest_rand(b, 2 + i, 0, 0));
1172
1173 if (!BN_mod_exp_ct(d, a, b, c, ctx)) {
1174 rc = 0;
1175 break;
1176 }
1177
1178 if (bp != NULL) {
1179 if (!results) {
1180 CHECK_GOTO(BN_print(bp, a));
1181 BIO_puts(bp, " ^ ");
1182 CHECK_GOTO(BN_print(bp, b));
1183 BIO_puts(bp, " % ");
1184 CHECK_GOTO(BN_print(bp, c));
1185 BIO_puts(bp, " - ");
1186 }
1187 CHECK_GOTO(BN_print(bp, d));
1188 BIO_puts(bp, "\n");
1189 }
1190 CHECK_GOTO(BN_exp(e, a, b, ctx));
1191 CHECK_GOTO(BN_sub(e, e, d));
1192 CHECK_GOTO(BN_div(a, b, e, c, ctx));
1193 if (!BN_is_zero(b)) {
1194 fprintf(stderr, "Modulo exponentiation test failed!\n");
1195 rc = 0;
1196 break;
1197 }
1198 }
1199
1200 CHECK_GOTO(BN_bntest_rand(c, 30, 0, 1)); /* must be odd for montgomery */
1201 for (i = 0; i < num2; i++) {
1202 CHECK_GOTO(BN_bntest_rand(a, 20 + i * 5, 0, 0));
1203 CHECK_GOTO(BN_bntest_rand(b, 2 + i, 0, 0));
1204
1205 if (!BN_mod_exp_nonct(d, a, b, c, ctx)) {
1206 rc = 0;
1207 break;
1208 }
1209
1210 if (bp != NULL) {
1211 if (!results) {
1212 CHECK_GOTO(BN_print(bp, a));
1213 BIO_puts(bp, " ^ ");
1214 CHECK_GOTO(BN_print(bp, b));
1215 BIO_puts(bp, " % ");
1216 CHECK_GOTO(BN_print(bp, c));
1217 BIO_puts(bp, " - ");
1218 }
1219 CHECK_GOTO(BN_print(bp, d));
1220 BIO_puts(bp, "\n");
1221 }
1222 CHECK_GOTO(BN_exp(e, a, b, ctx));
1223 CHECK_GOTO(BN_sub(e, e, d));
1224 CHECK_GOTO(BN_div(a, b, e, c, ctx));
1225 if (!BN_is_zero(b)) {
1226 fprintf(stderr, "Modulo exponentiation test failed!\n");
1227 rc = 0;
1228 break;
1229 }
1230 }
1231 err:
1232 BN_free(a);
1233 BN_free(b);
1234 BN_free(c);
1235 BN_free(d);
1236 BN_free(e);
1237 return (rc);
1238}
1239
1240int
1241test_mod_exp_mont_consttime(BIO *bp, BN_CTX *ctx)
1242{
1243 BIGNUM *a = NULL, *b = NULL, *c = NULL, *d = NULL, *e = NULL;
1244 int i;
1245 int rc = 1;
1246
1247 if ((a = BN_new()) == NULL)
1248 goto err;
1249 if ((b = BN_new()) == NULL)
1250 goto err;
1251 if ((c = BN_new()) == NULL)
1252 goto err;
1253 if ((d = BN_new()) == NULL)
1254 goto err;
1255 if ((e = BN_new()) == NULL)
1256 goto err;
1257
1258 CHECK_GOTO(BN_one(a));
1259 CHECK_GOTO(BN_one(b));
1260 CHECK_GOTO(BN_zero(c));
1261 if (BN_mod_exp_mont_consttime(d, a, b, c, ctx, NULL)) {
1262 fprintf(stderr, "BN_mod_exp_mont_consttime with zero modulus "
1263 "succeeded\n");
1264 rc = 0;
1265 goto err;
1266 }
1267
1268 CHECK_GOTO(BN_set_word(c, 16));
1269 if (BN_mod_exp_mont_consttime(d, a, b, c, ctx, NULL)) {
1270 fprintf(stderr, "BN_mod_exp_mont_consttime with even modulus "
1271 "succeeded\n");
1272 rc = 0;
1273 goto err;
1274 }
1275
1276 CHECK_GOTO(BN_bntest_rand(c, 30, 0, 1)); /* must be odd for montgomery */
1277 for (i = 0; i < num2; i++) {
1278 CHECK_GOTO(BN_bntest_rand(a, 20 + i * 5, 0, 0));
1279 CHECK_GOTO(BN_bntest_rand(b, 2 + i, 0, 0));
1280
1281 if (!BN_mod_exp_mont_consttime(d, a, b, c, ctx, NULL)) {
1282 rc = 0;
1283 break;
1284 }
1285
1286 if (bp != NULL) {
1287 if (!results) {
1288 CHECK_GOTO(BN_print(bp, a));
1289 BIO_puts(bp, " ^ ");
1290 CHECK_GOTO(BN_print(bp, b));
1291 BIO_puts(bp, " % ");
1292 CHECK_GOTO(BN_print(bp, c));
1293 BIO_puts(bp, " - ");
1294 }
1295 CHECK_GOTO(BN_print(bp, d));
1296 BIO_puts(bp, "\n");
1297 }
1298 CHECK_GOTO(BN_exp(e, a, b, ctx));
1299 CHECK_GOTO(BN_sub(e, e, d));
1300 CHECK_GOTO(BN_div(a, b, e, c, ctx));
1301 if (!BN_is_zero(b)) {
1302 fprintf(stderr, "Modulo exponentiation test failed!\n");
1303 rc = 0;
1304 break;
1305 }
1306 }
1307 err:
1308 BN_free(a);
1309 BN_free(b);
1310 BN_free(c);
1311 BN_free(d);
1312 BN_free(e);
1313 return (rc);
1314}
1315
1316/*
1317 * Test constant-time modular exponentiation with 1024-bit inputs, which on
1318 * x86_64 cause a different code branch to be taken.
1319 */
1320int
1321test_mod_exp_mont5(BIO *bp, BN_CTX *ctx)
1322{
1323 BIGNUM *a = NULL, *p = NULL, *m = NULL, *d = NULL, *e = NULL;
1324 BIGNUM *b = NULL, *n = NULL, *c = NULL;
1325 BN_MONT_CTX *mont = NULL;
1326 int len;
1327 int rc = 1;
1328
1329 if ((a = BN_new()) == NULL)
1330 goto err;
1331 if ((p = BN_new()) == NULL)
1332 goto err;
1333 if ((m = BN_new()) == NULL)
1334 goto err;
1335 if ((d = BN_new()) == NULL)
1336 goto err;
1337 if ((e = BN_new()) == NULL)
1338 goto err;
1339 if ((b = BN_new()) == NULL)
1340 goto err;
1341 if ((n = BN_new()) == NULL)
1342 goto err;
1343 if ((c = BN_new()) == NULL)
1344 goto err;
1345
1346 CHECK_GOTO(mont = BN_MONT_CTX_new());
1347
1348 CHECK_GOTO(BN_bntest_rand(m, 1024, 0, 1)); /* must be odd for montgomery */
1349 /* Zero exponent */
1350 CHECK_GOTO(BN_bntest_rand(a, 1024, 0, 0));
1351 CHECK_GOTO(BN_zero(p));
1352 if (!BN_mod_exp_mont_consttime(d, a, p, m, ctx, NULL)) {
1353 rc = 0;
1354 goto err;
1355 }
1356 if (!BN_is_one(d)) {
1357 fprintf(stderr, "Modular exponentiation test failed!\n");
1358 rc = 0;
1359 goto err;
1360 }
1361 /* Regression test for carry bug in mulx4x_mont */
1362 len = BN_hex2bn(&a,
1363 "7878787878787878787878787878787878787878787878787878787878787878"
1364 "7878787878787878787878787878787878787878787878787878787878787878"
1365 "7878787878787878787878787878787878787878787878787878787878787878"
1366 "7878787878787878787878787878787878787878787878787878787878787878");
1367 CHECK_GOTO(len);
1368 len = BN_hex2bn(&b,
1369 "095D72C08C097BA488C5E439C655A192EAFB6380073D8C2664668EDDB4060744"
1370 "E16E57FB4EDB9AE10A0CEFCDC28A894F689A128379DB279D48A2E20849D68593"
1371 "9B7803BCF46CEBF5C533FB0DD35B080593DE5472E3FE5DB951B8BFF9B4CB8F03"
1372 "9CC638A5EE8CDD703719F8000E6A9F63BEED5F2FCD52FF293EA05A251BB4AB81");
1373 CHECK_GOTO(len);
1374 len = BN_hex2bn(&n,
1375 "D78AF684E71DB0C39CFF4E64FB9DB567132CB9C50CC98009FEB820B26F2DED9B"
1376 "91B9B5E2B83AE0AE4EB4E0523CA726BFBE969B89FD754F674CE99118C3F2D1C5"
1377 "D81FDC7C54E02B60262B241D53C040E99E45826ECA37A804668E690E1AFC1CA4"
1378 "2C9A15D84D4954425F0B7642FC0BD9D7B24E2618D2DCC9B729D944BADACFDDAF");
1379 CHECK_GOTO(len);
1380 CHECK_GOTO(BN_MONT_CTX_set(mont, n, ctx));
1381 CHECK_GOTO(BN_mod_mul_montgomery(c, a, b, mont, ctx));
1382 CHECK_GOTO(BN_mod_mul_montgomery(d, b, a, mont, ctx));
1383 if (BN_cmp(c, d)) {
1384 fprintf(stderr, "Montgomery multiplication test failed:"
1385 " a*b != b*a.\n");
1386 rc = 0;
1387 goto err;
1388 }
1389 /* Regression test for carry bug in sqr[x]8x_mont */
1390 len = BN_hex2bn(&n,
1391 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
1392 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
1393 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
1394 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
1395 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
1396 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
1397 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
1398 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00000000000000FFFFFFFF00"
1399 "0000000000000000000000000000000000000000000000000000000000000000"
1400 "0000000000000000000000000000000000000000000000000000000000000000"
1401 "0000000000000000000000000000000000000000000000000000000000000000"
1402 "0000000000000000000000000000000000000000000000000000000000000000"
1403 "0000000000000000000000000000000000000000000000000000000000000000"
1404 "0000000000000000000000000000000000000000000000000000000000000000"
1405 "0000000000000000000000000000000000000000000000000000000000000000"
1406 "00000000000000000000000000000000000000000000000000FFFFFFFFFFFFFF");
1407 CHECK_GOTO(len);
1408 len = BN_hex2bn(&a,
1409 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
1410 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
1411 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
1412 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
1413 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
1414 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
1415 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
1416 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00000000000000FFFFFFFF0000000000"
1417 "0000000000000000000000000000000000000000000000000000000000000000"
1418 "0000000000000000000000000000000000000000000000000000000000000000"
1419 "0000000000000000000000000000000000000000000000000000000000000000"
1420 "0000000000000000000000000000000000000000000000000000000000000000"
1421 "0000000000000000000000000000000000000000000000000000000000000000"
1422 "0000000000000000000000000000000000000000000000000000000000000000"
1423 "0000000000000000000000000000000000000000000000000000000000000000"
1424 "000000000000000000000000000000000000000000FFFFFFFFFFFFFF00000000");
1425 CHECK_GOTO(len);
1426 BN_free(b);
1427 CHECK_GOTO(b = BN_dup(a));
1428 CHECK_GOTO(BN_MONT_CTX_set(mont, n, ctx));
1429 CHECK_GOTO(BN_mod_mul_montgomery(c, a, a, mont, ctx));
1430 CHECK_GOTO(BN_mod_mul_montgomery(d, a, b, mont, ctx));
1431 if (BN_cmp(c, d)) {
1432 fprintf(stderr, "Montgomery multiplication test failed:"
1433 " a**2 != a*a.\n");
1434 rc = 0;
1435 goto err;
1436 }
1437 /* Zero input */
1438 CHECK_GOTO(BN_bntest_rand(p, 1024, 0, 0));
1439 CHECK_GOTO(BN_zero(a));
1440 if (!BN_mod_exp_mont_consttime(d, a, p, m, ctx, NULL)) {
1441 rc = 0;
1442 goto err;
1443 }
1444 if (!BN_is_zero(d)) {
1445 fprintf(stderr, "Modular exponentiation test failed!\n");
1446 rc = 0;
1447 goto err;
1448 }
1449 /*
1450 * Craft an input whose Montgomery representation is 1, i.e., shorter
1451 * than the modulus m, in order to test the const time precomputation
1452 * scattering/gathering.
1453 */
1454 CHECK_GOTO(BN_one(a));
1455 CHECK_GOTO(BN_MONT_CTX_set(mont, m, ctx));
1456 if (!BN_from_montgomery(e, a, mont, ctx)) {
1457 rc = 0;
1458 goto err;
1459 }
1460 if (!BN_mod_exp_mont_consttime(d, e, p, m, ctx, NULL)) {
1461 rc = 0;
1462 goto err;
1463 }
1464 if (!BN_mod_exp_simple(a, e, p, m, ctx)) {
1465 rc = 0;
1466 goto err;
1467 }
1468 if (BN_cmp(a, d) != 0) {
1469 fprintf(stderr, "Modular exponentiation test failed!\n");
1470 rc = 0;
1471 goto err;
1472 }
1473 /* Finally, some regular test vectors. */
1474 CHECK_GOTO(BN_bntest_rand(e, 1024, 0, 0));
1475 if (!BN_mod_exp_mont_consttime(d, e, p, m, ctx, NULL)) {
1476 rc = 0;
1477 goto err;
1478 }
1479 if (!BN_mod_exp_simple(a, e, p, m, ctx)) {
1480 rc = 0;
1481 goto err;
1482 }
1483 if (BN_cmp(a, d) != 0) {
1484 fprintf(stderr, "Modular exponentiation test failed!\n");
1485 rc = 0;
1486 goto err;
1487 }
1488 err:
1489 BN_free(a);
1490 BN_free(p);
1491 BN_free(m);
1492 BN_free(d);
1493 BN_free(e);
1494 BN_free(b);
1495 BN_free(n);
1496 BN_free(c);
1497 BN_MONT_CTX_free(mont);
1498 return (rc);
1499}
1500
1501int
1502test_exp(BIO *bp, BN_CTX *ctx)
1503{
1504 BIGNUM *a = NULL, *b = NULL, *d = NULL, *e = NULL, *one = NULL;
1505 int i;
1506 int rc = 1;
1507
1508 if ((a = BN_new()) == NULL)
1509 goto err;
1510 if ((b = BN_new()) == NULL)
1511 goto err;
1512 if ((d = BN_new()) == NULL)
1513 goto err;
1514 if ((e = BN_new()) == NULL)
1515 goto err;
1516 if ((one = BN_new()) == NULL)
1517 goto err;
1518 CHECK_GOTO(BN_one(one));
1519
1520 for (i = 0; i < num2; i++) {
1521 CHECK_GOTO(BN_bntest_rand(a, 20 + i * 5, 0, 0));
1522 CHECK_GOTO(BN_bntest_rand(b, 2 + i, 0, 0));
1523
1524 if (BN_exp(d, a, b, ctx) <= 0) {
1525 rc = 0;
1526 break;
1527 }
1528
1529 if (bp != NULL) {
1530 if (!results) {
1531 CHECK_GOTO(BN_print(bp, a));
1532 BIO_puts(bp, " ^ ");
1533 CHECK_GOTO(BN_print(bp, b));
1534 BIO_puts(bp, " - ");
1535 }
1536 CHECK_GOTO(BN_print(bp, d));
1537 BIO_puts(bp, "\n");
1538 }
1539 CHECK_GOTO(BN_one(e));
1540 for (; !BN_is_zero(b); BN_sub(b, b, one))
1541 CHECK_GOTO(BN_mul(e, e, a, ctx));
1542 CHECK_GOTO(BN_sub(e, e, d));
1543 if (!BN_is_zero(e)) {
1544 fprintf(stderr, "Exponentiation test failed!\n");
1545 rc = 0;
1546 break;
1547 }
1548 }
1549 err:
1550 BN_free(a);
1551 BN_free(b);
1552 BN_free(d);
1553 BN_free(e);
1554 BN_free(one);
1555 return (rc);
1556}
1557
1558#ifndef OPENSSL_NO_EC2M
1559int
1560test_gf2m_add(BIO *bp)
1561{
1562 BIGNUM *a = NULL, *b = NULL, *c = NULL;
1563 int i, rc = 0;
1564
1565 if ((a = BN_new()) == NULL)
1566 goto err;
1567 if ((b = BN_new()) == NULL)
1568 goto err;
1569 if ((c = BN_new()) == NULL)
1570 goto err;
1571
1572 for (i = 0; i < num0; i++) {
1573 CHECK_GOTO(BN_rand(a, 512, 0, 0));
1574 CHECK_GOTO(BN_copy(b, BN_value_one()));
1575 BN_set_negative(a, rand_neg());
1576 BN_set_negative(b, rand_neg());
1577 CHECK_GOTO(BN_GF2m_add(c, a, b));
1578#if 0 /* make test uses ouput in bc but bc can't handle GF(2^m) arithmetic */
1579 if (bp != NULL) {
1580 if (!results) {
1581 CHECK_GOTO(BN_print(bp, a));
1582 BIO_puts(bp, " ^ ");
1583 CHECK_GOTO(BN_print(bp, b));
1584 BIO_puts(bp, " = ");
1585 }
1586 CHECK_GOTO(BN_print(bp, c));
1587 BIO_puts(bp, "\n");
1588 }
1589#endif
1590 /* Test that two added values have the correct parity. */
1591 if ((BN_is_odd(a) && BN_is_odd(c))
1592 || (!BN_is_odd(a) && !BN_is_odd(c))) {
1593 fprintf(stderr, "GF(2^m) addition test (a) failed!\n");
1594 goto err;
1595 }
1596 CHECK_GOTO(BN_GF2m_add(c, c, c));
1597 /* Test that c + c = 0. */
1598 if (!BN_is_zero(c)) {
1599 fprintf(stderr, "GF(2^m) addition test (b) failed!\n");
1600 goto err;
1601 }
1602 }
1603 rc = 1;
1604 err:
1605 BN_free(a);
1606 BN_free(b);
1607 BN_free(c);
1608 return rc;
1609}
1610
1611int
1612test_gf2m_mod(BIO *bp)
1613{
1614 BIGNUM *a = NULL, *b[2] = { 0 }, *c = NULL, *d = NULL, *e = NULL;
1615 int i, j;
1616 int p0[] = { 163, 7, 6, 3, 0, -1 };
1617 int p1[] = { 193, 15, 0, -1 };
1618 int rc = 0;
1619
1620 if ((a = BN_new()) == NULL)
1621 goto err;
1622 if ((b[0] = BN_new()) == NULL)
1623 goto err;
1624 if ((b[1] = BN_new()) == NULL)
1625 goto err;
1626 if ((c = BN_new()) == NULL)
1627 goto err;
1628 if ((d = BN_new()) == NULL)
1629 goto err;
1630 if ((e = BN_new()) == NULL)
1631 goto err;
1632
1633 CHECK_GOTO(BN_GF2m_arr2poly(p0, b[0]));
1634 CHECK_GOTO(BN_GF2m_arr2poly(p1, b[1]));
1635
1636 for (i = 0; i < num0; i++) {
1637 CHECK_GOTO(BN_bntest_rand(a, 1024, 0, 0));
1638 for (j = 0; j < 2; j++) {
1639 CHECK_GOTO(BN_GF2m_mod(c, a, b[j]));
1640#if 0 /* make test uses ouput in bc but bc can't handle GF(2^m) arithmetic */
1641 if (bp != NULL) {
1642 if (!results) {
1643 CHECK_GOTO(BN_print(bp, a));
1644 BIO_puts(bp, " % ");
1645 CHECK_GOTO(BN_print(bp, b[j]));
1646 BIO_puts(bp, " - ");
1647 CHECK_GOTO(BN_print(bp, c));
1648 BIO_puts(bp, "\n");
1649 }
1650 }
1651#endif
1652 CHECK_GOTO(BN_GF2m_add(d, a, c));
1653 CHECK_GOTO(BN_GF2m_mod(e, d, b[j]));
1654 /* Test that a + (a mod p) mod p == 0. */
1655 if (!BN_is_zero(e)) {
1656 fprintf(stderr, "GF(2^m) modulo test failed!\n");
1657 goto err;
1658 }
1659 }
1660 }
1661 rc = 1;
1662 err:
1663 BN_free(a);
1664 BN_free(b[0]);
1665 BN_free(b[1]);
1666 BN_free(c);
1667 BN_free(d);
1668 BN_free(e);
1669 return rc;
1670}
1671
1672int
1673test_gf2m_mod_mul(BIO *bp, BN_CTX *ctx)
1674{
1675 BIGNUM *a = NULL, *b[2] = { 0 }, *c = NULL, *d = NULL, *e = NULL, *f = NULL;
1676 BIGNUM *g = NULL, *h = NULL;
1677 int i, j;
1678 int p0[] = { 163, 7, 6, 3, 0, -1 };
1679 int p1[] = { 193, 15, 0, -1 };
1680 int rc = 0;
1681
1682 if ((a = BN_new()) == NULL)
1683 goto err;
1684 if ((b[0] = BN_new()) == NULL)
1685 goto err;
1686 if ((b[1] = BN_new()) == NULL)
1687 goto err;
1688 if ((c = BN_new()) == NULL)
1689 goto err;
1690 if ((d = BN_new()) == NULL)
1691 goto err;
1692 if ((e = BN_new()) == NULL)
1693 goto err;
1694 if ((f = BN_new()) == NULL)
1695 goto err;
1696 if ((g = BN_new()) == NULL)
1697 goto err;
1698 if ((h = BN_new()) == NULL)
1699 goto err;
1700
1701 CHECK_GOTO(BN_GF2m_arr2poly(p0, b[0]));
1702 CHECK_GOTO(BN_GF2m_arr2poly(p1, b[1]));
1703
1704 for (i = 0; i < num0; i++) {
1705 CHECK_GOTO(BN_bntest_rand(a, 1024, 0, 0));
1706 CHECK_GOTO(BN_bntest_rand(c, 1024, 0, 0));
1707 CHECK_GOTO(BN_bntest_rand(d, 1024, 0, 0));
1708 for (j = 0; j < 2; j++) {
1709 CHECK_GOTO(BN_GF2m_mod_mul(e, a, c, b[j], ctx));
1710#if 0 /* make test uses ouput in bc but bc can't handle GF(2^m) arithmetic */
1711 if (bp != NULL) {
1712 if (!results) {
1713 CHECK_GOTO(BN_print(bp, a));
1714 BIO_puts(bp, " * ");
1715 CHECK_GOTO(BN_print(bp, c));
1716 BIO_puts(bp, " % ");
1717 CHECK_GOTO(BN_print(bp, b[j]));
1718 BIO_puts(bp, " - ");
1719 CHECK_GOTO(BN_print(bp, e));
1720 BIO_puts(bp, "\n");
1721 }
1722 }
1723#endif
1724 CHECK_GOTO(BN_GF2m_add(f, a, d));
1725 CHECK_GOTO(BN_GF2m_mod_mul(g, f, c, b[j], ctx));
1726 CHECK_GOTO(BN_GF2m_mod_mul(h, d, c, b[j], ctx));
1727 CHECK_GOTO(BN_GF2m_add(f, e, g));
1728 CHECK_GOTO(BN_GF2m_add(f, f, h));
1729 /* Test that (a+d)*c = a*c + d*c. */
1730 if (!BN_is_zero(f)) {
1731 fprintf(stderr, "GF(2^m) modular multiplication test failed!\n");
1732 goto err;
1733 }
1734 }
1735 }
1736 rc = 1;
1737 err:
1738 BN_free(a);
1739 BN_free(b[0]);
1740 BN_free(b[1]);
1741 BN_free(c);
1742 BN_free(d);
1743 BN_free(e);
1744 BN_free(f);
1745 BN_free(g);
1746 BN_free(h);
1747 return rc;
1748}
1749
1750int
1751test_gf2m_mod_sqr(BIO *bp, BN_CTX *ctx)
1752{
1753 BIGNUM *a = NULL, *b[2] = { 0 }, *c = NULL, *d = NULL;
1754 int i, j, rc = 0;
1755 int p0[] = { 163, 7, 6, 3, 0, -1 };
1756 int p1[] = { 193, 15, 0, -1 };
1757
1758 if ((a = BN_new()) == NULL)
1759 goto err;
1760 if ((b[0] = BN_new()) == NULL)
1761 goto err;
1762 if ((b[1] = BN_new()) == NULL)
1763 goto err;
1764 if ((c = BN_new()) == NULL)
1765 goto err;
1766 if ((d = BN_new()) == NULL)
1767 goto err;
1768
1769 CHECK_GOTO(BN_GF2m_arr2poly(p0, b[0]));
1770 CHECK_GOTO(BN_GF2m_arr2poly(p1, b[1]));
1771
1772 for (i = 0; i < num0; i++) {
1773 CHECK_GOTO(BN_bntest_rand(a, 1024, 0, 0));
1774 for (j = 0; j < 2; j++) {
1775 CHECK_GOTO(BN_GF2m_mod_sqr(c, a, b[j], ctx));
1776 CHECK_GOTO(BN_copy(d, a));
1777 CHECK_GOTO(BN_GF2m_mod_mul(d, a, d, b[j], ctx));
1778#if 0 /* make test uses ouput in bc but bc can't handle GF(2^m) arithmetic */
1779 if (bp != NULL) {
1780 if (!results) {
1781 CHECK_GOTO(BN_print(bp, a));
1782 BIO_puts(bp, " ^ 2 % ");
1783 CHECK_GOTO(BN_print(bp, b[j]));
1784 BIO_puts(bp, " = ");
1785 CHECK_GOTO(BN_print(bp, c));
1786 BIO_puts(bp, "; a * a = ");
1787 CHECK_GOTO(BN_print(bp, d));
1788 BIO_puts(bp, "\n");
1789 }
1790 }
1791#endif
1792 CHECK_GOTO(BN_GF2m_add(d, c, d));
1793 /* Test that a*a = a^2. */
1794 if (!BN_is_zero(d)) {
1795 fprintf(stderr, "GF(2^m) modular squaring test failed!\n");
1796 goto err;
1797 }
1798 }
1799 }
1800 rc = 1;
1801 err:
1802 BN_free(a);
1803 BN_free(b[0]);
1804 BN_free(b[1]);
1805 BN_free(c);
1806 BN_free(d);
1807 return rc;
1808}
1809
1810int
1811test_gf2m_mod_inv(BIO *bp, BN_CTX *ctx)
1812{
1813 BIGNUM *a = NULL, *b[2] = { 0 }, *c = NULL, *d = NULL;
1814 int i, j, rc = 0;
1815 int p0[] = { 163, 7, 6, 3, 0, -1 };
1816 int p1[] = { 193, 15, 0, -1 };
1817
1818 if ((a = BN_new()) == NULL)
1819 goto err;
1820 if ((b[0] = BN_new()) == NULL)
1821 goto err;
1822 if ((b[1] = BN_new()) == NULL)
1823 goto err;
1824 if ((c = BN_new()) == NULL)
1825 goto err;
1826 if ((d = BN_new()) == NULL)
1827 goto err;
1828
1829 CHECK_GOTO(BN_GF2m_arr2poly(p0, b[0]));
1830 CHECK_GOTO(BN_GF2m_arr2poly(p1, b[1]));
1831
1832 for (i = 0; i < num0; i++) {
1833 CHECK_GOTO(BN_bntest_rand(a, 512, 0, 0));
1834 for (j = 0; j < 2; j++) {
1835 CHECK_GOTO(BN_GF2m_mod_inv(c, a, b[j], ctx));
1836 CHECK_GOTO(BN_GF2m_mod_mul(d, a, c, b[j], ctx));
1837#if 0 /* make test uses ouput in bc but bc can't handle GF(2^m) arithmetic */
1838 if (bp != NULL) {
1839 if (!results) {
1840 CHECK_GOTO(BN_print(bp, a));
1841 BIO_puts(bp, " * ");
1842 CHECK_GOTO(BN_print(bp, c));
1843 BIO_puts(bp, " - 1 % ");
1844 CHECK_GOTO(BN_print(bp, b[j]));
1845 BIO_puts(bp, "\n");
1846 }
1847 }
1848#endif
1849 /* Test that ((1/a)*a) = 1. */
1850 if (!BN_is_one(d)) {
1851 fprintf(stderr, "GF(2^m) modular inversion test failed!\n");
1852 goto err;
1853 }
1854 }
1855 }
1856 rc = 1;
1857 err:
1858 BN_free(a);
1859 BN_free(b[0]);
1860 BN_free(b[1]);
1861 BN_free(c);
1862 BN_free(d);
1863 return rc;
1864}
1865
1866int
1867test_gf2m_mod_div(BIO *bp, BN_CTX *ctx)
1868{
1869 BIGNUM *a = NULL, *b[2] = { 0 }, *c = NULL, *d = NULL, *e = NULL, *f = NULL;
1870 int i, j, rc = 0;
1871 int p0[] = { 163, 7, 6, 3, 0, -1 };
1872 int p1[] = { 193, 15, 0, -1 };
1873
1874 if ((a = BN_new()) == NULL)
1875 goto err;
1876 if ((b[0] = BN_new()) == NULL)
1877 goto err;
1878 if ((b[1] = BN_new()) == NULL)
1879 goto err;
1880 if ((c = BN_new()) == NULL)
1881 goto err;
1882 if ((d = BN_new()) == NULL)
1883 goto err;
1884 if ((e = BN_new()) == NULL)
1885 goto err;
1886 if ((f = BN_new()) == NULL)
1887 goto err;
1888
1889 CHECK_GOTO(BN_GF2m_arr2poly(p0, b[0]));
1890 CHECK_GOTO(BN_GF2m_arr2poly(p1, b[1]));
1891
1892 for (i = 0; i < num0; i++) {
1893 CHECK_GOTO(BN_bntest_rand(a, 512, 0, 0));
1894 CHECK_GOTO(BN_bntest_rand(c, 512, 0, 0));
1895 for (j = 0; j < 2; j++) {
1896 CHECK_GOTO(BN_GF2m_mod_div(d, a, c, b[j], ctx));
1897 CHECK_GOTO(BN_GF2m_mod_mul(e, d, c, b[j], ctx));
1898 CHECK_GOTO(BN_GF2m_mod_div(f, a, e, b[j], ctx));
1899#if 0 /* make test uses ouput in bc but bc can't handle GF(2^m) arithmetic */
1900 if (bp != NULL) {
1901 if (!results) {
1902 CHECK_GOTO(BN_print(bp, a));
1903 BIO_puts(bp, " = ");
1904 CHECK_GOTO(BN_print(bp, c));
1905 BIO_puts(bp, " * ");
1906 CHECK_GOTO(BN_print(bp, d));
1907 BIO_puts(bp, " % ");
1908 CHECK_GOTO(BN_print(bp, b[j]));
1909 BIO_puts(bp, "\n");
1910 }
1911 }
1912#endif
1913 /* Test that ((a/c)*c)/a = 1. */
1914 if (!BN_is_one(f)) {
1915 fprintf(stderr, "GF(2^m) modular division test failed!\n");
1916 goto err;
1917 }
1918 }
1919 }
1920 rc = 1;
1921 err:
1922 BN_free(a);
1923 BN_free(b[0]);
1924 BN_free(b[1]);
1925 BN_free(c);
1926 BN_free(d);
1927 BN_free(e);
1928 BN_free(f);
1929 return rc;
1930}
1931
1932int
1933test_gf2m_mod_exp(BIO *bp, BN_CTX *ctx)
1934{
1935 BIGNUM *a = NULL, *b[2] = { 0 }, *c = NULL, *d = NULL, *e = NULL, *f = NULL;
1936 int i, j, rc = 0;
1937 int p0[] = { 163, 7, 6, 3, 0, -1 };
1938 int p1[] = { 193, 15, 0, -1 };
1939
1940 if ((a = BN_new()) == NULL)
1941 goto err;
1942 if ((b[0] = BN_new()) == NULL)
1943 goto err;
1944 if ((b[1] = BN_new()) == NULL)
1945 goto err;
1946 if ((c = BN_new()) == NULL)
1947 goto err;
1948 if ((d = BN_new()) == NULL)
1949 goto err;
1950 if ((e = BN_new()) == NULL)
1951 goto err;
1952 if ((f = BN_new()) == NULL)
1953 goto err;
1954
1955 CHECK_GOTO(BN_GF2m_arr2poly(p0, b[0]));
1956 CHECK_GOTO(BN_GF2m_arr2poly(p1, b[1]));
1957
1958 for (i = 0; i < num0; i++) {
1959 CHECK_GOTO(BN_bntest_rand(a, 512, 0, 0));
1960 CHECK_GOTO(BN_bntest_rand(c, 512, 0, 0));
1961 CHECK_GOTO(BN_bntest_rand(d, 512, 0, 0));
1962 for (j = 0; j < 2; j++) {
1963 CHECK_GOTO(BN_GF2m_mod_exp(e, a, c, b[j], ctx));
1964 CHECK_GOTO(BN_GF2m_mod_exp(f, a, d, b[j], ctx));
1965 CHECK_GOTO(BN_GF2m_mod_mul(e, e, f, b[j], ctx));
1966 CHECK_GOTO(BN_add(f, c, d));
1967 CHECK_GOTO(BN_GF2m_mod_exp(f, a, f, b[j], ctx));
1968#if 0 /* make test uses ouput in bc but bc can't handle GF(2^m) arithmetic */
1969 if (bp != NULL) {
1970 if (!results) {
1971 CHECK_GOTO(BN_print(bp, a));
1972 BIO_puts(bp, " ^ (");
1973 CHECK_GOTO(BN_print(bp, c));
1974 BIO_puts(bp, " + ");
1975 CHECK_GOTO(BN_print(bp, d));
1976 BIO_puts(bp, ") = ");
1977 CHECK_GOTO(BN_print(bp, e));
1978 BIO_puts(bp, "; - ");
1979 CHECK_GOTO(BN_print(bp, f));
1980 BIO_puts(bp, " % ");
1981 CHECK_GOTO(BN_print(bp, b[j]));
1982 BIO_puts(bp, "\n");
1983 }
1984 }
1985#endif
1986 CHECK_GOTO(BN_GF2m_add(f, e, f));
1987 /* Test that a^(c+d)=a^c*a^d. */
1988 if (!BN_is_zero(f)) {
1989 fprintf(stderr, "GF(2^m) modular exponentiation test failed!\n");
1990 goto err;
1991 }
1992 }
1993 }
1994 rc = 1;
1995 err:
1996 BN_free(a);
1997 BN_free(b[0]);
1998 BN_free(b[1]);
1999 BN_free(c);
2000 BN_free(d);
2001 BN_free(e);
2002 BN_free(f);
2003 return rc;
2004}
2005
2006int
2007test_gf2m_mod_sqrt(BIO *bp, BN_CTX *ctx)
2008{
2009 BIGNUM *a = NULL, *b[2] = { 0 }, *c = NULL, *d = NULL, *e = NULL, *f = NULL;
2010 int i, j, rc = 0;
2011 int p0[] = { 163, 7, 6, 3, 0, -1 };
2012 int p1[] = { 193, 15, 0, -1 };
2013
2014 if ((a = BN_new()) == NULL)
2015 goto err;
2016 if ((b[0] = BN_new()) == NULL)
2017 goto err;
2018 if ((b[1] = BN_new()) == NULL)
2019 goto err;
2020 if ((c = BN_new()) == NULL)
2021 goto err;
2022 if ((d = BN_new()) == NULL)
2023 goto err;
2024 if ((e = BN_new()) == NULL)
2025 goto err;
2026 if ((f = BN_new()) == NULL)
2027 goto err;
2028
2029 CHECK_GOTO(BN_GF2m_arr2poly(p0, b[0]));
2030 CHECK_GOTO(BN_GF2m_arr2poly(p1, b[1]));
2031
2032 for (i = 0; i < num0; i++) {
2033 CHECK_GOTO(BN_bntest_rand(a, 512, 0, 0));
2034 for (j = 0; j < 2; j++) {
2035 CHECK_GOTO(BN_GF2m_mod(c, a, b[j]));
2036 CHECK_GOTO(BN_GF2m_mod_sqrt(d, a, b[j], ctx));
2037 CHECK_GOTO(BN_GF2m_mod_sqr(e, d, b[j], ctx));
2038#if 0 /* make test uses ouput in bc but bc can't handle GF(2^m) arithmetic */
2039 if (bp != NULL) {
2040 if (!results) {
2041 CHECK_GOTO(BN_print(bp, d));
2042 BIO_puts(bp, " ^ 2 - ");
2043 CHECK_GOTO(BN_print(bp, a));
2044 BIO_puts(bp, "\n");
2045 }
2046 }
2047#endif
2048 CHECK_GOTO(BN_GF2m_add(f, c, e));
2049 /* Test that d^2 = a, where d = sqrt(a). */
2050 if (!BN_is_zero(f)) {
2051 fprintf(stderr, "GF(2^m) modular square root test failed!\n");
2052 goto err;
2053 }
2054 }
2055 }
2056 rc = 1;
2057 err:
2058 BN_free(a);
2059 BN_free(b[0]);
2060 BN_free(b[1]);
2061 BN_free(c);
2062 BN_free(d);
2063 BN_free(e);
2064 BN_free(f);
2065 return rc;
2066}
2067
2068int
2069test_gf2m_mod_solve_quad(BIO *bp, BN_CTX *ctx)
2070{
2071 BIGNUM *a = NULL, *b[2] = { 0 }, *c = NULL, *d = NULL, *e = NULL;
2072 int i, j, s = 0, t, rc = 0;
2073 int p0[] = { 163, 7, 6, 3, 0, -1 };
2074 int p1[] = { 193, 15, 0, -1 };
2075
2076 if ((a = BN_new()) == NULL)
2077 goto err;
2078 if ((b[0] = BN_new()) == NULL)
2079 goto err;
2080 if ((b[1] = BN_new()) == NULL)
2081 goto err;
2082 if ((c = BN_new()) == NULL)
2083 goto err;
2084 if ((d = BN_new()) == NULL)
2085 goto err;
2086 if ((e = BN_new()) == NULL)
2087 goto err;
2088
2089 CHECK_GOTO(BN_GF2m_arr2poly(p0, b[0]));
2090 CHECK_GOTO(BN_GF2m_arr2poly(p1, b[1]));
2091
2092 for (i = 0; i < num0; i++) {
2093 CHECK_GOTO(BN_bntest_rand(a, 512, 0, 0));
2094 for (j = 0; j < 2; j++) {
2095 t = BN_GF2m_mod_solve_quad(c, a, b[j], ctx);
2096 if (t) {
2097 s++;
2098 CHECK_GOTO(BN_GF2m_mod_sqr(d, c, b[j], ctx));
2099 CHECK_GOTO(BN_GF2m_add(d, c, d));
2100 CHECK_GOTO(BN_GF2m_mod(e, a, b[j]));
2101#if 0 /* make test uses ouput in bc but bc can't handle GF(2^m) arithmetic */
2102 if (bp != NULL) {
2103 if (!results) {
2104 CHECK_GOTO(BN_print(bp, c));
2105 BIO_puts(bp, " is root of z^2 + z = ");
2106 CHECK_GOTO(BN_print(bp, a));
2107 BIO_puts(bp, " % ");
2108 CHECK_GOTO(BN_print(bp, b[j]));
2109 BIO_puts(bp, "\n");
2110 }
2111 }
2112#endif
2113 CHECK_GOTO(BN_GF2m_add(e, e, d));
2114 /* Test that solution of quadratic c satisfies c^2 + c = a. */
2115 if (!BN_is_zero(e)) {
2116 fprintf(stderr, "GF(2^m) modular solve quadratic test failed!\n");
2117 goto err;
2118 }
2119
2120 } else {
2121#if 0 /* make test uses ouput in bc but bc can't handle GF(2^m) arithmetic */
2122 if (bp != NULL) {
2123 if (!results) {
2124 BIO_puts(bp, "There are no roots of z^2 + z = ");
2125 CHECK_GOTO(BN_print(bp, a));
2126 BIO_puts(bp, " % ");
2127 CHECK_GOTO(BN_print(bp, b[j]));
2128 BIO_puts(bp, "\n");
2129 }
2130 }
2131#endif
2132 }
2133 }
2134 }
2135 if (s == 0) {
2136 fprintf(stderr, "All %d tests of GF(2^m) modular solve quadratic resulted in no roots;\n", num0);
2137 fprintf(stderr, "this is very unlikely and probably indicates an error.\n");
2138 goto err;
2139 }
2140 rc = 1;
2141 err:
2142 BN_free(a);
2143 BN_free(b[0]);
2144 BN_free(b[1]);
2145 BN_free(c);
2146 BN_free(d);
2147 BN_free(e);
2148 return rc;
2149}
2150#endif
2151static int
2152genprime_cb(int p, int n, BN_GENCB *arg)
2153{
2154 char c = '*';
2155
2156 if (p == 0)
2157 c = '.';
2158 if (p == 1)
2159 c = '+';
2160 if (p == 2)
2161 c = '*';
2162 if (p == 3)
2163 c = '\n';
2164 putc(c, stderr);
2165 return (1);
2166}
2167
2168int
2169test_kron(BIO *bp, BN_CTX *ctx)
2170{
2171 BIGNUM *a = NULL, *b = NULL, *r = NULL, *t = NULL;
2172 BN_GENCB *cb = NULL;
2173 int i;
2174 int legendre, kronecker;
2175 int rc = 0;
2176
2177 if ((a = BN_new()) == NULL)
2178 goto err;
2179 if ((b = BN_new()) == NULL)
2180 goto err;
2181 if ((r = BN_new()) == NULL)
2182 goto err;
2183 if ((t = BN_new()) == NULL)
2184 goto err;
2185
2186 if ((cb = BN_GENCB_new()) == NULL)
2187 goto err;
2188
2189 BN_GENCB_set(cb, genprime_cb, NULL);
2190
2191 /*
2192 * We test BN_kronecker(a, b, ctx) just for b odd (Jacobi symbol). In
2193 * this case we know that if b is prime, then BN_kronecker(a, b, ctx) is
2194 * congruent to $a^{(b-1)/2}$, modulo $b$ (Legendre symbol). So we
2195 * generate a random prime b and compare these values for a number of
2196 * random a's. (That is, we run the Solovay-Strassen primality test to
2197 * confirm that b is prime, except that we don't want to test whether b
2198 * is prime but whether BN_kronecker works.)
2199 */
2200
2201 if (!BN_generate_prime_ex(b, 512, 0, NULL, NULL, cb))
2202 goto err;
2203 BN_set_negative(b, rand_neg());
2204 putc('\n', stderr);
2205
2206 for (i = 0; i < num0; i++) {
2207 if (!BN_bntest_rand(a, 512, 0, 0))
2208 goto err;
2209 BN_set_negative(a, rand_neg());
2210
2211 /* t := (|b|-1)/2 (note that b is odd) */
2212 if (!BN_copy(t, b))
2213 goto err;
2214 BN_set_negative(t, 0);
2215 if (!BN_sub_word(t, 1))
2216 goto err;
2217 if (!BN_rshift1(t, t))
2218 goto err;
2219 /* r := a^t mod b */
2220 BN_set_negative(b, 0);
2221
2222 if (!BN_mod_exp_recp(r, a, t, b, ctx))
2223 goto err;
2224 BN_set_negative(b, 1);
2225
2226 if (BN_is_word(r, 1))
2227 legendre = 1;
2228 else if (BN_is_zero(r))
2229 legendre = 0;
2230 else {
2231 if (!BN_add_word(r, 1))
2232 goto err;
2233 if (0 != BN_ucmp(r, b)) {
2234 fprintf(stderr, "Legendre symbol computation failed\n");
2235 goto err;
2236 }
2237 legendre = -1;
2238 }
2239
2240 kronecker = BN_kronecker(a, b, ctx);
2241 if (kronecker < -1)
2242 goto err;
2243 /* we actually need BN_kronecker(a, |b|) */
2244 if (BN_is_negative(a) && BN_is_negative(b))
2245 kronecker = -kronecker;
2246
2247 if (legendre != kronecker) {
2248 fprintf(stderr, "legendre != kronecker; a = ");
2249 CHECK_GOTO(BN_print_fp(stderr, a));
2250 fprintf(stderr, ", b = ");
2251 CHECK_GOTO(BN_print_fp(stderr, b));
2252 fprintf(stderr, "\n");
2253 goto err;
2254 }
2255
2256 putc('.', stderr);
2257 }
2258
2259 putc('\n', stderr);
2260 rc = 1;
2261
2262 err:
2263 BN_GENCB_free(cb);
2264 BN_free(a);
2265 BN_free(b);
2266 BN_free(r);
2267 BN_free(t);
2268 return rc;
2269}
2270
2271int
2272test_sqrt(BIO *bp, BN_CTX *ctx)
2273{
2274 BIGNUM *a = NULL, *p = NULL, *r = NULL;
2275 BN_GENCB *cb = NULL;
2276 int i, j;
2277 int rc = 0;
2278
2279 if ((a = BN_new()) == NULL)
2280 goto err;
2281 if ((p = BN_new()) == NULL)
2282 goto err;
2283 if ((r = BN_new()) == NULL)
2284 goto err;
2285
2286 if ((cb = BN_GENCB_new()) == NULL)
2287 goto err;
2288
2289 BN_GENCB_set(cb, genprime_cb, NULL);
2290
2291 for (i = 0; i < 16; i++) {
2292 if (i < 8) {
2293 unsigned primes[8] = { 2, 3, 5, 7, 11, 13, 17, 19 };
2294
2295 if (!BN_set_word(p, primes[i]))
2296 goto err;
2297 } else {
2298 if (!BN_set_word(a, 32))
2299 goto err;
2300 if (!BN_set_word(r, 2 * i + 1))
2301 goto err;
2302
2303 if (!BN_generate_prime_ex(p, 256, 0, a, r, cb))
2304 goto err;
2305 putc('\n', stderr);
2306 }
2307 BN_set_negative(p, rand_neg());
2308
2309 for (j = 0; j < num2; j++) {
2310 /*
2311 * construct 'a' such that it is a square modulo p, but in
2312 * general not a proper square and not reduced modulo p
2313 */
2314 if (!BN_bntest_rand(r, 256, 0, 3))
2315 goto err;
2316 if (!BN_nnmod(r, r, p, ctx))
2317 goto err;
2318 if (!BN_mod_sqr(r, r, p, ctx))
2319 goto err;
2320 if (!BN_bntest_rand(a, 256, 0, 3))
2321 goto err;
2322 if (!BN_nnmod(a, a, p, ctx))
2323 goto err;
2324 if (!BN_mod_sqr(a, a, p, ctx))
2325 goto err;
2326 if (!BN_mul(a, a, r, ctx))
2327 goto err;
2328 if (rand_neg())
2329 if (!BN_sub(a, a, p))
2330 goto err;
2331
2332 if (!BN_mod_sqrt(r, a, p, ctx))
2333 goto err;
2334 if (!BN_mod_sqr(r, r, p, ctx))
2335 goto err;
2336
2337 if (!BN_nnmod(a, a, p, ctx))
2338 goto err;
2339
2340 if (BN_cmp(a, r) != 0) {
2341 fprintf(stderr, "BN_mod_sqrt failed: a = ");
2342 CHECK_GOTO(BN_print_fp(stderr, a));
2343 fprintf(stderr, ", r = ");
2344 CHECK_GOTO(BN_print_fp(stderr, r));
2345 fprintf(stderr, ", p = ");
2346 CHECK_GOTO(BN_print_fp(stderr, p));
2347 fprintf(stderr, "\n");
2348 goto err;
2349 }
2350
2351 putc('.', stderr);
2352 }
2353
2354 putc('\n', stderr);
2355 }
2356 rc = 1;
2357
2358 err:
2359 BN_GENCB_free(cb);
2360 BN_free(a);
2361 BN_free(p);
2362 BN_free(r);
2363 return rc;
2364}
2365
2366int
2367test_lshift(BIO *bp, BN_CTX *ctx, BIGNUM *a_)
2368{
2369 BIGNUM *a = NULL, *b = NULL, *c = NULL, *d = NULL;
2370 int i;
2371 int rc = 1;
2372
2373 if ((b = BN_new()) == NULL)
2374 goto err;
2375 if ((c = BN_new()) == NULL)
2376 goto err;
2377 if ((d = BN_new()) == NULL)
2378 goto err;
2379 CHECK_GOTO(BN_one(c));
2380
2381 if (a_)
2382 a = a_;
2383 else {
2384 if ((a = BN_new()) == NULL)
2385 goto err;
2386 CHECK_GOTO(BN_bntest_rand(a, 200, 0, 0));
2387 BN_set_negative(a, rand_neg());
2388 }
2389 for (i = 0; i < num0; i++) {
2390 CHECK_GOTO(BN_lshift(b, a, i + 1));
2391 CHECK_GOTO(BN_add(c, c, c));
2392 if (bp != NULL) {
2393 if (!results) {
2394 CHECK_GOTO(BN_print(bp, a));
2395 BIO_puts(bp, " * ");
2396 CHECK_GOTO(BN_print(bp, c));
2397 BIO_puts(bp, " - ");
2398 }
2399 CHECK_GOTO(BN_print(bp, b));
2400 BIO_puts(bp, "\n");
2401 }
2402 CHECK_GOTO(BN_mul(d, a, c, ctx));
2403 CHECK_GOTO(BN_sub(d, d, b));
2404 if (!BN_is_zero(d)) {
2405 fprintf(stderr, "Left shift test failed!\n");
2406 fprintf(stderr, "a=");
2407 CHECK_GOTO(BN_print_fp(stderr, a));
2408 fprintf(stderr, "\nb=");
2409 CHECK_GOTO(BN_print_fp(stderr, b));
2410 fprintf(stderr, "\nc=");
2411 CHECK_GOTO(BN_print_fp(stderr, c));
2412 fprintf(stderr, "\nd=");
2413 CHECK_GOTO(BN_print_fp(stderr, d));
2414 fprintf(stderr, "\n");
2415 rc = 0;
2416 break;
2417 }
2418 }
2419 err:
2420 BN_free(a);
2421 BN_free(b);
2422 BN_free(c);
2423 BN_free(d);
2424 return (rc);
2425}
2426
2427int
2428test_lshift1(BIO *bp)
2429{
2430 BIGNUM *a = NULL, *b = NULL, *c = NULL;
2431 int i;
2432 int rc = 1;
2433
2434 if ((a = BN_new()) == NULL)
2435 goto err;
2436 if ((b = BN_new()) == NULL)
2437 goto err;
2438 if ((c = BN_new()) == NULL)
2439 goto err;
2440
2441 CHECK_GOTO(BN_bntest_rand(a, 200, 0, 0));
2442 BN_set_negative(a, rand_neg());
2443 for (i = 0; i < num0; i++) {
2444 CHECK_GOTO(BN_lshift1(b, a));
2445 if (bp != NULL) {
2446 if (!results) {
2447 CHECK_GOTO(BN_print(bp, a));
2448 BIO_puts(bp, " * 2");
2449 BIO_puts(bp, " - ");
2450 }
2451 CHECK_GOTO(BN_print(bp, b));
2452 BIO_puts(bp, "\n");
2453 }
2454 CHECK_GOTO(BN_add(c, a, a));
2455 CHECK_GOTO(BN_sub(a, b, c));
2456 if (!BN_is_zero(a)) {
2457 fprintf(stderr, "Left shift one test failed!\n");
2458 rc = 0;
2459 break;
2460 }
2461
2462 CHECK_GOTO(BN_copy(a, b));
2463 }
2464 err:
2465 BN_free(a);
2466 BN_free(b);
2467 BN_free(c);
2468 return (rc);
2469}
2470
2471int
2472test_rshift(BIO *bp, BN_CTX *ctx)
2473{
2474 BIGNUM *a = NULL, *b = NULL, *c = NULL, *d = NULL, *e = NULL;
2475 int i;
2476 int rc = 1;
2477
2478 if ((a = BN_new()) == NULL)
2479 goto err;
2480 if ((b = BN_new()) == NULL)
2481 goto err;
2482 if ((c = BN_new()) == NULL)
2483 goto err;
2484 if ((d = BN_new()) == NULL)
2485 goto err;
2486 if ((e = BN_new()) == NULL)
2487 goto err;
2488 CHECK_GOTO(BN_one(c));
2489
2490 CHECK_GOTO(BN_bntest_rand(a, 200, 0, 0));
2491 BN_set_negative(a, rand_neg());
2492 for (i = 0; i < num0; i++) {
2493 CHECK_GOTO(BN_rshift(b, a, i + 1));
2494 CHECK_GOTO(BN_add(c, c, c));
2495 if (bp != NULL) {
2496 if (!results) {
2497 CHECK_GOTO(BN_print(bp, a));
2498 BIO_puts(bp, " / ");
2499 CHECK_GOTO(BN_print(bp, c));
2500 BIO_puts(bp, " - ");
2501 }
2502 CHECK_GOTO(BN_print(bp, b));
2503 BIO_puts(bp, "\n");
2504 }
2505 CHECK_GOTO(BN_div(d, e, a, c, ctx));
2506 CHECK_GOTO(BN_sub(d, d, b));
2507 if (!BN_is_zero(d)) {
2508 fprintf(stderr, "Right shift test failed!\n");
2509 rc = 0;
2510 break;
2511 }
2512 }
2513 err:
2514 BN_free(a);
2515 BN_free(b);
2516 BN_free(c);
2517 BN_free(d);
2518 BN_free(e);
2519 return (rc);
2520}
2521
2522int
2523test_rshift1(BIO *bp)
2524{
2525 BIGNUM *a = NULL, *b = NULL, *c = NULL;
2526 int i;
2527 int rc = 1;
2528
2529 if ((a = BN_new()) == NULL)
2530 goto err;
2531 if ((b = BN_new()) == NULL)
2532 goto err;
2533 if ((c = BN_new()) == NULL)
2534 goto err;
2535
2536 CHECK_GOTO(BN_bntest_rand(a, 200, 0, 0));
2537 BN_set_negative(a, rand_neg());
2538 for (i = 0; i < num0; i++) {
2539 CHECK_GOTO(BN_rshift1(b, a));
2540 if (bp != NULL) {
2541 if (!results) {
2542 CHECK_GOTO(BN_print(bp, a));
2543 BIO_puts(bp, " / 2");
2544 BIO_puts(bp, " - ");
2545 }
2546 CHECK_GOTO(BN_print(bp, b));
2547 BIO_puts(bp, "\n");
2548 }
2549 CHECK_GOTO(BN_sub(c, a, b));
2550 CHECK_GOTO(BN_sub(c, c, b));
2551 if (!BN_is_zero(c) && !BN_abs_is_word(c, 1)) {
2552 fprintf(stderr, "Right shift one test failed!\n");
2553 rc = 0;
2554 break;
2555 }
2556 CHECK_GOTO(BN_copy(a, b));
2557 }
2558 err:
2559 BN_free(a);
2560 BN_free(b);
2561 BN_free(c);
2562 return (rc);
2563}
2564
2565int
2566rand_neg(void)
2567{
2568 static unsigned int neg = 0;
2569 static int sign[8] = { 0, 0, 0, 1, 1, 0, 1, 1 };
2570
2571 return (sign[(neg++) % 8]);
2572}
2573
2574int
2575test_mod_exp_sizes(BIO *bp, BN_CTX *ctx)
2576{
2577 BN_MONT_CTX *mont_ctx = NULL;
2578 BIGNUM *p = NULL, *x = NULL, *y = NULL, *r = NULL, *r2 = NULL;
2579 int size;
2580 int rc = 0;
2581
2582 BN_CTX_start(ctx);
2583 CHECK_GOTO(p = BN_CTX_get(ctx));
2584 CHECK_GOTO(x = BN_CTX_get(ctx));
2585 CHECK_GOTO(y = BN_CTX_get(ctx));
2586 CHECK_GOTO(r = BN_CTX_get(ctx));
2587 CHECK_GOTO(r2 = BN_CTX_get(ctx));
2588 mont_ctx = BN_MONT_CTX_new();
2589
2590 if (r2 == NULL || mont_ctx == NULL)
2591 goto err;
2592
2593 if (!BN_generate_prime_ex(p, 32, 0, NULL, NULL, NULL) ||
2594 !BN_MONT_CTX_set(mont_ctx, p, ctx))
2595 goto err;
2596
2597 for (size = 32; size < 1024; size += 8) {
2598 if (!BN_rand(x, size, -1, 0) ||
2599 !BN_rand(y, size, -1, 0) ||
2600 !BN_mod_exp_mont_consttime(r, x, y, p, ctx, mont_ctx) ||
2601 !BN_mod_exp(r2, x, y, p, ctx))
2602 goto err;
2603
2604 if (BN_cmp(r, r2) != 0) {
2605 char *r_str = NULL;
2606 char *r2_str = NULL;
2607 CHECK_GOTO(r_str = BN_bn2hex(r));
2608 CHECK_GOTO(r2_str = BN_bn2hex(r2));
2609
2610 printf("Incorrect answer at size %d: %s vs %s\n",
2611 size, r_str, r2_str);
2612 free(r_str);
2613 free(r2_str);
2614 goto err;
2615 }
2616 }
2617
2618 rc = 1;
2619
2620 err:
2621 BN_MONT_CTX_free(mont_ctx);
2622 BN_CTX_end(ctx);
2623 return rc;
2624}