Made gcry_prime_check more robust (and slower).
authorWerner Koch <wk@gnupg.org>
Mon, 22 Aug 2005 09:30:25 +0000 (09:30 +0000)
committerWerner Koch <wk@gnupg.org>
Mon, 22 Aug 2005 09:30:25 +0000 (09:30 +0000)
cipher/ChangeLog
cipher/primegen.c

index 0a536fe..fbb4f8d 100644 (file)
@@ -1,3 +1,11 @@
+2005-08-22  Werner Koch  <wk@g10code.com>
+
+       * primegen.c (check_prime): New arg RM_ROUNDS.
+       (prime_generate_internal): Call it here with 5 rounds as used
+       before.
+       (gcry_prime_check): But here with 64 rounds.
+       (is_prime): Make sure never to use less than 5 rounds.
+
 2005-04-16  Moritz Schulte  <moritz@g10code.com>
 
        * ac.c (_gcry_ac_init): New function.
index afd435e..7e80517 100644 (file)
@@ -39,7 +39,7 @@
 static gcry_mpi_t gen_prime (unsigned int nbits, int secret, int randomlevel, 
                              int (*extra_check)(void *, gcry_mpi_t),
                              void *extra_check_arg);
-static int check_prime( gcry_mpi_t prime, gcry_mpi_t val_2,
+static int check_prime( gcry_mpi_t prime, gcry_mpi_t val_2, int rm_rounds,
                         gcry_prime_check_func_t cb_func, void *cb_arg );
 static int is_prime( gcry_mpi_t n, int steps, int *count );
 static void m_out_of_n( char *array, int m, int n );
@@ -372,7 +372,8 @@ prime_generate_internal (int mode,
        else
          count2 = 0;
     }
-  while (! ((nprime == pbits) && check_prime (prime, val_2, cb_func, cb_arg)));
+  while (! ((nprime == pbits) && check_prime (prime, val_2, 5,
+                                              cb_func, cb_arg)));
 
   if (DBG_CIPHER)
     {
@@ -637,9 +638,10 @@ gen_prime (unsigned int nbits, int secret, int randomlevel,
 
 /****************
  * Returns: true if this may be a prime
+ * RM_ROUNDS gives the number of Rabin-Miller tests to run.
  */
 static int
-check_prime( gcry_mpi_t prime, gcry_mpi_t val_2,
+check_prime( gcry_mpi_t prime, gcry_mpi_t val_2, int rm_rounds,
              gcry_prime_check_func_t cb_func, void *cb_arg)
 {
   int i;
@@ -673,7 +675,7 @@ check_prime( gcry_mpi_t prime, gcry_mpi_t val_2,
   if (!cb_func || cb_func (cb_arg, GCRY_PRIME_CHECK_AT_MAYBE_PRIME, prime))
     {
       /* Perform stronger tests. */
-      if ( is_prime( prime, 5, &count ) )
+      if ( is_prime( prime, rm_rounds, &count ) )
         {
           if (!cb_func
               || cb_func (cb_arg, GCRY_PRIME_CHECK_AT_GOT_PRIME, prime))
@@ -701,6 +703,9 @@ is_prime (gcry_mpi_t n, int steps, int *count)
   int rc = 0;
   unsigned nbits = mpi_get_nbits( n );
 
+  if (steps < 5) /* Make sure that we do at least 5 rounds. */
+    steps = 5; 
+
   mpi_sub_ui( nminus1, n, 1 );
 
   /* Find q and k, so that n = 1 + 2^k * q . */
@@ -935,7 +940,9 @@ gcry_prime_check (gcry_mpi_t x, unsigned int flags)
   gcry_err_code_t err = GPG_ERR_NO_ERROR;
   gcry_mpi_t val_2 = mpi_alloc_set_ui (2); /* Used by the Fermat test. */
 
-  if (! check_prime (x, val_2, NULL, NULL))
+  /* We use 64 rounds because the prime we are going to test is not
+     guaranteed to be a random one. */
+  if (! check_prime (x, val_2, 64, NULL, NULL))
     err = GPG_ERR_NO_PRIME;
 
   mpi_free (val_2);