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