2003-09-02 Moritz Schulte <mo@g10code.com>
authorMoritz Schulte <mo@g10code.com>
Tue, 2 Sep 2003 00:42:41 +0000 (00:42 +0000)
committerMoritz Schulte <mo@g10code.com>
Tue, 2 Sep 2003 00:42:41 +0000 (00:42 +0000)
* primegen.c (gcry_prime_check, gcry_prime_generate): New
functions.
(prime_generate_internal): New function, based on
_gcry_generate_elg_prime.
(_gcry_generate_elg_prime): Rewritten as a wrapper for
prime_generate_internal.

cipher/ChangeLog
cipher/primegen.c

index 5cdcd9a..4c2d9bc 100644 (file)
@@ -1,3 +1,12 @@
+2003-09-02  Moritz Schulte  <mo@g10code.com>
+
+       * primegen.c (gcry_prime_check, gcry_prime_generate): New
+       functions.
+       (prime_generate_internal): New function, based on
+       _gcry_generate_elg_prime.
+       (_gcry_generate_elg_prime): Rewritten as a wrapper for
+       prime_generate_internal.
+
 2003-08-28  Werner Koch  <wk@gnupg.org>
 
        * pubkey.c (gcry_pk_encrypt): Don't include the flags list in the
index 9575532..e74eed9 100644 (file)
  */
 
 #include <config.h>
+
 #include <stdio.h>
 #include <stdlib.h>
 #include <string.h>
 #include <assert.h>
+
 #include "g10lib.h"
 #include "mpi.h"
 #include "cipher.h"
@@ -180,205 +182,318 @@ _gcry_generate_public_prime( unsigned int nbits,
  * mode 0: Standard
  *     1: Make sure that at least one factor is of size qbits.
  */
-gcry_mpi_t
-_gcry_generate_elg_prime( int mode, unsigned pbits, unsigned qbits,
-                   gcry_mpi_t g, gcry_mpi_t **ret_factors )
+static gcry_err_code_t
+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)
 {
-    int n;  /* number of factors */
-    int m;  /* number of primes in pool */
-    unsigned fbits; /* length of prime factors */
-    gcry_mpi_t *factors; /* current factors */
-    gcry_mpi_t *pool;  /* pool of primes */
-    gcry_mpi_t q;      /* first prime factor (variable)*/
-    gcry_mpi_t prime;  /* prime test value */
-    gcry_mpi_t q_factor; /* used for mode 1 */
-    byte *perms = NULL;
-    int i, j;
-    int count1, count2;
-    unsigned nprime;
-    unsigned req_qbits = qbits; /* the requested q bits size */
-    gcry_mpi_t val_2  = mpi_alloc_set_ui( 2 );
-
-    /* find number of needed prime factors */
-    for(n=1; (pbits - qbits - 1) / n  >= qbits; n++ )
-       ;
-    n--;
-    if( !n || (mode==1 && n < 2) )
-       log_fatal("can't gen prime with pbits=%u qbits=%u\n", pbits, qbits );
-    if( mode == 1 ) {
-       n--;
-       fbits = (pbits - 2*req_qbits -1) / n;
-       qbits =  pbits - req_qbits - n*fbits;
-    }
-    else {
-       fbits = (pbits - req_qbits -1) / n;
-       qbits = pbits - n*fbits;
+  gcry_err_code_t err = GPG_ERR_NO_ERROR;
+  gcry_mpi_t *factors_new = NULL; /* Factors to return to the
+                                    caller.  */
+  gcry_mpi_t *factors = NULL;  /* Current factors.  */
+  gcry_mpi_t *pool = NULL;     /* Pool of primes.  */
+  unsigned char *perms = NULL; /* Permutations of POOL.  */
+  gcry_mpi_t q_factor = NULL;  /* Used if QBITS is non-zero.  */
+  unsigned int fbits = 0;      /* Length of prime factors.  */
+  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.  */
+  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 count1 = 0, count2 = 0;
+  unsigned int i = 0, j = 0;
+  
+  /* Find number of needed prime factors.  */
+  for (n = 1; (pbits - qbits - 1) / n  >= qbits; n++);
+  n--;
+
+  if ((! n) || ((mode == 1) && (n < 2)))
+    err = GPG_ERR_INV_ARG;
+
+  if (! err)
+    {
+      if (mode == 1)
+       {
+         n--;
+         fbits = (pbits - 2 * req_qbits -1) / n;
+         qbits =  pbits - req_qbits - n * fbits;
+       }
+      else
+       {
+         fbits = (pbits - req_qbits -1) / n;
+         qbits = pbits - n * fbits;
+       }
+      
+      if (DBG_CIPHER)
+       log_debug ("gen prime: pbits=%u qbits=%u fbits=%u/%u n=%d\n",
+                  pbits, req_qbits, qbits, fbits, n);
+
+      prime = gcry_mpi_new (pbits);
+
+      /* Generate first prime factor.  */
+      q = gen_prime (qbits, is_secret, random, NULL, NULL);
+
+      if (mode == 1)
+       q_factor = gen_prime (req_qbits, is_secret, random, NULL, NULL);
+
+      /* Allocate an array to hold the factors + 2 for later
+        usage.  */
+      factors = gcry_calloc (n + 2, sizeof (*factors));
+      if (! factors)
+       err = GPG_ERR_INTERNAL; /* FIXME.  */
     }
-    if( DBG_CIPHER )
-       log_debug("gen prime: pbits=%u qbits=%u fbits=%u/%u n=%d\n",
-                   pbits, req_qbits, qbits, fbits, n  );
-    prime = gcry_mpi_new ( pbits  );
-    q = gen_prime( qbits, 0, 0, NULL, NULL );
-    q_factor = mode==1? gen_prime( req_qbits, 0, 0, NULL, NULL ) : NULL;
-
-    /* allocate an array to hold the factors + 2 for later usage */
-    factors = gcry_xcalloc( n+2, sizeof *factors );
-
-    /* make a pool of 3n+5 primes (this is an arbitrary value) */
-    m = n*3+5;
-    if( mode == 1 )
-       m += 5; /* need some more for DSA */
-    if( m < 25 )
+
+  if (! err)
+    {
+      /* Make a pool of 3n+5 primes (this is an arbitrary value).  */
+
+      m = n * 3 + 5;
+      if (mode == 1)
+       /* Need some more (for e.g. DSA).  */
+       m += 5;
+      if (m < 25)
        m = 25;
-    pool = gcry_xcalloc( m , sizeof *pool );
+      pool = gcry_calloc (m , sizeof (*pool));
+      if (! pool)
+       err = GPG_ERR_INTERNAL;
+    }
 
-    /* permutate over the pool of primes */
-    count1=count2=0;
-    do {
+  if (! err)
+    /* Permutate over the pool of primes.  */
+    do
+      {
       next_try:
-       if( !perms ) {
-           /* allocate new primes */
-           for(i=0; i < m; i++ ) {
-               mpi_free(pool[i]);
+       if (! perms)
+         {
+           /* Allocate new primes.  */
+           for(i = 0; i < m; i++)
+             {
+               mpi_free (pool[i]);
                pool[i] = NULL;
-           }
-           /* init m_out_of_n() */
-           perms = gcry_xcalloc( 1, m );
-           for(i=0; i < n; i++ ) {
-               perms[i] = 1;
-               pool[i] = gen_prime( fbits, 0, 1, NULL, NULL );
-               factors[i] = pool[i];
-           }
-       }
-       else {
-           m_out_of_n( perms, n, m );
-           for(i=j=0; i < m && j < n ; i++ )
-               if( perms[i] ) {
-                   if( !pool[i] )
-                       pool[i] = gen_prime( fbits, 0, 1, NULL, NULL );
-                   factors[j++] = pool[i];
+             }
+
+           /* Init m_out_of_n().  */
+           perms = gcry_calloc (1, m);
+           if (! perms)
+             err = GPG_ERR_INTERNAL; /* FIXME.  */
+           else
+             {
+               for(i = 0; i < n; i++)
+                 {
+                   perms[i] = 1;
+                   pool[i] = gen_prime (fbits, is_secret, random, NULL, NULL);
+                   factors[i] = pool[i];
+                 }
+             }
+
+           if (err)
+             break;
+         }
+       else
+         {
+           m_out_of_n (perms, n, m);
+           for(i = j = 0; (i < m) && (j < n); i++)
+             if (perms[i])
+               {
+                 if(! pool[i])
+                   pool[i] = gen_prime (fbits, 0, 1, NULL, NULL);
+                 factors[j++] = pool[i];
                }
-           if( i == n ) {
-               gcry_free(perms); perms = NULL;
+           if (i == n)
+             {
+               gcry_free(perms);
+               perms = NULL;
                progress('!');
-               goto next_try;  /* allocate new primes */
-           }
-       }
-
-       mpi_set( prime, q );
-       mpi_mul_ui( prime, prime, 2 );
-       if( mode == 1 )
-           mpi_mul( prime, prime, q_factor );
-       for(i=0; i < n; i++ )
-           mpi_mul( prime, prime, factors[i] );
-       mpi_add_ui( prime, prime, 1 );
-       nprime = mpi_get_nbits(prime);
-       if( nprime < pbits ) {
-           if( ++count1 > 20 ) {
+               goto next_try;  /* Allocate new primes.  */
+             }
+         }
+
+       /* Generate next prime candidate:
+
+       p = 2 * q [ * q_factor] * factor_0 * factor_1 * ... * factor_n + 1.  */
+
+       mpi_set (prime, q);
+       mpi_mul_ui (prime, prime, 2);
+       if (mode == 1)
+         mpi_mul (prime, prime, q_factor);
+       for(i = 0; i < n; i++)
+         mpi_mul (prime, prime, factors[i]);
+       mpi_add_ui (prime, prime, 1);
+       nprime = mpi_get_nbits (prime);
+
+       if (nprime < pbits)
+         {
+           if (++count1 > 20)
+             {
                count1 = 0;
                qbits++;
                progress('>');
-                mpi_free (q);
-               q = gen_prime( qbits, 0, 0, NULL, NULL );
+               mpi_free (q);
+               q = gen_prime (qbits, 0, 0, NULL, NULL);
                goto next_try;
-           }
-       }
+             }
+         }
        else
-           count1 = 0;
-       if( nprime > pbits ) {
-           if( ++count2 > 20 ) {
+         count1 = 0;
+      
+       if (nprime > pbits)
+         {
+           if (++count2 > 20)
+             {
                count2 = 0;
                qbits--;
                progress('<');
-                mpi_free (q);
-               q = gen_prime( qbits, 0, 0, NULL, NULL );
+               mpi_free (q);
+               q = gen_prime (qbits, 0, 0, NULL, NULL);
                goto next_try;
-           }
-       }
+             }
+         }
        else
-           count2 = 0;
-    } while( !(nprime == pbits && check_prime( prime, val_2 )) );
-
-    if( DBG_CIPHER ) {
-       progress('\n');
-       log_mpidump( "prime    : ", prime );
-       log_mpidump( "factor  q: ", q );
-       if( mode == 1 )
-           log_mpidump( "factor q0: ", q_factor );
-       for(i=0; i < n; i++ )
-           log_mpidump( "factor pi: ", factors[i] );
-       log_debug("bit sizes: prime=%u, q=%u", mpi_get_nbits(prime), mpi_get_nbits(q) );
-       if( mode == 1 )
-           log_debug (", q0=%u", mpi_get_nbits(q_factor) );
-       for(i=0; i < n; i++ )
-           log_debug (", p%d=%u", i, mpi_get_nbits(factors[i]) );
+         count2 = 0;
+      }
+    while (! ((nprime == pbits) && check_prime (prime, val_2)));
+
+  if (! err)
+    if (DBG_CIPHER)
+      {
+       progress ('\n');
+       log_mpidump ("prime    : ", prime);
+       log_mpidump ("factor  q: ", q);
+       if (mode == 1)
+         log_mpidump ("factor q0: ", q_factor);
+       for(i = 0; i < n; i++)
+         log_mpidump ("factor pi: ", factors[i]);
+       log_debug ("bit sizes: prime=%u, q=%u",
+                  mpi_get_nbits (prime), mpi_get_nbits (q));
+       if (mode == 1)
+         log_debug (", q0=%u", mpi_get_nbits (q_factor));
+       for (i = 0; i < n; i++)
+         log_debug (", p%d=%u", i, mpi_get_nbits (factors[i]));
        progress('\n');
-    }
+      }
+
+  if (! err)
+    if (ret_factors)
+      {
+       /* Caller wants the factors.  */
+       factors_new = gcry_calloc (n + 2, sizeof (*factors_new));
+       if (! factors_new)
+         err = GPG_ERR_INTERNAL;       /* FIXME.  */
+       else
+         {
+           i = 0;
+           if (mode == 1)
+             {
+               (factors_new)[i++] = mpi_copy (q_factor);
+               for(; i <= n; i++)
+                 (factors_new)[i] = mpi_copy (factors[i]);
+             }
+           else
+             for(; i < n; i++ )
+               (factors_new)[i] = mpi_copy (factors[i]);
+         }
+      }
+
+  if (! err)
+    if (g)
+      {
+       /* Create a generator (start with 3).  */
+       gcry_mpi_t tmp = mpi_alloc (mpi_get_nlimbs (prime));
+       gcry_mpi_t b = mpi_alloc (mpi_get_nlimbs (prime));
+       gcry_mpi_t pmin1 = mpi_alloc (mpi_get_nlimbs (prime));
+
+       if (mode == 1)
+         err = GPG_ERR_NOT_IMPLEMENTED;
+       else
+         {
+           factors[n] = q;
+           factors[n + 1] = mpi_alloc_set_ui (2);
+           mpi_sub_ui (pmin1, prime, 1);
+           mpi_set_ui (g, 2);
+           do
+             {
+               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 + 2; i++)
+                 {
+                   mpi_fdiv_q (tmp, pmin1, factors[i]);
+                   /* No mpi_pow(), but it is okay to use this with mod
+                      prime.  */
+                   gcry_mpi_powm (b, g, tmp, prime);
+                   if (! mpi_cmp_ui (b, 1))
+                     break;
+                 }
+               if (DBG_CIPHER)
+                 progress('\n');
+             } while (i < n + 2);
+           mpi_free (factors[n+1]);
+           mpi_free (tmp);
+           mpi_free (b);
+           mpi_free (pmin1);
+         }
+      }
+  
+  if (! err)
+    if (! DBG_CIPHER)
+      progress ('\n');
 
-    if( ret_factors ) { /* caller wants the factors */
-       *ret_factors = gcry_xcalloc( n+2 , sizeof **ret_factors);
-        i = 0;
-       if( mode == 1 ) {
-           (*ret_factors)[i++] = mpi_copy( q_factor );
-           for(; i <= n; i++ )
-               (*ret_factors)[i] = mpi_copy( factors[i] );
-       }
-       else {
-           for(; i < n; i++ )
-               (*ret_factors)[i] = mpi_copy( factors[i] );
-       }
+  if (pool)
+    {
+      for(i = 0; i < m; i++)
+       mpi_free (pool[i]);
+      gcry_free (pool);
     }
+  if (factors)
+    gcry_free (factors);  /* Factors are shallow copies.  */
+  if (perms)
+    gcry_free (perms);
 
-    if( g ) { /* create a generator (start with 3)*/
-       gcry_mpi_t tmp   = mpi_alloc( mpi_get_nlimbs(prime) );
-       gcry_mpi_t b      = mpi_alloc( mpi_get_nlimbs(prime) );
-       gcry_mpi_t pmin1 = mpi_alloc( mpi_get_nlimbs(prime) );
-
-       if( mode == 1 )
-           BUG(); /* not yet implemented */
-       factors[n] = q;
-       factors[n+1] = mpi_alloc_set_ui(2);
-       mpi_sub_ui( pmin1, prime, 1 );
-       mpi_set_ui(g,2);
-       do {
-           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+2; i++ ) {
-               /*fputc('~', stderr);*/
-               mpi_fdiv_q(tmp, pmin1, factors[i] );
-               /* (no mpi_pow(), but it is okay to use this with mod prime) */
-               gcry_mpi_powm(b, g, tmp, prime );
-               if( !mpi_cmp_ui(b, 1) )
-                   break;
-           }
-           if( DBG_CIPHER )
-               progress('\n');
-       } while( i < n+2 );
-       mpi_free(factors[n+1]);
-       mpi_free(tmp);
-       mpi_free(b);
-       mpi_free(pmin1);
+  mpi_free (val_2);
+  mpi_free (q);
+
+  if (! err)
+    {
+      *prime_generated = prime;
+      if (ret_factors)
+       *ret_factors = factors_new;
+    }
+  else
+    {
+      if (factors_new)
+       {
+         for (i = 0; factors_new[i]; i++)
+           mpi_free (factors_new[i]);
+         gcry_free (factors_new);
+       }
     }
-    if( !DBG_CIPHER )
-       progress('\n');
 
-    gcry_free( factors );  /* (factors are shallow copies) */
-    for(i=0; i < m; i++ )
-       mpi_free( pool[i] );
-    gcry_free( pool );
-    gcry_free(perms);
-    mpi_free(val_2);
-    mpi_free (q);
-    return prime;
+  return err;
 }
 
+gcry_mpi_t
+_gcry_generate_elg_prime (int mode, unsigned pbits, unsigned qbits,
+                         gcry_mpi_t g, gcry_mpi_t **ret_factors)
+{
+  gcry_err_code_t err = GPG_ERR_NO_ERROR;
+  gcry_mpi_t prime = NULL;
+  
+  err = prime_generate_internal (mode, &prime, pbits, qbits, g,
+                                ret_factors, GCRY_WEAK_RANDOM, 0);
 
+  return prime;
+}
 
 static gcry_mpi_t
 gen_prime (unsigned int nbits, int secret, int randomlevel, 
@@ -673,3 +788,72 @@ m_out_of_n( char *array, int m, int n )
     array[k2-1] = !array[k2-1];
 }
 
+
+/* Generate a new prime number of PRIME_BITS bits and store it in
+   PRIME.  If FACTOR_BITS is non-zero, one of the prime factors of
+   (prime - 1) / 2 must be FACTOR_BITS bits long.  If FACTORS is
+   non-zero, allocate a new, NULL-terminated array holding the prime
+   factors and store it in FACTORS.  FLAGS might be used to influence
+   the prime number generation process.  */
+gcry_error_t
+gcry_prime_generate (gcry_mpi_t *prime, unsigned int prime_bits,
+                    unsigned int factor_bits, gcry_mpi_t **factors,
+                    gcry_prime_check_func_t cb_func, void *cb_arg,
+                    gcry_random_level_t random_level,
+                    unsigned int flags)
+{
+  gcry_err_code_t err = GPG_ERR_NO_ERROR;
+  gcry_mpi_t *factors_generated = NULL;
+  gcry_mpi_t prime_generated = NULL;
+  unsigned int mode = 0;
+
+  if (flags & GCRY_PRIME_FLAG_SPECIAL_FACTOR)
+    mode = 1;
+
+  /* Generate.  */
+  err = prime_generate_internal (mode, &prime_generated, prime_bits,
+                                factor_bits, NULL, &factors_generated,
+                                random_level, flags);
+
+  if (! err)
+    if (cb_func)
+      {
+       /* Additional check */
+       if (! (*cb_func) (cb_arg, 0, prime_generated))
+         {
+           /* Failed, deallocate resources.  */
+
+           unsigned int i;
+
+           mpi_free (prime_generated);
+           for (i = 0; factors_generated[i]; i++)
+             mpi_free (factors_generated[i]);
+           gcry_free (factors_generated);
+           err = GPG_ERR_INTERNAL; /* FIXME.  */
+         }
+      }
+
+  if (! err)
+    {
+      /* Done.  */
+      *prime = prime_generated;
+      *factors = factors_generated;
+    }
+
+  return gcry_error (err);
+}
+
+/* Check wether the number X is prime.  */
+gcry_error_t
+gcry_prime_check (gcry_mpi_t x, unsigned int flags)
+{
+  gcry_err_code_t err = GPG_ERR_NO_ERROR;
+  gcry_mpi_t test_value = mpi_alloc_set_ui (2); /* ? */
+
+  if (! check_prime (x, test_value))
+    err = GPG_ERR_NO_PRIME;
+
+  mpi_free (test_value);
+
+  return gcry_error (err);
+}