Generate safe primes not divisible by 3, 5 or 7.
authorFelix Laurie von Massenbach <felix@erbridge.co.uk>
Tue, 27 May 2014 01:12:59 +0000 (02:12 +0100)
committerBen Laurie <ben@links.org>
Sun, 1 Jun 2014 14:31:26 +0000 (15:31 +0100)
~2% speed improvement on trial division.

apps/speed.c
crypto/bn/bn_lcl.h
crypto/bn/bn_prime.c

index 84d0829..78b7923 100644 (file)
@@ -56,7 +56,7 @@
  * [including the GNU Public Licence.]
  */
 /* ====================================================================
- * Copyright 2002 Sun Microsystems, Inc. ALL RIGHTS RESERVED.
+ * Copyright 2002-2014 Sun Microsystems, Inc. ALL RIGHTS RESERVED.
  *
  * Portions of the attached software ("Contribution") are developed by 
  * SUN MICROSYSTEMS, INC., and are contributed to the OpenSSL project.
@@ -2054,7 +2054,7 @@ int MAIN(int argc, char **argv)
                        
                Time_F(START);
                for (count=0, run=1; COND(prime_c[D_PRIME_COPRIME]); count++)
-                       bn_probable_prime_dh_coprime(rnd, 1024, add, NULL, ctx);
+                       bn_probable_prime_dh_coprime_safe(rnd, 1024, add, NULL, ctx);
                
                d=Time_F(STOP);
                prime_print_result(D_PRIME_COPRIME, count, d);
@@ -2700,9 +2700,9 @@ static void print_result(int alg,int run_no,int count,double time_used)
 static void prime_print_result(int alg, int count, double time_used)
        {
        BIO_printf(bio_err,
-                          mr ? "+R:%d:%s:%f:%f\n" : "%d %s's in %.2fs (%.2fms/run)\n",
+                          mr ? "+R:%d:%s:%f:%f\n" : "%d %s's in %.2fs (%.2f microseconds / run)\n",
                           count, prime_names[alg], time_used,
-                          time_used / ((double)count) * 1000);
+                          time_used / ((double)count) * 1000000);
        }
 
 #ifndef NO_FORK
index fc54dce..f0cfaea 100644 (file)
@@ -536,7 +536,7 @@ BIGNUM *int_bn_mod_inverse(BIGNUM *in,
 
 int bn_probable_prime_dh(BIGNUM *rnd, int bits,
        const BIGNUM *add, const BIGNUM *rem, BN_CTX *ctx);
-int bn_probable_prime_dh_coprime(BIGNUM *rnd, int bits,
+int bn_probable_prime_dh_coprime_safe(BIGNUM *rnd, int bits,
        const BIGNUM *add, const BIGNUM *rem, BN_CTX *ctx);
 
 #ifdef  __cplusplus
index b303a48..90f840f 100644 (file)
@@ -134,7 +134,10 @@ static int probable_prime_dh(BIGNUM *rnd, const BIGNUM *add,
 static int probable_prime_dh_safe(BIGNUM *rnd, int bits,
        const BIGNUM *add, const BIGNUM *rem, BN_CTX *ctx);
 
-static int prime_offsets[8] = { 7, 11, 13, 17, 19, 23, 29, 31 };
+static int prime_multiplier = 210;
+static int prime_offsets[8] = { 23, 47, 59, 83, 107, 143, 167, 179 };
+static int prime_offset_count = 8;
+static int prime_offset_count_exponent = 3;
 
 int BN_GENCB_call(BN_GENCB *cb, int a, int b)
        {
@@ -372,20 +375,27 @@ int bn_probable_prime_dh(BIGNUM *rnd, int bits,
        return(probable_prime_dh(rnd, add, rem, ctx, 1));
        }
 
-int bn_probable_prime_dh_coprime(BIGNUM *rnd, int bits,
+int bn_probable_prime_dh_coprime_safe(BIGNUM *rnd, int bits,
        const BIGNUM *add, const BIGNUM *rem, BN_CTX *ctx)
        {
+       int i = prime_offset_count;
        BIGNUM *offset_index = BN_new();
 
        if (!BN_rand(rnd, bits, 0, 1)) return(0);
-       if (!BN_rand(offset_index, 3, -1, -1)) return(0);
+       
+       while (i >= prime_offset_count)
+               {
+               if (!BN_rand(offset_index, prime_offset_count_exponent, -1, -1))
+                       return(0);
+               i = BN_get_word(offset_index);
+               }
 
-       BN_mul_word(rnd, 30);
-       BN_add_word(rnd, prime_offsets[BN_get_word(offset_index)]);
+       BN_mul_word(rnd, prime_multiplier);
+       BN_add_word(rnd, prime_offsets[i]);
        
        BN_free(offset_index);
 
-       return(probable_prime_dh(rnd, add, rem, ctx, 3));
+       return(probable_prime_dh(rnd, add, rem, ctx, 4));
        }
 
 static int witness(BIGNUM *w, const BIGNUM *a, const BIGNUM *a1,