diff options
Diffstat (limited to 'crypto/openssl/crypto/bn/bn_prime.c')
-rw-r--r-- | crypto/openssl/crypto/bn/bn_prime.c | 378 |
1 files changed, 198 insertions, 180 deletions
diff --git a/crypto/openssl/crypto/bn/bn_prime.c b/crypto/openssl/crypto/bn/bn_prime.c index 6fa0f9b..a5f01b9 100644 --- a/crypto/openssl/crypto/bn/bn_prime.c +++ b/crypto/openssl/crypto/bn/bn_prime.c @@ -55,6 +55,59 @@ * copied and put under another distribution licence * [including the GNU Public Licence.] */ +/* ==================================================================== + * Copyright (c) 1998-2000 The OpenSSL Project. All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * 1. Redistributions of source code must retain the above copyright + * 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 + * the documentation and/or other materials provided with the + * distribution. + * + * 3. All advertising materials mentioning features or use of this + * software must display the following acknowledgment: + * "This product includes software developed by the OpenSSL Project + * for use in the OpenSSL Toolkit. (http://www.openssl.org/)" + * + * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to + * endorse or promote products derived from this software without + * prior written permission. For written permission, please contact + * openssl-core@openssl.org. + * + * 5. Products derived from this software may not be called "OpenSSL" + * nor may "OpenSSL" appear in their names without prior written + * permission of the OpenSSL Project. + * + * 6. Redistributions of any form whatsoever must retain the following + * acknowledgment: + * "This product includes software developed by the OpenSSL Project + * for use in the OpenSSL Toolkit (http://www.openssl.org/)" + * + * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY + * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR + * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR + * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; + * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT 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. + * ==================================================================== + * + * This product includes cryptographic software written by Eric Young + * (eay@cryptsoft.com). This product includes software written by Tim + * Hudson (tjh@cryptsoft.com). + * + */ #include <stdio.h> #include <time.h> @@ -62,26 +115,29 @@ #include "bn_lcl.h" #include <openssl/rand.h> -/* The quick seive algorithm approach to weeding out primes is +/* The quick sieve algorithm approach to weeding out primes is * Philip Zimmermann's, as implemented in PGP. I have had a read of * his comments and implemented my own version. */ #include "bn_prime.h" -static int witness(BIGNUM *a, BIGNUM *n, BN_CTX *ctx,BN_CTX *ctx2, - BN_MONT_CTX *mont); +static int witness(BIGNUM *w, const BIGNUM *a, const BIGNUM *a1, + 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, BIGNUM *add, BIGNUM *rem, BN_CTX *ctx); -static int probable_prime_dh_strong(BIGNUM *rnd, int bits, +static int probable_prime_dh_safe(BIGNUM *rnd, int bits, BIGNUM *add, BIGNUM *rem, BN_CTX *ctx); -BIGNUM *BN_generate_prime(BIGNUM *ret, int bits, int strong, BIGNUM *add, + +BIGNUM *BN_generate_prime(BIGNUM *ret, int bits, int safe, BIGNUM *add, BIGNUM *rem, void (*callback)(int,int,void *), void *cb_arg) { BIGNUM *rnd=NULL; BIGNUM t; + 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; @@ -100,9 +156,9 @@ loop: } else { - if (strong) + if (safe) { - if (!probable_prime_dh_strong(rnd,bits,add,rem,ctx)) + if (!probable_prime_dh_safe(rnd,bits,add,rem,ctx)) goto err; } else @@ -114,160 +170,185 @@ loop: /* if (BN_mod_word(rnd,(BN_ULONG)3) == 1) goto loop; */ if (callback != NULL) callback(0,c1++,cb_arg); - if (!strong) + if (!safe) { - i=BN_is_prime(rnd,BN_prime_checks,callback,ctx,cb_arg); + i=BN_is_prime_fasttest(rnd,checks,callback,ctx,cb_arg,0); if (i == -1) goto err; if (i == 0) goto loop; } else { - /* for a strong prime generation, + /* 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,rnd)) goto err; - for (i=0; i<BN_prime_checks; i++) + for (i=0; i<checks; i++) { - j=BN_is_prime(rnd,1,callback,ctx,cb_arg); + j=BN_is_prime_fasttest(rnd,1,callback,ctx,cb_arg,0); if (j == -1) goto err; if (j == 0) goto loop; - j=BN_is_prime(&t,1,callback,ctx,cb_arg); + j=BN_is_prime_fasttest(&t,1,callback,ctx,cb_arg,0); if (j == -1) goto err; if (j == 0) goto loop; if (callback != NULL) callback(2,c1-1,cb_arg); - /* We have a strong prime test pass */ + /* We have a safe prime test pass */ } } /* we have a prime :-) */ - ret=rnd; + found = 1; err: - if ((ret == NULL) && (rnd != NULL)) BN_free(rnd); + if (!found && (ret == NULL) && (rnd != NULL)) BN_free(rnd); BN_free(&t); if (ctx != NULL) BN_CTX_free(ctx); - return(ret); + return(found ? rnd : NULL); } -int BN_is_prime(BIGNUM *a, int checks, void (*callback)(int,int,void *), - BN_CTX *ctx_passed, void *cb_arg) +int BN_is_prime(const BIGNUM *a, int checks, void (*callback)(int,int,void *), + BN_CTX *ctx_passed, void *cb_arg) { - int i,j,c2=0,ret= -1; - BIGNUM *check; - BN_CTX *ctx=NULL,*ctx2=NULL; - BN_MONT_CTX *mont=NULL; + return BN_is_prime_fasttest(a, checks, callback, ctx_passed, cb_arg, 0); + } +int BN_is_prime_fasttest(const BIGNUM *a, int checks, + void (*callback)(int,int,void *), + BN_CTX *ctx_passed, void *cb_arg, + int do_trial_division) + { + int i, j, ret = -1; + int k; + BN_CTX *ctx = NULL; + BIGNUM *A1, *A1_odd, *check; /* taken from ctx */ + BN_MONT_CTX *mont = NULL; + const BIGNUM *A = NULL; + + if (checks == BN_prime_checks) + checks = BN_prime_checks_for_size(BN_num_bits(a)); + + /* first look for small factors */ if (!BN_is_odd(a)) return(0); + if (do_trial_division) + { + for (i = 1; i < NUMPRIMES; i++) + if (BN_mod_word(a, primes[i]) == 0) + return 0; + if (callback != NULL) callback(1, -1, cb_arg); + } + if (ctx_passed != NULL) - ctx=ctx_passed; + ctx = ctx_passed; else - if ((ctx=BN_CTX_new()) == NULL) goto err; - - if ((ctx2=BN_CTX_new()) == NULL) goto err; - if ((mont=BN_MONT_CTX_new()) == NULL) goto err; - - check= &(ctx->bn[ctx->tos++]); + if ((ctx=BN_CTX_new()) == NULL) + goto err; + BN_CTX_start(ctx); - /* Setup the montgomery structure */ - if (!BN_MONT_CTX_set(mont,a,ctx2)) goto err; + /* A := abs(a) */ + if (a->neg) + { + BIGNUM *t; + if ((t = BN_CTX_get(ctx)) == NULL) goto err; + BN_copy(t, a); + t->neg = 0; + A = t; + } + else + A = a; + A1 = BN_CTX_get(ctx); + A1_odd = BN_CTX_get(ctx); + check = BN_CTX_get(ctx); + 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)) + { + ret = 0; + goto err; + } - for (i=0; i<checks; i++) + /* write A1 as A1_odd * 2^k */ + k = 1; + while (!BN_is_bit_set(A1, k)) + k++; + if (!BN_rshift(A1_odd, A1, k)) + goto err; + + /* Montgomery setup for computations mod A */ + mont = BN_MONT_CTX_new(); + if (mont == NULL) + goto err; + if (!BN_MONT_CTX_set(mont, A, ctx)) + goto err; + + for (i = 0; i < checks; i++) { - if (!BN_rand(check,BN_num_bits(a)-1,0,0)) goto err; - j=witness(check,a,ctx,ctx2,mont); + if (!BN_pseudo_rand(check, BN_num_bits(A1), 0, 0)) + goto err; + if (BN_cmp(check, A1) >= 0) + if (!BN_sub(check, check, A1)) + goto err; + if (!BN_add_word(check, 1)) + goto err; + /* now 1 <= check < A */ + + j = witness(check, A, A1, A1_odd, k, ctx, mont); if (j == -1) goto err; if (j) { ret=0; goto err; } - if (callback != NULL) callback(1,c2++,cb_arg); + if (callback != NULL) callback(1,i,cb_arg); } ret=1; err: - ctx->tos--; - if ((ctx_passed == NULL) && (ctx != NULL)) - BN_CTX_free(ctx); - if (ctx2 != NULL) - BN_CTX_free(ctx2); - if (mont != NULL) BN_MONT_CTX_free(mont); - + 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); } -#define RECP_MUL_MOD - -static int witness(BIGNUM *a, BIGNUM *n, BN_CTX *ctx, BN_CTX *ctx2, - BN_MONT_CTX *mont) +static int witness(BIGNUM *w, const BIGNUM *a, const BIGNUM *a1, + const BIGNUM *a1_odd, int k, BN_CTX *ctx, BN_MONT_CTX *mont) { - int k,i,ret= -1,good; - BIGNUM *d,*dd,*tmp,*d1,*d2,*n1; - BIGNUM *mont_one,*mont_n1,*mont_a; - - d1= &(ctx->bn[ctx->tos]); - d2= &(ctx->bn[ctx->tos+1]); - n1= &(ctx->bn[ctx->tos+2]); - ctx->tos+=3; - - mont_one= &(ctx2->bn[ctx2->tos]); - mont_n1= &(ctx2->bn[ctx2->tos+1]); - mont_a= &(ctx2->bn[ctx2->tos+2]); - ctx2->tos+=3; - - d=d1; - dd=d2; - if (!BN_one(d)) goto err; - if (!BN_sub(n1,n,d)) goto err; /* n1=n-1; */ - k=BN_num_bits(n1); - - if (!BN_to_montgomery(mont_one,BN_value_one(),mont,ctx2)) goto err; - if (!BN_to_montgomery(mont_n1,n1,mont,ctx2)) goto err; - if (!BN_to_montgomery(mont_a,a,mont,ctx2)) goto err; - - BN_copy(d,mont_one); - for (i=k-1; i>=0; i--) + 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) { - if ( (BN_cmp(d,mont_one) != 0) && - (BN_cmp(d,mont_n1) != 0)) - good=1; - else - good=0; - - BN_mod_mul_montgomery(dd,d,d,mont,ctx2); - - if (good && (BN_cmp(dd,mont_one) == 0)) - { - ret=1; - goto err; - } - if (BN_is_bit_set(n1,i)) - { - BN_mod_mul_montgomery(d,dd,mont_a,mont,ctx2); - } - else - { - tmp=d; - d=dd; - dd=tmp; - } + if (!BN_mod_mul(w, w, w, a, ctx)) /* w := w^2 mod a */ + return -1; + if (BN_is_one(w)) + return 1; /* 'a' is composite, otherwise a previous 'w' would + * have been == -1 (mod 'a') */ + if (BN_cmp(w, a1) == 0) + return 0; /* w == -1 (mod a), 'a' is probably prime */ } - if (BN_cmp(d,mont_one) == 0) - i=0; - else i=1; - ret=i; -err: - ctx->tos-=3; - ctx2->tos-=3; - return(ret); + /* 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 */ + return 1; } static int probable_prime(BIGNUM *rnd, int bits) { int i; - MS_STATIC BN_ULONG mods[NUMPRIMES]; + BN_ULONG mods[NUMPRIMES]; BN_ULONG delta,d; again: @@ -285,7 +366,7 @@ again: d=delta; delta+=2; /* perhaps need to check for overflow of - * delta (but delta can be upto 2^32) + * delta (but delta can be up to 2^32) * 21-May-98 eay - added overflow check */ if (delta < d) goto again; goto loop; @@ -301,7 +382,8 @@ static int probable_prime_dh(BIGNUM *rnd, int bits, BIGNUM *add, BIGNUM *rem, int i,ret=0; BIGNUM *t1; - t1= &(ctx->bn[ctx->tos++]); + BN_CTX_start(ctx); + if ((t1 = BN_CTX_get(ctx)) == NULL) goto err; if (!BN_rand(rnd,bits,0,1)) goto err; @@ -327,20 +409,22 @@ static int probable_prime_dh(BIGNUM *rnd, int bits, BIGNUM *add, BIGNUM *rem, } ret=1; err: - ctx->tos--; + BN_CTX_end(ctx); return(ret); } -static int probable_prime_dh_strong(BIGNUM *p, int bits, BIGNUM *padd, +static int probable_prime_dh_safe(BIGNUM *p, int bits, BIGNUM *padd, BIGNUM *rem, BN_CTX *ctx) { int i,ret=0; - BIGNUM *t1,*qadd=NULL,*q=NULL; + BIGNUM *t1,*qadd,*q; bits--; - t1= &(ctx->bn[ctx->tos++]); - q= &(ctx->bn[ctx->tos++]); - qadd= &(ctx->bn[ctx->tos++]); + BN_CTX_start(ctx); + t1 = BN_CTX_get(ctx); + q = BN_CTX_get(ctx); + qadd = BN_CTX_get(ctx); + if (qadd == NULL) goto err; if (!BN_rshift1(qadd,padd)) goto err; @@ -376,72 +460,6 @@ static int probable_prime_dh_strong(BIGNUM *p, int bits, BIGNUM *padd, } ret=1; err: - ctx->tos-=3; - return(ret); - } - -#if 0 -static int witness(BIGNUM *a, BIGNUM *n, BN_CTX *ctx) - { - int k,i,nb,ret= -1; - BIGNUM *d,*dd,*tmp; - BIGNUM *d1,*d2,*x,*n1,*inv; - - d1= &(ctx->bn[ctx->tos]); - d2= &(ctx->bn[ctx->tos+1]); - x= &(ctx->bn[ctx->tos+2]); - n1= &(ctx->bn[ctx->tos+3]); - inv=&(ctx->bn[ctx->tos+4]); - ctx->tos+=5; - - d=d1; - dd=d2; - if (!BN_one(d)) goto err; - if (!BN_sub(n1,n,d)) goto err; /* n1=n-1; */ - k=BN_num_bits(n1); - - /* i=BN_num_bits(n); */ -#ifdef RECP_MUL_MOD - nb=BN_reciprocal(inv,n,ctx); /**/ - if (nb == -1) goto err; -#endif - - for (i=k-1; i>=0; i--) - { - if (BN_copy(x,d) == NULL) goto err; -#ifndef RECP_MUL_MOD - if (!BN_mod_mul(dd,d,d,n,ctx)) goto err; -#else - if (!BN_mod_mul_reciprocal(dd,d,d,n,inv,nb,ctx)) goto err; -#endif - if ( BN_is_one(dd) && - !BN_is_one(x) && - (BN_cmp(x,n1) != 0)) - { - ret=1; - goto err; - } - if (BN_is_bit_set(n1,i)) - { -#ifndef RECP_MUL_MOD - if (!BN_mod_mul(d,dd,a,n,ctx)) goto err; -#else - if (!BN_mod_mul_reciprocal(d,dd,a,n,inv,nb,ctx)) goto err; -#endif - } - else - { - tmp=d; - d=dd; - dd=tmp; - } - } - if (BN_is_one(d)) - i=0; - else i=1; - ret=i; -err: - ctx->tos-=5; + BN_CTX_end(ctx); return(ret); } -#endif |