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