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