1 /* $OpenBSD: bn_test.c,v 1.19 2023/04/25 17:17:21 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_recp");
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 if ((recp = BN_RECP_CTX_new()) == NULL)
585 goto err;
586
587 for (i = 0; i < num0 + num1; i++) {
588 if (i < num1) {
589 CHECK_GOTO(BN_bntest_rand(a, 400, 0, 0));
590 CHECK_GOTO(bn_copy(b, a));
591 CHECK_GOTO(BN_lshift(a, a, i));
592 CHECK_GOTO(BN_add_word(a, i));
593 } else
594 CHECK_GOTO(BN_bntest_rand(b, 50 + 3 * (i - num1), 0, 0));
595 BN_set_negative(a, rand_neg());
596 BN_set_negative(b, rand_neg());
597 CHECK_GOTO(BN_RECP_CTX_set(recp, b, ctx));
598 CHECK_GOTO(BN_div_recp(d, c, a, recp, ctx));
599 if (bp != NULL) {
600 if (!results) {
601 CHECK_GOTO(BN_print(bp, a));
602 BIO_puts(bp, " / ");
603 CHECK_GOTO(BN_print(bp, b));
604 BIO_puts(bp, " - ");
605 }
606 CHECK_GOTO(BN_print(bp, d));
607 BIO_puts(bp, "\n");
608
609 if (!results) {
610 CHECK_GOTO(BN_print(bp, a));
611 BIO_puts(bp, " % ");
612 CHECK_GOTO(BN_print(bp, b));
613 BIO_puts(bp, " - ");
614 }
615 CHECK_GOTO(BN_print(bp, c));
616 BIO_puts(bp, "\n");
617 }
618 CHECK_GOTO(BN_mul(e, d, b, ctx));
619 CHECK_GOTO(BN_add(d, e, c));
620 CHECK_GOTO(BN_sub(d, d, a));
621 if (!BN_is_zero(d)) {
622 fprintf(stderr, "Reciprocal division test failed!\n");
623 fprintf(stderr, "a=");
624 CHECK_GOTO(BN_print_fp(stderr, a));
625 fprintf(stderr, "\nb=");
626 CHECK_GOTO(BN_print_fp(stderr, b));
627 fprintf(stderr, "\n");
628 goto err;
629 }
630 }
631
632 ret = 1;
633 err:
634 BN_CTX_end(ctx);
635 BN_RECP_CTX_free(recp);
636
637 return ret;
638 }
639
640 int
test_mul(BIO * bp,BN_CTX * ctx)641 test_mul(BIO *bp, BN_CTX *ctx)
642 {
643 BIGNUM *a, *b, *c, *d, *e;
644 int i;
645 int ret = 0;
646
647 BN_CTX_start(ctx);
648
649 if ((a = BN_CTX_get(ctx)) == NULL)
650 goto err;
651 if ((b = BN_CTX_get(ctx)) == NULL)
652 goto err;
653 if ((c = BN_CTX_get(ctx)) == NULL)
654 goto err;
655 if ((d = BN_CTX_get(ctx)) == NULL)
656 goto err;
657 if ((e = BN_CTX_get(ctx)) == NULL)
658 goto err;
659
660 for (i = 0; i < num0 + num1; i++) {
661 if (i <= num1) {
662 CHECK_GOTO(BN_bntest_rand(a, 100, 0, 0));
663 CHECK_GOTO(BN_bntest_rand(b, 100, 0, 0));
664 } else
665 CHECK_GOTO(BN_bntest_rand(b, i - num1, 0, 0));
666 BN_set_negative(a, rand_neg());
667 BN_set_negative(b, rand_neg());
668 CHECK_GOTO(BN_mul(c, a, b, ctx));
669 if (bp != NULL) {
670 if (!results) {
671 CHECK_GOTO(BN_print(bp, a));
672 BIO_puts(bp, " * ");
673 CHECK_GOTO(BN_print(bp, b));
674 BIO_puts(bp, " - ");
675 }
676 CHECK_GOTO(BN_print(bp, c));
677 BIO_puts(bp, "\n");
678 }
679 CHECK_GOTO(BN_div(d, e, c, a, ctx));
680 CHECK_GOTO(BN_sub(d, d, b));
681 if (!BN_is_zero(d) || !BN_is_zero(e)) {
682 fprintf(stderr, "Multiplication test failed!\n");
683 goto err;
684 }
685 }
686
687 ret = 1;
688 err:
689 BN_CTX_end(ctx);
690
691 return ret;
692 }
693
694 int
test_sqr(BIO * bp,BN_CTX * ctx)695 test_sqr(BIO *bp, BN_CTX *ctx)
696 {
697 BIGNUM *a, *c, *d, *e;
698 int i;
699 int ret = 0;
700
701 BN_CTX_start(ctx);
702
703 if ((a = BN_CTX_get(ctx)) == NULL)
704 goto err;
705 if ((c = BN_CTX_get(ctx)) == NULL)
706 goto err;
707 if ((d = BN_CTX_get(ctx)) == NULL)
708 goto err;
709 if ((e = BN_CTX_get(ctx)) == NULL)
710 goto err;
711
712 for (i = 0; i < num0; i++) {
713 CHECK_GOTO(BN_bntest_rand(a, 40 + i * 10, 0, 0));
714 BN_set_negative(a, rand_neg());
715 CHECK_GOTO(BN_sqr(c, a, ctx));
716 if (bp != NULL) {
717 if (!results) {
718 CHECK_GOTO(BN_print(bp, a));
719 BIO_puts(bp, " * ");
720 CHECK_GOTO(BN_print(bp, a));
721 BIO_puts(bp, " - ");
722 }
723 CHECK_GOTO(BN_print(bp, c));
724 BIO_puts(bp, "\n");
725 }
726 CHECK_GOTO(BN_div(d, e, c, a, ctx));
727 CHECK_GOTO(BN_sub(d, d, a));
728 if (!BN_is_zero(d) || !BN_is_zero(e)) {
729 fprintf(stderr, "Square test failed!\n");
730 goto err;
731 }
732 }
733
734 /* Regression test for a BN_sqr overflow bug. */
735 if (!BN_hex2bn(&a, "80000000000000008000000000000001"
736 "FFFFFFFFFFFFFFFE0000000000000000")) {
737 fprintf(stderr, "BN_hex2bn failed\n");
738 goto err;
739 }
740 CHECK_GOTO(BN_sqr(c, a, ctx));
741 if (bp != NULL) {
742 if (!results) {
743 CHECK_GOTO(BN_print(bp, a));
744 BIO_puts(bp, " * ");
745 CHECK_GOTO(BN_print(bp, a));
746 BIO_puts(bp, " - ");
747 }
748 CHECK_GOTO(BN_print(bp, c));
749 BIO_puts(bp, "\n");
750 }
751 CHECK_GOTO(BN_mul(d, a, a, ctx));
752 if (BN_cmp(c, d)) {
753 fprintf(stderr,
754 "Square test failed: BN_sqr and BN_mul produce "
755 "different results!\n");
756 goto err;
757 }
758
759 /* Regression test for a BN_sqr overflow bug. */
760 if (!BN_hex2bn(&a, "80000000000000000000000080000001"
761 "FFFFFFFE000000000000000000000000")) {
762 fprintf(stderr, "BN_hex2bn failed\n");
763 goto err;
764 }
765 CHECK_GOTO(BN_sqr(c, a, ctx));
766 if (bp != NULL) {
767 if (!results) {
768 CHECK_GOTO(BN_print(bp, a));
769 BIO_puts(bp, " * ");
770 CHECK_GOTO(BN_print(bp, a));
771 BIO_puts(bp, " - ");
772 }
773 CHECK_GOTO(BN_print(bp, c));
774 BIO_puts(bp, "\n");
775 }
776 CHECK_GOTO(BN_mul(d, a, a, ctx));
777 if (BN_cmp(c, d)) {
778 fprintf(stderr, "Square test failed: BN_sqr and BN_mul produce "
779 "different results!\n");
780 goto err;
781 }
782
783 ret = 1;
784 err:
785 BN_CTX_end(ctx);
786
787 return ret;
788 }
789
790 int
test_mont(BIO * bp,BN_CTX * ctx)791 test_mont(BIO *bp, BN_CTX *ctx)
792 {
793 BN_MONT_CTX *mont = NULL;
794 BIGNUM *a, *b, *c, *d, *A, *B, *n;
795 int i;
796 int ret = 0;
797
798 BN_CTX_start(ctx);
799
800 if ((a = BN_CTX_get(ctx)) == NULL)
801 goto err;
802 if ((b = BN_CTX_get(ctx)) == NULL)
803 goto err;
804 if ((c = BN_CTX_get(ctx)) == NULL)
805 goto err;
806 if ((d = BN_CTX_get(ctx)) == NULL)
807 goto err;
808 if ((A = BN_CTX_get(ctx)) == NULL)
809 goto err;
810 if ((B = BN_CTX_get(ctx)) == NULL)
811 goto err;
812 if ((n = BN_CTX_get(ctx)) == NULL)
813 goto err;
814
815 if ((mont = BN_MONT_CTX_new()) == NULL)
816 goto err;
817
818 BN_zero(n);
819 if (BN_MONT_CTX_set(mont, n, ctx)) {
820 fprintf(stderr, "BN_MONT_CTX_set succeeded for zero modulus!\n");
821 goto err;
822 }
823 ERR_clear_error();
824
825 CHECK_GOTO(BN_set_word(n, 16));
826 if (BN_MONT_CTX_set(mont, n, ctx)) {
827 fprintf(stderr, "BN_MONT_CTX_set succeeded for even modulus!\n");
828 goto err;
829 }
830 ERR_clear_error();
831
832 CHECK_GOTO(BN_bntest_rand(a, 100, 0, 0));
833 CHECK_GOTO(BN_bntest_rand(b, 100, 0, 0));
834 for (i = 0; i < num2; i++) {
835 int bits = (200 * (i + 1)) / num2;
836
837 if (bits == 0)
838 continue;
839 CHECK_GOTO(BN_bntest_rand(n, bits, 0, 1));
840 CHECK_GOTO(BN_MONT_CTX_set(mont, n, ctx));
841
842 CHECK_GOTO(BN_nnmod(a, a, n, ctx));
843 CHECK_GOTO(BN_nnmod(b, b, n, ctx));
844
845 CHECK_GOTO(BN_to_montgomery(A, a, mont, ctx));
846 CHECK_GOTO(BN_to_montgomery(B, b, mont, ctx));
847
848 CHECK_GOTO(BN_mod_mul_montgomery(c, A, B, mont, ctx));
849 CHECK_GOTO(BN_from_montgomery(A, c, mont, ctx));
850 if (bp != NULL) {
851 if (!results) {
852 CHECK_GOTO(BN_print(bp, a));
853 BIO_puts(bp, " * ");
854 CHECK_GOTO(BN_print(bp, b));
855 BIO_puts(bp, " % ");
856 /* n == &mont->N */
857 CHECK_GOTO(BN_print(bp, n));
858 BIO_puts(bp, " - ");
859 }
860 CHECK_GOTO(BN_print(bp, A));
861 BIO_puts(bp, "\n");
862 }
863 CHECK_GOTO(BN_mod_mul(d, a, b, n, ctx));
864 CHECK_GOTO(BN_sub(d, d, A));
865 if (!BN_is_zero(d)) {
866 fprintf(stderr, "Montgomery multiplication test failed!\n");
867 goto err;
868 }
869 }
870
871 ret = 1;
872 err:
873 BN_CTX_end(ctx);
874 BN_MONT_CTX_free(mont);
875
876 return ret;
877 }
878
879 int
test_mod(BIO * bp,BN_CTX * ctx)880 test_mod(BIO *bp, BN_CTX *ctx)
881 {
882 BIGNUM *a, *b, *c, *d, *e;
883 int i;
884 int ret = 0;
885
886 BN_CTX_start(ctx);
887
888 if ((a = BN_CTX_get(ctx)) == NULL)
889 goto err;
890 if ((b = BN_CTX_get(ctx)) == NULL)
891 goto err;
892 if ((c = BN_CTX_get(ctx)) == NULL)
893 goto err;
894 if ((d = BN_CTX_get(ctx)) == NULL)
895 goto err;
896 if ((e = BN_CTX_get(ctx)) == NULL)
897 goto err;
898
899 CHECK_GOTO(BN_bntest_rand(a, 1024, 0, 0));
900 for (i = 0; i < num0; i++) {
901 CHECK_GOTO(BN_bntest_rand(b, 450 + i * 10, 0, 0));
902 BN_set_negative(a, rand_neg());
903 BN_set_negative(b, rand_neg());
904 CHECK_GOTO(BN_mod(c, a, b, ctx));
905 if (bp != NULL) {
906 if (!results) {
907 CHECK_GOTO(BN_print(bp, a));
908 BIO_puts(bp, " % ");
909 CHECK_GOTO(BN_print(bp, b));
910 BIO_puts(bp, " - ");
911 }
912 CHECK_GOTO(BN_print(bp, c));
913 BIO_puts(bp, "\n");
914 }
915 CHECK_GOTO(BN_div(d, e, a, b, ctx));
916 CHECK_GOTO(BN_sub(e, e, c));
917 if (!BN_is_zero(e)) {
918 fprintf(stderr, "Modulo test failed!\n");
919 goto err;
920 }
921 }
922
923 ret = 1;
924 err:
925 BN_CTX_end(ctx);
926
927 return ret;
928 }
929
930 int
test_mod_mul(BIO * bp,BN_CTX * ctx)931 test_mod_mul(BIO *bp, BN_CTX *ctx)
932 {
933 BIGNUM *a, *b, *c, *d, *e;
934 int i, j;
935 int ret = 0;
936
937 BN_CTX_start(ctx);
938
939 if ((a = BN_CTX_get(ctx)) == NULL)
940 goto err;
941 if ((b = BN_CTX_get(ctx)) == NULL)
942 goto err;
943 if ((c = BN_CTX_get(ctx)) == NULL)
944 goto err;
945 if ((d = BN_CTX_get(ctx)) == NULL)
946 goto err;
947 if ((e = BN_CTX_get(ctx)) == NULL)
948 goto err;
949
950 CHECK_GOTO(BN_one(a));
951 CHECK_GOTO(BN_one(b));
952 BN_zero(c);
953 if (BN_mod_mul(e, a, b, c, ctx)) {
954 fprintf(stderr, "BN_mod_mul with zero modulus succeeded!\n");
955 goto err;
956 }
957 ERR_clear_error();
958
959 for (j = 0; j < 3; j++) {
960 CHECK_GOTO(BN_bntest_rand(c, 1024, 0, 0));
961 for (i = 0; i < num0; i++) {
962 CHECK_GOTO(BN_bntest_rand(a, 475 + i * 10, 0, 0));
963 CHECK_GOTO(BN_bntest_rand(b, 425 + i * 11, 0, 0));
964 BN_set_negative(a, rand_neg());
965 BN_set_negative(b, rand_neg());
966 if (!BN_mod_mul(e, a, b, c, ctx)) {
967 unsigned long l;
968
969 while ((l = ERR_get_error()))
970 fprintf(stderr, "ERROR:%s\n",
971 ERR_error_string(l, NULL));
972 exit(1);
973 }
974 if (bp != NULL) {
975 if (!results) {
976 CHECK_GOTO(BN_print(bp, a));
977 BIO_puts(bp, " * ");
978 CHECK_GOTO(BN_print(bp, b));
979 BIO_puts(bp, " % ");
980 CHECK_GOTO(BN_print(bp, c));
981 if ((BN_is_negative(a) ^ BN_is_negative(b)) &&
982 !BN_is_zero(e)) {
983 /* If (a*b) % c is negative, c must be added
984 * in order to obtain the normalized remainder
985 * (new with OpenSSL 0.9.7, previous versions of
986 * BN_mod_mul could generate negative results)
987 */
988 BIO_puts(bp, " + ");
989 CHECK_GOTO(BN_print(bp, c));
990 }
991 BIO_puts(bp, " - ");
992 }
993 CHECK_GOTO(BN_print(bp, e));
994 BIO_puts(bp, "\n");
995 }
996 CHECK_GOTO(BN_mul(d, a, b, ctx));
997 CHECK_GOTO(BN_sub(d, d, e));
998 CHECK_GOTO(BN_div(a, b, d, c, ctx));
999 if (!BN_is_zero(b)) {
1000 fprintf(stderr, "Modulo multiply test failed!\n");
1001 ERR_print_errors_fp(stderr);
1002 goto err;
1003 }
1004 }
1005 }
1006
1007 ret = 1;
1008 err:
1009 BN_CTX_end(ctx);
1010
1011 return ret;
1012 }
1013
1014 int
test_mod_exp(BIO * bp,BN_CTX * ctx)1015 test_mod_exp(BIO *bp, BN_CTX *ctx)
1016 {
1017 BIGNUM *a, *b, *c, *d, *e;
1018 int i;
1019 int ret = 0;
1020
1021 BN_CTX_start(ctx);
1022
1023 if ((a = BN_CTX_get(ctx)) == NULL)
1024 goto err;
1025 if ((b = BN_CTX_get(ctx)) == NULL)
1026 goto err;
1027 if ((c = BN_CTX_get(ctx)) == NULL)
1028 goto err;
1029 if ((d = BN_CTX_get(ctx)) == NULL)
1030 goto err;
1031 if ((e = BN_CTX_get(ctx)) == NULL)
1032 goto err;
1033
1034 CHECK_GOTO(BN_one(a));
1035 CHECK_GOTO(BN_one(b));
1036 BN_zero(c);
1037 if (BN_mod_exp(d, a, b, c, ctx)) {
1038 fprintf(stderr, "BN_mod_exp with zero modulus succeeded!\n");
1039 goto err;
1040 }
1041 ERR_clear_error();
1042 if (BN_mod_exp_ct(d, a, b, c, ctx)) {
1043 fprintf(stderr, "BN_mod_exp_ct with zero modulus succeeded!\n");
1044 goto err;
1045 }
1046 ERR_clear_error();
1047 if (BN_mod_exp_nonct(d, a, b, c, ctx)) {
1048 fprintf(stderr, "BN_mod_exp_nonct with zero modulus succeeded!\n");
1049 goto err;
1050 }
1051 ERR_clear_error();
1052
1053 CHECK_GOTO(BN_bntest_rand(c, 30, 0, 1)); /* must be odd for montgomery */
1054 for (i = 0; i < num2; i++) {
1055 CHECK_GOTO(BN_bntest_rand(a, 20 + i * 5, 0, 0));
1056 CHECK_GOTO(BN_bntest_rand(b, 2 + i, 0, 0));
1057
1058 if (!BN_mod_exp(d, a, b, c, ctx))
1059 goto err;
1060
1061 if (bp != NULL) {
1062 if (!results) {
1063 CHECK_GOTO(BN_print(bp, a));
1064 BIO_puts(bp, " ^ ");
1065 CHECK_GOTO(BN_print(bp, b));
1066 BIO_puts(bp, " % ");
1067 CHECK_GOTO(BN_print(bp, c));
1068 BIO_puts(bp, " - ");
1069 }
1070 CHECK_GOTO(BN_print(bp, d));
1071 BIO_puts(bp, "\n");
1072 }
1073 CHECK_GOTO(BN_exp(e, a, b, ctx));
1074 CHECK_GOTO(BN_sub(e, e, d));
1075 CHECK_GOTO(BN_div(a, b, e, c, ctx));
1076 if (!BN_is_zero(b)) {
1077 fprintf(stderr, "Modulo exponentiation test failed!\n");
1078 goto err;
1079 }
1080 }
1081
1082 CHECK_GOTO(BN_bntest_rand(c, 30, 0, 1)); /* must be odd for montgomery */
1083 for (i = 0; i < num2; i++) {
1084 CHECK_GOTO(BN_bntest_rand(a, 20 + i * 5, 0, 0));
1085 CHECK_GOTO(BN_bntest_rand(b, 2 + i, 0, 0));
1086
1087 if (!BN_mod_exp_ct(d, a, b, c, ctx))
1088 goto err;
1089
1090 if (bp != NULL) {
1091 if (!results) {
1092 CHECK_GOTO(BN_print(bp, a));
1093 BIO_puts(bp, " ^ ");
1094 CHECK_GOTO(BN_print(bp, b));
1095 BIO_puts(bp, " % ");
1096 CHECK_GOTO(BN_print(bp, c));
1097 BIO_puts(bp, " - ");
1098 }
1099 CHECK_GOTO(BN_print(bp, d));
1100 BIO_puts(bp, "\n");
1101 }
1102 CHECK_GOTO(BN_exp(e, a, b, ctx));
1103 CHECK_GOTO(BN_sub(e, e, d));
1104 CHECK_GOTO(BN_div(a, b, e, c, ctx));
1105 if (!BN_is_zero(b)) {
1106 fprintf(stderr, "Modulo exponentiation test failed!\n");
1107 goto err;
1108 }
1109 }
1110
1111 CHECK_GOTO(BN_bntest_rand(c, 30, 0, 1)); /* must be odd for montgomery */
1112 for (i = 0; i < num2; i++) {
1113 CHECK_GOTO(BN_bntest_rand(a, 20 + i * 5, 0, 0));
1114 CHECK_GOTO(BN_bntest_rand(b, 2 + i, 0, 0));
1115
1116 if (!BN_mod_exp_nonct(d, a, b, c, ctx))
1117 goto err;
1118
1119 if (bp != NULL) {
1120 if (!results) {
1121 CHECK_GOTO(BN_print(bp, a));
1122 BIO_puts(bp, " ^ ");
1123 CHECK_GOTO(BN_print(bp, b));
1124 BIO_puts(bp, " % ");
1125 CHECK_GOTO(BN_print(bp, c));
1126 BIO_puts(bp, " - ");
1127 }
1128 CHECK_GOTO(BN_print(bp, d));
1129 BIO_puts(bp, "\n");
1130 }
1131 CHECK_GOTO(BN_exp(e, a, b, ctx));
1132 CHECK_GOTO(BN_sub(e, e, d));
1133 CHECK_GOTO(BN_div(a, b, e, c, ctx));
1134 if (!BN_is_zero(b)) {
1135 fprintf(stderr, "Modulo exponentiation test failed!\n");
1136 goto err;
1137 }
1138 }
1139
1140 ret = 1;
1141 err:
1142 BN_CTX_end(ctx);
1143
1144 return ret;
1145 }
1146
1147 int
test_mod_exp_mont_consttime(BIO * bp,BN_CTX * ctx)1148 test_mod_exp_mont_consttime(BIO *bp, BN_CTX *ctx)
1149 {
1150 BIGNUM *a, *b, *c, *d, *e;
1151 int i;
1152 int ret = 0;
1153
1154 BN_CTX_start(ctx);
1155
1156 if ((a = BN_CTX_get(ctx)) == NULL)
1157 goto err;
1158 if ((b = BN_CTX_get(ctx)) == NULL)
1159 goto err;
1160 if ((c = BN_CTX_get(ctx)) == NULL)
1161 goto err;
1162 if ((d = BN_CTX_get(ctx)) == NULL)
1163 goto err;
1164 if ((e = BN_CTX_get(ctx)) == NULL)
1165 goto err;
1166
1167 CHECK_GOTO(BN_one(a));
1168 CHECK_GOTO(BN_one(b));
1169 BN_zero(c);
1170 if (BN_mod_exp_mont_consttime(d, a, b, c, ctx, NULL)) {
1171 fprintf(stderr, "BN_mod_exp_mont_consttime with zero modulus "
1172 "succeeded\n");
1173 goto err;
1174 }
1175 ERR_clear_error();
1176
1177 CHECK_GOTO(BN_set_word(c, 16));
1178 if (BN_mod_exp_mont_consttime(d, a, b, c, ctx, NULL)) {
1179 fprintf(stderr, "BN_mod_exp_mont_consttime with even modulus "
1180 "succeeded\n");
1181 goto err;
1182 }
1183 ERR_clear_error();
1184
1185 CHECK_GOTO(BN_bntest_rand(c, 30, 0, 1)); /* must be odd for montgomery */
1186 for (i = 0; i < num2; i++) {
1187 CHECK_GOTO(BN_bntest_rand(a, 20 + i * 5, 0, 0));
1188 CHECK_GOTO(BN_bntest_rand(b, 2 + i, 0, 0));
1189
1190 if (!BN_mod_exp_mont_consttime(d, a, b, c, ctx, NULL))
1191 goto err;
1192
1193 if (bp != NULL) {
1194 if (!results) {
1195 CHECK_GOTO(BN_print(bp, a));
1196 BIO_puts(bp, " ^ ");
1197 CHECK_GOTO(BN_print(bp, b));
1198 BIO_puts(bp, " % ");
1199 CHECK_GOTO(BN_print(bp, c));
1200 BIO_puts(bp, " - ");
1201 }
1202 CHECK_GOTO(BN_print(bp, d));
1203 BIO_puts(bp, "\n");
1204 }
1205 CHECK_GOTO(BN_exp(e, a, b, ctx));
1206 CHECK_GOTO(BN_sub(e, e, d));
1207 CHECK_GOTO(BN_div(a, b, e, c, ctx));
1208 if (!BN_is_zero(b)) {
1209 fprintf(stderr, "Modulo exponentiation test failed!\n");
1210 goto err;
1211 }
1212 }
1213
1214 ret = 1;
1215 err:
1216 BN_CTX_end(ctx);
1217
1218 return ret;
1219 }
1220
1221 /*
1222 * Test constant-time modular exponentiation with 1024-bit inputs, which on
1223 * x86_64 cause a different code branch to be taken.
1224 */
1225 int
test_mod_exp_mont5(BIO * bp,BN_CTX * ctx)1226 test_mod_exp_mont5(BIO *bp, BN_CTX *ctx)
1227 {
1228 BIGNUM *a, *p, *m, *d, *e;
1229 BIGNUM *b, *n, *c;
1230 BN_MONT_CTX *mont = NULL;
1231 int len;
1232 int ret = 0;
1233
1234 BN_CTX_start(ctx);
1235
1236 if ((a = BN_CTX_get(ctx)) == NULL)
1237 goto err;
1238 if ((p = BN_CTX_get(ctx)) == NULL)
1239 goto err;
1240 if ((m = BN_CTX_get(ctx)) == NULL)
1241 goto err;
1242 if ((d = BN_CTX_get(ctx)) == NULL)
1243 goto err;
1244 if ((e = BN_CTX_get(ctx)) == NULL)
1245 goto err;
1246 if ((b = BN_CTX_get(ctx)) == NULL)
1247 goto err;
1248 if ((n = BN_CTX_get(ctx)) == NULL)
1249 goto err;
1250 if ((c = BN_CTX_get(ctx)) == NULL)
1251 goto err;
1252
1253 CHECK_GOTO(mont = BN_MONT_CTX_new());
1254
1255 CHECK_GOTO(BN_bntest_rand(m, 1024, 0, 1)); /* must be odd for montgomery */
1256 /* Zero exponent */
1257 CHECK_GOTO(BN_bntest_rand(a, 1024, 0, 0));
1258 BN_zero(p);
1259 if (!BN_mod_exp_mont_consttime(d, a, p, m, ctx, NULL))
1260 goto err;
1261 if (!BN_is_one(d)) {
1262 fprintf(stderr, "Modular exponentiation test failed!\n");
1263 goto err;
1264 }
1265 /* Regression test for carry bug in mulx4x_mont */
1266 len = BN_hex2bn(&a,
1267 "7878787878787878787878787878787878787878787878787878787878787878"
1268 "7878787878787878787878787878787878787878787878787878787878787878"
1269 "7878787878787878787878787878787878787878787878787878787878787878"
1270 "7878787878787878787878787878787878787878787878787878787878787878");
1271 CHECK_GOTO(len);
1272 len = BN_hex2bn(&b,
1273 "095D72C08C097BA488C5E439C655A192EAFB6380073D8C2664668EDDB4060744"
1274 "E16E57FB4EDB9AE10A0CEFCDC28A894F689A128379DB279D48A2E20849D68593"
1275 "9B7803BCF46CEBF5C533FB0DD35B080593DE5472E3FE5DB951B8BFF9B4CB8F03"
1276 "9CC638A5EE8CDD703719F8000E6A9F63BEED5F2FCD52FF293EA05A251BB4AB81");
1277 CHECK_GOTO(len);
1278 len = BN_hex2bn(&n,
1279 "D78AF684E71DB0C39CFF4E64FB9DB567132CB9C50CC98009FEB820B26F2DED9B"
1280 "91B9B5E2B83AE0AE4EB4E0523CA726BFBE969B89FD754F674CE99118C3F2D1C5"
1281 "D81FDC7C54E02B60262B241D53C040E99E45826ECA37A804668E690E1AFC1CA4"
1282 "2C9A15D84D4954425F0B7642FC0BD9D7B24E2618D2DCC9B729D944BADACFDDAF");
1283 CHECK_GOTO(len);
1284 CHECK_GOTO(BN_MONT_CTX_set(mont, n, ctx));
1285 CHECK_GOTO(BN_mod_mul_montgomery(c, a, b, mont, ctx));
1286 CHECK_GOTO(BN_mod_mul_montgomery(d, b, a, mont, ctx));
1287 if (BN_cmp(c, d)) {
1288 fprintf(stderr, "Montgomery multiplication test failed:"
1289 " a*b != b*a.\n");
1290 goto err;
1291 }
1292 /* Regression test for carry bug in sqr[x]8x_mont */
1293 len = BN_hex2bn(&n,
1294 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
1295 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
1296 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
1297 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
1298 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
1299 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
1300 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
1301 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00000000000000FFFFFFFF00"
1302 "0000000000000000000000000000000000000000000000000000000000000000"
1303 "0000000000000000000000000000000000000000000000000000000000000000"
1304 "0000000000000000000000000000000000000000000000000000000000000000"
1305 "0000000000000000000000000000000000000000000000000000000000000000"
1306 "0000000000000000000000000000000000000000000000000000000000000000"
1307 "0000000000000000000000000000000000000000000000000000000000000000"
1308 "0000000000000000000000000000000000000000000000000000000000000000"
1309 "00000000000000000000000000000000000000000000000000FFFFFFFFFFFFFF");
1310 CHECK_GOTO(len);
1311 len = BN_hex2bn(&a,
1312 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
1313 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
1314 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
1315 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
1316 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
1317 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
1318 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
1319 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00000000000000FFFFFFFF0000000000"
1320 "0000000000000000000000000000000000000000000000000000000000000000"
1321 "0000000000000000000000000000000000000000000000000000000000000000"
1322 "0000000000000000000000000000000000000000000000000000000000000000"
1323 "0000000000000000000000000000000000000000000000000000000000000000"
1324 "0000000000000000000000000000000000000000000000000000000000000000"
1325 "0000000000000000000000000000000000000000000000000000000000000000"
1326 "0000000000000000000000000000000000000000000000000000000000000000"
1327 "000000000000000000000000000000000000000000FFFFFFFFFFFFFF00000000");
1328 CHECK_GOTO(len);
1329 CHECK_GOTO(bn_copy(b, a));
1330 CHECK_GOTO(BN_MONT_CTX_set(mont, n, ctx));
1331 CHECK_GOTO(BN_mod_mul_montgomery(c, a, a, mont, ctx));
1332 CHECK_GOTO(BN_mod_mul_montgomery(d, a, b, mont, ctx));
1333 if (BN_cmp(c, d)) {
1334 fprintf(stderr, "Montgomery multiplication test failed:"
1335 " a**2 != a*a.\n");
1336 goto err;
1337 }
1338 /* Zero input */
1339 CHECK_GOTO(BN_bntest_rand(p, 1024, 0, 0));
1340 BN_zero(a);
1341 if (!BN_mod_exp_mont_consttime(d, a, p, m, ctx, NULL))
1342 goto err;
1343 if (!BN_is_zero(d)) {
1344 fprintf(stderr, "Modular exponentiation test failed!\n");
1345 goto err;
1346 }
1347 /*
1348 * Craft an input whose Montgomery representation is 1, i.e., shorter
1349 * than the modulus m, in order to test the const time precomputation
1350 * scattering/gathering.
1351 */
1352 CHECK_GOTO(BN_one(a));
1353 CHECK_GOTO(BN_MONT_CTX_set(mont, m, ctx));
1354 if (!BN_from_montgomery(e, a, mont, ctx))
1355 goto err;
1356 if (!BN_mod_exp_mont_consttime(d, e, p, m, ctx, NULL))
1357 goto err;
1358 if (!BN_mod_exp_simple(a, e, p, m, ctx))
1359 goto err;
1360 if (BN_cmp(a, d) != 0) {
1361 fprintf(stderr, "Modular exponentiation test failed!\n");
1362 goto err;
1363 }
1364 /* Finally, some regular test vectors. */
1365 CHECK_GOTO(BN_bntest_rand(e, 1024, 0, 0));
1366 if (!BN_mod_exp_mont_consttime(d, e, p, m, ctx, NULL))
1367 goto err;
1368 if (!BN_mod_exp_simple(a, e, p, m, ctx))
1369 goto err;
1370 if (BN_cmp(a, d) != 0) {
1371 fprintf(stderr, "Modular exponentiation test failed!\n");
1372 goto err;
1373 }
1374
1375 ret = 1;
1376 err:
1377 BN_CTX_end(ctx);
1378 BN_MONT_CTX_free(mont);
1379
1380 return ret;
1381 }
1382
1383 int
test_exp(BIO * bp,BN_CTX * ctx)1384 test_exp(BIO *bp, BN_CTX *ctx)
1385 {
1386 BIGNUM *a, *b, *d, *e;
1387 int i;
1388 int ret = 0;
1389
1390 BN_CTX_start(ctx);
1391
1392 if ((a = BN_CTX_get(ctx)) == NULL)
1393 goto err;
1394 if ((b = BN_CTX_get(ctx)) == NULL)
1395 goto err;
1396 if ((d = BN_CTX_get(ctx)) == NULL)
1397 goto err;
1398 if ((e = BN_CTX_get(ctx)) == NULL)
1399 goto err;
1400
1401 for (i = 0; i < num2; i++) {
1402 CHECK_GOTO(BN_bntest_rand(a, 20 + i * 5, 0, 0));
1403 CHECK_GOTO(BN_bntest_rand(b, 2 + i, 0, 0));
1404
1405 if (BN_exp(d, a, b, ctx) <= 0)
1406 goto err;
1407
1408 if (bp != NULL) {
1409 if (!results) {
1410 CHECK_GOTO(BN_print(bp, a));
1411 BIO_puts(bp, " ^ ");
1412 CHECK_GOTO(BN_print(bp, b));
1413 BIO_puts(bp, " - ");
1414 }
1415 CHECK_GOTO(BN_print(bp, d));
1416 BIO_puts(bp, "\n");
1417 }
1418 CHECK_GOTO(BN_one(e));
1419 for (; !BN_is_zero(b); BN_sub_word(b, 1))
1420 CHECK_GOTO(BN_mul(e, e, a, ctx));
1421 CHECK_GOTO(BN_sub(e, e, d));
1422 if (!BN_is_zero(e)) {
1423 fprintf(stderr, "Exponentiation test failed!\n");
1424 goto err;
1425 }
1426 }
1427
1428 ret = 1;
1429 err:
1430 BN_CTX_end(ctx);
1431
1432 return ret;
1433 }
1434
1435 static int
genprime_cb(int p,int n,BN_GENCB * arg)1436 genprime_cb(int p, int n, BN_GENCB *arg)
1437 {
1438 char c = '*';
1439
1440 if (p == 0)
1441 c = '.';
1442 if (p == 1)
1443 c = '+';
1444 if (p == 2)
1445 c = '*';
1446 if (p == 3)
1447 c = '\n';
1448 putc(c, stderr);
1449 return 1;
1450 }
1451
1452 int
test_kron(BIO * bp,BN_CTX * ctx)1453 test_kron(BIO *bp, BN_CTX *ctx)
1454 {
1455 BIGNUM *a, *b, *r, *t;
1456 BN_GENCB *cb = NULL;
1457 int i;
1458 int legendre, kronecker;
1459 int ret = 0;
1460
1461 BN_CTX_start(ctx);
1462
1463 if ((a = BN_CTX_get(ctx)) == NULL)
1464 goto err;
1465 if ((b = BN_CTX_get(ctx)) == NULL)
1466 goto err;
1467 if ((r = BN_CTX_get(ctx)) == NULL)
1468 goto err;
1469 if ((t = BN_CTX_get(ctx)) == NULL)
1470 goto err;
1471
1472 if ((cb = BN_GENCB_new()) == NULL)
1473 goto err;
1474
1475 BN_GENCB_set(cb, genprime_cb, NULL);
1476
1477 /*
1478 * We test BN_kronecker(a, b, ctx) just for b odd (Jacobi symbol). In
1479 * this case we know that if b is prime, then BN_kronecker(a, b, ctx) is
1480 * congruent to $a^{(b-1)/2}$, modulo $b$ (Legendre symbol). So we
1481 * generate a random prime b and compare these values for a number of
1482 * random a's. (That is, we run the Solovay-Strassen primality test to
1483 * confirm that b is prime, except that we don't want to test whether b
1484 * is prime but whether BN_kronecker works.)
1485 */
1486
1487 if (!BN_generate_prime_ex(b, 512, 0, NULL, NULL, cb))
1488 goto err;
1489 BN_set_negative(b, rand_neg());
1490 putc('\n', stderr);
1491
1492 for (i = 0; i < num0; i++) {
1493 if (!BN_bntest_rand(a, 512, 0, 0))
1494 goto err;
1495 BN_set_negative(a, rand_neg());
1496
1497 /* t := (|b|-1)/2 (note that b is odd) */
1498 if (!bn_copy(t, b))
1499 goto err;
1500 BN_set_negative(t, 0);
1501 if (!BN_sub_word(t, 1))
1502 goto err;
1503 if (!BN_rshift1(t, t))
1504 goto err;
1505 /* r := a^t mod b */
1506 BN_set_negative(b, 0);
1507
1508 if (!BN_mod_exp_recp(r, a, t, b, ctx))
1509 goto err;
1510 BN_set_negative(b, 1);
1511
1512 if (BN_is_word(r, 1))
1513 legendre = 1;
1514 else if (BN_is_zero(r))
1515 legendre = 0;
1516 else {
1517 if (!BN_add_word(r, 1))
1518 goto err;
1519 if (0 != BN_ucmp(r, b)) {
1520 fprintf(stderr, "Legendre symbol computation failed\n");
1521 goto err;
1522 }
1523 legendre = -1;
1524 }
1525
1526 kronecker = BN_kronecker(a, b, ctx);
1527 if (kronecker < -1)
1528 goto err;
1529 /* we actually need BN_kronecker(a, |b|) */
1530 if (BN_is_negative(a) && BN_is_negative(b))
1531 kronecker = -kronecker;
1532
1533 if (legendre != kronecker) {
1534 fprintf(stderr, "legendre != kronecker; a = ");
1535 CHECK_GOTO(BN_print_fp(stderr, a));
1536 fprintf(stderr, ", b = ");
1537 CHECK_GOTO(BN_print_fp(stderr, b));
1538 fprintf(stderr, "\n");
1539 goto err;
1540 }
1541
1542 putc('.', stderr);
1543 }
1544
1545 putc('\n', stderr);
1546
1547 ret = 1;
1548 err:
1549 BN_GENCB_free(cb);
1550 BN_CTX_end(ctx);
1551
1552 return ret;
1553 }
1554
1555 int
test_sqrt(BIO * bp,BN_CTX * ctx)1556 test_sqrt(BIO *bp, BN_CTX *ctx)
1557 {
1558 BIGNUM *a, *p, *r;
1559 BN_GENCB *cb = NULL;
1560 int i, j;
1561 int ret = 0;
1562
1563 BN_CTX_start(ctx);
1564
1565 if ((a = BN_CTX_get(ctx)) == NULL)
1566 goto err;
1567 if ((p = BN_CTX_get(ctx)) == NULL)
1568 goto err;
1569 if ((r = BN_CTX_get(ctx)) == NULL)
1570 goto err;
1571
1572 if ((cb = BN_GENCB_new()) == NULL)
1573 goto err;
1574
1575 BN_GENCB_set(cb, genprime_cb, NULL);
1576
1577 for (i = 0; i < 16; i++) {
1578 if (i < 8) {
1579 unsigned primes[8] = { 2, 3, 5, 7, 11, 13, 17, 19 };
1580
1581 if (!BN_set_word(p, primes[i]))
1582 goto err;
1583 } else {
1584 if (!BN_set_word(a, 32))
1585 goto err;
1586 if (!BN_set_word(r, 2 * i + 1))
1587 goto err;
1588
1589 if (!BN_generate_prime_ex(p, 256, 0, a, r, cb))
1590 goto err;
1591 putc('\n', stderr);
1592 }
1593 BN_set_negative(p, rand_neg());
1594
1595 for (j = 0; j < num2; j++) {
1596 /*
1597 * construct 'a' such that it is a square modulo p, but in
1598 * general not a proper square and not reduced modulo p
1599 */
1600 if (!BN_bntest_rand(r, 256, 0, 3))
1601 goto err;
1602 if (!BN_nnmod(r, r, p, ctx))
1603 goto err;
1604 if (!BN_mod_sqr(r, r, p, ctx))
1605 goto err;
1606 if (!BN_bntest_rand(a, 256, 0, 3))
1607 goto err;
1608 if (!BN_nnmod(a, a, p, ctx))
1609 goto err;
1610 if (!BN_mod_sqr(a, a, p, ctx))
1611 goto err;
1612 if (!BN_mul(a, a, r, ctx))
1613 goto err;
1614 if (rand_neg())
1615 if (!BN_sub(a, a, p))
1616 goto err;
1617
1618 if (!BN_mod_sqrt(r, a, p, ctx))
1619 goto err;
1620 if (!BN_mod_sqr(r, r, p, ctx))
1621 goto err;
1622
1623 if (!BN_nnmod(a, a, p, ctx))
1624 goto err;
1625
1626 if (BN_cmp(a, r) != 0) {
1627 fprintf(stderr, "BN_mod_sqrt failed: a = ");
1628 CHECK_GOTO(BN_print_fp(stderr, a));
1629 fprintf(stderr, ", r = ");
1630 CHECK_GOTO(BN_print_fp(stderr, r));
1631 fprintf(stderr, ", p = ");
1632 CHECK_GOTO(BN_print_fp(stderr, p));
1633 fprintf(stderr, "\n");
1634 goto err;
1635 }
1636
1637 putc('.', stderr);
1638 }
1639
1640 putc('\n', stderr);
1641 }
1642
1643 ret = 1;
1644 err:
1645 BN_GENCB_free(cb);
1646 BN_CTX_end(ctx);
1647
1648 return ret;
1649 }
1650
1651 int
test_lshift(BIO * bp,BN_CTX * ctx,int use_lst)1652 test_lshift(BIO *bp, BN_CTX *ctx, int use_lst)
1653 {
1654 BIGNUM *a, *b, *c, *d;
1655 int i;
1656 int ret = 0;
1657
1658 BN_CTX_start(ctx);
1659
1660 if ((a = BN_CTX_get(ctx)) == NULL)
1661 goto err;
1662 if ((b = BN_CTX_get(ctx)) == NULL)
1663 goto err;
1664 if ((c = BN_CTX_get(ctx)) == NULL)
1665 goto err;
1666 if ((d = BN_CTX_get(ctx)) == NULL)
1667 goto err;
1668 CHECK_GOTO(BN_one(c));
1669
1670 if (use_lst) {
1671 if (!BN_hex2bn(&a, "C64F43042AEACA6E5836805BE8C99B04"
1672 "5D4836C2FD16C964F0"))
1673 goto err;
1674 } else {
1675 CHECK_GOTO(BN_bntest_rand(a, 200, 0, 0));
1676 BN_set_negative(a, rand_neg());
1677 }
1678 for (i = 0; i < num0; i++) {
1679 CHECK_GOTO(BN_lshift(b, a, i + 1));
1680 CHECK_GOTO(BN_add(c, c, c));
1681 if (bp != NULL) {
1682 if (!results) {
1683 CHECK_GOTO(BN_print(bp, a));
1684 BIO_puts(bp, " * ");
1685 CHECK_GOTO(BN_print(bp, c));
1686 BIO_puts(bp, " - ");
1687 }
1688 CHECK_GOTO(BN_print(bp, b));
1689 BIO_puts(bp, "\n");
1690 }
1691 CHECK_GOTO(BN_mul(d, a, c, ctx));
1692 CHECK_GOTO(BN_sub(d, d, b));
1693 if (!BN_is_zero(d)) {
1694 fprintf(stderr, "Left shift test failed!\n");
1695 fprintf(stderr, "a=");
1696 CHECK_GOTO(BN_print_fp(stderr, a));
1697 fprintf(stderr, "\nb=");
1698 CHECK_GOTO(BN_print_fp(stderr, b));
1699 fprintf(stderr, "\nc=");
1700 CHECK_GOTO(BN_print_fp(stderr, c));
1701 fprintf(stderr, "\nd=");
1702 CHECK_GOTO(BN_print_fp(stderr, d));
1703 fprintf(stderr, "\n");
1704 goto err;
1705 }
1706 }
1707
1708 ret = 1;
1709 err:
1710 BN_CTX_end(ctx);
1711
1712 return ret;
1713 }
1714
1715 int
test_lshift1(BIO * bp,BN_CTX * ctx)1716 test_lshift1(BIO *bp, BN_CTX *ctx)
1717 {
1718 BIGNUM *a, *b, *c;
1719 int i;
1720 int ret = 0;
1721
1722 BN_CTX_start(ctx);
1723
1724 if ((a = BN_CTX_get(ctx)) == NULL)
1725 goto err;
1726 if ((b = BN_CTX_get(ctx)) == NULL)
1727 goto err;
1728 if ((c = BN_CTX_get(ctx)) == NULL)
1729 goto err;
1730
1731 CHECK_GOTO(BN_bntest_rand(a, 200, 0, 0));
1732 BN_set_negative(a, rand_neg());
1733 for (i = 0; i < num0; i++) {
1734 CHECK_GOTO(BN_lshift1(b, a));
1735 if (bp != NULL) {
1736 if (!results) {
1737 CHECK_GOTO(BN_print(bp, a));
1738 BIO_puts(bp, " * 2");
1739 BIO_puts(bp, " - ");
1740 }
1741 CHECK_GOTO(BN_print(bp, b));
1742 BIO_puts(bp, "\n");
1743 }
1744 CHECK_GOTO(BN_add(c, a, a));
1745 CHECK_GOTO(BN_sub(a, b, c));
1746 if (!BN_is_zero(a)) {
1747 fprintf(stderr, "Left shift one test failed!\n");
1748 goto err;
1749 }
1750
1751 CHECK_GOTO(bn_copy(a, b));
1752 }
1753
1754 ret = 1;
1755 err:
1756 BN_CTX_end(ctx);
1757
1758 return ret;
1759 }
1760
1761 int
test_rshift(BIO * bp,BN_CTX * ctx)1762 test_rshift(BIO *bp, BN_CTX *ctx)
1763 {
1764 BIGNUM *a, *b, *c, *d, *e;
1765 int i;
1766 int ret = 0;
1767
1768 BN_CTX_start(ctx);
1769
1770 if ((a = BN_CTX_get(ctx)) == NULL)
1771 goto err;
1772 if ((b = BN_CTX_get(ctx)) == NULL)
1773 goto err;
1774 if ((c = BN_CTX_get(ctx)) == NULL)
1775 goto err;
1776 if ((d = BN_CTX_get(ctx)) == NULL)
1777 goto err;
1778 if ((e = BN_CTX_get(ctx)) == NULL)
1779 goto err;
1780 CHECK_GOTO(BN_one(c));
1781
1782 CHECK_GOTO(BN_bntest_rand(a, 200, 0, 0));
1783 BN_set_negative(a, rand_neg());
1784 for (i = 0; i < num0; i++) {
1785 CHECK_GOTO(BN_rshift(b, a, i + 1));
1786 CHECK_GOTO(BN_add(c, c, c));
1787 if (bp != NULL) {
1788 if (!results) {
1789 CHECK_GOTO(BN_print(bp, a));
1790 BIO_puts(bp, " / ");
1791 CHECK_GOTO(BN_print(bp, c));
1792 BIO_puts(bp, " - ");
1793 }
1794 CHECK_GOTO(BN_print(bp, b));
1795 BIO_puts(bp, "\n");
1796 }
1797 CHECK_GOTO(BN_div(d, e, a, c, ctx));
1798 CHECK_GOTO(BN_sub(d, d, b));
1799 if (!BN_is_zero(d)) {
1800 fprintf(stderr, "Right shift test failed!\n");
1801 goto err;
1802 }
1803 }
1804
1805 ret = 1;
1806 err:
1807 BN_CTX_end(ctx);
1808
1809 return ret;
1810 }
1811
1812 int
test_rshift1(BIO * bp,BN_CTX * ctx)1813 test_rshift1(BIO *bp, BN_CTX *ctx)
1814 {
1815 BIGNUM *a, *b, *c;
1816 int i;
1817 int ret = 0;
1818
1819 BN_CTX_start(ctx);
1820
1821 if ((a = BN_CTX_get(ctx)) == NULL)
1822 goto err;
1823 if ((b = BN_CTX_get(ctx)) == NULL)
1824 goto err;
1825 if ((c = BN_CTX_get(ctx)) == NULL)
1826 goto err;
1827
1828 CHECK_GOTO(BN_bntest_rand(a, 200, 0, 0));
1829 BN_set_negative(a, rand_neg());
1830 for (i = 0; i < num0; i++) {
1831 CHECK_GOTO(BN_rshift1(b, a));
1832 if (bp != NULL) {
1833 if (!results) {
1834 CHECK_GOTO(BN_print(bp, a));
1835 BIO_puts(bp, " / 2");
1836 BIO_puts(bp, " - ");
1837 }
1838 CHECK_GOTO(BN_print(bp, b));
1839 BIO_puts(bp, "\n");
1840 }
1841 CHECK_GOTO(BN_sub(c, a, b));
1842 CHECK_GOTO(BN_sub(c, c, b));
1843 if (!BN_is_zero(c) && !BN_abs_is_word(c, 1)) {
1844 fprintf(stderr, "Right shift one test failed!\n");
1845 goto err;
1846 }
1847 CHECK_GOTO(bn_copy(a, b));
1848 }
1849
1850 ret = 1;
1851 err:
1852 BN_CTX_end(ctx);
1853
1854 return ret;
1855 }
1856
1857 int
rand_neg(void)1858 rand_neg(void)
1859 {
1860 static unsigned int neg = 0;
1861 static int sign[8] = { 0, 0, 0, 1, 1, 0, 1, 1 };
1862
1863 return sign[neg++ % 8];
1864 }
1865
1866 int
test_mod_exp_sizes(BIO * bp,BN_CTX * ctx)1867 test_mod_exp_sizes(BIO *bp, BN_CTX *ctx)
1868 {
1869 BN_MONT_CTX *mont_ctx = NULL;
1870 BIGNUM *p, *x, *y, *r, *r2;
1871 int size;
1872 int ret = 0;
1873
1874 BN_CTX_start(ctx);
1875 CHECK_GOTO(p = BN_CTX_get(ctx));
1876 CHECK_GOTO(x = BN_CTX_get(ctx));
1877 CHECK_GOTO(y = BN_CTX_get(ctx));
1878 CHECK_GOTO(r = BN_CTX_get(ctx));
1879 CHECK_GOTO(r2 = BN_CTX_get(ctx));
1880 mont_ctx = BN_MONT_CTX_new();
1881
1882 if (r2 == NULL || mont_ctx == NULL)
1883 goto err;
1884
1885 if (!BN_generate_prime_ex(p, 32, 0, NULL, NULL, NULL) ||
1886 !BN_MONT_CTX_set(mont_ctx, p, ctx))
1887 goto err;
1888
1889 for (size = 32; size < 1024; size += 8) {
1890 if (!BN_rand(x, size, -1, 0) ||
1891 !BN_rand(y, size, -1, 0) ||
1892 !BN_mod_exp_mont_consttime(r, x, y, p, ctx, mont_ctx) ||
1893 !BN_mod_exp(r2, x, y, p, ctx))
1894 goto err;
1895
1896 if (BN_cmp(r, r2) != 0) {
1897 char *r_str = NULL;
1898 char *r2_str = NULL;
1899 CHECK_GOTO(r_str = BN_bn2hex(r));
1900 CHECK_GOTO(r2_str = BN_bn2hex(r2));
1901
1902 printf("Incorrect answer at size %d: %s vs %s\n",
1903 size, r_str, r2_str);
1904 free(r_str);
1905 free(r2_str);
1906 goto err;
1907 }
1908 }
1909
1910 ret = 1;
1911 err:
1912 BN_CTX_end(ctx);
1913 BN_MONT_CTX_free(mont_ctx);
1914
1915 return ret;
1916 }
1917