* keygen.c (check_rsa_keys): Don't expect an exponent when asking
authorWerner Koch <wk@gnupg.org>
Wed, 19 Mar 2003 11:57:55 +0000 (11:57 +0000)
committerWerner Koch <wk@gnupg.org>
Wed, 19 Mar 2003 11:57:55 +0000 (11:57 +0000)
for e=0.
(check_generated_rsa_key): Just print exponent if EXPECTED_E is 0.

* primegen.c (gen_prime): New args EXTRA_CHECK and EXTRA_CHECK_ARG
to allow for a user callback.  Changed all callers.
(_gcry_generate_secret_prime)
(_gcry_generate_public_prime): Ditto, pass them to gen_prime.
* rsa.c (check_exponent): New.
(generate): Use a callback to ensure that a given exponent is
actually generated.

cipher/ChangeLog
cipher/primegen.c
cipher/rsa.c
tests/ChangeLog
tests/basic.c
tests/keygen.c

index e69cc50..20ff652 100644 (file)
@@ -1,3 +1,13 @@
+2003-03-19  Werner Koch  <wk@gnupg.org>
+
+       * primegen.c (gen_prime): New args EXTRA_CHECK and EXTRA_CHECK_ARG
+       to allow for a user callback.  Changed all callers.
+       (_gcry_generate_secret_prime)
+       (_gcry_generate_public_prime): Ditto, pass them to gen_prime.
+       * rsa.c (check_exponent): New.
+       (generate): Use a callback to ensure that a given exponent is
+       actually generated.
+
 2003-03-12  Moritz Schulte  <moritz@g10code.com>
 
        * primegen.c: Initialize `no_of_small_prime_numbers' statically.
index ffeb52c..f2ece0e 100644 (file)
@@ -1,5 +1,5 @@
 /* primegen.c - prime number generator
- * Copyright (C) 1998, 2000, 2001, 2002 Free Software Foundation, Inc.
+ * Copyright (C) 1998, 2000, 2001, 2002, 2003 Free Software Foundation, Inc.
  *
  * This file is part of Libgcrypt.
  *
@@ -32,7 +32,8 @@
 #include "mpi.h"
 #include "cipher.h"
 
-static MPI gen_prime( unsigned nbits, int mode, int randomlevel );
+static MPI gen_prime (unsigned int nbits, int secret, int randomlevel, 
+                      int (*extra_check)(void *, MPI), void *extra_check_arg);
 static int check_prime( MPI prime, MPI val_2 );
 static int is_prime( MPI n, int steps, int *count );
 static void m_out_of_n( char *array, int m, int n );
@@ -146,21 +147,25 @@ progress( int c )
  * Generate a prime number (stored in secure memory)
  */
 MPI
-_gcry_generate_secret_prime( unsigned  nbits )
+_gcry_generate_secret_prime (unsigned int nbits,
+                             int (*extra_check)(void*, MPI),
+                             void *extra_check_arg)
 {
     MPI prime;
 
-    prime = gen_prime( nbits, 1, 2 );
+    prime = gen_prime( nbits, 1, 2, extra_check, extra_check_arg);
     progress('\n');
     return prime;
 }
 
 MPI
-_gcry_generate_public_prime( unsigned  nbits )
+_gcry_generate_public_prime( unsigned int nbits,
+                             int (*extra_check)(void*, MPI),
+                             void *extra_check_arg)
 {
     MPI prime;
 
-    prime = gen_prime( nbits, 0, 2 );
+    prime = gen_prime( nbits, 0, 2, extra_check, extra_check_arg );
     progress('\n');
     return prime;
 }
@@ -213,8 +218,8 @@ _gcry_generate_elg_prime( int mode, unsigned pbits, unsigned qbits,
        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 );
-    q_factor = mode==1? gen_prime( req_qbits, 0, 0 ) : NULL;
+    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 );
@@ -241,7 +246,7 @@ _gcry_generate_elg_prime( int mode, unsigned pbits, unsigned qbits,
            perms = gcry_xcalloc( 1, m );
            for(i=0; i < n; i++ ) {
                perms[i] = 1;
-               pool[i] = gen_prime( fbits, 0, 1 );
+               pool[i] = gen_prime( fbits, 0, 1, NULL, NULL );
                factors[i] = pool[i];
            }
        }
@@ -250,7 +255,7 @@ _gcry_generate_elg_prime( int mode, unsigned pbits, unsigned qbits,
            for(i=j=0; i < m && j < n ; i++ )
                if( perms[i] ) {
                    if( !pool[i] )
-                       pool[i] = gen_prime( fbits, 0, 1 );
+                       pool[i] = gen_prime( fbits, 0, 1, NULL, NULL );
                    factors[j++] = pool[i];
                }
            if( i == n ) {
@@ -274,7 +279,7 @@ _gcry_generate_elg_prime( int mode, unsigned pbits, unsigned qbits,
                qbits++;
                progress('>');
                 mpi_free (q);
-               q = gen_prime( qbits, 0, 0 );
+               q = gen_prime( qbits, 0, 0, NULL, NULL );
                goto next_try;
            }
        }
@@ -286,7 +291,7 @@ _gcry_generate_elg_prime( int mode, unsigned pbits, unsigned qbits,
                qbits--;
                progress('<');
                 mpi_free (q);
-               q = gen_prime( qbits, 0, 0 );
+               q = gen_prime( qbits, 0, 0, NULL, NULL );
                goto next_try;
            }
        }
@@ -378,88 +383,103 @@ _gcry_generate_elg_prime( int mode, unsigned pbits, unsigned qbits,
 
 
 static MPI
-gen_prime( unsigned  nbits, int secret, int randomlevel )
+gen_prime (unsigned int nbits, int secret, int randomlevel, 
+           int (*extra_check)(void *, MPI), void *extra_check_arg)
 {
-    MPI prime, ptest, pminus1, val_2, val_3, result;
-    int i;
-    unsigned x, step;
-    unsigned count1, count2;
-    int *mods;
-
-    if( 0 && DBG_CIPHER )
-       log_debug("generate a prime of %u bits ", nbits );
-
-    mods = gcry_xmalloc( no_of_small_prime_numbers * sizeof *mods );
-    /* make nbits fit into MPI implementation */
-    val_2  = mpi_alloc_set_ui( 2 );
-    val_3 = mpi_alloc_set_ui( 3);
-    prime  = secret? gcry_mpi_snew ( nbits ): gcry_mpi_new ( nbits );
-    result = mpi_alloc_like( prime );
-    pminus1= mpi_alloc_like( prime );
-    ptest  = mpi_alloc_like( prime );
-    count1 = count2 = 0;
-    for(;;) {  /* try forvever */
-       int dotcount=0;
-
-       /* generate a random number */
-       gcry_mpi_randomize( prime, nbits, randomlevel );
-
-       /* Set high order bit to 1, set low order bit to 0.  If we are
-           generating a secret prime we are most probably doing that
-           for RSA, to make sure that the modulus does have the
-           requested keysize we set the 2 high order bits */
-       mpi_set_highbit (prime, nbits-1);
-        if (secret)
-          mpi_set_bit (prime, nbits-2);
-       mpi_set_bit(prime, 0);
-
-       /* calculate all remainders */
-       for(i=0; (x = small_prime_numbers[i]); i++ )
-           mods[i] = mpi_fdiv_r_ui(NULL, prime, x);
-
-       /* now try some primes starting with prime */
-       for(step=0; step < 20000; step += 2 ) {
-           /* check against all the small primes we have in mods */
-           count1++;
-           for(i=0; (x = small_prime_numbers[i]); i++ ) {
-               while( mods[i] + step >= x )
-                   mods[i] -= x;
-               if( !(mods[i] + step) )
-                   break;
+  MPI prime, ptest, pminus1, val_2, val_3, result;
+  int i;
+  unsigned x, step;
+  unsigned count1, count2;
+  int *mods;
+  
+  if( 0 && DBG_CIPHER )
+    log_debug("generate a prime of %u bits ", nbits );
+
+  mods = gcry_xmalloc( no_of_small_prime_numbers * sizeof *mods );
+  /* make nbits fit into MPI implementation */
+  val_2  = mpi_alloc_set_ui( 2 );
+  val_3 = mpi_alloc_set_ui( 3);
+  prime  = secret? gcry_mpi_snew ( nbits ): gcry_mpi_new ( nbits );
+  result = mpi_alloc_like( prime );
+  pminus1= mpi_alloc_like( prime );
+  ptest  = mpi_alloc_like( prime );
+  count1 = count2 = 0;
+  for (;;)
+    {  /* try forvever */
+      int dotcount=0;
+      
+      /* generate a random number */
+      gcry_mpi_randomize( prime, nbits, randomlevel );
+      
+      /* Set high order bit to 1, set low order bit to 0.  If we are
+         generating a secret prime we are most probably doing that
+         for RSA, to make sure that the modulus does have the
+         requested keysize we set the 2 high order bits */
+      mpi_set_highbit (prime, nbits-1);
+      if (secret)
+        mpi_set_bit (prime, nbits-2);
+      mpi_set_bit(prime, 0);
+      
+      /* calculate all remainders */
+      for (i=0; (x = small_prime_numbers[i]); i++ )
+        mods[i] = mpi_fdiv_r_ui(NULL, prime, x);
+      
+      /* now try some primes starting with prime */
+      for(step=0; step < 20000; step += 2 ) 
+        {
+          /* check against all the small primes we have in mods */
+          count1++;
+          for (i=0; (x = small_prime_numbers[i]); i++ ) 
+            {
+              while ( mods[i] + step >= x )
+                mods[i] -= x;
+              if ( !(mods[i] + step) )
+                break;
            }
-           if( x )
-               continue;   /* found a multiple of an already known prime */
-
-           mpi_add_ui( ptest, prime, step );
-
-           /* do a faster Fermat test */
-           count2++;
-           mpi_sub_ui( pminus1, ptest, 1);
-           gcry_mpi_powm( result, val_2, pminus1, ptest );
-           if( !mpi_cmp_ui( result, 1 ) ) { /* not composite */
-               /* perform stronger tests */
-               if( is_prime(ptest, 5, &count2 ) ) {
-                   if( !mpi_test_bit( ptest, nbits-1-secret ) ) {
+          if ( x )
+            continue;   /* found a multiple of an already known prime */
+
+          mpi_add_ui( ptest, prime, step );
+
+          /* do a faster Fermat test */
+          count2++;
+          mpi_sub_ui( pminus1, ptest, 1);
+          gcry_mpi_powm( result, val_2, pminus1, ptest );
+          if ( !mpi_cmp_ui( result, 1 ) )
+            { /* not composite, perform stronger tests */
+               if (is_prime(ptest, 5, &count2 ))
+                  {
+                   if (!mpi_test_bit( ptest, nbits-1-secret ))
+                      {
                        progress('\n');
                        log_debug("overflow in prime generation\n");
-                       break; /* step loop, continue with a new prime */
-                   }
-
-                   mpi_free(val_2);
-                   mpi_free(val_3);
-                   mpi_free(result);
-                   mpi_free(pminus1);
-                   mpi_free(prime);
-                   gcry_free(mods);
-                   return ptest;
-               }
+                       break; /* stop loop, continue with a new prime */
+                      }
+
+                    if (extra_check && extra_check (ptest, extra_check_arg))
+                      { /* The extra check told us that this prime is
+                           not of the caller's taste. */
+                        progress ('/');
+                      }
+                    else
+                      { /* got it */
+                        mpi_free(val_2);
+                        mpi_free(val_3);
+                        mpi_free(result);
+                        mpi_free(pminus1);
+                        mpi_free(prime);
+                        gcry_free(mods);
+                        return ptest; 
+                      }
+                  }
            }
-           if( ++dotcount == 10 ) {
-               progress('.');
-               dotcount = 0;
+          if (++dotcount == 10 )
+            {
+              progress('.');
+              dotcount = 0;
            }
        }
-       progress(':'); /* restart with a new random value */
+      progress(':'); /* restart with a new random value */
     }
 }
 
index a8097be..9514a06 100644 (file)
@@ -83,6 +83,24 @@ test_keys( RSA_secret_key *sk, unsigned nbits )
     gcry_mpi_release ( out2 );
 }
 
+
+/* Callback used by the prime generation to test whether the exponent
+   is suitable. Returns 0 if the test has been passed. */
+static int
+check_exponent (void *arg, MPI a)
+{
+  MPI e = arg;
+  MPI tmp;
+  int result;
+  
+  mpi_sub_ui (a, a, 1);
+  tmp = _gcry_mpi_alloc_like (a);
+  result = !gcry_mpi_gcd(tmp, e, a); /* GCD is not 1. */
+  gcry_mpi_release (tmp);
+  mpi_add_ui (a, a, 1);
+  return result;
+}
+
 /****************
  * Generate a key pair with a key of size NBITS.  
  * USE_E = 0 let Libcgrypt decide what exponent to use.
@@ -108,6 +126,27 @@ generate (RSA_secret_key *sk, unsigned int nbits, unsigned long use_e)
     if ( (nbits&1) )
       nbits++; 
 
+    if (use_e == 1)   /* Alias for a secure value. */
+      use_e = 65537;  /* as demanded by Spinx. */
+
+    /* Public exponent:
+       In general we use 41 as this is quite fast and more secure than the
+       commonly used 17.  Benchmarking the RSA verify function
+       with a 1024 bit key yields (2001-11-08): 
+         e=17    0.54 ms
+         e=41    0.75 ms
+         e=257   0.95 ms
+         e=65537 1.80 ms
+    */
+    e = mpi_alloc( (32+BITS_PER_MPI_LIMB-1)/BITS_PER_MPI_LIMB );
+    if (!use_e)
+      mpi_set_ui (e, 41);     /* This is a reasonable secure and fast value */
+    else 
+      {
+        use_e |= 1; /* make sure this is odd */
+        mpi_set_ui (e, use_e); 
+      }
+    
     n = gcry_mpi_new (nbits);
 
     p = q = NULL;
@@ -117,8 +156,17 @@ generate (RSA_secret_key *sk, unsigned int nbits, unsigned long use_e)
         gcry_mpi_release (p);
       if (q)
         gcry_mpi_release (q);
-      p = _gcry_generate_secret_prime (nbits/2);
-      q = _gcry_generate_secret_prime (nbits/2);
+      if (use_e)
+        { /* Do an extra test to ensure that the given exponent is
+             suitable. */
+          p = _gcry_generate_secret_prime (nbits/2, check_exponent, e);
+          q = _gcry_generate_secret_prime (nbits/2, check_exponent, e);
+        }
+      else
+        { /* We check the exponent later. */
+          p = _gcry_generate_secret_prime (nbits/2, NULL, NULL);
+          q = _gcry_generate_secret_prime (nbits/2, NULL, NULL);
+        }
       if (mpi_cmp (p, q) > 0 ) /* p shall be smaller than q (for calc of u)*/
         mpi_swap(p,q);
       /* calculate the modulus */
@@ -137,25 +185,13 @@ generate (RSA_secret_key *sk, unsigned int nbits, unsigned long use_e)
     gcry_mpi_gcd(g, t1, t2);
     mpi_fdiv_q(f, phi, g);
 
-    /* find an public exponent.
-       We use 41 as this is quite fast and more secure than the
-       commonly used 17.  Benchmarking the RSA verify function
-       with a 1024 bit key yields (2001-11-08): 
-         e=17    0.54 ms
-         e=41    0.75 ms
-         e=257   0.95 ms
-         e=65537 1.80 ms
-    */
-    e = mpi_alloc( (32+BITS_PER_MPI_LIMB-1)/BITS_PER_MPI_LIMB );
-    if (!use_e)
-      use_e = 41;     /* This is a reasonable secure and fast value */
-    else if (use_e == 1)
-      use_e = 65537;  /* A secure value as demanded by Spinx. */
-
-    use_e |= 1; /* make sure this is odd */
-    mpi_set_ui (e, use_e); 
     while (!gcry_mpi_gcd(t1, e, phi)) /* (while gcd is not 1) */
-      mpi_add_ui (e, e, 2);
+      {
+        if (use_e)
+          BUG (); /* The prime generator already made sure that we
+                     never can get to here. */
+        mpi_add_ui (e, e, 2);
+      }
 
     /* calculate the secret key d = e^1 mod phi */
     d = gcry_mpi_snew ( nbits );
index cc85867..2aa94e8 100644 (file)
@@ -1,3 +1,9 @@
+2003-03-19  Werner Koch  <wk@gnupg.org>
+
+       * keygen.c (check_rsa_keys): Don't expect an exponent when asking
+       for e=0.
+       (check_generated_rsa_key): Just print exponent if EXPECTED_E is 0.
+
 2003-03-02  Moritz Schulte  <moritz@g10code.com>
 
        * basic.c (check_one_cipher): Use gcry_cipher_reset() instead of
index abbc7dd..a33d0b9 100644 (file)
@@ -592,10 +592,9 @@ main (int argc, char **argv)
   else if (argc > 1 && !strcmp (argv[1], "--debug"))
     verbose = debug = 1;
 
-  /*gcry_control (GCRYCTL_DISABLE_INTERNAL_LOCKING,0);*/
-  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);
index 8554118..a65a0c3 100644 (file)
@@ -77,7 +77,7 @@ check_generated_rsa_key (GcrySexp key, unsigned long expected_e)
 {
   GcrySexp skey, pkey, list;
 
- pkey = gcry_sexp_find_token (key, "public-key", 0);
 pkey = gcry_sexp_find_token (key, "public-key", 0);
   if (!pkey)
     fail ("public part missing in return value\n");
   else
@@ -87,7 +87,12 @@ check_generated_rsa_key (GcrySexp key, unsigned long expected_e)
       list = gcry_sexp_find_token (pkey, "e", 0);
       if (!list || !(e=gcry_sexp_nth_mpi (list, 1, 0)) )
         fail ("public exponent not found\n");
-      else if (gcry_mpi_cmp_ui (e, expected_e)) 
+      else if (!expected_e)
+        {
+          if (verbose)
+            print_mpi ("e", e);
+        }
+      else if ( gcry_mpi_cmp_ui (e, expected_e)) 
         {
           print_mpi ("e", e);
           fail ("public exponent is not %lu\n", expected_e);
@@ -152,7 +157,7 @@ check_rsa_keys (void)
   gcry_sexp_release (key);
 
   if (verbose)
-    fprintf (stderr, "creating 512 bit RSA key with default e=41\n");
+    fprintf (stderr, "creating 512 bit RSA key with default e\n");
   rc = gcry_sexp_new (&keyparm, 
                       "(genkey\n"
                       " (rsa\n"
@@ -166,7 +171,7 @@ check_rsa_keys (void)
   if (rc)
     die ("error generating RSA key: %s\n", gcry_strerror (rc));
 
-  check_generated_rsa_key (key, 41);
+  check_generated_rsa_key (key, 0); /* We don't expect a constant exponent. */
   gcry_sexp_release (key);
 
 }
@@ -184,9 +189,9 @@ 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);
@@ -196,3 +201,4 @@ main (int argc, char **argv)
   
   return error_count? 1:0;
 }
+