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