* primegen.c (gen_prime): Bail out if NBITS is less than 16.
authorWerner Koch <wk@gnupg.org>
Fri, 10 Oct 2003 14:17:21 +0000 (14:17 +0000)
committerWerner Koch <wk@gnupg.org>
Fri, 10 Oct 2003 14:17:21 +0000 (14:17 +0000)
(prime_generate_internal): Initialize prime variable to suppress
compiler warning.  Check pbits, initialize qbits when passed as
zero.

* primegen.c (prime_generate_internal): New arg
ALL_FACTORS. Changed all callers.
(gcry_prime_generate): Make the factors arg optional. Request
all_factors.
(gcry_prime_group_generator): New.
(gcry_prime_release_factors): New.

* global.c (_gcry_malloc): Handle the no_secure_memory option.

* gcrypt.h (gcry_prime_group_generator): New.
(gcry_prime_release_factors): New.

* prime.c (check_primes): Generate a generator and avoid printing
unless in verbose mode.

NEWS
cipher/ChangeLog
cipher/primegen.c
src/ChangeLog
src/gcrypt.h
src/global.c
tests/ChangeLog
tests/prime.c

diff --git a/NEWS b/NEWS
index d0c834e..1f2934a 100644 (file)
--- a/NEWS
+++ b/NEWS
@@ -2,6 +2,12 @@ Noteworthy changes in version 1.1.44 (unreleased)
 -------------------------------------------------
 
 
+ * Interface changes relative to the 1.1.43 release:
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+gcry_prime_group_generator      NEW
+gcry_prime_release_factors      NEW
+
+
 Noteworthy changes in version 1.1.43 (2003-09-04)
 -------------------------------------------------
 
index 30d4e4d..10ff54d 100644 (file)
@@ -1,3 +1,17 @@
+2003-10-10  Werner Koch  <wk@gnupg.org>
+
+       * primegen.c (gen_prime): Bail out if NBITS is less than 16.
+       (prime_generate_internal): Initialize prime variable to suppress
+       compiler warning.  Check pbits, initialize qbits when passed as
+       zero.
+
+       * primegen.c (prime_generate_internal): New arg
+       ALL_FACTORS. Changed all callers.
+       (gcry_prime_generate): Make the factors arg optional. Request
+       all_factors.
+       (gcry_prime_group_generator): New.
+       (gcry_prime_release_factors): New.
+
 2003-10-06  Werner Koch  <wk@gnupg.org>
 
        * primegen.c (gen_prime): Assert that NBITS is never zero, it
index b676bed..cc082e5 100644 (file)
@@ -177,7 +177,8 @@ _gcry_generate_public_prime( unsigned int nbits,
  * We do not need to use the strongest RNG because we gain no extra
  * security from it - The prime number is public and we could also
  * offer the factors for those who are willing to check that it is
- * indeed a strong prime.
+ * indeed a strong prime.  With ALL_FACTORS set to true all afcors of
+ * prime-1 are returned in FACTORS.
  *
  * mode 0: Standard
  *     1: Make sure that at least one factor is of size qbits.
@@ -187,9 +188,10 @@ prime_generate_internal (int mode,
                         gcry_mpi_t *prime_generated, unsigned int pbits,
                         unsigned int qbits, gcry_mpi_t g,
                         gcry_mpi_t **ret_factors,
-                        gcry_random_level_t random, unsigned int flags)
+                        gcry_random_level_t random, unsigned int flags,
+                         int all_factors)
 {
-  gcry_err_code_t err = GPG_ERR_NO_ERROR;
+  gcry_err_code_t err = 0;
   gcry_mpi_t *factors_new = NULL; /* Factors to return to the
                                     caller.  */
   gcry_mpi_t *factors = NULL;  /* Current factors.  */
@@ -200,18 +202,30 @@ prime_generate_internal (int mode,
   unsigned int n = 0;          /* Number of factors.  */
   unsigned int m = 0;          /* Number of primes in pool.  */
   gcry_mpi_t q = NULL;         /* First prime factor.  */
-  gcry_mpi_t prime;            /* Prime candidate.  */
+  gcry_mpi_t prime = NULL;     /* Prime candidate.  */
   unsigned int nprime = 0;     /* Bits of PRIME.  */
-  unsigned int req_qbits = qbits; /* The original QBITS value.  */
-  gcry_mpi_t val_2  = mpi_alloc_set_ui (2); /* For check_prime().  */
-  unsigned int is_secret = flags & GCRY_PRIME_FLAG_SECRET;
+  unsigned int req_qbits;       /* The original QBITS value.  */
+  gcry_mpi_t val_2;             /* For check_prime().  */
+  unsigned int is_secret = (flags & GCRY_PRIME_FLAG_SECRET);
   unsigned int count1 = 0, count2 = 0;
   unsigned int i = 0, j = 0;
-  
+
+  if (pbits < 48)
+    return GPG_ERR_INV_ARG;
+
+  /* If QBITS is not given, assume a reasonable value. */
+  if (!qbits)
+    qbits = pbits / 3;
+
+  req_qbits = qbits;
+
   /* Find number of needed prime factors.  */
-  for (n = 1; (pbits - qbits - 1) / n  >= qbits; n++);
+  for (n = 1; (pbits - qbits - 1) / n  >= qbits; n++)
+    ;
   n--;
 
+  val_2 = mpi_alloc_set_ui (2);
+
   if ((! n) || ((mode == 1) && (n < 2)))
     err = GPG_ERR_INV_ARG;
 
@@ -381,9 +395,19 @@ prime_generate_internal (int mode,
     if (ret_factors)
       {
        /* Caller wants the factors.  */
-       factors_new = gcry_calloc (n + 2, sizeof (*factors_new));
+       factors_new = gcry_calloc (n + 4, sizeof (*factors_new));
        if (! factors_new)
          err = GPG_ERR_INTERNAL;       /* FIXME.  */
+        else if (all_factors)
+          {
+           i = 0;
+            (factors_new)[i++] = gcry_mpi_set_ui (NULL, 2);
+            (factors_new)[i++] = mpi_copy (q);
+           if (mode == 1)
+              (factors_new)[i++] = mpi_copy (q_factor);
+            for(j=0; j < n; j++)
+              (factors_new)[i++] = mpi_copy (factors[j]);
+          }
        else
          {
            i = 0;
@@ -490,7 +514,7 @@ _gcry_generate_elg_prime (int mode, unsigned pbits, unsigned qbits,
   gcry_mpi_t prime = NULL;
   
   err = prime_generate_internal (mode, &prime, pbits, qbits, g,
-                                ret_factors, GCRY_WEAK_RANDOM, 0);
+                                ret_factors, GCRY_WEAK_RANDOM, 0, 0);
 
   return prime;
 }
@@ -508,8 +532,8 @@ gen_prime (unsigned int nbits, int secret, int randomlevel,
   if( 0 && DBG_CIPHER )
     log_debug ("generate a prime of %u bits ", nbits );
 
-  if (!nbits)
-    log_fatal ("trying to generate a prime of zero bits\n");
+  if (nbits < 16)
+    log_fatal ("can't generate a prime with less than %d bits\n", 16);
 
   mods = gcry_xmalloc( no_of_small_prime_numbers * sizeof *mods );
   /* make nbits fit into gcry_mpi_t implementation */
@@ -815,8 +839,9 @@ gcry_prime_generate (gcry_mpi_t *prime, unsigned int prime_bits,
 
   /* Generate.  */
   err = prime_generate_internal (mode, &prime_generated, prime_bits,
-                                factor_bits, NULL, &factors_generated,
-                                random_level, flags);
+                                factor_bits, NULL,
+                                 factors? &factors_generated : NULL,
+                                random_level, flags, 1);
 
   if (! err)
     if (cb_func)
@@ -829,18 +854,21 @@ gcry_prime_generate (gcry_mpi_t *prime, unsigned int prime_bits,
            unsigned int i;
 
            mpi_free (prime_generated);
-           for (i = 0; factors_generated[i]; i++)
-             mpi_free (factors_generated[i]);
-           gcry_free (factors_generated);
+            if (factors)
+              {
+                for (i = 0; factors_generated[i]; i++)
+                  mpi_free (factors_generated[i]);
+                gcry_free (factors_generated);
+              }
            err = GPG_ERR_INTERNAL; /* FIXME.  */
          }
       }
 
   if (! err)
     {
-      /* Done.  */
+      if (factors)
+        *factors = factors_generated;
       *prime = prime_generated;
-      *factors = factors_generated;
     }
 
   return gcry_error (err);
@@ -860,3 +888,89 @@ gcry_prime_check (gcry_mpi_t x, unsigned int flags)
 
   return gcry_error (err);
 }
+
+/* Find a generator for PRIME where the factorization of (prime-1) is
+   in the NULL terminated array FACTORS. Return the generator as a
+   newly allocated MPI in R_G.  If START_G is not NULL, use this as s
+   atart for the search. Returns 0 on success.*/
+gcry_error_t
+gcry_prime_group_generator (gcry_mpi_t *r_g,
+                            gcry_mpi_t prime, gcry_mpi_t *factors,
+                            gcry_mpi_t start_g)
+{
+  gcry_mpi_t tmp = gcry_mpi_new (0);
+  gcry_mpi_t b = gcry_mpi_new (0);
+  gcry_mpi_t pmin1 = gcry_mpi_new (0);
+  gcry_mpi_t g = start_g? gcry_mpi_copy (start_g) : gcry_mpi_set_ui (NULL, 3);
+  int first = 1;
+  int i, n;
+
+  if (!factors || !r_g || !prime)
+    return gpg_error (GPG_ERR_INV_ARG);
+
+  for (n=0; factors[n]; n++)
+    ;
+  if (n < 2)
+    return gpg_error (GPG_ERR_INV_ARG);
+
+#if 1 /* Extra sanity check - usually disabled. */  
+  {
+    mpi_set (tmp, factors[0]);
+    for(i = 1; i < n; i++)
+        mpi_mul (tmp, tmp, factors[i]);
+    mpi_add_ui (tmp, tmp, 1);
+    if (mpi_cmp (prime, tmp))
+      return gpg_error (GPG_ERR_INV_ARG);
+  }
+#endif /* Extra sanity check. */
+  
+  gcry_mpi_sub_ui (pmin1, prime, 1);      
+  do         
+    {
+      if (first)
+        first = 0;
+      else
+        gcry_mpi_add_ui (g, g, 1);
+      
+      if (DBG_CIPHER)
+        {
+          log_debug ("checking g:");
+          gcry_mpi_dump (g);
+          log_debug ("\n");
+        }
+      else
+        progress('^');
+      
+      for (i = 0; i < n; i++)
+        {
+          mpi_fdiv_q (tmp, pmin1, factors[i]);
+          gcry_mpi_powm (b, g, tmp, prime);
+          if (! mpi_cmp_ui (b, 1))
+            break;
+        }
+      if (DBG_CIPHER)
+        progress('\n');
+    }
+  while (i < n);
+  
+  gcry_mpi_release (tmp);
+  gcry_mpi_release (b); 
+  gcry_mpi_release (pmin1); 
+  *r_g = g; 
+
+  return 0; 
+}
+
+/* Convenience function to release the factors array. */
+void
+gcry_prime_release_factors (gcry_mpi_t *factors)
+{
+  if (factors)
+    {
+      int i;
+      
+      for (i=0; factors[i]; i++)
+        mpi_free (factors[i]);
+      gcry_free (factors);
+    }
+}
index b032512..77fbeb3 100644 (file)
@@ -1,3 +1,10 @@
+2003-10-10  Werner Koch  <wk@gnupg.org>
+
+       * global.c (_gcry_malloc): Handle the no_secure_memory option.
+
+       * gcrypt.h (gcry_prime_group_generator): New.
+       (gcry_prime_release_factors): New.
+
 2003-10-07  Werner Koch  <wk@gnupg.org>
 
        * sexp.c (sexp_sscan): Check that parenthesis are matching.
index de3c6f2..5f04255 100644 (file)
@@ -1228,6 +1228,19 @@ gcry_error_t gcry_prime_generate (gcry_mpi_t *prime,
                                  gcry_random_level_t random_level,
                                  unsigned int flags);
 
+/* Find a generator for PRIME where the factorization of (prime-1) is
+   in the NULL terminated array FACTORS. Return the generator as a
+   newly allocated MPI in R_G.  If START_G is not NULL, use this as
+   teh start for the search. */
+gcry_error_t gcry_prime_group_generator (gcry_mpi_t *r_g,
+                                         gcry_mpi_t prime, gcry_mpi_t *factors,
+                                         gcry_mpi_t start_g);
+
+
+/* Convenience function to release the FACTORS array. */
+void gcry_prime_release_factors (gcry_mpi_t *factors);
+
+
 /* Check wether the number X is prime.  */
 gcry_error_t gcry_prime_check (gcry_mpi_t x, unsigned int flags);
 
index d7d9418..02a6767 100644 (file)
@@ -383,7 +383,7 @@ _gcry_malloc (size_t n, unsigned int flags, void **mem)
   gcry_err_code_t err = GPG_ERR_NO_ERROR;
   void *m = NULL;
 
-  if (flags & GCRY_ALLOC_FLAG_SECURE)
+  if ((flags & GCRY_ALLOC_FLAG_SECURE) && !no_secure_memory)
     {
       if (alloc_secure_func)
        m = (*alloc_secure_func) (n);
@@ -474,7 +474,8 @@ gcry_calloc (size_t n, size_t m)
   size_t bytes;
   void *p;
 
-  bytes = n * m; /* size_t is unsigned so the behavior on overflow is defined. */
+  bytes = n * m; /* size_t is unsigned so the behavior on overflow is
+                    defined. */
   if (m && bytes / m != n) 
     {
       errno = ENOMEM;
index 77660ff..2129aa0 100644 (file)
@@ -1,3 +1,8 @@
+2003-10-10  Werner Koch  <wk@gnupg.org>
+
+       * prime.c (check_primes): Generate a generator and avoid printing
+       unless in verbose mode.
+
 2003-10-07  Werner Koch  <wk@gnupg.org>
 
        * tsexp.c (check_sscan): New.
index aa10149..625c153 100644 (file)
@@ -23,7 +23,7 @@
 
 #include "../src/gcrypt.h"
 
-static int verbose, debug;
+static int verbose;
 
 static void
 die (const char *format, ...)
@@ -42,6 +42,7 @@ check_primes (void)
   gcry_error_t err = GPG_ERR_NO_ERROR;
   gcry_mpi_t *factors = NULL;
   gcry_mpi_t prime = NULL;
+  gcry_mpi_t g;
   unsigned int i = 0;
   struct prime_spec
   {
@@ -51,6 +52,7 @@ check_primes (void)
   } prime_specs[] =
     {
       { 1024, 100, GCRY_PRIME_FLAG_SPECIAL_FACTOR },
+      { 128, 0, 0 },
       { 0 },
     };
 
@@ -64,11 +66,29 @@ check_primes (void)
                                 GCRY_WEAK_RANDOM,
                                 prime_specs[i].flags);
       assert (! err);
-      printf ("%i: ", i);
-      gcry_mpi_dump (prime);
-      putchar ('\n');
+      if (verbose)
+        {
+          fprintf (stderr, "test %d: p = ", i);
+          gcry_mpi_dump (prime);
+          putc ('\n', stderr);
+        }
+
       err = gcry_prime_check (prime, 0);
       assert (! err);
+
+      err = gcry_prime_group_generator (&g, prime, factors, NULL);
+      assert (!err);
+      gcry_prime_release_factors (factors); factors = NULL;
+      
+      if (verbose)
+        {
+          fprintf (stderr, "     %d: g = ", i);
+          gcry_mpi_dump (g);
+          putc ('\n', stderr);
+        }
+      gcry_mpi_release (g);
+
+
       gcry_mpi_add_ui (prime, prime, 1);
       err = gcry_prime_check (prime, 0);
       assert (err);
@@ -85,10 +105,10 @@ main (int argc, char **argv)
   else if ((argc > 1) && (! strcmp (argv[1], "--debug")))
     verbose = debug = 1;
 
+  gcry_control (GCRYCTL_DISABLE_SECMEM, 0);
   if (! gcry_check_version (GCRYPT_VERSION))
     die ("version mismatch\n");
 
-  gcry_control (GCRYCTL_DISABLE_SECMEM, 0);
   gcry_control (GCRYCTL_INITIALIZATION_FINISHED, 0);
   if (debug)
     gcry_control (GCRYCTL_SET_DEBUG_FLAGS, 1u, 0);