From 2e8879604fe3abbc2431ca79a4a923f1e87da75e Mon Sep 17 00:00:00 2001 From: jsing <> Date: Thu, 8 May 2014 13:20:49 +0000 Subject: Emergency knfectomie requested by tedu@. --- src/lib/libcrypto/bn/bn_prime.c | 393 +++++++++++++++++++++------------------- 1 file changed, 209 insertions(+), 184 deletions(-) (limited to 'src/lib/libcrypto/bn/bn_prime.c') diff --git a/src/lib/libcrypto/bn/bn_prime.c b/src/lib/libcrypto/bn/bn_prime.c index 7b25979dd1..7d4cab4acd 100644 --- a/src/lib/libcrypto/bn/bn_prime.c +++ b/src/lib/libcrypto/bn/bn_prime.c @@ -5,21 +5,21 @@ * This package is an SSL implementation written * by Eric Young (eay@cryptsoft.com). * The implementation was written so as to conform with Netscapes SSL. - * + * * This library is free for commercial and non-commercial use as long as * the following conditions are aheared to. The following conditions * apply to all code found in this distribution, be it the RC4, RSA, * lhash, DES, etc., code; not just the SSL code. The SSL documentation * included with this distribution is covered by the same copyright terms * except that the holder is Tim Hudson (tjh@cryptsoft.com). - * + * * Copyright remains Eric Young's, and as such any Copyright notices in * the code are not to be removed. * If this package is used in a product, Eric Young should be given attribution * as the author of the parts of the library used. * This can be in the form of a textual message at program startup or * in documentation (online or textual) provided with the package. - * + * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: @@ -34,10 +34,10 @@ * Eric Young (eay@cryptsoft.com)" * The word 'cryptographic' can be left out if the rouines from the library * being used are not cryptographic related :-). - * 4. If you include any Windows specific code (or a derivative thereof) from + * 4. If you include any Windows specific code (or a derivative thereof) from * the apps directory (application code) you must include an acknowledgement: * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)" - * + * * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE @@ -49,7 +49,7 @@ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF * SUCH DAMAGE. - * + * * The licence and distribution terms for any publically available version or * derivative of this code cannot be changed. i.e. this code cannot simply be * copied and put under another distribution licence @@ -63,7 +63,7 @@ * are met: * * 1. Redistributions of source code must retain the above copyright - * notice, this list of conditions and the following disclaimer. + * notice, this list of conditions and the following disclaimer. * * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in @@ -127,22 +127,23 @@ #include "bn_prime.h" static int witness(BIGNUM *w, const BIGNUM *a, const BIGNUM *a1, - const BIGNUM *a1_odd, int k, BN_CTX *ctx, BN_MONT_CTX *mont); + const BIGNUM *a1_odd, int k, BN_CTX *ctx, BN_MONT_CTX *mont); static int probable_prime(BIGNUM *rnd, int bits); static int probable_prime_dh(BIGNUM *rnd, int bits, - const BIGNUM *add, const BIGNUM *rem, BN_CTX *ctx); + const BIGNUM *add, const BIGNUM *rem, BN_CTX *ctx); static int probable_prime_dh_safe(BIGNUM *rnd, int bits, - const BIGNUM *add, const BIGNUM *rem, BN_CTX *ctx); + const BIGNUM *add, const BIGNUM *rem, BN_CTX *ctx); -int BN_GENCB_call(BN_GENCB *cb, int a, int b) - { +int +BN_GENCB_call(BN_GENCB *cb, int a, int b) +{ /* No callback means continue */ - if(!cb) return 1; - switch(cb->ver) - { + if (!cb) + return 1; + switch (cb->ver) { case 1: /* Deprecated-style callbacks */ - if(!cb->cb.cb_1) + if (!cb->cb.cb_1) return 1; cb->cb.cb_1(a, b, cb->arg); return 1; @@ -151,98 +152,101 @@ int BN_GENCB_call(BN_GENCB *cb, int a, int b) return cb->cb.cb_2(a, b, cb); default: break; - } + } /* Unrecognised callback type */ return 0; - } +} -int BN_generate_prime_ex(BIGNUM *ret, int bits, int safe, - const BIGNUM *add, const BIGNUM *rem, BN_GENCB *cb) - { +int +BN_generate_prime_ex(BIGNUM *ret, int bits, int safe, const BIGNUM *add, + const BIGNUM *rem, BN_GENCB *cb) +{ BIGNUM *t; - int found=0; - int i,j,c1=0; + int found = 0; + int i, j, c1 = 0; BN_CTX *ctx; int checks = BN_prime_checks_for_size(bits); - ctx=BN_CTX_new(); - if (ctx == NULL) goto err; + ctx = BN_CTX_new(); + if (ctx == NULL) + goto err; BN_CTX_start(ctx); t = BN_CTX_get(ctx); - if(!t) goto err; -loop: + if (!t) + goto err; +loop: /* make a random number and set the top and bottom bits */ - if (add == NULL) - { - if (!probable_prime(ret,bits)) goto err; - } - else - { - if (safe) - { - if (!probable_prime_dh_safe(ret,bits,add,rem,ctx)) - goto err; - } - else - { - if (!probable_prime_dh(ret,bits,add,rem,ctx)) + if (add == NULL) { + if (!probable_prime(ret, bits)) + goto err; + } else { + if (safe) { + if (!probable_prime_dh_safe(ret, bits, add, rem, ctx)) + goto err; + } else { + if (!probable_prime_dh(ret, bits, add, rem, ctx)) goto err; - } } + } /* if (BN_mod_word(ret,(BN_ULONG)3) == 1) goto loop; */ - if(!BN_GENCB_call(cb, 0, c1++)) + if (!BN_GENCB_call(cb, 0, c1++)) /* aborted */ goto err; - if (!safe) - { - i=BN_is_prime_fasttest_ex(ret,checks,ctx,0,cb); - if (i == -1) goto err; - if (i == 0) goto loop; - } - else - { + if (!safe) { + i = BN_is_prime_fasttest_ex(ret, checks, ctx, 0, cb); + if (i == -1) + goto err; + if (i == 0) + goto loop; + } else { /* for "safe prime" generation, * check that (p-1)/2 is prime. * Since a prime is odd, We just * need to divide by 2 */ - if (!BN_rshift1(t,ret)) goto err; + if (!BN_rshift1(t, ret)) + goto err; - for (i=0; i a is prime if and only if a == 2 */ return BN_is_word(a, 2); - if (do_trial_division) - { + if (do_trial_division) { for (i = 1; i < NUMPRIMES; i++) - if (BN_mod_word(a, primes[i]) == 0) + if (BN_mod_word(a, primes[i]) == 0) return 0; - if(!BN_GENCB_call(cb, 1, -1)) + if (!BN_GENCB_call(cb, 1, -1)) goto err; - } + } if (ctx_passed != NULL) ctx = ctx_passed; - else - if ((ctx=BN_CTX_new()) == NULL) - goto err; + else if ((ctx = BN_CTX_new()) == NULL) + goto err; BN_CTX_start(ctx); /* A := abs(a) */ - if (a->neg) - { + if (a->neg) { BIGNUM *t; - if ((t = BN_CTX_get(ctx)) == NULL) goto err; + if ((t = BN_CTX_get(ctx)) == NULL) + goto err; BN_copy(t, a); t->neg = 0; A = t; - } - else + } else A = a; A1 = BN_CTX_get(ctx); A1_odd = BN_CTX_get(ctx); check = BN_CTX_get(ctx); - if (check == NULL) goto err; + if (check == NULL) + goto err; /* compute A1 := A - 1 */ if (!BN_copy(A1, A)) goto err; if (!BN_sub_word(A1, 1)) goto err; - if (BN_is_zero(A1)) - { + if (BN_is_zero(A1)) { ret = 0; goto err; - } + } /* write A1 as A1_odd * 2^k */ k = 1; @@ -316,9 +317,8 @@ int BN_is_prime_fasttest_ex(const BIGNUM *a, int checks, BN_CTX *ctx_passed, goto err; if (!BN_MONT_CTX_set(mont, A, ctx)) goto err; - - for (i = 0; i < checks; i++) - { + + for (i = 0; i < checks; i++) { if (!BN_pseudo_rand_range(check, A1)) goto err; if (!BN_add_word(check, 1)) @@ -326,40 +326,41 @@ int BN_is_prime_fasttest_ex(const BIGNUM *a, int checks, BN_CTX *ctx_passed, /* now 1 <= check < A */ j = witness(check, A, A1, A1_odd, k, ctx, mont); - if (j == -1) goto err; - if (j) - { - ret=0; + if (j == -1) goto err; - } - if(!BN_GENCB_call(cb, 1, i)) + if (j) { + ret = 0; goto err; } - ret=1; + if (!BN_GENCB_call(cb, 1, i)) + goto err; + } + ret = 1; + err: - if (ctx != NULL) - { + if (ctx != NULL) { BN_CTX_end(ctx); if (ctx_passed == NULL) BN_CTX_free(ctx); - } + } if (mont != NULL) BN_MONT_CTX_free(mont); - return(ret); - } + return (ret); +} -static int witness(BIGNUM *w, const BIGNUM *a, const BIGNUM *a1, - const BIGNUM *a1_odd, int k, BN_CTX *ctx, BN_MONT_CTX *mont) - { - if (!BN_mod_exp_mont(w, w, a1_odd, a, ctx, mont)) /* w := w^a1_odd mod a */ +static int +witness(BIGNUM *w, const BIGNUM *a, const BIGNUM *a1, const BIGNUM *a1_odd, + int k, BN_CTX *ctx, BN_MONT_CTX *mont) +{ + if (!BN_mod_exp_mont(w, w, a1_odd, a, ctx, mont)) + /* w := w^a1_odd mod a */ return -1; if (BN_is_one(w)) return 0; /* probably prime */ if (BN_cmp(w, a1) == 0) return 0; /* w == -1 (mod a), 'a' is probably prime */ - while (--k) - { + while (--k) { if (!BN_mod_mul(w, w, w, a, ctx)) /* w := w^2 mod a */ return -1; if (BN_is_one(w)) @@ -367,128 +368,152 @@ static int witness(BIGNUM *w, const BIGNUM *a, const BIGNUM *a1, * have been == -1 (mod 'a') */ if (BN_cmp(w, a1) == 0) return 0; /* w == -1 (mod a), 'a' is probably prime */ - } + } /* If we get here, 'w' is the (a-1)/2-th power of the original 'w', * and it is neither -1 nor +1 -- so 'a' cannot be prime */ bn_check_top(w); return 1; - } +} -static int probable_prime(BIGNUM *rnd, int bits) - { +static int +probable_prime(BIGNUM *rnd, int bits) +{ int i; prime_t mods[NUMPRIMES]; - BN_ULONG delta,maxdelta; + BN_ULONG delta, maxdelta; again: - if (!BN_rand(rnd,bits,1,1)) return(0); + if (!BN_rand(rnd, bits, 1, 1)) + return (0); /* we now have a random number 'rand' to test. */ - for (i=1; i maxdelta) goto again; + if (((mods[i] + delta) % primes[i]) <= 1) { + delta += 2; + if (delta > maxdelta) + goto again; goto loop; - } } - if (!BN_add_word(rnd,delta)) return(0); - bn_check_top(rnd); - return(1); } - -static int probable_prime_dh(BIGNUM *rnd, int bits, - const BIGNUM *add, const BIGNUM *rem, BN_CTX *ctx) - { - int i,ret=0; + if (!BN_add_word(rnd, delta)) + return (0); + bn_check_top(rnd); + return (1); +} + +static int +probable_prime_dh(BIGNUM *rnd, int bits, const BIGNUM *add, const BIGNUM *rem, + BN_CTX *ctx) +{ + int i, ret = 0; BIGNUM *t1; BN_CTX_start(ctx); - if ((t1 = BN_CTX_get(ctx)) == NULL) goto err; + if ((t1 = BN_CTX_get(ctx)) == NULL) + goto err; - if (!BN_rand(rnd,bits,0,1)) goto err; + if (!BN_rand(rnd, bits, 0, 1)) + goto err; /* we need ((rnd-rem) % add) == 0 */ - if (!BN_mod(t1,rnd,add,ctx)) goto err; - if (!BN_sub(rnd,rnd,t1)) goto err; - if (rem == NULL) - { if (!BN_add_word(rnd,1)) goto err; } - else - { if (!BN_add(rnd,rnd,rem)) goto err; } + if (!BN_mod(t1, rnd, add, ctx)) + goto err; + if (!BN_sub(rnd, rnd, t1)) + goto err; + if (rem == NULL) { + if (!BN_add_word(rnd, 1)) + goto err; + } else { + if (!BN_add(rnd, rnd, rem)) + goto err; + } /* we now have a random number 'rand' to test. */ - loop: for (i=1; i