Turn BN_prime_checks into a macro.
authorBodo Möller <bodo@openssl.org>
Wed, 12 Jan 2000 11:57:30 +0000 (11:57 +0000)
committerBodo Möller <bodo@openssl.org>
Wed, 12 Jan 2000 11:57:30 +0000 (11:57 +0000)
Primes p where (p-1)/2 is prime too are called "safe", not "strong".

CHANGES
crypto/bn/bn.h
crypto/bn/bn_prime.c
crypto/bn/bn_prime.h
crypto/dh/dh_check.c
crypto/rsa/rsa_chk.c

diff --git a/CHANGES b/CHANGES
index aa62657..8ec7107 100644 (file)
--- a/CHANGES
+++ b/CHANGES
@@ -4,6 +4,14 @@
 
  Changes between 0.9.4 and 0.9.5  [xx XXX 1999]
 
+  *) Do more iterations of Rabin-Miller probable prime test (specifically,
+     3 for 1024-bit primes, 6 for 512-bit primes, 12 for 256-bit primes
+     instead of only 2 for all lengths; see BN_prime_checks definition
+     in crypto/bn/bn.h for the complete table).  This guarantees a
+     false-positive rate of at most 2^-80 (actually less because we are
+     additionally doing trial division) for random input.
+     [Bodo Moeller]
+
   *) Rewrite ssl3_read_n (ssl/s3_pkt.c) avoiding a couple of bugs.
      [Bodo Moeller]
 
index f935e1c..dd1d263 100644 (file)
@@ -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);
index 6fa0f9b..57305c7 100644 (file)
@@ -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;
index c10217d..8bb1685 100644 (file)
@@ -55,6 +55,7 @@
  * copied and put under another distribution licence
  * [including the GNU Public Licence.]
  */
+
 #ifndef EIGHT_BIT
 #define NUMPRIMES 2048
 #else
index 95ce9cf..a2e7433 100644 (file)
@@ -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;
index 91b9115..03497f8 100644 (file)
@@ -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;