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