1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/os/ossrv/ssl/libcrypto/src/crypto/bn/bntest.c Fri Jun 15 03:10:57 2012 +0200
1.3 @@ -0,0 +1,2011 @@
1.4 +/* crypto/bn/bntest.c */
1.5 +/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
1.6 + * All rights reserved.
1.7 + *
1.8 + * This package is an SSL implementation written
1.9 + * by Eric Young (eay@cryptsoft.com).
1.10 + * The implementation was written so as to conform with Netscapes SSL.
1.11 + *
1.12 + * This library is free for commercial and non-commercial use as long as
1.13 + * the following conditions are aheared to. The following conditions
1.14 + * apply to all code found in this distribution, be it the RC4, RSA,
1.15 + * lhash, DES, etc., code; not just the SSL code. The SSL documentation
1.16 + * included with this distribution is covered by the same copyright terms
1.17 + * except that the holder is Tim Hudson (tjh@cryptsoft.com).
1.18 + *
1.19 + * Copyright remains Eric Young's, and as such any Copyright notices in
1.20 + * the code are not to be removed.
1.21 + * If this package is used in a product, Eric Young should be given attribution
1.22 + * as the author of the parts of the library used.
1.23 + * This can be in the form of a textual message at program startup or
1.24 + * in documentation (online or textual) provided with the package.
1.25 + *
1.26 + * Redistribution and use in source and binary forms, with or without
1.27 + * modification, are permitted provided that the following conditions
1.28 + * are met:
1.29 + * 1. Redistributions of source code must retain the copyright
1.30 + * notice, this list of conditions and the following disclaimer.
1.31 + * 2. Redistributions in binary form must reproduce the above copyright
1.32 + * notice, this list of conditions and the following disclaimer in the
1.33 + * documentation and/or other materials provided with the distribution.
1.34 + * 3. All advertising materials mentioning features or use of this software
1.35 + * must display the following acknowledgement:
1.36 + * "This product includes cryptographic software written by
1.37 + * Eric Young (eay@cryptsoft.com)"
1.38 + * The word 'cryptographic' can be left out if the rouines from the library
1.39 + * being used are not cryptographic related :-).
1.40 + * 4. If you include any Windows specific code (or a derivative thereof) from
1.41 + * the apps directory (application code) you must include an acknowledgement:
1.42 + * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)"
1.43 + *
1.44 + * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND
1.45 + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
1.46 + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
1.47 + * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
1.48 + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
1.49 + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
1.50 + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
1.51 + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
1.52 + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
1.53 + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
1.54 + * SUCH DAMAGE.
1.55 + *
1.56 + * The licence and distribution terms for any publically available version or
1.57 + * derivative of this code cannot be changed. i.e. this code cannot simply be
1.58 + * copied and put under another distribution licence
1.59 + * [including the GNU Public Licence.]
1.60 + */
1.61 +/* ====================================================================
1.62 + * Copyright 2002 Sun Microsystems, Inc. ALL RIGHTS RESERVED.
1.63 + *
1.64 + * Portions of the attached software ("Contribution") are developed by
1.65 + * SUN MICROSYSTEMS, INC., and are contributed to the OpenSSL project.
1.66 + *
1.67 + * The Contribution is licensed pursuant to the Eric Young open source
1.68 + * license provided above.
1.69 + *
1.70 + * The binary polynomial arithmetic software is originally written by
1.71 + * Sheueling Chang Shantz and Douglas Stebila of Sun Microsystems Laboratories.
1.72 + *
1.73 + */
1.74 +
1.75 +/* Until the key-gen callbacks are modified to use newer prototypes, we allow
1.76 + * deprecated functions for openssl-internal code */
1.77 +#ifdef OPENSSL_NO_DEPRECATED
1.78 +#undef OPENSSL_NO_DEPRECATED
1.79 +#endif
1.80 +
1.81 +#include <stdio.h>
1.82 +#include <stdlib.h>
1.83 +#include <string.h>
1.84 +
1.85 +#include "e_os.h"
1.86 +
1.87 +#include <openssl/bio.h>
1.88 +#include <openssl/bn.h>
1.89 +#include <openssl/rand.h>
1.90 +#include <openssl/x509.h>
1.91 +#include <openssl/err.h>
1.92 +
1.93 +const int num0 = 100; /* number of tests */
1.94 +const int num1 = 50; /* additional tests for some functions */
1.95 +const int num2 = 5; /* number of tests for slow functions */
1.96 +
1.97 +int test_add(BIO *bp);
1.98 +int test_sub(BIO *bp);
1.99 +int test_lshift1(BIO *bp);
1.100 +int test_lshift(BIO *bp,BN_CTX *ctx,BIGNUM *a_);
1.101 +int test_rshift1(BIO *bp);
1.102 +int test_rshift(BIO *bp,BN_CTX *ctx);
1.103 +int test_div(BIO *bp,BN_CTX *ctx);
1.104 +int test_div_word(BIO *bp);
1.105 +int test_div_recp(BIO *bp,BN_CTX *ctx);
1.106 +int test_mul(BIO *bp);
1.107 +int test_sqr(BIO *bp,BN_CTX *ctx);
1.108 +int test_mont(BIO *bp,BN_CTX *ctx);
1.109 +int test_mod(BIO *bp,BN_CTX *ctx);
1.110 +int test_mod_mul(BIO *bp,BN_CTX *ctx);
1.111 +int test_mod_exp(BIO *bp,BN_CTX *ctx);
1.112 +int test_mod_exp_mont_consttime(BIO *bp,BN_CTX *ctx);
1.113 +int test_exp(BIO *bp,BN_CTX *ctx);
1.114 +int test_gf2m_add(BIO *bp);
1.115 +int test_gf2m_mod(BIO *bp);
1.116 +int test_gf2m_mod_mul(BIO *bp,BN_CTX *ctx);
1.117 +int test_gf2m_mod_sqr(BIO *bp,BN_CTX *ctx);
1.118 +int test_gf2m_mod_inv(BIO *bp,BN_CTX *ctx);
1.119 +int test_gf2m_mod_div(BIO *bp,BN_CTX *ctx);
1.120 +int test_gf2m_mod_exp(BIO *bp,BN_CTX *ctx);
1.121 +int test_gf2m_mod_sqrt(BIO *bp,BN_CTX *ctx);
1.122 +int test_gf2m_mod_solve_quad(BIO *bp,BN_CTX *ctx);
1.123 +int test_kron(BIO *bp,BN_CTX *ctx);
1.124 +int test_sqrt(BIO *bp,BN_CTX *ctx);
1.125 +int rand_neg(void);
1.126 +static int results=0;
1.127 +
1.128 +static unsigned char lst[]="\xC6\x4F\x43\x04\x2A\xEA\xCA\x6E\x58\x36\x80\x5B\xE8\xC9"
1.129 +"\x9B\x04\x5D\x48\x36\xC2\xFD\x16\xC9\x64\xF0";
1.130 +
1.131 +static const char rnd_seed[] = "string to make the random number generator think it has entropy";
1.132 +
1.133 +static void message(BIO *out, char *m)
1.134 + {
1.135 + fprintf(stderr, "test %s\n", m);
1.136 + BIO_puts(out, "print \"test ");
1.137 + BIO_puts(out, m);
1.138 + BIO_puts(out, "\\n\"\n");
1.139 + }
1.140 +
1.141 +int main(int argc, char *argv[])
1.142 + {
1.143 + BN_CTX *ctx;
1.144 + BIO *out;
1.145 + char *outfile=NULL;
1.146 +
1.147 + results = 0;
1.148 +
1.149 + RAND_seed(rnd_seed, sizeof rnd_seed); /* or BN_generate_prime may fail */
1.150 +
1.151 + argc--;
1.152 + argv++;
1.153 + while (argc >= 1)
1.154 + {
1.155 + if (strcmp(*argv,"-results") == 0)
1.156 + results=1;
1.157 + else if (strcmp(*argv,"-out") == 0)
1.158 + {
1.159 + if (--argc < 1) break;
1.160 + outfile= *(++argv);
1.161 + }
1.162 + argc--;
1.163 + argv++;
1.164 + }
1.165 +
1.166 +
1.167 + ctx=BN_CTX_new();
1.168 + if (ctx == NULL) EXIT(1);
1.169 +
1.170 + out=BIO_new(BIO_s_file());
1.171 + if (out == NULL) EXIT(1);
1.172 + if (outfile == NULL)
1.173 + {
1.174 + BIO_set_fp(out,stdout,BIO_NOCLOSE);
1.175 + }
1.176 + else
1.177 + {
1.178 + if (!BIO_write_filename(out,outfile))
1.179 + {
1.180 + perror(outfile);
1.181 + EXIT(1);
1.182 + }
1.183 + }
1.184 +
1.185 + if (!results)
1.186 + BIO_puts(out,"obase=16\nibase=16\n");
1.187 +
1.188 + message(out,"BN_add");
1.189 + if (!test_add(out)) goto err;
1.190 + (void)BIO_flush(out);
1.191 +
1.192 + message(out,"BN_sub");
1.193 + if (!test_sub(out)) goto err;
1.194 + (void)BIO_flush(out);
1.195 +
1.196 + message(out,"BN_lshift1");
1.197 + if (!test_lshift1(out)) goto err;
1.198 + (void)BIO_flush(out);
1.199 +
1.200 + message(out,"BN_lshift (fixed)");
1.201 + if (!test_lshift(out,ctx,BN_bin2bn(lst,sizeof(lst)-1,NULL)))
1.202 + goto err;
1.203 + (void)BIO_flush(out);
1.204 +
1.205 + message(out,"BN_lshift");
1.206 + if (!test_lshift(out,ctx,NULL)) goto err;
1.207 + (void)BIO_flush(out);
1.208 +
1.209 + message(out,"BN_rshift1");
1.210 + if (!test_rshift1(out)) goto err;
1.211 + (void)BIO_flush(out);
1.212 +
1.213 + message(out,"BN_rshift");
1.214 + if (!test_rshift(out,ctx)) goto err;
1.215 + (void)BIO_flush(out);
1.216 +
1.217 + message(out,"BN_sqr");
1.218 + if (!test_sqr(out,ctx)) goto err;
1.219 + (void)BIO_flush(out);
1.220 +
1.221 + message(out,"BN_mul");
1.222 + if (!test_mul(out)) goto err;
1.223 + (void)BIO_flush(out);
1.224 +
1.225 + message(out,"BN_div");
1.226 + if (!test_div(out,ctx)) goto err;
1.227 + (void)BIO_flush(out);
1.228 +
1.229 + message(out,"BN_div_word");
1.230 + if (!test_div_word(out)) goto err;
1.231 + (void)BIO_flush(out);
1.232 +
1.233 + message(out,"BN_div_recp");
1.234 + if (!test_div_recp(out,ctx)) goto err;
1.235 + (void)BIO_flush(out);
1.236 +
1.237 + message(out,"BN_mod");
1.238 + if (!test_mod(out,ctx)) goto err;
1.239 + (void)BIO_flush(out);
1.240 +
1.241 + message(out,"BN_mod_mul");
1.242 + if (!test_mod_mul(out,ctx)) goto err;
1.243 + (void)BIO_flush(out);
1.244 +
1.245 + message(out,"BN_mont");
1.246 + if (!test_mont(out,ctx)) goto err;
1.247 + (void)BIO_flush(out);
1.248 +
1.249 + message(out,"BN_mod_exp");
1.250 + if (!test_mod_exp(out,ctx)) goto err;
1.251 + (void)BIO_flush(out);
1.252 +
1.253 + message(out,"BN_mod_exp_mont_consttime");
1.254 + if (!test_mod_exp_mont_consttime(out,ctx)) goto err;
1.255 + (void)BIO_flush(out);
1.256 +
1.257 + message(out,"BN_exp");
1.258 + if (!test_exp(out,ctx)) goto err;
1.259 + (void)BIO_flush(out);
1.260 +
1.261 + message(out,"BN_kronecker");
1.262 + if (!test_kron(out,ctx)) goto err;
1.263 + (void)BIO_flush(out);
1.264 +
1.265 + message(out,"BN_mod_sqrt");
1.266 + if (!test_sqrt(out,ctx)) goto err;
1.267 + (void)BIO_flush(out);
1.268 +
1.269 + message(out,"BN_GF2m_add");
1.270 + if (!test_gf2m_add(out)) goto err;
1.271 + (void)BIO_flush(out);
1.272 +
1.273 + message(out,"BN_GF2m_mod");
1.274 + if (!test_gf2m_mod(out)) goto err;
1.275 + (void)BIO_flush(out);
1.276 +
1.277 + message(out,"BN_GF2m_mod_mul");
1.278 + if (!test_gf2m_mod_mul(out,ctx)) goto err;
1.279 + (void)BIO_flush(out);
1.280 +
1.281 + message(out,"BN_GF2m_mod_sqr");
1.282 + if (!test_gf2m_mod_sqr(out,ctx)) goto err;
1.283 + (void)BIO_flush(out);
1.284 +
1.285 + message(out,"BN_GF2m_mod_inv");
1.286 + if (!test_gf2m_mod_inv(out,ctx)) goto err;
1.287 + (void)BIO_flush(out);
1.288 +
1.289 + message(out,"BN_GF2m_mod_div");
1.290 + if (!test_gf2m_mod_div(out,ctx)) goto err;
1.291 + (void)BIO_flush(out);
1.292 +
1.293 + message(out,"BN_GF2m_mod_exp");
1.294 + if (!test_gf2m_mod_exp(out,ctx)) goto err;
1.295 + (void)BIO_flush(out);
1.296 +
1.297 + message(out,"BN_GF2m_mod_sqrt");
1.298 + if (!test_gf2m_mod_sqrt(out,ctx)) goto err;
1.299 + (void)BIO_flush(out);
1.300 +
1.301 + message(out,"BN_GF2m_mod_solve_quad");
1.302 + if (!test_gf2m_mod_solve_quad(out,ctx)) goto err;
1.303 + (void)BIO_flush(out);
1.304 +
1.305 + BN_CTX_free(ctx);
1.306 + BIO_free(out);
1.307 +
1.308 +/**/
1.309 + EXIT(0);
1.310 +err:
1.311 + BIO_puts(out,"1\n"); /* make sure the Perl script fed by bc notices
1.312 + * the failure, see test_bn in test/Makefile.ssl*/
1.313 + (void)BIO_flush(out);
1.314 + ERR_load_crypto_strings();
1.315 + ERR_print_errors_fp(stderr);
1.316 + EXIT(1);
1.317 + return(1);
1.318 + }
1.319 +
1.320 +int test_add(BIO *bp)
1.321 + {
1.322 + BIGNUM a,b,c;
1.323 + int i;
1.324 +
1.325 + BN_init(&a);
1.326 + BN_init(&b);
1.327 + BN_init(&c);
1.328 +
1.329 + BN_bntest_rand(&a,512,0,0);
1.330 + for (i=0; i<num0; i++)
1.331 + {
1.332 + BN_bntest_rand(&b,450+i,0,0);
1.333 + a.neg=rand_neg();
1.334 + b.neg=rand_neg();
1.335 + BN_add(&c,&a,&b);
1.336 + if (bp != NULL)
1.337 + {
1.338 + if (!results)
1.339 + {
1.340 + BN_print(bp,&a);
1.341 + BIO_puts(bp," + ");
1.342 + BN_print(bp,&b);
1.343 + BIO_puts(bp," - ");
1.344 + }
1.345 + BN_print(bp,&c);
1.346 + BIO_puts(bp,"\n");
1.347 + }
1.348 + a.neg=!a.neg;
1.349 + b.neg=!b.neg;
1.350 + BN_add(&c,&c,&b);
1.351 + BN_add(&c,&c,&a);
1.352 + if(!BN_is_zero(&c))
1.353 + {
1.354 + fprintf(stderr,"Add test failed!\n");
1.355 + return 0;
1.356 + }
1.357 + }
1.358 + BN_free(&a);
1.359 + BN_free(&b);
1.360 + BN_free(&c);
1.361 + return(1);
1.362 + }
1.363 +
1.364 +int test_sub(BIO *bp)
1.365 + {
1.366 + BIGNUM a,b,c;
1.367 + int i;
1.368 +
1.369 + BN_init(&a);
1.370 + BN_init(&b);
1.371 + BN_init(&c);
1.372 +
1.373 + for (i=0; i<num0+num1; i++)
1.374 + {
1.375 + if (i < num1)
1.376 + {
1.377 + BN_bntest_rand(&a,512,0,0);
1.378 + BN_copy(&b,&a);
1.379 + if (BN_set_bit(&a,i)==0) return(0);
1.380 + BN_add_word(&b,i);
1.381 + }
1.382 + else
1.383 + {
1.384 + BN_bntest_rand(&b,400+i-num1,0,0);
1.385 + a.neg=rand_neg();
1.386 + b.neg=rand_neg();
1.387 + }
1.388 + BN_sub(&c,&a,&b);
1.389 + if (bp != NULL)
1.390 + {
1.391 + if (!results)
1.392 + {
1.393 + BN_print(bp,&a);
1.394 + BIO_puts(bp," - ");
1.395 + BN_print(bp,&b);
1.396 + BIO_puts(bp," - ");
1.397 + }
1.398 + BN_print(bp,&c);
1.399 + BIO_puts(bp,"\n");
1.400 + }
1.401 + BN_add(&c,&c,&b);
1.402 + BN_sub(&c,&c,&a);
1.403 + if(!BN_is_zero(&c))
1.404 + {
1.405 + fprintf(stderr,"Subtract test failed!\n");
1.406 + return 0;
1.407 + }
1.408 + }
1.409 + BN_free(&a);
1.410 + BN_free(&b);
1.411 + BN_free(&c);
1.412 + return(1);
1.413 + }
1.414 +
1.415 +int test_div(BIO *bp, BN_CTX *ctx)
1.416 + {
1.417 + BIGNUM a,b,c,d,e;
1.418 + int i;
1.419 +
1.420 + BN_init(&a);
1.421 + BN_init(&b);
1.422 + BN_init(&c);
1.423 + BN_init(&d);
1.424 + BN_init(&e);
1.425 +
1.426 + for (i=0; i<num0+num1; i++)
1.427 + {
1.428 + if (i < num1)
1.429 + {
1.430 + BN_bntest_rand(&a,400,0,0);
1.431 + BN_copy(&b,&a);
1.432 + BN_lshift(&a,&a,i);
1.433 + BN_add_word(&a,i);
1.434 + }
1.435 + else
1.436 + BN_bntest_rand(&b,50+3*(i-num1),0,0);
1.437 + a.neg=rand_neg();
1.438 + b.neg=rand_neg();
1.439 + BN_div(&d,&c,&a,&b,ctx);
1.440 + if (bp != NULL)
1.441 + {
1.442 + if (!results)
1.443 + {
1.444 + BN_print(bp,&a);
1.445 + BIO_puts(bp," / ");
1.446 + BN_print(bp,&b);
1.447 + BIO_puts(bp," - ");
1.448 + }
1.449 + BN_print(bp,&d);
1.450 + BIO_puts(bp,"\n");
1.451 +
1.452 + if (!results)
1.453 + {
1.454 + BN_print(bp,&a);
1.455 + BIO_puts(bp," % ");
1.456 + BN_print(bp,&b);
1.457 + BIO_puts(bp," - ");
1.458 + }
1.459 + BN_print(bp,&c);
1.460 + BIO_puts(bp,"\n");
1.461 + }
1.462 + BN_mul(&e,&d,&b,ctx);
1.463 + BN_add(&d,&e,&c);
1.464 + BN_sub(&d,&d,&a);
1.465 + if(!BN_is_zero(&d))
1.466 + {
1.467 + fprintf(stderr,"Division test failed!\n");
1.468 + return 0;
1.469 + }
1.470 + }
1.471 + BN_free(&a);
1.472 + BN_free(&b);
1.473 + BN_free(&c);
1.474 + BN_free(&d);
1.475 + BN_free(&e);
1.476 + return(1);
1.477 + }
1.478 +
1.479 +static void print_word(BIO *bp,BN_ULONG w)
1.480 + {
1.481 +#ifdef SIXTY_FOUR_BIT
1.482 + if (sizeof(w) > sizeof(unsigned long))
1.483 + {
1.484 + unsigned long h=(unsigned long)(w>>32),
1.485 + l=(unsigned long)(w);
1.486 +
1.487 + if (h) BIO_printf(bp,"%lX%08lX",h,l);
1.488 + else BIO_printf(bp,"%lX",l);
1.489 + return;
1.490 + }
1.491 +#endif
1.492 + BIO_printf(bp,"%lX",w);
1.493 + }
1.494 +
1.495 +int test_div_word(BIO *bp)
1.496 + {
1.497 + BIGNUM a,b;
1.498 + BN_ULONG r,s;
1.499 + int i;
1.500 +
1.501 + BN_init(&a);
1.502 + BN_init(&b);
1.503 +
1.504 + for (i=0; i<num0; i++)
1.505 + {
1.506 + do {
1.507 + BN_bntest_rand(&a,512,-1,0);
1.508 + BN_bntest_rand(&b,BN_BITS2,-1,0);
1.509 + s = b.d[0];
1.510 + } while (!s);
1.511 +
1.512 + BN_copy(&b, &a);
1.513 + r = BN_div_word(&b, s);
1.514 +
1.515 + if (bp != NULL)
1.516 + {
1.517 + if (!results)
1.518 + {
1.519 + BN_print(bp,&a);
1.520 + BIO_puts(bp," / ");
1.521 + print_word(bp,s);
1.522 + BIO_puts(bp," - ");
1.523 + }
1.524 + BN_print(bp,&b);
1.525 + BIO_puts(bp,"\n");
1.526 +
1.527 + if (!results)
1.528 + {
1.529 + BN_print(bp,&a);
1.530 + BIO_puts(bp," % ");
1.531 + print_word(bp,s);
1.532 + BIO_puts(bp," - ");
1.533 + }
1.534 + print_word(bp,r);
1.535 + BIO_puts(bp,"\n");
1.536 + }
1.537 + BN_mul_word(&b,s);
1.538 + BN_add_word(&b,r);
1.539 + BN_sub(&b,&a,&b);
1.540 + if(!BN_is_zero(&b))
1.541 + {
1.542 + fprintf(stderr,"Division (word) test failed!\n");
1.543 + return 0;
1.544 + }
1.545 + }
1.546 + BN_free(&a);
1.547 + BN_free(&b);
1.548 + return(1);
1.549 + }
1.550 +
1.551 +int test_div_recp(BIO *bp, BN_CTX *ctx)
1.552 + {
1.553 + BIGNUM a,b,c,d,e;
1.554 + BN_RECP_CTX recp;
1.555 + int i;
1.556 +
1.557 + BN_RECP_CTX_init(&recp);
1.558 + BN_init(&a);
1.559 + BN_init(&b);
1.560 + BN_init(&c);
1.561 + BN_init(&d);
1.562 + BN_init(&e);
1.563 +
1.564 + for (i=0; i<num0+num1; i++)
1.565 + {
1.566 + if (i < num1)
1.567 + {
1.568 + BN_bntest_rand(&a,400,0,0);
1.569 + BN_copy(&b,&a);
1.570 + BN_lshift(&a,&a,i);
1.571 + BN_add_word(&a,i);
1.572 + }
1.573 + else
1.574 + BN_bntest_rand(&b,50+3*(i-num1),0,0);
1.575 + a.neg=rand_neg();
1.576 + b.neg=rand_neg();
1.577 + BN_RECP_CTX_set(&recp,&b,ctx);
1.578 + BN_div_recp(&d,&c,&a,&recp,ctx);
1.579 + if (bp != NULL)
1.580 + {
1.581 + if (!results)
1.582 + {
1.583 + BN_print(bp,&a);
1.584 + BIO_puts(bp," / ");
1.585 + BN_print(bp,&b);
1.586 + BIO_puts(bp," - ");
1.587 + }
1.588 + BN_print(bp,&d);
1.589 + BIO_puts(bp,"\n");
1.590 +
1.591 + if (!results)
1.592 + {
1.593 + BN_print(bp,&a);
1.594 + BIO_puts(bp," % ");
1.595 + BN_print(bp,&b);
1.596 + BIO_puts(bp," - ");
1.597 + }
1.598 + BN_print(bp,&c);
1.599 + BIO_puts(bp,"\n");
1.600 + }
1.601 + BN_mul(&e,&d,&b,ctx);
1.602 + BN_add(&d,&e,&c);
1.603 + BN_sub(&d,&d,&a);
1.604 + if(!BN_is_zero(&d))
1.605 + {
1.606 + fprintf(stderr,"Reciprocal division test failed!\n");
1.607 + fprintf(stderr,"a=");
1.608 + BN_print_fp(stderr,&a);
1.609 + fprintf(stderr,"\nb=");
1.610 + BN_print_fp(stderr,&b);
1.611 + fprintf(stderr,"\n");
1.612 + return 0;
1.613 + }
1.614 + }
1.615 + BN_free(&a);
1.616 + BN_free(&b);
1.617 + BN_free(&c);
1.618 + BN_free(&d);
1.619 + BN_free(&e);
1.620 + BN_RECP_CTX_free(&recp);
1.621 + return(1);
1.622 + }
1.623 +
1.624 +int test_mul(BIO *bp)
1.625 + {
1.626 + BIGNUM a,b,c,d,e;
1.627 + int i;
1.628 + BN_CTX *ctx;
1.629 +
1.630 + ctx = BN_CTX_new();
1.631 + if (ctx == NULL) EXIT(1);
1.632 +
1.633 + BN_init(&a);
1.634 + BN_init(&b);
1.635 + BN_init(&c);
1.636 + BN_init(&d);
1.637 + BN_init(&e);
1.638 +
1.639 + for (i=0; i<num0+num1; i++)
1.640 + {
1.641 + if (i <= num1)
1.642 + {
1.643 + BN_bntest_rand(&a,100,0,0);
1.644 + BN_bntest_rand(&b,100,0,0);
1.645 + }
1.646 + else
1.647 + BN_bntest_rand(&b,i-num1,0,0);
1.648 + a.neg=rand_neg();
1.649 + b.neg=rand_neg();
1.650 + BN_mul(&c,&a,&b,ctx);
1.651 + if (bp != NULL)
1.652 + {
1.653 + if (!results)
1.654 + {
1.655 + BN_print(bp,&a);
1.656 + BIO_puts(bp," * ");
1.657 + BN_print(bp,&b);
1.658 + BIO_puts(bp," - ");
1.659 + }
1.660 + BN_print(bp,&c);
1.661 + BIO_puts(bp,"\n");
1.662 + }
1.663 + BN_div(&d,&e,&c,&a,ctx);
1.664 + BN_sub(&d,&d,&b);
1.665 + if(!BN_is_zero(&d) || !BN_is_zero(&e))
1.666 + {
1.667 + fprintf(stderr,"Multiplication test failed!\n");
1.668 + return 0;
1.669 + }
1.670 + }
1.671 + BN_free(&a);
1.672 + BN_free(&b);
1.673 + BN_free(&c);
1.674 + BN_free(&d);
1.675 + BN_free(&e);
1.676 + BN_CTX_free(ctx);
1.677 + return(1);
1.678 + }
1.679 +
1.680 +int test_sqr(BIO *bp, BN_CTX *ctx)
1.681 + {
1.682 + BIGNUM a,c,d,e;
1.683 + int i;
1.684 +
1.685 + BN_init(&a);
1.686 + BN_init(&c);
1.687 + BN_init(&d);
1.688 + BN_init(&e);
1.689 +
1.690 + for (i=0; i<num0; i++)
1.691 + {
1.692 + BN_bntest_rand(&a,40+i*10,0,0);
1.693 + a.neg=rand_neg();
1.694 + BN_sqr(&c,&a,ctx);
1.695 + if (bp != NULL)
1.696 + {
1.697 + if (!results)
1.698 + {
1.699 + BN_print(bp,&a);
1.700 + BIO_puts(bp," * ");
1.701 + BN_print(bp,&a);
1.702 + BIO_puts(bp," - ");
1.703 + }
1.704 + BN_print(bp,&c);
1.705 + BIO_puts(bp,"\n");
1.706 + }
1.707 + BN_div(&d,&e,&c,&a,ctx);
1.708 + BN_sub(&d,&d,&a);
1.709 + if(!BN_is_zero(&d) || !BN_is_zero(&e))
1.710 + {
1.711 + fprintf(stderr,"Square test failed!\n");
1.712 + return 0;
1.713 + }
1.714 + }
1.715 + BN_free(&a);
1.716 + BN_free(&c);
1.717 + BN_free(&d);
1.718 + BN_free(&e);
1.719 + return(1);
1.720 + }
1.721 +
1.722 +int test_mont(BIO *bp, BN_CTX *ctx)
1.723 + {
1.724 + BIGNUM a,b,c,d,A,B;
1.725 + BIGNUM n;
1.726 + int i;
1.727 + BN_MONT_CTX *mont;
1.728 +
1.729 + BN_init(&a);
1.730 + BN_init(&b);
1.731 + BN_init(&c);
1.732 + BN_init(&d);
1.733 + BN_init(&A);
1.734 + BN_init(&B);
1.735 + BN_init(&n);
1.736 +
1.737 + mont=BN_MONT_CTX_new();
1.738 +
1.739 + BN_bntest_rand(&a,100,0,0); /**/
1.740 + BN_bntest_rand(&b,100,0,0); /**/
1.741 + for (i=0; i<num2; i++)
1.742 + {
1.743 + int bits = (200*(i+1))/num2;
1.744 +
1.745 + if (bits == 0)
1.746 + continue;
1.747 + BN_bntest_rand(&n,bits,0,1);
1.748 + BN_MONT_CTX_set(mont,&n,ctx);
1.749 +
1.750 + BN_nnmod(&a,&a,&n,ctx);
1.751 + BN_nnmod(&b,&b,&n,ctx);
1.752 +
1.753 + BN_to_montgomery(&A,&a,mont,ctx);
1.754 + BN_to_montgomery(&B,&b,mont,ctx);
1.755 +
1.756 + BN_mod_mul_montgomery(&c,&A,&B,mont,ctx);/**/
1.757 + BN_from_montgomery(&A,&c,mont,ctx);/**/
1.758 + if (bp != NULL)
1.759 + {
1.760 + if (!results)
1.761 + {
1.762 +#ifdef undef
1.763 +fprintf(stderr,"%d * %d %% %d\n",
1.764 +BN_num_bits(&a),
1.765 +BN_num_bits(&b),
1.766 +BN_num_bits(mont->N));
1.767 +#endif
1.768 + BN_print(bp,&a);
1.769 + BIO_puts(bp," * ");
1.770 + BN_print(bp,&b);
1.771 + BIO_puts(bp," % ");
1.772 + BN_print(bp,&(mont->N));
1.773 + BIO_puts(bp," - ");
1.774 + }
1.775 + BN_print(bp,&A);
1.776 + BIO_puts(bp,"\n");
1.777 + }
1.778 + BN_mod_mul(&d,&a,&b,&n,ctx);
1.779 + BN_sub(&d,&d,&A);
1.780 + if(!BN_is_zero(&d))
1.781 + {
1.782 + fprintf(stderr,"Montgomery multiplication test failed!\n");
1.783 + return 0;
1.784 + }
1.785 + }
1.786 + BN_MONT_CTX_free(mont);
1.787 + BN_free(&a);
1.788 + BN_free(&b);
1.789 + BN_free(&c);
1.790 + BN_free(&d);
1.791 + BN_free(&A);
1.792 + BN_free(&B);
1.793 + BN_free(&n);
1.794 + return(1);
1.795 + }
1.796 +
1.797 +int test_mod(BIO *bp, BN_CTX *ctx)
1.798 + {
1.799 + BIGNUM *a,*b,*c,*d,*e;
1.800 + int i;
1.801 +
1.802 + a=BN_new();
1.803 + b=BN_new();
1.804 + c=BN_new();
1.805 + d=BN_new();
1.806 + e=BN_new();
1.807 +
1.808 + BN_bntest_rand(a,1024,0,0); /**/
1.809 + for (i=0; i<num0; i++)
1.810 + {
1.811 + BN_bntest_rand(b,450+i*10,0,0); /**/
1.812 + a->neg=rand_neg();
1.813 + b->neg=rand_neg();
1.814 + BN_mod(c,a,b,ctx);/**/
1.815 + if (bp != NULL)
1.816 + {
1.817 + if (!results)
1.818 + {
1.819 + BN_print(bp,a);
1.820 + BIO_puts(bp," % ");
1.821 + BN_print(bp,b);
1.822 + BIO_puts(bp," - ");
1.823 + }
1.824 + BN_print(bp,c);
1.825 + BIO_puts(bp,"\n");
1.826 + }
1.827 + BN_div(d,e,a,b,ctx);
1.828 + BN_sub(e,e,c);
1.829 + if(!BN_is_zero(e))
1.830 + {
1.831 + fprintf(stderr,"Modulo test failed!\n");
1.832 + return 0;
1.833 + }
1.834 + }
1.835 + BN_free(a);
1.836 + BN_free(b);
1.837 + BN_free(c);
1.838 + BN_free(d);
1.839 + BN_free(e);
1.840 + return(1);
1.841 + }
1.842 +
1.843 +int test_mod_mul(BIO *bp, BN_CTX *ctx)
1.844 + {
1.845 + BIGNUM *a,*b,*c,*d,*e;
1.846 + int i,j;
1.847 +
1.848 + a=BN_new();
1.849 + b=BN_new();
1.850 + c=BN_new();
1.851 + d=BN_new();
1.852 + e=BN_new();
1.853 +
1.854 + for (j=0; j<3; j++) {
1.855 + BN_bntest_rand(c,1024,0,0); /**/
1.856 + for (i=0; i<num0; i++)
1.857 + {
1.858 + BN_bntest_rand(a,475+i*10,0,0); /**/
1.859 + BN_bntest_rand(b,425+i*11,0,0); /**/
1.860 + a->neg=rand_neg();
1.861 + b->neg=rand_neg();
1.862 + if (!BN_mod_mul(e,a,b,c,ctx))
1.863 + {
1.864 + unsigned long l;
1.865 +
1.866 + while ((l=ERR_get_error()))
1.867 + fprintf(stderr,"ERROR:%s\n",
1.868 + ERR_error_string(l,NULL));
1.869 + EXIT(1);
1.870 + }
1.871 + if (bp != NULL)
1.872 + {
1.873 + if (!results)
1.874 + {
1.875 + BN_print(bp,a);
1.876 + BIO_puts(bp," * ");
1.877 + BN_print(bp,b);
1.878 + BIO_puts(bp," % ");
1.879 + BN_print(bp,c);
1.880 + if ((a->neg ^ b->neg) && !BN_is_zero(e))
1.881 + {
1.882 + /* If (a*b) % c is negative, c must be added
1.883 + * in order to obtain the normalized remainder
1.884 + * (new with OpenSSL 0.9.7, previous versions of
1.885 + * BN_mod_mul could generate negative results)
1.886 + */
1.887 + BIO_puts(bp," + ");
1.888 + BN_print(bp,c);
1.889 + }
1.890 + BIO_puts(bp," - ");
1.891 + }
1.892 + BN_print(bp,e);
1.893 + BIO_puts(bp,"\n");
1.894 + }
1.895 + BN_mul(d,a,b,ctx);
1.896 + BN_sub(d,d,e);
1.897 + BN_div(a,b,d,c,ctx);
1.898 + if(!BN_is_zero(b))
1.899 + {
1.900 + fprintf(stderr,"Modulo multiply test failed!\n");
1.901 + ERR_print_errors_fp(stderr);
1.902 + return 0;
1.903 + }
1.904 + }
1.905 + }
1.906 + BN_free(a);
1.907 + BN_free(b);
1.908 + BN_free(c);
1.909 + BN_free(d);
1.910 + BN_free(e);
1.911 + return(1);
1.912 + }
1.913 +
1.914 +int test_mod_exp(BIO *bp, BN_CTX *ctx)
1.915 + {
1.916 + BIGNUM *a,*b,*c,*d,*e;
1.917 + int i;
1.918 +
1.919 + a=BN_new();
1.920 + b=BN_new();
1.921 + c=BN_new();
1.922 + d=BN_new();
1.923 + e=BN_new();
1.924 +
1.925 + BN_bntest_rand(c,30,0,1); /* must be odd for montgomery */
1.926 + for (i=0; i<num2; i++)
1.927 + {
1.928 + BN_bntest_rand(a,20+i*5,0,0); /**/
1.929 + BN_bntest_rand(b,2+i,0,0); /**/
1.930 +
1.931 + if (!BN_mod_exp(d,a,b,c,ctx))
1.932 + return(00);
1.933 +
1.934 + if (bp != NULL)
1.935 + {
1.936 + if (!results)
1.937 + {
1.938 + BN_print(bp,a);
1.939 + BIO_puts(bp," ^ ");
1.940 + BN_print(bp,b);
1.941 + BIO_puts(bp," % ");
1.942 + BN_print(bp,c);
1.943 + BIO_puts(bp," - ");
1.944 + }
1.945 + BN_print(bp,d);
1.946 + BIO_puts(bp,"\n");
1.947 + }
1.948 + BN_exp(e,a,b,ctx);
1.949 + BN_sub(e,e,d);
1.950 + BN_div(a,b,e,c,ctx);
1.951 + if(!BN_is_zero(b))
1.952 + {
1.953 + fprintf(stderr,"Modulo exponentiation test failed!\n");
1.954 + return 0;
1.955 + }
1.956 + }
1.957 + BN_free(a);
1.958 + BN_free(b);
1.959 + BN_free(c);
1.960 + BN_free(d);
1.961 + BN_free(e);
1.962 + return(1);
1.963 + }
1.964 +
1.965 +int test_mod_exp_mont_consttime(BIO *bp, BN_CTX *ctx)
1.966 + {
1.967 + BIGNUM *a,*b,*c,*d,*e;
1.968 + int i;
1.969 +
1.970 + a=BN_new();
1.971 + b=BN_new();
1.972 + c=BN_new();
1.973 + d=BN_new();
1.974 + e=BN_new();
1.975 +
1.976 + BN_bntest_rand(c,30,0,1); /* must be odd for montgomery */
1.977 + for (i=0; i<num2; i++)
1.978 + {
1.979 + BN_bntest_rand(a,20+i*5,0,0); /**/
1.980 + BN_bntest_rand(b,2+i,0,0); /**/
1.981 +
1.982 + if (!BN_mod_exp_mont_consttime(d,a,b,c,ctx,NULL))
1.983 + return(00);
1.984 +
1.985 + if (bp != NULL)
1.986 + {
1.987 + if (!results)
1.988 + {
1.989 + BN_print(bp,a);
1.990 + BIO_puts(bp," ^ ");
1.991 + BN_print(bp,b);
1.992 + BIO_puts(bp," % ");
1.993 + BN_print(bp,c);
1.994 + BIO_puts(bp," - ");
1.995 + }
1.996 + BN_print(bp,d);
1.997 + BIO_puts(bp,"\n");
1.998 + }
1.999 + BN_exp(e,a,b,ctx);
1.1000 + BN_sub(e,e,d);
1.1001 + BN_div(a,b,e,c,ctx);
1.1002 + if(!BN_is_zero(b))
1.1003 + {
1.1004 + fprintf(stderr,"Modulo exponentiation test failed!\n");
1.1005 + return 0;
1.1006 + }
1.1007 + }
1.1008 + BN_free(a);
1.1009 + BN_free(b);
1.1010 + BN_free(c);
1.1011 + BN_free(d);
1.1012 + BN_free(e);
1.1013 + return(1);
1.1014 + }
1.1015 +
1.1016 +int test_exp(BIO *bp, BN_CTX *ctx)
1.1017 + {
1.1018 + BIGNUM *a,*b,*d,*e,*one;
1.1019 + int i;
1.1020 +
1.1021 + a=BN_new();
1.1022 + b=BN_new();
1.1023 + d=BN_new();
1.1024 + e=BN_new();
1.1025 + one=BN_new();
1.1026 + BN_one(one);
1.1027 +
1.1028 + for (i=0; i<num2; i++)
1.1029 + {
1.1030 + BN_bntest_rand(a,20+i*5,0,0); /**/
1.1031 + BN_bntest_rand(b,2+i,0,0); /**/
1.1032 +
1.1033 + if (!BN_exp(d,a,b,ctx))
1.1034 + return(00);
1.1035 +
1.1036 + if (bp != NULL)
1.1037 + {
1.1038 + if (!results)
1.1039 + {
1.1040 + BN_print(bp,a);
1.1041 + BIO_puts(bp," ^ ");
1.1042 + BN_print(bp,b);
1.1043 + BIO_puts(bp," - ");
1.1044 + }
1.1045 + BN_print(bp,d);
1.1046 + BIO_puts(bp,"\n");
1.1047 + }
1.1048 + BN_one(e);
1.1049 + for( ; !BN_is_zero(b) ; BN_sub(b,b,one))
1.1050 + BN_mul(e,e,a,ctx);
1.1051 + BN_sub(e,e,d);
1.1052 + if(!BN_is_zero(e))
1.1053 + {
1.1054 + fprintf(stderr,"Exponentiation test failed!\n");
1.1055 + return 0;
1.1056 + }
1.1057 + }
1.1058 + BN_free(a);
1.1059 + BN_free(b);
1.1060 + BN_free(d);
1.1061 + BN_free(e);
1.1062 + BN_free(one);
1.1063 + return(1);
1.1064 + }
1.1065 +
1.1066 +int test_gf2m_add(BIO *bp)
1.1067 + {
1.1068 + BIGNUM a,b,c;
1.1069 + int i, ret = 0;
1.1070 +
1.1071 + BN_init(&a);
1.1072 + BN_init(&b);
1.1073 + BN_init(&c);
1.1074 +
1.1075 + for (i=0; i<num0; i++)
1.1076 + {
1.1077 + BN_rand(&a,512,0,0);
1.1078 + BN_copy(&b, BN_value_one());
1.1079 + a.neg=rand_neg();
1.1080 + b.neg=rand_neg();
1.1081 + BN_GF2m_add(&c,&a,&b);
1.1082 +#if 0 /* make test uses ouput in bc but bc can't handle GF(2^m) arithmetic */
1.1083 + if (bp != NULL)
1.1084 + {
1.1085 + if (!results)
1.1086 + {
1.1087 + BN_print(bp,&a);
1.1088 + BIO_puts(bp," ^ ");
1.1089 + BN_print(bp,&b);
1.1090 + BIO_puts(bp," = ");
1.1091 + }
1.1092 + BN_print(bp,&c);
1.1093 + BIO_puts(bp,"\n");
1.1094 + }
1.1095 +#endif
1.1096 + /* Test that two added values have the correct parity. */
1.1097 + if((BN_is_odd(&a) && BN_is_odd(&c)) || (!BN_is_odd(&a) && !BN_is_odd(&c)))
1.1098 + {
1.1099 + fprintf(stderr,"GF(2^m) addition test (a) failed!\n");
1.1100 + goto err;
1.1101 + }
1.1102 + BN_GF2m_add(&c,&c,&c);
1.1103 + /* Test that c + c = 0. */
1.1104 + if(!BN_is_zero(&c))
1.1105 + {
1.1106 + fprintf(stderr,"GF(2^m) addition test (b) failed!\n");
1.1107 + goto err;
1.1108 + }
1.1109 + }
1.1110 + ret = 1;
1.1111 + err:
1.1112 + BN_free(&a);
1.1113 + BN_free(&b);
1.1114 + BN_free(&c);
1.1115 + return ret;
1.1116 + }
1.1117 +
1.1118 +int test_gf2m_mod(BIO *bp)
1.1119 + {
1.1120 + BIGNUM *a,*b[2],*c,*d,*e;
1.1121 + int i, j, ret = 0;
1.1122 + unsigned int p0[] = {163,7,6,3,0};
1.1123 + unsigned int p1[] = {193,15,0};
1.1124 +
1.1125 + a=BN_new();
1.1126 + b[0]=BN_new();
1.1127 + b[1]=BN_new();
1.1128 + c=BN_new();
1.1129 + d=BN_new();
1.1130 + e=BN_new();
1.1131 +
1.1132 + BN_GF2m_arr2poly(p0, b[0]);
1.1133 + BN_GF2m_arr2poly(p1, b[1]);
1.1134 +
1.1135 + for (i=0; i<num0; i++)
1.1136 + {
1.1137 + BN_bntest_rand(a, 1024, 0, 0);
1.1138 + for (j=0; j < 2; j++)
1.1139 + {
1.1140 + BN_GF2m_mod(c, a, b[j]);
1.1141 +#if 0 /* make test uses ouput in bc but bc can't handle GF(2^m) arithmetic */
1.1142 + if (bp != NULL)
1.1143 + {
1.1144 + if (!results)
1.1145 + {
1.1146 + BN_print(bp,a);
1.1147 + BIO_puts(bp," % ");
1.1148 + BN_print(bp,b[j]);
1.1149 + BIO_puts(bp," - ");
1.1150 + BN_print(bp,c);
1.1151 + BIO_puts(bp,"\n");
1.1152 + }
1.1153 + }
1.1154 +#endif
1.1155 + BN_GF2m_add(d, a, c);
1.1156 + BN_GF2m_mod(e, d, b[j]);
1.1157 + /* Test that a + (a mod p) mod p == 0. */
1.1158 + if(!BN_is_zero(e))
1.1159 + {
1.1160 + fprintf(stderr,"GF(2^m) modulo test failed!\n");
1.1161 + goto err;
1.1162 + }
1.1163 + }
1.1164 + }
1.1165 + ret = 1;
1.1166 + err:
1.1167 + BN_free(a);
1.1168 + BN_free(b[0]);
1.1169 + BN_free(b[1]);
1.1170 + BN_free(c);
1.1171 + BN_free(d);
1.1172 + BN_free(e);
1.1173 + return ret;
1.1174 + }
1.1175 +
1.1176 +int test_gf2m_mod_mul(BIO *bp,BN_CTX *ctx)
1.1177 + {
1.1178 + BIGNUM *a,*b[2],*c,*d,*e,*f,*g,*h;
1.1179 + int i, j, ret = 0;
1.1180 + unsigned int p0[] = {163,7,6,3,0};
1.1181 + unsigned int p1[] = {193,15,0};
1.1182 +
1.1183 + a=BN_new();
1.1184 + b[0]=BN_new();
1.1185 + b[1]=BN_new();
1.1186 + c=BN_new();
1.1187 + d=BN_new();
1.1188 + e=BN_new();
1.1189 + f=BN_new();
1.1190 + g=BN_new();
1.1191 + h=BN_new();
1.1192 +
1.1193 + BN_GF2m_arr2poly(p0, b[0]);
1.1194 + BN_GF2m_arr2poly(p1, b[1]);
1.1195 +
1.1196 + for (i=0; i<num0; i++)
1.1197 + {
1.1198 + BN_bntest_rand(a, 1024, 0, 0);
1.1199 + BN_bntest_rand(c, 1024, 0, 0);
1.1200 + BN_bntest_rand(d, 1024, 0, 0);
1.1201 + for (j=0; j < 2; j++)
1.1202 + {
1.1203 + BN_GF2m_mod_mul(e, a, c, b[j], ctx);
1.1204 +#if 0 /* make test uses ouput in bc but bc can't handle GF(2^m) arithmetic */
1.1205 + if (bp != NULL)
1.1206 + {
1.1207 + if (!results)
1.1208 + {
1.1209 + BN_print(bp,a);
1.1210 + BIO_puts(bp," * ");
1.1211 + BN_print(bp,c);
1.1212 + BIO_puts(bp," % ");
1.1213 + BN_print(bp,b[j]);
1.1214 + BIO_puts(bp," - ");
1.1215 + BN_print(bp,e);
1.1216 + BIO_puts(bp,"\n");
1.1217 + }
1.1218 + }
1.1219 +#endif
1.1220 + BN_GF2m_add(f, a, d);
1.1221 + BN_GF2m_mod_mul(g, f, c, b[j], ctx);
1.1222 + BN_GF2m_mod_mul(h, d, c, b[j], ctx);
1.1223 + BN_GF2m_add(f, e, g);
1.1224 + BN_GF2m_add(f, f, h);
1.1225 + /* Test that (a+d)*c = a*c + d*c. */
1.1226 + if(!BN_is_zero(f))
1.1227 + {
1.1228 + fprintf(stderr,"GF(2^m) modular multiplication test failed!\n");
1.1229 + goto err;
1.1230 + }
1.1231 + }
1.1232 + }
1.1233 + ret = 1;
1.1234 + err:
1.1235 + BN_free(a);
1.1236 + BN_free(b[0]);
1.1237 + BN_free(b[1]);
1.1238 + BN_free(c);
1.1239 + BN_free(d);
1.1240 + BN_free(e);
1.1241 + BN_free(f);
1.1242 + BN_free(g);
1.1243 + BN_free(h);
1.1244 + return ret;
1.1245 + }
1.1246 +
1.1247 +int test_gf2m_mod_sqr(BIO *bp,BN_CTX *ctx)
1.1248 + {
1.1249 + BIGNUM *a,*b[2],*c,*d;
1.1250 + int i, j, ret = 0;
1.1251 + unsigned int p0[] = {163,7,6,3,0};
1.1252 + unsigned int p1[] = {193,15,0};
1.1253 +
1.1254 + a=BN_new();
1.1255 + b[0]=BN_new();
1.1256 + b[1]=BN_new();
1.1257 + c=BN_new();
1.1258 + d=BN_new();
1.1259 +
1.1260 + BN_GF2m_arr2poly(p0, b[0]);
1.1261 + BN_GF2m_arr2poly(p1, b[1]);
1.1262 +
1.1263 + for (i=0; i<num0; i++)
1.1264 + {
1.1265 + BN_bntest_rand(a, 1024, 0, 0);
1.1266 + for (j=0; j < 2; j++)
1.1267 + {
1.1268 + BN_GF2m_mod_sqr(c, a, b[j], ctx);
1.1269 + BN_copy(d, a);
1.1270 + BN_GF2m_mod_mul(d, a, d, b[j], ctx);
1.1271 +#if 0 /* make test uses ouput in bc but bc can't handle GF(2^m) arithmetic */
1.1272 + if (bp != NULL)
1.1273 + {
1.1274 + if (!results)
1.1275 + {
1.1276 + BN_print(bp,a);
1.1277 + BIO_puts(bp," ^ 2 % ");
1.1278 + BN_print(bp,b[j]);
1.1279 + BIO_puts(bp, " = ");
1.1280 + BN_print(bp,c);
1.1281 + BIO_puts(bp,"; a * a = ");
1.1282 + BN_print(bp,d);
1.1283 + BIO_puts(bp,"\n");
1.1284 + }
1.1285 + }
1.1286 +#endif
1.1287 + BN_GF2m_add(d, c, d);
1.1288 + /* Test that a*a = a^2. */
1.1289 + if(!BN_is_zero(d))
1.1290 + {
1.1291 + fprintf(stderr,"GF(2^m) modular squaring test failed!\n");
1.1292 + goto err;
1.1293 + }
1.1294 + }
1.1295 + }
1.1296 + ret = 1;
1.1297 + err:
1.1298 + BN_free(a);
1.1299 + BN_free(b[0]);
1.1300 + BN_free(b[1]);
1.1301 + BN_free(c);
1.1302 + BN_free(d);
1.1303 + return ret;
1.1304 + }
1.1305 +
1.1306 +int test_gf2m_mod_inv(BIO *bp,BN_CTX *ctx)
1.1307 + {
1.1308 + BIGNUM *a,*b[2],*c,*d;
1.1309 + int i, j, ret = 0;
1.1310 + unsigned int p0[] = {163,7,6,3,0};
1.1311 + unsigned int p1[] = {193,15,0};
1.1312 +
1.1313 + a=BN_new();
1.1314 + b[0]=BN_new();
1.1315 + b[1]=BN_new();
1.1316 + c=BN_new();
1.1317 + d=BN_new();
1.1318 +
1.1319 + BN_GF2m_arr2poly(p0, b[0]);
1.1320 + BN_GF2m_arr2poly(p1, b[1]);
1.1321 +
1.1322 + for (i=0; i<num0; i++)
1.1323 + {
1.1324 + BN_bntest_rand(a, 512, 0, 0);
1.1325 + for (j=0; j < 2; j++)
1.1326 + {
1.1327 + BN_GF2m_mod_inv(c, a, b[j], ctx);
1.1328 + BN_GF2m_mod_mul(d, a, c, b[j], ctx);
1.1329 +#if 0 /* make test uses ouput in bc but bc can't handle GF(2^m) arithmetic */
1.1330 + if (bp != NULL)
1.1331 + {
1.1332 + if (!results)
1.1333 + {
1.1334 + BN_print(bp,a);
1.1335 + BIO_puts(bp, " * ");
1.1336 + BN_print(bp,c);
1.1337 + BIO_puts(bp," - 1 % ");
1.1338 + BN_print(bp,b[j]);
1.1339 + BIO_puts(bp,"\n");
1.1340 + }
1.1341 + }
1.1342 +#endif
1.1343 + /* Test that ((1/a)*a) = 1. */
1.1344 + if(!BN_is_one(d))
1.1345 + {
1.1346 + fprintf(stderr,"GF(2^m) modular inversion test failed!\n");
1.1347 + goto err;
1.1348 + }
1.1349 + }
1.1350 + }
1.1351 + ret = 1;
1.1352 + err:
1.1353 + BN_free(a);
1.1354 + BN_free(b[0]);
1.1355 + BN_free(b[1]);
1.1356 + BN_free(c);
1.1357 + BN_free(d);
1.1358 + return ret;
1.1359 + }
1.1360 +
1.1361 +int test_gf2m_mod_div(BIO *bp,BN_CTX *ctx)
1.1362 + {
1.1363 + BIGNUM *a,*b[2],*c,*d,*e,*f;
1.1364 + int i, j, ret = 0;
1.1365 + unsigned int p0[] = {163,7,6,3,0};
1.1366 + unsigned int p1[] = {193,15,0};
1.1367 +
1.1368 + a=BN_new();
1.1369 + b[0]=BN_new();
1.1370 + b[1]=BN_new();
1.1371 + c=BN_new();
1.1372 + d=BN_new();
1.1373 + e=BN_new();
1.1374 + f=BN_new();
1.1375 +
1.1376 + BN_GF2m_arr2poly(p0, b[0]);
1.1377 + BN_GF2m_arr2poly(p1, b[1]);
1.1378 +
1.1379 + for (i=0; i<num0; i++)
1.1380 + {
1.1381 + BN_bntest_rand(a, 512, 0, 0);
1.1382 + BN_bntest_rand(c, 512, 0, 0);
1.1383 + for (j=0; j < 2; j++)
1.1384 + {
1.1385 + BN_GF2m_mod_div(d, a, c, b[j], ctx);
1.1386 + BN_GF2m_mod_mul(e, d, c, b[j], ctx);
1.1387 + BN_GF2m_mod_div(f, a, e, b[j], ctx);
1.1388 +#if 0 /* make test uses ouput in bc but bc can't handle GF(2^m) arithmetic */
1.1389 + if (bp != NULL)
1.1390 + {
1.1391 + if (!results)
1.1392 + {
1.1393 + BN_print(bp,a);
1.1394 + BIO_puts(bp, " = ");
1.1395 + BN_print(bp,c);
1.1396 + BIO_puts(bp," * ");
1.1397 + BN_print(bp,d);
1.1398 + BIO_puts(bp, " % ");
1.1399 + BN_print(bp,b[j]);
1.1400 + BIO_puts(bp,"\n");
1.1401 + }
1.1402 + }
1.1403 +#endif
1.1404 + /* Test that ((a/c)*c)/a = 1. */
1.1405 + if(!BN_is_one(f))
1.1406 + {
1.1407 + fprintf(stderr,"GF(2^m) modular division test failed!\n");
1.1408 + goto err;
1.1409 + }
1.1410 + }
1.1411 + }
1.1412 + ret = 1;
1.1413 + err:
1.1414 + BN_free(a);
1.1415 + BN_free(b[0]);
1.1416 + BN_free(b[1]);
1.1417 + BN_free(c);
1.1418 + BN_free(d);
1.1419 + BN_free(e);
1.1420 + BN_free(f);
1.1421 + return ret;
1.1422 + }
1.1423 +
1.1424 +int test_gf2m_mod_exp(BIO *bp,BN_CTX *ctx)
1.1425 + {
1.1426 + BIGNUM *a,*b[2],*c,*d,*e,*f;
1.1427 + int i, j, ret = 0;
1.1428 + unsigned int p0[] = {163,7,6,3,0};
1.1429 + unsigned int p1[] = {193,15,0};
1.1430 +
1.1431 + a=BN_new();
1.1432 + b[0]=BN_new();
1.1433 + b[1]=BN_new();
1.1434 + c=BN_new();
1.1435 + d=BN_new();
1.1436 + e=BN_new();
1.1437 + f=BN_new();
1.1438 +
1.1439 + BN_GF2m_arr2poly(p0, b[0]);
1.1440 + BN_GF2m_arr2poly(p1, b[1]);
1.1441 +
1.1442 + for (i=0; i<num0; i++)
1.1443 + {
1.1444 + BN_bntest_rand(a, 512, 0, 0);
1.1445 + BN_bntest_rand(c, 512, 0, 0);
1.1446 + BN_bntest_rand(d, 512, 0, 0);
1.1447 + for (j=0; j < 2; j++)
1.1448 + {
1.1449 + BN_GF2m_mod_exp(e, a, c, b[j], ctx);
1.1450 + BN_GF2m_mod_exp(f, a, d, b[j], ctx);
1.1451 + BN_GF2m_mod_mul(e, e, f, b[j], ctx);
1.1452 + BN_add(f, c, d);
1.1453 + BN_GF2m_mod_exp(f, a, f, b[j], ctx);
1.1454 +#if 0 /* make test uses ouput in bc but bc can't handle GF(2^m) arithmetic */
1.1455 + if (bp != NULL)
1.1456 + {
1.1457 + if (!results)
1.1458 + {
1.1459 + BN_print(bp,a);
1.1460 + BIO_puts(bp, " ^ (");
1.1461 + BN_print(bp,c);
1.1462 + BIO_puts(bp," + ");
1.1463 + BN_print(bp,d);
1.1464 + BIO_puts(bp, ") = ");
1.1465 + BN_print(bp,e);
1.1466 + BIO_puts(bp, "; - ");
1.1467 + BN_print(bp,f);
1.1468 + BIO_puts(bp, " % ");
1.1469 + BN_print(bp,b[j]);
1.1470 + BIO_puts(bp,"\n");
1.1471 + }
1.1472 + }
1.1473 +#endif
1.1474 + BN_GF2m_add(f, e, f);
1.1475 + /* Test that a^(c+d)=a^c*a^d. */
1.1476 + if(!BN_is_zero(f))
1.1477 + {
1.1478 + fprintf(stderr,"GF(2^m) modular exponentiation test failed!\n");
1.1479 + goto err;
1.1480 + }
1.1481 + }
1.1482 + }
1.1483 + ret = 1;
1.1484 + err:
1.1485 + BN_free(a);
1.1486 + BN_free(b[0]);
1.1487 + BN_free(b[1]);
1.1488 + BN_free(c);
1.1489 + BN_free(d);
1.1490 + BN_free(e);
1.1491 + BN_free(f);
1.1492 + return ret;
1.1493 + }
1.1494 +
1.1495 +int test_gf2m_mod_sqrt(BIO *bp,BN_CTX *ctx)
1.1496 + {
1.1497 + BIGNUM *a,*b[2],*c,*d,*e,*f;
1.1498 + int i, j, ret = 0;
1.1499 + unsigned int p0[] = {163,7,6,3,0};
1.1500 + unsigned int p1[] = {193,15,0};
1.1501 +
1.1502 + a=BN_new();
1.1503 + b[0]=BN_new();
1.1504 + b[1]=BN_new();
1.1505 + c=BN_new();
1.1506 + d=BN_new();
1.1507 + e=BN_new();
1.1508 + f=BN_new();
1.1509 +
1.1510 + BN_GF2m_arr2poly(p0, b[0]);
1.1511 + BN_GF2m_arr2poly(p1, b[1]);
1.1512 +
1.1513 + for (i=0; i<num0; i++)
1.1514 + {
1.1515 + BN_bntest_rand(a, 512, 0, 0);
1.1516 + for (j=0; j < 2; j++)
1.1517 + {
1.1518 + BN_GF2m_mod(c, a, b[j]);
1.1519 + BN_GF2m_mod_sqrt(d, a, b[j], ctx);
1.1520 + BN_GF2m_mod_sqr(e, d, b[j], ctx);
1.1521 +#if 0 /* make test uses ouput in bc but bc can't handle GF(2^m) arithmetic */
1.1522 + if (bp != NULL)
1.1523 + {
1.1524 + if (!results)
1.1525 + {
1.1526 + BN_print(bp,d);
1.1527 + BIO_puts(bp, " ^ 2 - ");
1.1528 + BN_print(bp,a);
1.1529 + BIO_puts(bp,"\n");
1.1530 + }
1.1531 + }
1.1532 +#endif
1.1533 + BN_GF2m_add(f, c, e);
1.1534 + /* Test that d^2 = a, where d = sqrt(a). */
1.1535 + if(!BN_is_zero(f))
1.1536 + {
1.1537 + fprintf(stderr,"GF(2^m) modular square root test failed!\n");
1.1538 + goto err;
1.1539 + }
1.1540 + }
1.1541 + }
1.1542 + ret = 1;
1.1543 + err:
1.1544 + BN_free(a);
1.1545 + BN_free(b[0]);
1.1546 + BN_free(b[1]);
1.1547 + BN_free(c);
1.1548 + BN_free(d);
1.1549 + BN_free(e);
1.1550 + BN_free(f);
1.1551 + return ret;
1.1552 + }
1.1553 +
1.1554 +int test_gf2m_mod_solve_quad(BIO *bp,BN_CTX *ctx)
1.1555 + {
1.1556 + BIGNUM *a,*b[2],*c,*d,*e;
1.1557 + int i, j, s = 0, t, ret = 0;
1.1558 + unsigned int p0[] = {163,7,6,3,0};
1.1559 + unsigned int p1[] = {193,15,0};
1.1560 +
1.1561 + a=BN_new();
1.1562 + b[0]=BN_new();
1.1563 + b[1]=BN_new();
1.1564 + c=BN_new();
1.1565 + d=BN_new();
1.1566 + e=BN_new();
1.1567 +
1.1568 + BN_GF2m_arr2poly(p0, b[0]);
1.1569 + BN_GF2m_arr2poly(p1, b[1]);
1.1570 +
1.1571 + for (i=0; i<num0; i++)
1.1572 + {
1.1573 + BN_bntest_rand(a, 512, 0, 0);
1.1574 + for (j=0; j < 2; j++)
1.1575 + {
1.1576 + t = BN_GF2m_mod_solve_quad(c, a, b[j], ctx);
1.1577 + if (t)
1.1578 + {
1.1579 + s++;
1.1580 + BN_GF2m_mod_sqr(d, c, b[j], ctx);
1.1581 + BN_GF2m_add(d, c, d);
1.1582 + BN_GF2m_mod(e, a, b[j]);
1.1583 +#if 0 /* make test uses ouput in bc but bc can't handle GF(2^m) arithmetic */
1.1584 + if (bp != NULL)
1.1585 + {
1.1586 + if (!results)
1.1587 + {
1.1588 + BN_print(bp,c);
1.1589 + BIO_puts(bp, " is root of z^2 + z = ");
1.1590 + BN_print(bp,a);
1.1591 + BIO_puts(bp, " % ");
1.1592 + BN_print(bp,b[j]);
1.1593 + BIO_puts(bp, "\n");
1.1594 + }
1.1595 + }
1.1596 +#endif
1.1597 + BN_GF2m_add(e, e, d);
1.1598 + /* Test that solution of quadratic c satisfies c^2 + c = a. */
1.1599 + if(!BN_is_zero(e))
1.1600 + {
1.1601 + fprintf(stderr,"GF(2^m) modular solve quadratic test failed!\n");
1.1602 + goto err;
1.1603 + }
1.1604 +
1.1605 + }
1.1606 + else
1.1607 + {
1.1608 +#if 0 /* make test uses ouput in bc but bc can't handle GF(2^m) arithmetic */
1.1609 + if (bp != NULL)
1.1610 + {
1.1611 + if (!results)
1.1612 + {
1.1613 + BIO_puts(bp, "There are no roots of z^2 + z = ");
1.1614 + BN_print(bp,a);
1.1615 + BIO_puts(bp, " % ");
1.1616 + BN_print(bp,b[j]);
1.1617 + BIO_puts(bp, "\n");
1.1618 + }
1.1619 + }
1.1620 +#endif
1.1621 + }
1.1622 + }
1.1623 + }
1.1624 + if (s == 0)
1.1625 + {
1.1626 + fprintf(stderr,"All %i tests of GF(2^m) modular solve quadratic resulted in no roots;\n", num0);
1.1627 + fprintf(stderr,"this is very unlikely and probably indicates an error.\n");
1.1628 + goto err;
1.1629 + }
1.1630 + ret = 1;
1.1631 + err:
1.1632 + BN_free(a);
1.1633 + BN_free(b[0]);
1.1634 + BN_free(b[1]);
1.1635 + BN_free(c);
1.1636 + BN_free(d);
1.1637 + BN_free(e);
1.1638 + return ret;
1.1639 + }
1.1640 +
1.1641 +static int genprime_cb(int p, int n, BN_GENCB *arg)
1.1642 + {
1.1643 + char c='*';
1.1644 +
1.1645 + if (p == 0) c='.';
1.1646 + if (p == 1) c='+';
1.1647 + if (p == 2) c='*';
1.1648 + if (p == 3) c='\n';
1.1649 + putc(c, stderr);
1.1650 + fflush(stderr);
1.1651 + return 1;
1.1652 + }
1.1653 +
1.1654 +int test_kron(BIO *bp, BN_CTX *ctx)
1.1655 + {
1.1656 + BN_GENCB cb;
1.1657 + BIGNUM *a,*b,*r,*t;
1.1658 + int i;
1.1659 + int legendre, kronecker;
1.1660 + int ret = 0;
1.1661 +
1.1662 + a = BN_new();
1.1663 + b = BN_new();
1.1664 + r = BN_new();
1.1665 + t = BN_new();
1.1666 + if (a == NULL || b == NULL || r == NULL || t == NULL) goto err;
1.1667 +
1.1668 + BN_GENCB_set(&cb, genprime_cb, NULL);
1.1669 +
1.1670 + /* We test BN_kronecker(a, b, ctx) just for b odd (Jacobi symbol).
1.1671 + * In this case we know that if b is prime, then BN_kronecker(a, b, ctx)
1.1672 + * is congruent to $a^{(b-1)/2}$, modulo $b$ (Legendre symbol).
1.1673 + * So we generate a random prime b and compare these values
1.1674 + * for a number of random a's. (That is, we run the Solovay-Strassen
1.1675 + * primality test to confirm that b is prime, except that we
1.1676 + * don't want to test whether b is prime but whether BN_kronecker
1.1677 + * works.) */
1.1678 +
1.1679 + if (!BN_generate_prime_ex(b, 512, 0, NULL, NULL, &cb)) goto err;
1.1680 + b->neg = rand_neg();
1.1681 + putc('\n', stderr);
1.1682 +
1.1683 + for (i = 0; i < num0; i++)
1.1684 + {
1.1685 + if (!BN_bntest_rand(a, 512, 0, 0)) goto err;
1.1686 + a->neg = rand_neg();
1.1687 +
1.1688 + /* t := (|b|-1)/2 (note that b is odd) */
1.1689 + if (!BN_copy(t, b)) goto err;
1.1690 + t->neg = 0;
1.1691 + if (!BN_sub_word(t, 1)) goto err;
1.1692 + if (!BN_rshift1(t, t)) goto err;
1.1693 + /* r := a^t mod b */
1.1694 + b->neg=0;
1.1695 +
1.1696 + if (!BN_mod_exp_recp(r, a, t, b, ctx)) goto err;
1.1697 + b->neg=1;
1.1698 +
1.1699 + if (BN_is_word(r, 1))
1.1700 + legendre = 1;
1.1701 + else if (BN_is_zero(r))
1.1702 + legendre = 0;
1.1703 + else
1.1704 + {
1.1705 + if (!BN_add_word(r, 1)) goto err;
1.1706 + if (0 != BN_ucmp(r, b))
1.1707 + {
1.1708 + fprintf(stderr, "Legendre symbol computation failed\n");
1.1709 + goto err;
1.1710 + }
1.1711 + legendre = -1;
1.1712 + }
1.1713 +
1.1714 + kronecker = BN_kronecker(a, b, ctx);
1.1715 + if (kronecker < -1) goto err;
1.1716 + /* we actually need BN_kronecker(a, |b|) */
1.1717 + if (a->neg && b->neg)
1.1718 + kronecker = -kronecker;
1.1719 +
1.1720 + if (legendre != kronecker)
1.1721 + {
1.1722 + fprintf(stderr, "legendre != kronecker; a = ");
1.1723 + BN_print_fp(stderr, a);
1.1724 + fprintf(stderr, ", b = ");
1.1725 + BN_print_fp(stderr, b);
1.1726 + fprintf(stderr, "\n");
1.1727 + goto err;
1.1728 + }
1.1729 +
1.1730 + putc('.', stderr);
1.1731 + fflush(stderr);
1.1732 + }
1.1733 +
1.1734 + putc('\n', stderr);
1.1735 + fflush(stderr);
1.1736 + ret = 1;
1.1737 + err:
1.1738 + if (a != NULL) BN_free(a);
1.1739 + if (b != NULL) BN_free(b);
1.1740 + if (r != NULL) BN_free(r);
1.1741 + if (t != NULL) BN_free(t);
1.1742 + return ret;
1.1743 + }
1.1744 +
1.1745 +int test_sqrt(BIO *bp, BN_CTX *ctx)
1.1746 + {
1.1747 + BN_GENCB cb;
1.1748 + BIGNUM *a,*p,*r;
1.1749 + int i, j;
1.1750 + int ret = 0;
1.1751 +
1.1752 + a = BN_new();
1.1753 + p = BN_new();
1.1754 + r = BN_new();
1.1755 + if (a == NULL || p == NULL || r == NULL) goto err;
1.1756 +
1.1757 + BN_GENCB_set(&cb, genprime_cb, NULL);
1.1758 +
1.1759 + for (i = 0; i < 16; i++)
1.1760 + {
1.1761 + if (i < 8)
1.1762 + {
1.1763 + unsigned primes[8] = { 2, 3, 5, 7, 11, 13, 17, 19 };
1.1764 +
1.1765 + if (!BN_set_word(p, primes[i])) goto err;
1.1766 + }
1.1767 + else
1.1768 + {
1.1769 + if (!BN_set_word(a, 32)) goto err;
1.1770 + if (!BN_set_word(r, 2*i + 1)) goto err;
1.1771 +
1.1772 + if (!BN_generate_prime_ex(p, 256, 0, a, r, &cb)) goto err;
1.1773 + putc('\n', stderr);
1.1774 + }
1.1775 + p->neg = rand_neg();
1.1776 +
1.1777 + for (j = 0; j < num2; j++)
1.1778 + {
1.1779 + /* construct 'a' such that it is a square modulo p,
1.1780 + * but in general not a proper square and not reduced modulo p */
1.1781 + if (!BN_bntest_rand(r, 256, 0, 3)) goto err;
1.1782 + if (!BN_nnmod(r, r, p, ctx)) goto err;
1.1783 + if (!BN_mod_sqr(r, r, p, ctx)) goto err;
1.1784 + if (!BN_bntest_rand(a, 256, 0, 3)) goto err;
1.1785 + if (!BN_nnmod(a, a, p, ctx)) goto err;
1.1786 + if (!BN_mod_sqr(a, a, p, ctx)) goto err;
1.1787 + if (!BN_mul(a, a, r, ctx)) goto err;
1.1788 + if (rand_neg())
1.1789 + if (!BN_sub(a, a, p)) goto err;
1.1790 +
1.1791 + if (!BN_mod_sqrt(r, a, p, ctx)) goto err;
1.1792 + if (!BN_mod_sqr(r, r, p, ctx)) goto err;
1.1793 +
1.1794 + if (!BN_nnmod(a, a, p, ctx)) goto err;
1.1795 +
1.1796 + if (BN_cmp(a, r) != 0)
1.1797 + {
1.1798 + fprintf(stderr, "BN_mod_sqrt failed: a = ");
1.1799 + BN_print_fp(stderr, a);
1.1800 + fprintf(stderr, ", r = ");
1.1801 + BN_print_fp(stderr, r);
1.1802 + fprintf(stderr, ", p = ");
1.1803 + BN_print_fp(stderr, p);
1.1804 + fprintf(stderr, "\n");
1.1805 + goto err;
1.1806 + }
1.1807 +
1.1808 + putc('.', stderr);
1.1809 + fflush(stderr);
1.1810 + }
1.1811 +
1.1812 + putc('\n', stderr);
1.1813 + fflush(stderr);
1.1814 + }
1.1815 + ret = 1;
1.1816 + err:
1.1817 + if (a != NULL) BN_free(a);
1.1818 + if (p != NULL) BN_free(p);
1.1819 + if (r != NULL) BN_free(r);
1.1820 + return ret;
1.1821 + }
1.1822 +
1.1823 +int test_lshift(BIO *bp,BN_CTX *ctx,BIGNUM *a_)
1.1824 + {
1.1825 + BIGNUM *a,*b,*c,*d;
1.1826 + int i;
1.1827 +
1.1828 + b=BN_new();
1.1829 + c=BN_new();
1.1830 + d=BN_new();
1.1831 + BN_one(c);
1.1832 +
1.1833 + if(a_)
1.1834 + a=a_;
1.1835 + else
1.1836 + {
1.1837 + a=BN_new();
1.1838 + BN_bntest_rand(a,200,0,0); /**/
1.1839 + a->neg=rand_neg();
1.1840 + }
1.1841 + for (i=0; i<num0; i++)
1.1842 + {
1.1843 + BN_lshift(b,a,i+1);
1.1844 + BN_add(c,c,c);
1.1845 + if (bp != NULL)
1.1846 + {
1.1847 + if (!results)
1.1848 + {
1.1849 + BN_print(bp,a);
1.1850 + BIO_puts(bp," * ");
1.1851 + BN_print(bp,c);
1.1852 + BIO_puts(bp," - ");
1.1853 + }
1.1854 + BN_print(bp,b);
1.1855 + BIO_puts(bp,"\n");
1.1856 + }
1.1857 + BN_mul(d,a,c,ctx);
1.1858 + BN_sub(d,d,b);
1.1859 + if(!BN_is_zero(d))
1.1860 + {
1.1861 + fprintf(stderr,"Left shift test failed!\n");
1.1862 + fprintf(stderr,"a=");
1.1863 + BN_print_fp(stderr,a);
1.1864 + fprintf(stderr,"\nb=");
1.1865 + BN_print_fp(stderr,b);
1.1866 + fprintf(stderr,"\nc=");
1.1867 + BN_print_fp(stderr,c);
1.1868 + fprintf(stderr,"\nd=");
1.1869 + BN_print_fp(stderr,d);
1.1870 + fprintf(stderr,"\n");
1.1871 + return 0;
1.1872 + }
1.1873 + }
1.1874 + BN_free(a);
1.1875 + BN_free(b);
1.1876 + BN_free(c);
1.1877 + BN_free(d);
1.1878 + return(1);
1.1879 + }
1.1880 +
1.1881 +int test_lshift1(BIO *bp)
1.1882 + {
1.1883 + BIGNUM *a,*b,*c;
1.1884 + int i;
1.1885 +
1.1886 + a=BN_new();
1.1887 + b=BN_new();
1.1888 + c=BN_new();
1.1889 +
1.1890 + BN_bntest_rand(a,200,0,0); /**/
1.1891 + a->neg=rand_neg();
1.1892 + for (i=0; i<num0; i++)
1.1893 + {
1.1894 + BN_lshift1(b,a);
1.1895 + if (bp != NULL)
1.1896 + {
1.1897 + if (!results)
1.1898 + {
1.1899 + BN_print(bp,a);
1.1900 + BIO_puts(bp," * 2");
1.1901 + BIO_puts(bp," - ");
1.1902 + }
1.1903 + BN_print(bp,b);
1.1904 + BIO_puts(bp,"\n");
1.1905 + }
1.1906 + BN_add(c,a,a);
1.1907 + BN_sub(a,b,c);
1.1908 + if(!BN_is_zero(a))
1.1909 + {
1.1910 + fprintf(stderr,"Left shift one test failed!\n");
1.1911 + return 0;
1.1912 + }
1.1913 +
1.1914 + BN_copy(a,b);
1.1915 + }
1.1916 + BN_free(a);
1.1917 + BN_free(b);
1.1918 + BN_free(c);
1.1919 + return(1);
1.1920 + }
1.1921 +
1.1922 +int test_rshift(BIO *bp,BN_CTX *ctx)
1.1923 + {
1.1924 + BIGNUM *a,*b,*c,*d,*e;
1.1925 + int i;
1.1926 +
1.1927 + a=BN_new();
1.1928 + b=BN_new();
1.1929 + c=BN_new();
1.1930 + d=BN_new();
1.1931 + e=BN_new();
1.1932 + BN_one(c);
1.1933 +
1.1934 + BN_bntest_rand(a,200,0,0); /**/
1.1935 + a->neg=rand_neg();
1.1936 + for (i=0; i<num0; i++)
1.1937 + {
1.1938 + BN_rshift(b,a,i+1);
1.1939 + BN_add(c,c,c);
1.1940 + if (bp != NULL)
1.1941 + {
1.1942 + if (!results)
1.1943 + {
1.1944 + BN_print(bp,a);
1.1945 + BIO_puts(bp," / ");
1.1946 + BN_print(bp,c);
1.1947 + BIO_puts(bp," - ");
1.1948 + }
1.1949 + BN_print(bp,b);
1.1950 + BIO_puts(bp,"\n");
1.1951 + }
1.1952 + BN_div(d,e,a,c,ctx);
1.1953 + BN_sub(d,d,b);
1.1954 + if(!BN_is_zero(d))
1.1955 + {
1.1956 + fprintf(stderr,"Right shift test failed!\n");
1.1957 + return 0;
1.1958 + }
1.1959 + }
1.1960 + BN_free(a);
1.1961 + BN_free(b);
1.1962 + BN_free(c);
1.1963 + BN_free(d);
1.1964 + BN_free(e);
1.1965 + return(1);
1.1966 + }
1.1967 +
1.1968 +int test_rshift1(BIO *bp)
1.1969 + {
1.1970 + BIGNUM *a,*b,*c;
1.1971 + int i;
1.1972 +
1.1973 + a=BN_new();
1.1974 + b=BN_new();
1.1975 + c=BN_new();
1.1976 +
1.1977 + BN_bntest_rand(a,200,0,0); /**/
1.1978 + a->neg=rand_neg();
1.1979 + for (i=0; i<num0; i++)
1.1980 + {
1.1981 + BN_rshift1(b,a);
1.1982 + if (bp != NULL)
1.1983 + {
1.1984 + if (!results)
1.1985 + {
1.1986 + BN_print(bp,a);
1.1987 + BIO_puts(bp," / 2");
1.1988 + BIO_puts(bp," - ");
1.1989 + }
1.1990 + BN_print(bp,b);
1.1991 + BIO_puts(bp,"\n");
1.1992 + }
1.1993 + BN_sub(c,a,b);
1.1994 + BN_sub(c,c,b);
1.1995 + if(!BN_is_zero(c) && !BN_abs_is_word(c, 1))
1.1996 + {
1.1997 + fprintf(stderr,"Right shift one test failed!\n");
1.1998 + return 0;
1.1999 + }
1.2000 + BN_copy(a,b);
1.2001 + }
1.2002 + BN_free(a);
1.2003 + BN_free(b);
1.2004 + BN_free(c);
1.2005 + return(1);
1.2006 + }
1.2007 +
1.2008 +int rand_neg(void)
1.2009 + {
1.2010 + static unsigned int neg=0;
1.2011 + static int sign[8]={0,0,0,1,1,0,1,1};
1.2012 +
1.2013 + return(sign[(neg++)%8]);
1.2014 + }