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