From 58964a492275ca9a59a0cd9c8155cb2491b4b909 Mon Sep 17 00:00:00 2001 From: "Ralf S. Engelschall" Date: Mon, 21 Dec 1998 10:56:39 +0000 Subject: Import of old SSLeay release: SSLeay 0.9.0b --- crypto/bn/bn_prime.c | 172 ++++++++++++++++++++++++++++++++++++++------------- 1 file changed, 128 insertions(+), 44 deletions(-) (limited to 'crypto/bn/bn_prime.c') diff --git a/crypto/bn/bn_prime.c b/crypto/bn/bn_prime.c index 07a8289..0c85f70 100644 --- a/crypto/bn/bn_prime.c +++ b/crypto/bn/bn_prime.c @@ -1,5 +1,5 @@ /* crypto/bn/bn_prime.c */ -/* Copyright (C) 1995-1997 Eric Young (eay@cryptsoft.com) +/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) * All rights reserved. * * This package is an SSL implementation written @@ -69,7 +69,8 @@ #include "bn_prime.h" #ifndef NOPROTO -static int witness(BIGNUM *a, BIGNUM *n, BN_CTX *ctx); +static int witness(BIGNUM *a, BIGNUM *n, BN_CTX *ctx,BN_CTX *ctx2, + 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); @@ -82,12 +83,13 @@ static int probable_prime_dh(); static int probable_prime_dh_strong(); #endif -BIGNUM *BN_generate_prime(bits,strong,add,rem,callback) +BIGNUM *BN_generate_prime(bits,strong,add,rem,callback,cb_arg) int bits; int strong; BIGNUM *add; BIGNUM *rem; -void (*callback)(P_I_I); +void (*callback)(P_I_I_P); +char *cb_arg; { BIGNUM *rnd=NULL; BIGNUM *ret=NULL; @@ -120,11 +122,11 @@ loop: } } /* if (BN_mod_word(rnd,(BN_ULONG)3) == 1) goto loop; */ - if (callback != NULL) callback(0,c1++); + if (callback != NULL) callback(0,c1++,cb_arg); if (!strong) { - i=BN_is_prime(rnd,BN_prime_checks,callback,ctx); + i=BN_is_prime(rnd,BN_prime_checks,callback,ctx,cb_arg); if (i == -1) goto err; if (i == 0) goto loop; } @@ -138,15 +140,15 @@ loop: for (i=0; ibn[ctx->tos++]; + + /* Setup the montgomery structure */ + if (!BN_MONT_CTX_set(mont,a,ctx2)) goto err; + for (i=0; itos--; 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); return(ret); } #define RECP_MUL_MOD -static int witness(a, n,ctx) +static int witness(a,n,ctx,ctx2,mont) BIGNUM *a; BIGNUM *n; -BN_CTX *ctx; +BN_CTX *ctx,*ctx2; +BN_MONT_CTX *mont; { - int k,i,nb,ret= -1; - BIGNUM *d,*dd,*tmp; - BIGNUM *d1,*d2,*x,*n1,*inv; + 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]; - x=ctx->bn[ctx->tos+2]; - n1=ctx->bn[ctx->tos+3]; - inv=ctx->bn[ctx->tos+4]; - ctx->tos+=5; + 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; @@ -220,34 +240,29 @@ BN_CTX *ctx; 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 + 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_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)) + 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)) { -#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 + BN_mod_mul_montgomery(d,dd,mont_a,mont,ctx2); } else { @@ -256,12 +271,13 @@ BN_CTX *ctx; dd=tmp; } } - if (BN_is_one(d)) + if (BN_cmp(d,mont_one) == 0) i=0; else i=1; ret=i; err: - ctx->tos-=5; + ctx->tos-=3; + ctx2->tos-=3; return(ret); } @@ -387,3 +403,71 @@ err: return(ret); } +#if 0 +static int witness(a, n,ctx) +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; + return(ret); + } +#endif -- cgit v1.1