1 /* $OpenBSD: bn_test.c,v 1.22 2025/01/22 13:02:14 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 #include <stdio.h>
73 #include <stdlib.h>
74 #include <string.h>
75
76 #include <openssl/bio.h>
77 #include <openssl/bn.h>
78 #include <openssl/err.h>
79
80 #include "bn_local.h"
81
82 const int num0 = 100; /* number of tests */
83 const int num1 = 50; /* additional tests for some functions */
84 const int num2 = 5; /* number of tests for slow functions */
85
86 int test_add(BIO *bp, BN_CTX *ctx);
87 int test_sub(BIO *bp, BN_CTX *ctx);
88 int test_lshift1(BIO *bp, BN_CTX *ctx);
89 int test_lshift(BIO *bp, BN_CTX *ctx, int use_lst);
90 int test_rshift1(BIO *bp, BN_CTX *ctx);
91 int test_rshift(BIO *bp, BN_CTX *ctx);
92 int test_div(BIO *bp, BN_CTX *ctx);
93 int test_div_word(BIO *bp, BN_CTX *ctx);
94 int test_div_recp(BIO *bp, BN_CTX *ctx);
95 int test_mul(BIO *bp, BN_CTX *ctx);
96 int test_sqr(BIO *bp, BN_CTX *ctx);
97 int test_mont(BIO *bp, BN_CTX *ctx);
98 int test_mod(BIO *bp, BN_CTX *ctx);
99 int test_mod_mul(BIO *bp, BN_CTX *ctx);
100 int test_mod_exp(BIO *bp, BN_CTX *ctx);
101 int test_mod_exp_mont_consttime(BIO *bp, BN_CTX *ctx);
102 int test_mod_exp_mont5(BIO *bp, BN_CTX *ctx);
103 int test_mod_exp_sizes(BIO *bp, BN_CTX *ctx);
104 int test_exp(BIO *bp, BN_CTX *ctx);
105 int test_kron(BIO *bp, BN_CTX *ctx);
106 int test_sqrt(BIO *bp, BN_CTX *ctx);
107 int rand_neg(void);
108 static int results = 0;
109
110 #define PRINT_ERROR printf("Error in %s [%s:%d]\n", __func__, __FILE__, \
111 __LINE__)
112
113 #define CHECK_GOTO(a) do { \
114 if (!(a)) { \
115 PRINT_ERROR; \
116 goto err; \
117 } \
118 } while (0)
119
120 static void
message(BIO * out,char * m)121 message(BIO *out, char *m)
122 {
123 ERR_print_errors_fp(stderr);
124 ERR_clear_error();
125
126 fprintf(stderr, "test %s\n", m);
127 BIO_puts(out, "print \"test ");
128 BIO_puts(out, m);
129 BIO_puts(out, "\\n\"\n");
130 }
131
132 int
main(int argc,char * argv[])133 main(int argc, char *argv[])
134 {
135 BN_CTX *ctx;
136 BIO *out;
137 char *outfile = NULL;
138
139 results = 0;
140
141 argc--;
142 argv++;
143 while (argc >= 1) {
144 if (strcmp(*argv, "-results") == 0)
145 results = 1;
146 else if (strcmp(*argv, "-out") == 0) {
147 if (--argc < 1)
148 break;
149 outfile= *(++argv);
150 }
151 argc--;
152 argv++;
153 }
154
155 if ((ctx = BN_CTX_new()) == NULL)
156 exit(1);
157
158 if ((out = BIO_new(BIO_s_file())) == NULL)
159 exit(1);
160 if (outfile == NULL) {
161 BIO_set_fp(out, stdout, BIO_NOCLOSE);
162 } else {
163 if (!BIO_write_filename(out, outfile)) {
164 perror(outfile);
165 exit(1);
166 }
167 }
168
169 if (!results)
170 BIO_puts(out, "obase=16\nibase=16\n");
171
172 message(out, "BN_add");
173 if (!test_add(out, ctx))
174 goto err;
175 (void)BIO_flush(out);
176
177 message(out, "BN_sub");
178 if (!test_sub(out, ctx))
179 goto err;
180 (void)BIO_flush(out);
181
182 message(out, "BN_lshift1");
183 if (!test_lshift1(out, ctx))
184 goto err;
185 (void)BIO_flush(out);
186
187 message(out, "BN_lshift (fixed)");
188 if (!test_lshift(out, ctx, 0))
189 goto err;
190 (void)BIO_flush(out);
191
192 message(out, "BN_lshift");
193 if (!test_lshift(out, ctx, 1))
194 goto err;
195 (void)BIO_flush(out);
196
197 message(out, "BN_rshift1");
198 if (!test_rshift1(out, ctx))
199 goto err;
200 (void)BIO_flush(out);
201
202 message(out, "BN_rshift");
203 if (!test_rshift(out, ctx))
204 goto err;
205 (void)BIO_flush(out);
206
207 message(out, "BN_sqr");
208 if (!test_sqr(out, ctx))
209 goto err;
210 (void)BIO_flush(out);
211
212 message(out, "BN_mul");
213 if (!test_mul(out, ctx))
214 goto err;
215 (void)BIO_flush(out);
216
217 message(out, "BN_div");
218 if (!test_div(out, ctx))
219 goto err;
220 (void)BIO_flush(out);
221
222 message(out, "BN_div_word");
223 if (!test_div_word(out, ctx))
224 goto err;
225 (void)BIO_flush(out);
226
227 message(out, "BN_div_reciprocal");
228 if (!test_div_recp(out, ctx))
229 goto err;
230 (void)BIO_flush(out);
231
232 message(out, "BN_mod");
233 if (!test_mod(out, ctx))
234 goto err;
235 (void)BIO_flush(out);
236
237 message(out, "BN_mod_mul");
238 if (!test_mod_mul(out, ctx))
239 goto err;
240 (void)BIO_flush(out);
241
242 message(out, "BN_mont");
243 if (!test_mont(out, ctx))
244 goto err;
245 (void)BIO_flush(out);
246
247 message(out, "BN_mod_exp");
248 if (!test_mod_exp(out, ctx))
249 goto err;
250 (void)BIO_flush(out);
251
252 message(out, "BN_mod_exp_mont_consttime");
253 if (!test_mod_exp_mont_consttime(out, ctx))
254 goto err;
255 (void)BIO_flush(out);
256
257 message(out, "BN_mod_exp_mont5");
258 if (!test_mod_exp_mont5(out, ctx))
259 goto err;
260 (void)BIO_flush(out);
261
262 message(out, "BN_exp");
263 if (!test_exp(out, ctx))
264 goto err;
265 (void)BIO_flush(out);
266
267 message(out, "BN_kronecker");
268 if (!test_kron(out, ctx))
269 goto err;
270 (void)BIO_flush(out);
271
272 message(out, "BN_mod_sqrt");
273 if (!test_sqrt(out, ctx))
274 goto err;
275 (void)BIO_flush(out);
276
277 message(out, "Modexp with different sizes");
278 if (!test_mod_exp_sizes(out, ctx))
279 goto err;
280 (void)BIO_flush(out);
281
282 BN_CTX_free(ctx);
283 BIO_free(out);
284
285 exit(0);
286 err:
287 BIO_puts(out, "1\n"); /* make sure the Perl script fed by bc notices
288 * the failure, see test_bn in test/Makefile.ssl*/
289
290 (void)BIO_flush(out);
291 ERR_load_crypto_strings();
292 ERR_print_errors_fp(stderr);
293 exit(1);
294 }
295
296 int
test_add(BIO * bp,BN_CTX * ctx)297 test_add(BIO *bp, BN_CTX *ctx)
298 {
299 BIGNUM *a, *b, *c;
300 int i;
301 int ret = 0;
302
303 BN_CTX_start(ctx);
304
305 if ((a = BN_CTX_get(ctx)) == NULL)
306 goto err;
307 if ((b = BN_CTX_get(ctx)) == NULL)
308 goto err;
309 if ((c = BN_CTX_get(ctx)) == NULL)
310 goto err;
311
312 CHECK_GOTO(BN_bntest_rand(a, 512, 0, 0));
313 for (i = 0; i < num0; i++) {
314 CHECK_GOTO(BN_bntest_rand(b, 450 + i, 0, 0));
315 BN_set_negative(a, rand_neg());
316 BN_set_negative(b, rand_neg());
317 CHECK_GOTO(BN_add(c, a, b));
318 if (bp != NULL) {
319 if (!results) {
320 CHECK_GOTO(BN_print(bp, a));
321 BIO_puts(bp, " + ");
322 CHECK_GOTO(BN_print(bp, b));
323 BIO_puts(bp, " - ");
324 }
325 CHECK_GOTO(BN_print(bp, c));
326 BIO_puts(bp, "\n");
327 }
328 BN_set_negative(a, !BN_is_negative(a));
329 BN_set_negative(b, !BN_is_negative(b));
330 CHECK_GOTO(BN_add(c, c, b));
331 CHECK_GOTO(BN_add(c, c, a));
332 if (!BN_is_zero(c)) {
333 fprintf(stderr, "Add test failed!\n");
334 goto err;
335 }
336 }
337
338 ret = 1;
339 err:
340 BN_CTX_end(ctx);
341
342 return ret;
343 }
344
345 int
test_sub(BIO * bp,BN_CTX * ctx)346 test_sub(BIO *bp, BN_CTX *ctx)
347 {
348 BIGNUM *a, *b, *c;
349 int i;
350 int ret = 0;
351
352 BN_CTX_start(ctx);
353
354 if ((a = BN_CTX_get(ctx)) == NULL)
355 goto err;
356 if ((b = BN_CTX_get(ctx)) == NULL)
357 goto err;
358 if ((c = BN_CTX_get(ctx)) == NULL)
359 goto err;
360
361 for (i = 0; i < num0 + num1; i++) {
362 if (i < num1) {
363 CHECK_GOTO(BN_bntest_rand(a, 512, 0, 0));
364 CHECK_GOTO(bn_copy(b, a));
365 if (BN_set_bit(a, i) == 0)
366 goto err;
367 CHECK_GOTO(BN_add_word(b, i));
368 } else {
369 CHECK_GOTO(BN_bntest_rand(b, 400 + i - num1, 0, 0));
370 BN_set_negative(a, rand_neg());
371 BN_set_negative(b, rand_neg());
372 }
373 CHECK_GOTO(BN_sub(c, a, b));
374 if (bp != NULL) {
375 if (!results) {
376 CHECK_GOTO(BN_print(bp, a));
377 BIO_puts(bp, " - ");
378 CHECK_GOTO(BN_print(bp, b));
379 BIO_puts(bp, " - ");
380 }
381 CHECK_GOTO(BN_print(bp, c));
382 BIO_puts(bp, "\n");
383 }
384 CHECK_GOTO(BN_add(c, c, b));
385 CHECK_GOTO(BN_sub(c, c, a));
386 if (!BN_is_zero(c)) {
387 fprintf(stderr, "Subtract test failed!\n");
388 goto err;
389 }
390 }
391
392 ret = 1;
393 err:
394 BN_CTX_end(ctx);
395
396 return ret;
397 }
398
399 int
test_div(BIO * bp,BN_CTX * ctx)400 test_div(BIO *bp, BN_CTX *ctx)
401 {
402 BIGNUM *a, *b, *c, *d, *e;
403 int i;
404 int ret = 0;
405
406 BN_CTX_start(ctx);
407
408 if ((a = BN_CTX_get(ctx)) == NULL)
409 goto err;
410 if ((b = BN_CTX_get(ctx)) == NULL)
411 goto err;
412 if ((c = BN_CTX_get(ctx)) == NULL)
413 goto err;
414 if ((d = BN_CTX_get(ctx)) == NULL)
415 goto err;
416 if ((e = BN_CTX_get(ctx)) == NULL)
417 goto err;
418
419 CHECK_GOTO(BN_one(a));
420 BN_zero(b);
421
422 if (BN_div(d, c, a, b, ctx)) {
423 fprintf(stderr, "Division by zero succeeded!\n");
424 goto err;
425 }
426 ERR_clear_error();
427
428 for (i = 0; i < num0 + num1; i++) {
429 if (i < num1) {
430 CHECK_GOTO(BN_bntest_rand(a, 400, 0, 0));
431 CHECK_GOTO(bn_copy(b, a));
432 CHECK_GOTO(BN_lshift(a, a, i));
433 CHECK_GOTO(BN_add_word(a, i));
434 } else
435 CHECK_GOTO(BN_bntest_rand(b, 50 + 3 * (i - num1), 0, 0));
436 BN_set_negative(a, rand_neg());
437 BN_set_negative(b, rand_neg());
438 CHECK_GOTO(BN_div(d, c, a, b, ctx));
439 if (bp != NULL) {
440 if (!results) {
441 CHECK_GOTO(BN_print(bp, a));
442 BIO_puts(bp, " / ");
443 CHECK_GOTO(BN_print(bp, b));
444 BIO_puts(bp, " - ");
445 }
446 CHECK_GOTO(BN_print(bp, d));
447 BIO_puts(bp, "\n");
448
449 if (!results) {
450 CHECK_GOTO(BN_print(bp, a));
451 BIO_puts(bp, " % ");
452 CHECK_GOTO(BN_print(bp, b));
453 BIO_puts(bp, " - ");
454 }
455 CHECK_GOTO(BN_print(bp, c));
456 BIO_puts(bp, "\n");
457 }
458 CHECK_GOTO(BN_mul(e, d, b, ctx));
459 CHECK_GOTO(BN_add(d, e, c));
460 CHECK_GOTO(BN_sub(d, d, a));
461 if (!BN_is_zero(d)) {
462 fprintf(stderr, "Division test failed!\n");
463 goto err;
464 }
465 }
466
467 ret = 1;
468 err:
469 BN_CTX_end(ctx);
470
471 return ret;
472 }
473
474 static void
print_word(BIO * bp,BN_ULONG w)475 print_word(BIO *bp, BN_ULONG w)
476 {
477 #ifdef SIXTY_FOUR_BIT
478 if (sizeof(w) > sizeof(unsigned long)) {
479 unsigned long h = (unsigned long)(w >> 32), l = (unsigned long)(w);
480
481 if (h)
482 BIO_printf(bp, "%lX%08lX", h, l);
483 else
484 BIO_printf(bp, "%lX", l);
485 return;
486 }
487 #endif
488 BIO_printf(bp, BN_HEX_FMT1, w);
489 }
490
491 int
test_div_word(BIO * bp,BN_CTX * ctx)492 test_div_word(BIO *bp, BN_CTX *ctx)
493 {
494 BIGNUM *a, *b;
495 BN_ULONG r, rmod, s = 0;
496 int i;
497 int ret = 0;
498
499 BN_CTX_start(ctx);
500
501 if ((a = BN_CTX_get(ctx)) == NULL)
502 goto err;
503 if ((b = BN_CTX_get(ctx)) == NULL)
504 goto err;
505
506 for (i = 0; i < num0; i++) {
507 do {
508 if (!BN_bntest_rand(a, 512, -1, 0) ||
509 !BN_bntest_rand(b, BN_BITS2, -1, 0))
510 goto err;
511 s = BN_get_word(b);
512 } while (!s);
513
514 if (!bn_copy(b, a))
515 goto err;
516
517 rmod = BN_mod_word(b, s);
518 r = BN_div_word(b, s);
519
520 if (r == (BN_ULONG)-1 || rmod == (BN_ULONG)-1)
521 goto err;
522
523 if (rmod != r) {
524 fprintf(stderr, "Mod (word) test failed!\n");
525 goto err;
526 }
527
528 if (bp != NULL) {
529 if (!results) {
530 CHECK_GOTO(BN_print(bp, a));
531 BIO_puts(bp, " / ");
532 print_word(bp, s);
533 BIO_puts(bp, " - ");
534 }
535 CHECK_GOTO(BN_print(bp, b));
536 BIO_puts(bp, "\n");
537
538 if (!results) {
539 CHECK_GOTO(BN_print(bp, a));
540 BIO_puts(bp, " % ");
541 print_word(bp, s);
542 BIO_puts(bp, " - ");
543 }
544 print_word(bp, r);
545 BIO_puts(bp, "\n");
546 }
547 CHECK_GOTO(BN_mul_word(b, s));
548 CHECK_GOTO(BN_add_word(b, r));
549 CHECK_GOTO(BN_sub(b, a, b));
550 if (!BN_is_zero(b)) {
551 fprintf(stderr, "Division (word) test failed!\n");
552 goto err;
553 }
554 }
555
556 ret = 1;
557 err:
558 BN_CTX_end(ctx);
559
560 return ret;
561 }
562
563 int
test_div_recp(BIO * bp,BN_CTX * ctx)564 test_div_recp(BIO *bp, BN_CTX *ctx)
565 {
566 BN_RECP_CTX *recp = NULL;
567 BIGNUM *a, *b, *c, *d, *e;
568 int i;
569 int ret = 0;
570
571 BN_CTX_start(ctx);
572
573 if ((a = BN_CTX_get(ctx)) == NULL)
574 goto err;
575 if ((b = BN_CTX_get(ctx)) == NULL)
576 goto err;
577 if ((c = BN_CTX_get(ctx)) == NULL)
578 goto err;
579 if ((d = BN_CTX_get(ctx)) == NULL)
580 goto err;
581 if ((e = BN_CTX_get(ctx)) == NULL)
582 goto err;
583
584 for (i = 0; i < num0 + num1; i++) {
585 if (i < num1) {
586 CHECK_GOTO(BN_bntest_rand(a, 400, 0, 0));
587 CHECK_GOTO(bn_copy(b, a));
588 CHECK_GOTO(BN_lshift(a, a, i));
589 CHECK_GOTO(BN_add_word(a, i));
590 } else
591 CHECK_GOTO(BN_bntest_rand(b, 50 + 3 * (i - num1), 0, 0));
592 BN_RECP_CTX_free(recp);
593 CHECK_GOTO(recp = BN_RECP_CTX_create(b));
594 CHECK_GOTO(BN_div_reciprocal(d, c, a, recp, ctx));
595 if (bp != NULL) {
596 if (!results) {
597 CHECK_GOTO(BN_print(bp, a));
598 BIO_puts(bp, " / ");
599 CHECK_GOTO(BN_print(bp, b));
600 BIO_puts(bp, " - ");
601 }
602 CHECK_GOTO(BN_print(bp, d));
603 BIO_puts(bp, "\n");
604
605 if (!results) {
606 CHECK_GOTO(BN_print(bp, a));
607 BIO_puts(bp, " % ");
608 CHECK_GOTO(BN_print(bp, b));
609 BIO_puts(bp, " - ");
610 }
611 CHECK_GOTO(BN_print(bp, c));
612 BIO_puts(bp, "\n");
613 }
614 CHECK_GOTO(BN_mul(e, d, b, ctx));
615 CHECK_GOTO(BN_add(d, e, c));
616 CHECK_GOTO(BN_sub(d, d, a));
617 if (!BN_is_zero(d)) {
618 fprintf(stderr, "Reciprocal division test failed!\n");
619 fprintf(stderr, "a=");
620 CHECK_GOTO(BN_print_fp(stderr, a));
621 fprintf(stderr, "\nb=");
622 CHECK_GOTO(BN_print_fp(stderr, b));
623 fprintf(stderr, "\n");
624 goto err;
625 }
626 }
627
628 ret = 1;
629 err:
630 BN_CTX_end(ctx);
631 BN_RECP_CTX_free(recp);
632
633 return ret;
634 }
635
636 int
test_mul(BIO * bp,BN_CTX * ctx)637 test_mul(BIO *bp, BN_CTX *ctx)
638 {
639 BIGNUM *a, *b, *c, *d, *e;
640 int i;
641 int ret = 0;
642
643 BN_CTX_start(ctx);
644
645 if ((a = BN_CTX_get(ctx)) == NULL)
646 goto err;
647 if ((b = BN_CTX_get(ctx)) == NULL)
648 goto err;
649 if ((c = BN_CTX_get(ctx)) == NULL)
650 goto err;
651 if ((d = BN_CTX_get(ctx)) == NULL)
652 goto err;
653 if ((e = BN_CTX_get(ctx)) == NULL)
654 goto err;
655
656 for (i = 0; i < num0 + num1; i++) {
657 if (i <= num1) {
658 CHECK_GOTO(BN_bntest_rand(a, 100, 0, 0));
659 CHECK_GOTO(BN_bntest_rand(b, 100, 0, 0));
660 } else
661 CHECK_GOTO(BN_bntest_rand(b, i - num1, 0, 0));
662 BN_set_negative(a, rand_neg());
663 BN_set_negative(b, rand_neg());
664 CHECK_GOTO(BN_mul(c, a, b, ctx));
665 if (bp != NULL) {
666 if (!results) {
667 CHECK_GOTO(BN_print(bp, a));
668 BIO_puts(bp, " * ");
669 CHECK_GOTO(BN_print(bp, b));
670 BIO_puts(bp, " - ");
671 }
672 CHECK_GOTO(BN_print(bp, c));
673 BIO_puts(bp, "\n");
674 }
675 CHECK_GOTO(BN_div(d, e, c, a, ctx));
676 CHECK_GOTO(BN_sub(d, d, b));
677 if (!BN_is_zero(d) || !BN_is_zero(e)) {
678 fprintf(stderr, "Multiplication test failed!\n");
679 goto err;
680 }
681 }
682
683 ret = 1;
684 err:
685 BN_CTX_end(ctx);
686
687 return ret;
688 }
689
690 int
test_sqr(BIO * bp,BN_CTX * ctx)691 test_sqr(BIO *bp, BN_CTX *ctx)
692 {
693 BIGNUM *a, *c, *d, *e;
694 int i;
695 int ret = 0;
696
697 BN_CTX_start(ctx);
698
699 if ((a = BN_CTX_get(ctx)) == NULL)
700 goto err;
701 if ((c = BN_CTX_get(ctx)) == NULL)
702 goto err;
703 if ((d = BN_CTX_get(ctx)) == NULL)
704 goto err;
705 if ((e = BN_CTX_get(ctx)) == NULL)
706 goto err;
707
708 for (i = 0; i < num0; i++) {
709 CHECK_GOTO(BN_bntest_rand(a, 40 + i * 10, 0, 0));
710 BN_set_negative(a, rand_neg());
711 CHECK_GOTO(BN_sqr(c, a, ctx));
712 if (bp != NULL) {
713 if (!results) {
714 CHECK_GOTO(BN_print(bp, a));
715 BIO_puts(bp, " * ");
716 CHECK_GOTO(BN_print(bp, a));
717 BIO_puts(bp, " - ");
718 }
719 CHECK_GOTO(BN_print(bp, c));
720 BIO_puts(bp, "\n");
721 }
722 CHECK_GOTO(BN_div(d, e, c, a, ctx));
723 CHECK_GOTO(BN_sub(d, d, a));
724 if (!BN_is_zero(d) || !BN_is_zero(e)) {
725 fprintf(stderr, "Square test failed!\n");
726 goto err;
727 }
728 }
729
730 /* Regression test for a BN_sqr overflow bug. */
731 if (!BN_hex2bn(&a, "80000000000000008000000000000001"
732 "FFFFFFFFFFFFFFFE0000000000000000")) {
733 fprintf(stderr, "BN_hex2bn failed\n");
734 goto err;
735 }
736 CHECK_GOTO(BN_sqr(c, a, ctx));
737 if (bp != NULL) {
738 if (!results) {
739 CHECK_GOTO(BN_print(bp, a));
740 BIO_puts(bp, " * ");
741 CHECK_GOTO(BN_print(bp, a));
742 BIO_puts(bp, " - ");
743 }
744 CHECK_GOTO(BN_print(bp, c));
745 BIO_puts(bp, "\n");
746 }
747 CHECK_GOTO(BN_mul(d, a, a, ctx));
748 if (BN_cmp(c, d)) {
749 fprintf(stderr,
750 "Square test failed: BN_sqr and BN_mul produce "
751 "different results!\n");
752 goto err;
753 }
754
755 /* Regression test for a BN_sqr overflow bug. */
756 if (!BN_hex2bn(&a, "80000000000000000000000080000001"
757 "FFFFFFFE000000000000000000000000")) {
758 fprintf(stderr, "BN_hex2bn failed\n");
759 goto err;
760 }
761 CHECK_GOTO(BN_sqr(c, a, ctx));
762 if (bp != NULL) {
763 if (!results) {
764 CHECK_GOTO(BN_print(bp, a));
765 BIO_puts(bp, " * ");
766 CHECK_GOTO(BN_print(bp, a));
767 BIO_puts(bp, " - ");
768 }
769 CHECK_GOTO(BN_print(bp, c));
770 BIO_puts(bp, "\n");
771 }
772 CHECK_GOTO(BN_mul(d, a, a, ctx));
773 if (BN_cmp(c, d)) {
774 fprintf(stderr, "Square test failed: BN_sqr and BN_mul produce "
775 "different results!\n");
776 goto err;
777 }
778
779 ret = 1;
780 err:
781 BN_CTX_end(ctx);
782
783 return ret;
784 }
785
786 int
test_mont(BIO * bp,BN_CTX * ctx)787 test_mont(BIO *bp, BN_CTX *ctx)
788 {
789 BN_MONT_CTX *mont = NULL;
790 BIGNUM *a, *b, *c, *d, *A, *B, *n;
791 int i;
792 int ret = 0;
793
794 BN_CTX_start(ctx);
795
796 if ((a = BN_CTX_get(ctx)) == NULL)
797 goto err;
798 if ((b = BN_CTX_get(ctx)) == NULL)
799 goto err;
800 if ((c = BN_CTX_get(ctx)) == NULL)
801 goto err;
802 if ((d = BN_CTX_get(ctx)) == NULL)
803 goto err;
804 if ((A = BN_CTX_get(ctx)) == NULL)
805 goto err;
806 if ((B = BN_CTX_get(ctx)) == NULL)
807 goto err;
808 if ((n = BN_CTX_get(ctx)) == NULL)
809 goto err;
810
811 if ((mont = BN_MONT_CTX_new()) == NULL)
812 goto err;
813
814 BN_zero(n);
815 if (BN_MONT_CTX_set(mont, n, ctx)) {
816 fprintf(stderr, "BN_MONT_CTX_set succeeded for zero modulus!\n");
817 goto err;
818 }
819 ERR_clear_error();
820
821 CHECK_GOTO(BN_set_word(n, 16));
822 if (BN_MONT_CTX_set(mont, n, ctx)) {
823 fprintf(stderr, "BN_MONT_CTX_set succeeded for even modulus!\n");
824 goto err;
825 }
826 ERR_clear_error();
827
828 CHECK_GOTO(BN_bntest_rand(a, 100, 0, 0));
829 CHECK_GOTO(BN_bntest_rand(b, 100, 0, 0));
830 for (i = 0; i < num2; i++) {
831 int bits = (200 * (i + 1)) / num2;
832
833 if (bits == 0)
834 continue;
835 CHECK_GOTO(BN_bntest_rand(n, bits, 0, 1));
836 CHECK_GOTO(BN_MONT_CTX_set(mont, n, ctx));
837
838 CHECK_GOTO(BN_nnmod(a, a, n, ctx));
839 CHECK_GOTO(BN_nnmod(b, b, n, ctx));
840
841 CHECK_GOTO(BN_to_montgomery(A, a, mont, ctx));
842 CHECK_GOTO(BN_to_montgomery(B, b, mont, ctx));
843
844 CHECK_GOTO(BN_mod_mul_montgomery(c, A, B, mont, ctx));
845 CHECK_GOTO(BN_from_montgomery(A, c, mont, ctx));
846 if (bp != NULL) {
847 if (!results) {
848 CHECK_GOTO(BN_print(bp, a));
849 BIO_puts(bp, " * ");
850 CHECK_GOTO(BN_print(bp, b));
851 BIO_puts(bp, " % ");
852 /* n == &mont->N */
853 CHECK_GOTO(BN_print(bp, n));
854 BIO_puts(bp, " - ");
855 }
856 CHECK_GOTO(BN_print(bp, A));
857 BIO_puts(bp, "\n");
858 }
859 CHECK_GOTO(BN_mod_mul(d, a, b, n, ctx));
860 CHECK_GOTO(BN_sub(d, d, A));
861 if (!BN_is_zero(d)) {
862 fprintf(stderr, "Montgomery multiplication test failed!\n");
863 goto err;
864 }
865 }
866
867 ret = 1;
868 err:
869 BN_CTX_end(ctx);
870 BN_MONT_CTX_free(mont);
871
872 return ret;
873 }
874
875 int
test_mod(BIO * bp,BN_CTX * ctx)876 test_mod(BIO *bp, BN_CTX *ctx)
877 {
878 BIGNUM *a, *b, *c, *d, *e;
879 int i;
880 int ret = 0;
881
882 BN_CTX_start(ctx);
883
884 if ((a = BN_CTX_get(ctx)) == NULL)
885 goto err;
886 if ((b = BN_CTX_get(ctx)) == NULL)
887 goto err;
888 if ((c = BN_CTX_get(ctx)) == NULL)
889 goto err;
890 if ((d = BN_CTX_get(ctx)) == NULL)
891 goto err;
892 if ((e = BN_CTX_get(ctx)) == NULL)
893 goto err;
894
895 CHECK_GOTO(BN_bntest_rand(a, 1024, 0, 0));
896 for (i = 0; i < num0; i++) {
897 CHECK_GOTO(BN_bntest_rand(b, 450 + i * 10, 0, 0));
898 BN_set_negative(a, rand_neg());
899 BN_set_negative(b, rand_neg());
900 CHECK_GOTO(BN_mod(c, a, b, ctx));
901 if (bp != NULL) {
902 if (!results) {
903 CHECK_GOTO(BN_print(bp, a));
904 BIO_puts(bp, " % ");
905 CHECK_GOTO(BN_print(bp, b));
906 BIO_puts(bp, " - ");
907 }
908 CHECK_GOTO(BN_print(bp, c));
909 BIO_puts(bp, "\n");
910 }
911 CHECK_GOTO(BN_div(d, e, a, b, ctx));
912 CHECK_GOTO(BN_sub(e, e, c));
913 if (!BN_is_zero(e)) {
914 fprintf(stderr, "Modulo test failed!\n");
915 goto err;
916 }
917 }
918
919 ret = 1;
920 err:
921 BN_CTX_end(ctx);
922
923 return ret;
924 }
925
926 int
test_mod_mul(BIO * bp,BN_CTX * ctx)927 test_mod_mul(BIO *bp, BN_CTX *ctx)
928 {
929 BIGNUM *a, *b, *c, *d, *e;
930 int i, j;
931 int ret = 0;
932
933 BN_CTX_start(ctx);
934
935 if ((a = BN_CTX_get(ctx)) == NULL)
936 goto err;
937 if ((b = BN_CTX_get(ctx)) == NULL)
938 goto err;
939 if ((c = BN_CTX_get(ctx)) == NULL)
940 goto err;
941 if ((d = BN_CTX_get(ctx)) == NULL)
942 goto err;
943 if ((e = BN_CTX_get(ctx)) == NULL)
944 goto err;
945
946 CHECK_GOTO(BN_one(a));
947 CHECK_GOTO(BN_one(b));
948 BN_zero(c);
949 if (BN_mod_mul(e, a, b, c, ctx)) {
950 fprintf(stderr, "BN_mod_mul with zero modulus succeeded!\n");
951 goto err;
952 }
953 ERR_clear_error();
954
955 for (j = 0; j < 3; j++) {
956 CHECK_GOTO(BN_bntest_rand(c, 1024, 0, 0));
957 for (i = 0; i < num0; i++) {
958 CHECK_GOTO(BN_bntest_rand(a, 475 + i * 10, 0, 0));
959 CHECK_GOTO(BN_bntest_rand(b, 425 + i * 11, 0, 0));
960 BN_set_negative(a, rand_neg());
961 BN_set_negative(b, rand_neg());
962 if (!BN_mod_mul(e, a, b, c, ctx)) {
963 unsigned long l;
964
965 while ((l = ERR_get_error()))
966 fprintf(stderr, "ERROR:%s\n",
967 ERR_error_string(l, NULL));
968 exit(1);
969 }
970 if (bp != NULL) {
971 if (!results) {
972 CHECK_GOTO(BN_print(bp, a));
973 BIO_puts(bp, " * ");
974 CHECK_GOTO(BN_print(bp, b));
975 BIO_puts(bp, " % ");
976 CHECK_GOTO(BN_print(bp, c));
977 if ((BN_is_negative(a) ^ BN_is_negative(b)) &&
978 !BN_is_zero(e)) {
979 /* If (a*b) % c is negative, c must be added
980 * in order to obtain the normalized remainder
981 * (new with OpenSSL 0.9.7, previous versions of
982 * BN_mod_mul could generate negative results)
983 */
984 BIO_puts(bp, " + ");
985 CHECK_GOTO(BN_print(bp, c));
986 }
987 BIO_puts(bp, " - ");
988 }
989 CHECK_GOTO(BN_print(bp, e));
990 BIO_puts(bp, "\n");
991 }
992 CHECK_GOTO(BN_mul(d, a, b, ctx));
993 CHECK_GOTO(BN_sub(d, d, e));
994 CHECK_GOTO(BN_div(a, b, d, c, ctx));
995 if (!BN_is_zero(b)) {
996 fprintf(stderr, "Modulo multiply test failed!\n");
997 ERR_print_errors_fp(stderr);
998 goto err;
999 }
1000 }
1001 }
1002
1003 ret = 1;
1004 err:
1005 BN_CTX_end(ctx);
1006
1007 return ret;
1008 }
1009
1010 int
test_mod_exp(BIO * bp,BN_CTX * ctx)1011 test_mod_exp(BIO *bp, BN_CTX *ctx)
1012 {
1013 BIGNUM *a, *b, *c, *d, *e;
1014 int i;
1015 int ret = 0;
1016
1017 BN_CTX_start(ctx);
1018
1019 if ((a = BN_CTX_get(ctx)) == NULL)
1020 goto err;
1021 if ((b = BN_CTX_get(ctx)) == NULL)
1022 goto err;
1023 if ((c = BN_CTX_get(ctx)) == NULL)
1024 goto err;
1025 if ((d = BN_CTX_get(ctx)) == NULL)
1026 goto err;
1027 if ((e = BN_CTX_get(ctx)) == NULL)
1028 goto err;
1029
1030 CHECK_GOTO(BN_one(a));
1031 CHECK_GOTO(BN_one(b));
1032 BN_zero(c);
1033 if (BN_mod_exp(d, a, b, c, ctx)) {
1034 fprintf(stderr, "BN_mod_exp with zero modulus succeeded!\n");
1035 goto err;
1036 }
1037 ERR_clear_error();
1038 if (BN_mod_exp_ct(d, a, b, c, ctx)) {
1039 fprintf(stderr, "BN_mod_exp_ct with zero modulus succeeded!\n");
1040 goto err;
1041 }
1042 ERR_clear_error();
1043 if (BN_mod_exp_nonct(d, a, b, c, ctx)) {
1044 fprintf(stderr, "BN_mod_exp_nonct with zero modulus succeeded!\n");
1045 goto err;
1046 }
1047 ERR_clear_error();
1048
1049 CHECK_GOTO(BN_bntest_rand(c, 30, 0, 1)); /* must be odd for montgomery */
1050 for (i = 0; i < num2; i++) {
1051 CHECK_GOTO(BN_bntest_rand(a, 20 + i * 5, 0, 0));
1052 CHECK_GOTO(BN_bntest_rand(b, 2 + i, 0, 0));
1053
1054 if (!BN_mod_exp(d, a, b, c, ctx))
1055 goto err;
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 BIO_puts(bp, " - ");
1065 }
1066 CHECK_GOTO(BN_print(bp, d));
1067 BIO_puts(bp, "\n");
1068 }
1069 CHECK_GOTO(BN_exp(e, a, b, ctx));
1070 CHECK_GOTO(BN_sub(e, e, d));
1071 CHECK_GOTO(BN_div(a, b, e, c, ctx));
1072 if (!BN_is_zero(b)) {
1073 fprintf(stderr, "Modulo exponentiation test failed!\n");
1074 goto err;
1075 }
1076 }
1077
1078 CHECK_GOTO(BN_bntest_rand(c, 30, 0, 1)); /* must be odd for montgomery */
1079 for (i = 0; i < num2; i++) {
1080 CHECK_GOTO(BN_bntest_rand(a, 20 + i * 5, 0, 0));
1081 CHECK_GOTO(BN_bntest_rand(b, 2 + i, 0, 0));
1082
1083 if (!BN_mod_exp_ct(d, a, b, c, ctx))
1084 goto err;
1085
1086 if (bp != NULL) {
1087 if (!results) {
1088 CHECK_GOTO(BN_print(bp, a));
1089 BIO_puts(bp, " ^ ");
1090 CHECK_GOTO(BN_print(bp, b));
1091 BIO_puts(bp, " % ");
1092 CHECK_GOTO(BN_print(bp, c));
1093 BIO_puts(bp, " - ");
1094 }
1095 CHECK_GOTO(BN_print(bp, d));
1096 BIO_puts(bp, "\n");
1097 }
1098 CHECK_GOTO(BN_exp(e, a, b, ctx));
1099 CHECK_GOTO(BN_sub(e, e, d));
1100 CHECK_GOTO(BN_div(a, b, e, c, ctx));
1101 if (!BN_is_zero(b)) {
1102 fprintf(stderr, "Modulo exponentiation test failed!\n");
1103 goto err;
1104 }
1105 }
1106
1107 CHECK_GOTO(BN_bntest_rand(c, 30, 0, 1)); /* must be odd for montgomery */
1108 for (i = 0; i < num2; i++) {
1109 CHECK_GOTO(BN_bntest_rand(a, 20 + i * 5, 0, 0));
1110 CHECK_GOTO(BN_bntest_rand(b, 2 + i, 0, 0));
1111
1112 if (!BN_mod_exp_nonct(d, a, b, c, ctx))
1113 goto err;
1114
1115 if (bp != NULL) {
1116 if (!results) {
1117 CHECK_GOTO(BN_print(bp, a));
1118 BIO_puts(bp, " ^ ");
1119 CHECK_GOTO(BN_print(bp, b));
1120 BIO_puts(bp, " % ");
1121 CHECK_GOTO(BN_print(bp, c));
1122 BIO_puts(bp, " - ");
1123 }
1124 CHECK_GOTO(BN_print(bp, d));
1125 BIO_puts(bp, "\n");
1126 }
1127 CHECK_GOTO(BN_exp(e, a, b, ctx));
1128 CHECK_GOTO(BN_sub(e, e, d));
1129 CHECK_GOTO(BN_div(a, b, e, c, ctx));
1130 if (!BN_is_zero(b)) {
1131 fprintf(stderr, "Modulo exponentiation test failed!\n");
1132 goto err;
1133 }
1134 }
1135
1136 ret = 1;
1137 err:
1138 BN_CTX_end(ctx);
1139
1140 return ret;
1141 }
1142
1143 int
test_mod_exp_mont_consttime(BIO * bp,BN_CTX * ctx)1144 test_mod_exp_mont_consttime(BIO *bp, BN_CTX *ctx)
1145 {
1146 BIGNUM *a, *b, *c, *d, *e;
1147 int i;
1148 int ret = 0;
1149
1150 BN_CTX_start(ctx);
1151
1152 if ((a = BN_CTX_get(ctx)) == NULL)
1153 goto err;
1154 if ((b = BN_CTX_get(ctx)) == NULL)
1155 goto err;
1156 if ((c = BN_CTX_get(ctx)) == NULL)
1157 goto err;
1158 if ((d = BN_CTX_get(ctx)) == NULL)
1159 goto err;
1160 if ((e = BN_CTX_get(ctx)) == NULL)
1161 goto err;
1162
1163 CHECK_GOTO(BN_one(a));
1164 CHECK_GOTO(BN_one(b));
1165 BN_zero(c);
1166 if (BN_mod_exp_mont_consttime(d, a, b, c, ctx, NULL)) {
1167 fprintf(stderr, "BN_mod_exp_mont_consttime with zero modulus "
1168 "succeeded\n");
1169 goto err;
1170 }
1171 ERR_clear_error();
1172
1173 CHECK_GOTO(BN_set_word(c, 16));
1174 if (BN_mod_exp_mont_consttime(d, a, b, c, ctx, NULL)) {
1175 fprintf(stderr, "BN_mod_exp_mont_consttime with even modulus "
1176 "succeeded\n");
1177 goto err;
1178 }
1179 ERR_clear_error();
1180
1181 CHECK_GOTO(BN_bntest_rand(c, 30, 0, 1)); /* must be odd for montgomery */
1182 for (i = 0; i < num2; i++) {
1183 CHECK_GOTO(BN_bntest_rand(a, 20 + i * 5, 0, 0));
1184 CHECK_GOTO(BN_bntest_rand(b, 2 + i, 0, 0));
1185
1186 if (!BN_mod_exp_mont_consttime(d, a, b, c, ctx, NULL))
1187 goto err;
1188
1189 if (bp != NULL) {
1190 if (!results) {
1191 CHECK_GOTO(BN_print(bp, a));
1192 BIO_puts(bp, " ^ ");
1193 CHECK_GOTO(BN_print(bp, b));
1194 BIO_puts(bp, " % ");
1195 CHECK_GOTO(BN_print(bp, c));
1196 BIO_puts(bp, " - ");
1197 }
1198 CHECK_GOTO(BN_print(bp, d));
1199 BIO_puts(bp, "\n");
1200 }
1201 CHECK_GOTO(BN_exp(e, a, b, ctx));
1202 CHECK_GOTO(BN_sub(e, e, d));
1203 CHECK_GOTO(BN_div(a, b, e, c, ctx));
1204 if (!BN_is_zero(b)) {
1205 fprintf(stderr, "Modulo exponentiation test failed!\n");
1206 goto err;
1207 }
1208 }
1209
1210 ret = 1;
1211 err:
1212 BN_CTX_end(ctx);
1213
1214 return ret;
1215 }
1216
1217 /*
1218 * Test constant-time modular exponentiation with 1024-bit inputs, which on
1219 * x86_64 cause a different code branch to be taken.
1220 */
1221 int
test_mod_exp_mont5(BIO * bp,BN_CTX * ctx)1222 test_mod_exp_mont5(BIO *bp, BN_CTX *ctx)
1223 {
1224 BIGNUM *a, *p, *m, *d, *e;
1225 BIGNUM *b, *n, *c;
1226 BN_MONT_CTX *mont = NULL;
1227 int len;
1228 int ret = 0;
1229
1230 BN_CTX_start(ctx);
1231
1232 if ((a = BN_CTX_get(ctx)) == NULL)
1233 goto err;
1234 if ((p = BN_CTX_get(ctx)) == NULL)
1235 goto err;
1236 if ((m = BN_CTX_get(ctx)) == NULL)
1237 goto err;
1238 if ((d = BN_CTX_get(ctx)) == NULL)
1239 goto err;
1240 if ((e = BN_CTX_get(ctx)) == NULL)
1241 goto err;
1242 if ((b = BN_CTX_get(ctx)) == NULL)
1243 goto err;
1244 if ((n = BN_CTX_get(ctx)) == NULL)
1245 goto err;
1246 if ((c = BN_CTX_get(ctx)) == NULL)
1247 goto err;
1248
1249 CHECK_GOTO(mont = BN_MONT_CTX_new());
1250
1251 CHECK_GOTO(BN_bntest_rand(m, 1024, 0, 1)); /* must be odd for montgomery */
1252 /* Zero exponent */
1253 CHECK_GOTO(BN_bntest_rand(a, 1024, 0, 0));
1254 BN_zero(p);
1255 if (!BN_mod_exp_mont_consttime(d, a, p, m, ctx, NULL))
1256 goto err;
1257 if (!BN_is_one(d)) {
1258 fprintf(stderr, "Modular exponentiation test failed!\n");
1259 goto err;
1260 }
1261 /* Regression test for carry bug in mulx4x_mont */
1262 len = BN_hex2bn(&a,
1263 "7878787878787878787878787878787878787878787878787878787878787878"
1264 "7878787878787878787878787878787878787878787878787878787878787878"
1265 "7878787878787878787878787878787878787878787878787878787878787878"
1266 "7878787878787878787878787878787878787878787878787878787878787878");
1267 CHECK_GOTO(len);
1268 len = BN_hex2bn(&b,
1269 "095D72C08C097BA488C5E439C655A192EAFB6380073D8C2664668EDDB4060744"
1270 "E16E57FB4EDB9AE10A0CEFCDC28A894F689A128379DB279D48A2E20849D68593"
1271 "9B7803BCF46CEBF5C533FB0DD35B080593DE5472E3FE5DB951B8BFF9B4CB8F03"
1272 "9CC638A5EE8CDD703719F8000E6A9F63BEED5F2FCD52FF293EA05A251BB4AB81");
1273 CHECK_GOTO(len);
1274 len = BN_hex2bn(&n,
1275 "D78AF684E71DB0C39CFF4E64FB9DB567132CB9C50CC98009FEB820B26F2DED9B"
1276 "91B9B5E2B83AE0AE4EB4E0523CA726BFBE969B89FD754F674CE99118C3F2D1C5"
1277 "D81FDC7C54E02B60262B241D53C040E99E45826ECA37A804668E690E1AFC1CA4"
1278 "2C9A15D84D4954425F0B7642FC0BD9D7B24E2618D2DCC9B729D944BADACFDDAF");
1279 CHECK_GOTO(len);
1280 CHECK_GOTO(BN_MONT_CTX_set(mont, n, ctx));
1281 CHECK_GOTO(BN_mod_mul_montgomery(c, a, b, mont, ctx));
1282 CHECK_GOTO(BN_mod_mul_montgomery(d, b, a, mont, ctx));
1283 if (BN_cmp(c, d)) {
1284 fprintf(stderr, "Montgomery multiplication test failed:"
1285 " a*b != b*a.\n");
1286 goto err;
1287 }
1288 /* Regression test for carry bug in sqr[x]8x_mont */
1289 len = BN_hex2bn(&n,
1290 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
1291 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
1292 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
1293 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
1294 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
1295 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
1296 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
1297 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00000000000000FFFFFFFF00"
1298 "0000000000000000000000000000000000000000000000000000000000000000"
1299 "0000000000000000000000000000000000000000000000000000000000000000"
1300 "0000000000000000000000000000000000000000000000000000000000000000"
1301 "0000000000000000000000000000000000000000000000000000000000000000"
1302 "0000000000000000000000000000000000000000000000000000000000000000"
1303 "0000000000000000000000000000000000000000000000000000000000000000"
1304 "0000000000000000000000000000000000000000000000000000000000000000"
1305 "00000000000000000000000000000000000000000000000000FFFFFFFFFFFFFF");
1306 CHECK_GOTO(len);
1307 len = BN_hex2bn(&a,
1308 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
1309 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
1310 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
1311 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
1312 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
1313 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
1314 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
1315 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00000000000000FFFFFFFF0000000000"
1316 "0000000000000000000000000000000000000000000000000000000000000000"
1317 "0000000000000000000000000000000000000000000000000000000000000000"
1318 "0000000000000000000000000000000000000000000000000000000000000000"
1319 "0000000000000000000000000000000000000000000000000000000000000000"
1320 "0000000000000000000000000000000000000000000000000000000000000000"
1321 "0000000000000000000000000000000000000000000000000000000000000000"
1322 "0000000000000000000000000000000000000000000000000000000000000000"
1323 "000000000000000000000000000000000000000000FFFFFFFFFFFFFF00000000");
1324 CHECK_GOTO(len);
1325 CHECK_GOTO(bn_copy(b, a));
1326 CHECK_GOTO(BN_MONT_CTX_set(mont, n, ctx));
1327 CHECK_GOTO(BN_mod_mul_montgomery(c, a, a, mont, ctx));
1328 CHECK_GOTO(BN_mod_mul_montgomery(d, a, b, mont, ctx));
1329 if (BN_cmp(c, d)) {
1330 fprintf(stderr, "Montgomery multiplication test failed:"
1331 " a**2 != a*a.\n");
1332 goto err;
1333 }
1334 /* Zero input */
1335 CHECK_GOTO(BN_bntest_rand(p, 1024, 0, 0));
1336 BN_zero(a);
1337 if (!BN_mod_exp_mont_consttime(d, a, p, m, ctx, NULL))
1338 goto err;
1339 if (!BN_is_zero(d)) {
1340 fprintf(stderr, "Modular exponentiation test failed!\n");
1341 goto err;
1342 }
1343 /*
1344 * Craft an input whose Montgomery representation is 1, i.e., shorter
1345 * than the modulus m, in order to test the const time precomputation
1346 * scattering/gathering.
1347 */
1348 CHECK_GOTO(BN_one(a));
1349 CHECK_GOTO(BN_MONT_CTX_set(mont, m, ctx));
1350 if (!BN_from_montgomery(e, a, mont, ctx))
1351 goto err;
1352 if (!BN_mod_exp_mont_consttime(d, e, p, m, ctx, NULL))
1353 goto err;
1354 if (!BN_mod_exp_simple(a, e, p, m, ctx))
1355 goto err;
1356 if (BN_cmp(a, d) != 0) {
1357 fprintf(stderr, "Modular exponentiation test failed!\n");
1358 goto err;
1359 }
1360 /* Finally, some regular test vectors. */
1361 CHECK_GOTO(BN_bntest_rand(e, 1024, 0, 0));
1362 if (!BN_mod_exp_mont_consttime(d, e, p, m, ctx, NULL))
1363 goto err;
1364 if (!BN_mod_exp_simple(a, e, p, m, ctx))
1365 goto err;
1366 if (BN_cmp(a, d) != 0) {
1367 fprintf(stderr, "Modular exponentiation test failed!\n");
1368 goto err;
1369 }
1370
1371 ret = 1;
1372 err:
1373 BN_CTX_end(ctx);
1374 BN_MONT_CTX_free(mont);
1375
1376 return ret;
1377 }
1378
1379 int
test_exp(BIO * bp,BN_CTX * ctx)1380 test_exp(BIO *bp, BN_CTX *ctx)
1381 {
1382 BIGNUM *a, *b, *d, *e;
1383 int i;
1384 int ret = 0;
1385
1386 BN_CTX_start(ctx);
1387
1388 if ((a = BN_CTX_get(ctx)) == NULL)
1389 goto err;
1390 if ((b = BN_CTX_get(ctx)) == NULL)
1391 goto err;
1392 if ((d = BN_CTX_get(ctx)) == NULL)
1393 goto err;
1394 if ((e = BN_CTX_get(ctx)) == NULL)
1395 goto err;
1396
1397 for (i = 0; i < num2; i++) {
1398 CHECK_GOTO(BN_bntest_rand(a, 20 + i * 5, 0, 0));
1399 CHECK_GOTO(BN_bntest_rand(b, 2 + i, 0, 0));
1400
1401 if (BN_exp(d, a, b, ctx) <= 0)
1402 goto err;
1403
1404 if (bp != NULL) {
1405 if (!results) {
1406 CHECK_GOTO(BN_print(bp, a));
1407 BIO_puts(bp, " ^ ");
1408 CHECK_GOTO(BN_print(bp, b));
1409 BIO_puts(bp, " - ");
1410 }
1411 CHECK_GOTO(BN_print(bp, d));
1412 BIO_puts(bp, "\n");
1413 }
1414 CHECK_GOTO(BN_one(e));
1415 for (; !BN_is_zero(b); BN_sub_word(b, 1))
1416 CHECK_GOTO(BN_mul(e, e, a, ctx));
1417 CHECK_GOTO(BN_sub(e, e, d));
1418 if (!BN_is_zero(e)) {
1419 fprintf(stderr, "Exponentiation test failed!\n");
1420 goto err;
1421 }
1422 }
1423
1424 ret = 1;
1425 err:
1426 BN_CTX_end(ctx);
1427
1428 return ret;
1429 }
1430
1431 static int
genprime_cb(int p,int n,BN_GENCB * arg)1432 genprime_cb(int p, int n, BN_GENCB *arg)
1433 {
1434 char c = '*';
1435
1436 if (p == 0)
1437 c = '.';
1438 if (p == 1)
1439 c = '+';
1440 if (p == 2)
1441 c = '*';
1442 if (p == 3)
1443 c = '\n';
1444 putc(c, stderr);
1445 return 1;
1446 }
1447
1448 int
test_kron(BIO * bp,BN_CTX * ctx)1449 test_kron(BIO *bp, BN_CTX *ctx)
1450 {
1451 BIGNUM *a, *b, *r, *t;
1452 BN_GENCB *cb = NULL;
1453 int i;
1454 int legendre, kronecker;
1455 int ret = 0;
1456
1457 BN_CTX_start(ctx);
1458
1459 if ((a = BN_CTX_get(ctx)) == NULL)
1460 goto err;
1461 if ((b = BN_CTX_get(ctx)) == NULL)
1462 goto err;
1463 if ((r = BN_CTX_get(ctx)) == NULL)
1464 goto err;
1465 if ((t = BN_CTX_get(ctx)) == NULL)
1466 goto err;
1467
1468 if ((cb = BN_GENCB_new()) == NULL)
1469 goto err;
1470
1471 BN_GENCB_set(cb, genprime_cb, NULL);
1472
1473 /*
1474 * We test BN_kronecker(a, b, ctx) just for b odd (Jacobi symbol). In
1475 * this case we know that if b is prime, then BN_kronecker(a, b, ctx) is
1476 * congruent to $a^{(b-1)/2}$, modulo $b$ (Legendre symbol). So we
1477 * generate a random prime b and compare these values for a number of
1478 * random a's. (That is, we run the Solovay-Strassen primality test to
1479 * confirm that b is prime, except that we don't want to test whether b
1480 * is prime but whether BN_kronecker works.)
1481 */
1482
1483 if (!BN_generate_prime_ex(b, 512, 0, NULL, NULL, cb))
1484 goto err;
1485 BN_set_negative(b, rand_neg());
1486 putc('\n', stderr);
1487
1488 for (i = 0; i < num0; i++) {
1489 if (!BN_bntest_rand(a, 512, 0, 0))
1490 goto err;
1491 BN_set_negative(a, rand_neg());
1492
1493 /* t := (|b|-1)/2 (note that b is odd) */
1494 if (!bn_copy(t, b))
1495 goto err;
1496 BN_set_negative(t, 0);
1497 if (!BN_sub_word(t, 1))
1498 goto err;
1499 if (!BN_rshift1(t, t))
1500 goto err;
1501 /* r := a^t mod b */
1502 BN_set_negative(b, 0);
1503
1504 if (!BN_mod_exp_recp(r, a, t, b, ctx))
1505 goto err;
1506 BN_set_negative(b, 1);
1507
1508 if (BN_is_word(r, 1))
1509 legendre = 1;
1510 else if (BN_is_zero(r))
1511 legendre = 0;
1512 else {
1513 if (!BN_add_word(r, 1))
1514 goto err;
1515 if (0 != BN_ucmp(r, b)) {
1516 fprintf(stderr, "Legendre symbol computation failed\n");
1517 goto err;
1518 }
1519 legendre = -1;
1520 }
1521
1522 kronecker = BN_kronecker(a, b, ctx);
1523 if (kronecker < -1)
1524 goto err;
1525 /* we actually need BN_kronecker(a, |b|) */
1526 if (BN_is_negative(a) && BN_is_negative(b))
1527 kronecker = -kronecker;
1528
1529 if (legendre != kronecker) {
1530 fprintf(stderr, "legendre != kronecker; a = ");
1531 CHECK_GOTO(BN_print_fp(stderr, a));
1532 fprintf(stderr, ", b = ");
1533 CHECK_GOTO(BN_print_fp(stderr, b));
1534 fprintf(stderr, "\n");
1535 goto err;
1536 }
1537
1538 putc('.', stderr);
1539 }
1540
1541 putc('\n', stderr);
1542
1543 ret = 1;
1544 err:
1545 BN_GENCB_free(cb);
1546 BN_CTX_end(ctx);
1547
1548 return ret;
1549 }
1550
1551 int
test_sqrt(BIO * bp,BN_CTX * ctx)1552 test_sqrt(BIO *bp, BN_CTX *ctx)
1553 {
1554 BIGNUM *a, *p, *r;
1555 BN_GENCB *cb = NULL;
1556 int i, j;
1557 int ret = 0;
1558
1559 BN_CTX_start(ctx);
1560
1561 if ((a = BN_CTX_get(ctx)) == NULL)
1562 goto err;
1563 if ((p = BN_CTX_get(ctx)) == NULL)
1564 goto err;
1565 if ((r = BN_CTX_get(ctx)) == NULL)
1566 goto err;
1567
1568 if ((cb = BN_GENCB_new()) == NULL)
1569 goto err;
1570
1571 BN_GENCB_set(cb, genprime_cb, NULL);
1572
1573 for (i = 0; i < 16; i++) {
1574 if (i < 8) {
1575 unsigned primes[8] = { 2, 3, 5, 7, 11, 13, 17, 19 };
1576
1577 if (!BN_set_word(p, primes[i]))
1578 goto err;
1579 } else {
1580 if (!BN_set_word(a, 32))
1581 goto err;
1582 if (!BN_set_word(r, 2 * i + 1))
1583 goto err;
1584
1585 if (!BN_generate_prime_ex(p, 256, 0, a, r, cb))
1586 goto err;
1587 putc('\n', stderr);
1588 }
1589 BN_set_negative(p, rand_neg());
1590
1591 for (j = 0; j < num2; j++) {
1592 /*
1593 * construct 'a' such that it is a square modulo p, but in
1594 * general not a proper square and not reduced modulo p
1595 */
1596 if (!BN_bntest_rand(r, 256, 0, 3))
1597 goto err;
1598 if (!BN_nnmod(r, r, p, ctx))
1599 goto err;
1600 if (!BN_mod_sqr(r, r, p, ctx))
1601 goto err;
1602 if (!BN_bntest_rand(a, 256, 0, 3))
1603 goto err;
1604 if (!BN_nnmod(a, a, p, ctx))
1605 goto err;
1606 if (!BN_mod_sqr(a, a, p, ctx))
1607 goto err;
1608 if (!BN_mul(a, a, r, ctx))
1609 goto err;
1610 if (rand_neg())
1611 if (!BN_sub(a, a, p))
1612 goto err;
1613
1614 if (!BN_mod_sqrt(r, a, p, ctx))
1615 goto err;
1616 if (!BN_mod_sqr(r, r, p, ctx))
1617 goto err;
1618
1619 if (!BN_nnmod(a, a, p, ctx))
1620 goto err;
1621
1622 if (BN_cmp(a, r) != 0) {
1623 fprintf(stderr, "BN_mod_sqrt failed: a = ");
1624 CHECK_GOTO(BN_print_fp(stderr, a));
1625 fprintf(stderr, ", r = ");
1626 CHECK_GOTO(BN_print_fp(stderr, r));
1627 fprintf(stderr, ", p = ");
1628 CHECK_GOTO(BN_print_fp(stderr, p));
1629 fprintf(stderr, "\n");
1630 goto err;
1631 }
1632
1633 putc('.', stderr);
1634 }
1635
1636 putc('\n', stderr);
1637 }
1638
1639 ret = 1;
1640 err:
1641 BN_GENCB_free(cb);
1642 BN_CTX_end(ctx);
1643
1644 return ret;
1645 }
1646
1647 int
test_lshift(BIO * bp,BN_CTX * ctx,int use_lst)1648 test_lshift(BIO *bp, BN_CTX *ctx, int use_lst)
1649 {
1650 BIGNUM *a, *b, *c, *d;
1651 int i;
1652 int ret = 0;
1653
1654 BN_CTX_start(ctx);
1655
1656 if ((a = BN_CTX_get(ctx)) == NULL)
1657 goto err;
1658 if ((b = BN_CTX_get(ctx)) == NULL)
1659 goto err;
1660 if ((c = BN_CTX_get(ctx)) == NULL)
1661 goto err;
1662 if ((d = BN_CTX_get(ctx)) == NULL)
1663 goto err;
1664 CHECK_GOTO(BN_one(c));
1665
1666 if (use_lst) {
1667 if (!BN_hex2bn(&a, "C64F43042AEACA6E5836805BE8C99B04"
1668 "5D4836C2FD16C964F0"))
1669 goto err;
1670 } else {
1671 CHECK_GOTO(BN_bntest_rand(a, 200, 0, 0));
1672 BN_set_negative(a, rand_neg());
1673 }
1674 for (i = 0; i < num0; i++) {
1675 CHECK_GOTO(BN_lshift(b, a, i + 1));
1676 CHECK_GOTO(BN_add(c, c, c));
1677 if (bp != NULL) {
1678 if (!results) {
1679 CHECK_GOTO(BN_print(bp, a));
1680 BIO_puts(bp, " * ");
1681 CHECK_GOTO(BN_print(bp, c));
1682 BIO_puts(bp, " - ");
1683 }
1684 CHECK_GOTO(BN_print(bp, b));
1685 BIO_puts(bp, "\n");
1686 }
1687 CHECK_GOTO(BN_mul(d, a, c, ctx));
1688 CHECK_GOTO(BN_sub(d, d, b));
1689 if (!BN_is_zero(d)) {
1690 fprintf(stderr, "Left shift test failed!\n");
1691 fprintf(stderr, "a=");
1692 CHECK_GOTO(BN_print_fp(stderr, a));
1693 fprintf(stderr, "\nb=");
1694 CHECK_GOTO(BN_print_fp(stderr, b));
1695 fprintf(stderr, "\nc=");
1696 CHECK_GOTO(BN_print_fp(stderr, c));
1697 fprintf(stderr, "\nd=");
1698 CHECK_GOTO(BN_print_fp(stderr, d));
1699 fprintf(stderr, "\n");
1700 goto err;
1701 }
1702 }
1703
1704 ret = 1;
1705 err:
1706 BN_CTX_end(ctx);
1707
1708 return ret;
1709 }
1710
1711 int
test_lshift1(BIO * bp,BN_CTX * ctx)1712 test_lshift1(BIO *bp, BN_CTX *ctx)
1713 {
1714 BIGNUM *a, *b, *c;
1715 int i;
1716 int ret = 0;
1717
1718 BN_CTX_start(ctx);
1719
1720 if ((a = BN_CTX_get(ctx)) == NULL)
1721 goto err;
1722 if ((b = BN_CTX_get(ctx)) == NULL)
1723 goto err;
1724 if ((c = BN_CTX_get(ctx)) == NULL)
1725 goto err;
1726
1727 CHECK_GOTO(BN_bntest_rand(a, 200, 0, 0));
1728 BN_set_negative(a, rand_neg());
1729 for (i = 0; i < num0; i++) {
1730 CHECK_GOTO(BN_lshift1(b, a));
1731 if (bp != NULL) {
1732 if (!results) {
1733 CHECK_GOTO(BN_print(bp, a));
1734 BIO_puts(bp, " * 2");
1735 BIO_puts(bp, " - ");
1736 }
1737 CHECK_GOTO(BN_print(bp, b));
1738 BIO_puts(bp, "\n");
1739 }
1740 CHECK_GOTO(BN_add(c, a, a));
1741 CHECK_GOTO(BN_sub(a, b, c));
1742 if (!BN_is_zero(a)) {
1743 fprintf(stderr, "Left shift one test failed!\n");
1744 goto err;
1745 }
1746
1747 CHECK_GOTO(bn_copy(a, b));
1748 }
1749
1750 ret = 1;
1751 err:
1752 BN_CTX_end(ctx);
1753
1754 return ret;
1755 }
1756
1757 int
test_rshift(BIO * bp,BN_CTX * ctx)1758 test_rshift(BIO *bp, BN_CTX *ctx)
1759 {
1760 BIGNUM *a, *b, *c, *d, *e;
1761 int i;
1762 int ret = 0;
1763
1764 BN_CTX_start(ctx);
1765
1766 if ((a = BN_CTX_get(ctx)) == NULL)
1767 goto err;
1768 if ((b = BN_CTX_get(ctx)) == NULL)
1769 goto err;
1770 if ((c = BN_CTX_get(ctx)) == NULL)
1771 goto err;
1772 if ((d = BN_CTX_get(ctx)) == NULL)
1773 goto err;
1774 if ((e = BN_CTX_get(ctx)) == NULL)
1775 goto err;
1776 CHECK_GOTO(BN_one(c));
1777
1778 CHECK_GOTO(BN_bntest_rand(a, 200, 0, 0));
1779 BN_set_negative(a, rand_neg());
1780 for (i = 0; i < num0; i++) {
1781 CHECK_GOTO(BN_rshift(b, a, i + 1));
1782 CHECK_GOTO(BN_add(c, c, c));
1783 if (bp != NULL) {
1784 if (!results) {
1785 CHECK_GOTO(BN_print(bp, a));
1786 BIO_puts(bp, " / ");
1787 CHECK_GOTO(BN_print(bp, c));
1788 BIO_puts(bp, " - ");
1789 }
1790 CHECK_GOTO(BN_print(bp, b));
1791 BIO_puts(bp, "\n");
1792 }
1793 CHECK_GOTO(BN_div(d, e, a, c, ctx));
1794 CHECK_GOTO(BN_sub(d, d, b));
1795 if (!BN_is_zero(d)) {
1796 fprintf(stderr, "Right shift test failed!\n");
1797 goto err;
1798 }
1799 }
1800
1801 ret = 1;
1802 err:
1803 BN_CTX_end(ctx);
1804
1805 return ret;
1806 }
1807
1808 int
test_rshift1(BIO * bp,BN_CTX * ctx)1809 test_rshift1(BIO *bp, BN_CTX *ctx)
1810 {
1811 BIGNUM *a, *b, *c;
1812 int i;
1813 int ret = 0;
1814
1815 BN_CTX_start(ctx);
1816
1817 if ((a = BN_CTX_get(ctx)) == NULL)
1818 goto err;
1819 if ((b = BN_CTX_get(ctx)) == NULL)
1820 goto err;
1821 if ((c = BN_CTX_get(ctx)) == NULL)
1822 goto err;
1823
1824 CHECK_GOTO(BN_bntest_rand(a, 200, 0, 0));
1825 BN_set_negative(a, rand_neg());
1826 for (i = 0; i < num0; i++) {
1827 CHECK_GOTO(BN_rshift1(b, a));
1828 if (bp != NULL) {
1829 if (!results) {
1830 CHECK_GOTO(BN_print(bp, a));
1831 BIO_puts(bp, " / 2");
1832 BIO_puts(bp, " - ");
1833 }
1834 CHECK_GOTO(BN_print(bp, b));
1835 BIO_puts(bp, "\n");
1836 }
1837 CHECK_GOTO(BN_sub(c, a, b));
1838 CHECK_GOTO(BN_sub(c, c, b));
1839 if (!BN_is_zero(c) && !BN_abs_is_word(c, 1)) {
1840 fprintf(stderr, "Right shift one test failed!\n");
1841 goto err;
1842 }
1843 CHECK_GOTO(bn_copy(a, b));
1844 }
1845
1846 ret = 1;
1847 err:
1848 BN_CTX_end(ctx);
1849
1850 return ret;
1851 }
1852
1853 int
rand_neg(void)1854 rand_neg(void)
1855 {
1856 static unsigned int neg = 0;
1857 static int sign[8] = { 0, 0, 0, 1, 1, 0, 1, 1 };
1858
1859 return sign[neg++ % 8];
1860 }
1861
1862 int
test_mod_exp_sizes(BIO * bp,BN_CTX * ctx)1863 test_mod_exp_sizes(BIO *bp, BN_CTX *ctx)
1864 {
1865 BN_MONT_CTX *mont_ctx = NULL;
1866 BIGNUM *p, *x, *y, *r, *r2;
1867 int size;
1868 int ret = 0;
1869
1870 BN_CTX_start(ctx);
1871 CHECK_GOTO(p = BN_CTX_get(ctx));
1872 CHECK_GOTO(x = BN_CTX_get(ctx));
1873 CHECK_GOTO(y = BN_CTX_get(ctx));
1874 CHECK_GOTO(r = BN_CTX_get(ctx));
1875 CHECK_GOTO(r2 = BN_CTX_get(ctx));
1876 mont_ctx = BN_MONT_CTX_new();
1877
1878 if (r2 == NULL || mont_ctx == NULL)
1879 goto err;
1880
1881 if (!BN_generate_prime_ex(p, 32, 0, NULL, NULL, NULL) ||
1882 !BN_MONT_CTX_set(mont_ctx, p, ctx))
1883 goto err;
1884
1885 for (size = 32; size < 1024; size += 8) {
1886 if (!BN_rand(x, size, -1, 0) ||
1887 !BN_rand(y, size, -1, 0) ||
1888 !BN_mod_exp_mont_consttime(r, x, y, p, ctx, mont_ctx) ||
1889 !BN_mod_exp(r2, x, y, p, ctx))
1890 goto err;
1891
1892 if (BN_cmp(r, r2) != 0) {
1893 char *r_str = NULL;
1894 char *r2_str = NULL;
1895 CHECK_GOTO(r_str = BN_bn2hex(r));
1896 CHECK_GOTO(r2_str = BN_bn2hex(r2));
1897
1898 printf("Incorrect answer at size %d: %s vs %s\n",
1899 size, r_str, r2_str);
1900 free(r_str);
1901 free(r2_str);
1902 goto err;
1903 }
1904 }
1905
1906 ret = 1;
1907 err:
1908 BN_CTX_end(ctx);
1909 BN_MONT_CTX_free(mont_ctx);
1910
1911 return ret;
1912 }
1913