diff options
author | Bodo Möller <bodo@openssl.org> | 2000-01-12 11:57:30 +0000 |
---|---|---|
committer | Bodo Möller <bodo@openssl.org> | 2000-01-12 11:57:30 +0000 |
commit | 76aa0ddc86772080db4f61821b9ff357e330c843 (patch) | |
tree | 156e6551fb083163ca4717274f3970601bf7946e /crypto | |
parent | e4b76456310f6a337c471ec5c7525bc65e4e40d5 (diff) |
Turn BN_prime_checks into a macro.
Primes p where (p-1)/2 is prime too are called "safe", not "strong".
Diffstat (limited to 'crypto')
-rw-r--r-- | crypto/bn/bn.h | 20 | ||||
-rw-r--r-- | crypto/bn/bn_prime.c | 21 | ||||
-rw-r--r-- | crypto/bn/bn_prime.h | 1 | ||||
-rw-r--r-- | crypto/dh/dh_check.c | 4 | ||||
-rw-r--r-- | crypto/rsa/rsa_chk.c | 4 |
5 files changed, 34 insertions, 16 deletions
diff --git a/crypto/bn/bn.h b/crypto/bn/bn.h index f935e1ca79..dd1d263098 100644 --- a/crypto/bn/bn.h +++ b/crypto/bn/bn.h @@ -283,7 +283,23 @@ typedef struct bn_recp_ctx_st #define BN_to_montgomery(r,a,mont,ctx) BN_mod_mul_montgomery(\ r,a,&((mont)->RR),(mont),ctx) -#define BN_prime_checks (5) +/* number of Miller-Rabin iterations for an error rate of less than 2^-80 + * for random 'b'-bit input, b >= 100 (taken from table 4.4 in the Handbook + * of Applied Cryptography [Menezes, van Oorschot, Vanstone; CRC Press 1996]; + * original paper: Damgaard, Landrock, Pomerance: Average case error estimates + * for the strong probable prime test. -- Math. Comp. 61 (1993) 177-194) */ +#define BN_prime_checks(b) ((b) >= 1300 ? 2 : \ + (b) >= 850 ? 3 : \ + (b) >= 650 ? 4 : \ + (b) >= 550 ? 5 : \ + (b) >= 450 ? 6 : \ + (b) >= 400 ? 7 : \ + (b) >= 350 ? 8 : \ + (b) >= 300 ? 9 : \ + (b) >= 250 ? 12 : \ + (b) >= 200 ? 15 : \ + (b) >= 150 ? 18 : \ + /* b >= 100 */ 27) #define BN_num_bytes(a) ((BN_num_bits(a)+7)/8) #define BN_is_word(a,w) (((a)->top == 1) && ((a)->d[0] == (BN_ULONG)(w))) @@ -381,7 +397,7 @@ int BN_hex2bn(BIGNUM **a, const char *str); int BN_dec2bn(BIGNUM **a, const char *str); int BN_gcd(BIGNUM *r,BIGNUM *in_a,BIGNUM *in_b,BN_CTX *ctx); BIGNUM *BN_mod_inverse(BIGNUM *ret,BIGNUM *a, const BIGNUM *n,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); int BN_is_prime(BIGNUM *p,int nchecks,void (*callback)(int,int,void *), BN_CTX *ctx,void *cb_arg); diff --git a/crypto/bn/bn_prime.c b/crypto/bn/bn_prime.c index 6fa0f9be1e..57305c7273 100644 --- a/crypto/bn/bn_prime.c +++ b/crypto/bn/bn_prime.c @@ -73,15 +73,16 @@ static int witness(BIGNUM *a, BIGNUM *n, BN_CTX *ctx,BN_CTX *ctx2, 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 i,j,c1=0; BN_CTX *ctx; + int checks = BN_prime_checks(bits); ctx=BN_CTX_new(); if (ctx == NULL) goto err; @@ -100,9 +101,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,21 +115,21 @@ 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(rnd,checks,callback,ctx,cb_arg); 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); if (j == -1) goto err; @@ -139,7 +140,7 @@ loop: 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 :-) */ @@ -331,7 +332,7 @@ err: 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; diff --git a/crypto/bn/bn_prime.h b/crypto/bn/bn_prime.h index c10217dfea..8bb168517d 100644 --- a/crypto/bn/bn_prime.h +++ b/crypto/bn/bn_prime.h @@ -55,6 +55,7 @@ * copied and put under another distribution licence * [including the GNU Public Licence.] */ + #ifndef EIGHT_BIT #define NUMPRIMES 2048 #else diff --git a/crypto/dh/dh_check.c b/crypto/dh/dh_check.c index 95ce9cfad0..a2e7433b9c 100644 --- a/crypto/dh/dh_check.c +++ b/crypto/dh/dh_check.c @@ -102,12 +102,12 @@ int DH_check(DH *dh, int *ret) else *ret|=DH_UNABLE_TO_CHECK_GENERATOR; - if (!BN_is_prime(dh->p,BN_prime_checks,NULL,ctx,NULL)) + if (!BN_is_prime(dh->p,BN_prime_checks(BN_num_bits(dh->p)),NULL,ctx,NULL)) *ret|=DH_CHECK_P_NOT_PRIME; else { if (!BN_rshift1(q,dh->p)) goto err; - if (!BN_is_prime(q,BN_prime_checks,NULL,ctx,NULL)) + if (!BN_is_prime(q,BN_prime_checks(BN_num_bits(q)),NULL,ctx,NULL)) *ret|=DH_CHECK_P_NOT_STRONG_PRIME; } ok=1; diff --git a/crypto/rsa/rsa_chk.c b/crypto/rsa/rsa_chk.c index 91b9115798..03497f8463 100644 --- a/crypto/rsa/rsa_chk.c +++ b/crypto/rsa/rsa_chk.c @@ -75,7 +75,7 @@ int RSA_check_key(RSA *key) } /* p prime? */ - r = BN_is_prime(key->p, BN_prime_checks, NULL, NULL, NULL); + r = BN_is_prime(key->p, BN_prime_checks(BN_num_bits(key->p)), NULL, NULL, NULL); if (r != 1) { ret = r; @@ -85,7 +85,7 @@ int RSA_check_key(RSA *key) } /* q prime? */ - r = BN_is_prime(key->q, BN_prime_checks, NULL, NULL, NULL); + r = BN_is_prime(key->q, BN_prime_checks(BN_num_bits(key->q)), NULL, NULL, NULL); if (r != 1) { ret = r; |