* rsa.c (generate): Loop until we find the exact modulus size.
authorWerner Koch <wk@gnupg.org>
Tue, 18 Dec 2001 15:29:02 +0000 (15:29 +0000)
committerWerner Koch <wk@gnupg.org>
Tue, 18 Dec 2001 15:29:02 +0000 (15:29 +0000)
Changed the exponent to 41.
(rsa_get_info): s/usage/r_usage/ to avoid shadow warnings.
* primegen.c (gen_prime): Set 2 high order bits for secret primes.
* Makefile.am (DISTCLEANFILES): Include construct.c.

cipher/ChangeLog
cipher/Makefile.am
cipher/primegen.c
cipher/random.c
cipher/rsa.c

index 8f0536d..14fe312 100644 (file)
@@ -1,3 +1,12 @@
+2001-12-18  Werner Koch  <wk@gnupg.org>
+
+       * rsa.c (generate): Loop until we find the exact modulus size.
+       Changed the exponent to 41.
+       (rsa_get_info): s/usage/r_usage/ to avoid shadow warnings.
+       * primegen.c (gen_prime): Set 2 high order bits for secret primes.
+
+       * Makefile.am (DISTCLEANFILES): Include construct.c.
+
 2001-12-17  Werner Koch  <wk@gnupg.org>
 
        * pubkey.c (gcry_pk_get_keygrip): New - experimental.
index 20b8ffc..04bbf1f 100644 (file)
@@ -79,16 +79,20 @@ libcipher_la_SOURCES = cipher.c  \
 
 # configure creates the constructor file
 BUILT_SOURCES = construct.c
+DISTCLEANFILES = construct.c
 
 libcipher_la_DEPENDENCIES = @STATIC_CIPHER_OBJS@
 libcipher_la_LIBADD =    @STATIC_CIPHER_OBJS@
 
 
-# If I remember it correct, automake 1.4 has a feature to set
-# fooFLAGS depending on the program.  So we should check it out.
+# We could to something like 
+#   tiger_SOURCES = tiger.c
+#   tiger_CFLAGS = $(DYNLINK_MOD_CFLAGS)
+# but I have not yet figured out on how to suppress the link step.
+# this is probably a libtool thing.
 
 #if BUILD_MODULE_TIGER
-tiger: $(srcdir)/tiger.c
+tiger$(EXEEXT): $(srcdir)/tiger.c
        `echo $(COMPILE) $(DYNLINK_MOD_CFLAGS) -o tiger $(srcdir)/tiger.c | \
            sed -e 's/-O[2-9s]*/-O/g' `
 #endif
@@ -101,7 +105,7 @@ tiger.o: $(srcdir)/tiger.c
 #           sed -e 's/-O[0-9s]*/  /g' `
 
 #if BUILD_MODULE_TWOFISH
-twofish: $(srcdir)/twofish.c
+twofish$(EXEEXT): $(srcdir)/twofish.c
        $(COMPILE) $(DYNLINK_MOD_CFLAGS) -o twofish $(srcdir)/twofish.c
 #endif
 
@@ -109,17 +113,17 @@ twofish: $(srcdir)/twofish.c
 #       `echo $(COMPILE) -c $(srcdir)/twofish.c | sed -e 's/-O[0-9s]*/  /g' `
 
 #if BUILD_MODULE_RNDUNIX
-rndunix: $(srcdir)/rndunix.c
+rndunix$(EXEEXT): $(srcdir)/rndunix.c
        $(COMPILE) $(DYNLINK_MOD_CFLAGS) -o rndunix $(srcdir)/rndunix.c
 #endif
 
 #if BUILD_MODULE_RNDLINUX
-rndlinux: $(srcdir)/rndlinux.c
+rndlinux$(EXEEXT): $(srcdir)/rndlinux.c
        $(COMPILE) $(DYNLINK_MOD_CFLAGS) -o rndlinux $(srcdir)/rndlinux.c
 #endif
 
 #if BUILD_MODULE_RNDEGD
-rndegd: $(srcdir)/rndegd.c
+rndegd$(EXEEXT): $(srcdir)/rndegd.c
        $(COMPILE) $(DYNLINK_MOD_CFLAGS) -o rndegd $(srcdir)/rndegd.c
 #endif
 
index 9489f0e..e131e33 100644 (file)
@@ -257,7 +257,9 @@ _gcry_generate_elg_prime( int mode, unsigned pbits, unsigned qbits,
            if( DBG_CIPHER ) {
                log_debug("checking g: ");
                /*mpi_print( stderr, g, 1 );*/
-               #warning we need an internal mpi_print for debugging
+#if __GNUC__ >= 2
+#   warning we need an internal mpi_print for debugging
+#endif
            }
            else
                progress('^');
@@ -323,9 +325,14 @@ gen_prime( unsigned  nbits, int secret, int randomlevel )
        /* generate a random number */
        gcry_mpi_randomize( prime, nbits, randomlevel );
 
-       /* set high order bit to 1, set low order bit to 1 */
-       mpi_set_highbit( prime, nbits-1 );
-       mpi_set_bit( prime, 0 );
+       /* set high order bit to 1, set low order bit to 1.  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_highbit (prime, nbits-2);
+       mpi_set_bit(prime, 0);
 
        /* calculate all remainders */
        for(i=0; (x = small_prime_numbers[i]); i++ )
index 8608951..5c48bf6 100644 (file)
@@ -672,7 +672,9 @@ gather_faked( void (*add)(const void*, size_t, int), int requester,
        /* we can't use tty_printf here - do we need this function at
          all - does it really make sense or canit be viewed as a potential
          security problem ? wk 17.11.99 */
-       #warning Extended warning disabled
+#if __GNUC__ >= 2
+#     warning Extended warning disabled
+#endif
       #if 0
        tty_printf(_("The random number generator is only a kludge to let\n"
                   "it run - it is in no way a strong RNG!\n\n"
index 51310ad..3a72ca2 100644 (file)
@@ -84,7 +84,7 @@ test_keys( RSA_secret_key *sk, unsigned nbits )
 
 /****************
  * Generate a key pair with a key of size NBITS
- * Returns: 2 structures filles with all needed values
+ * Returns: 2 structures filled with all needed values
  */
 static void
 generate( RSA_secret_key *sk, unsigned nbits )
@@ -95,15 +95,31 @@ generate( RSA_secret_key *sk, unsigned nbits )
     MPI t1, t2;
     MPI n;    /* the public key */
     MPI e;    /* the exponent */
-    MPI phi;  /* helper: (p-a)(q-1) */
+    MPI phi;  /* helper: (p-1)(q-1) */
     MPI g;
     MPI f;
 
-    /* select two (very secret) primes */
-    p = _gcry_generate_secret_prime( nbits / 2 );
-    q = _gcry_generate_secret_prime( nbits / 2 );
-    if( mpi_cmp( p, q ) > 0 ) /* p shall be smaller than q (for calc of u)*/
-       mpi_swap(p,q);
+    /* make sure that nbits is even so that we generate p, q of equal size */
+    if ( (nbits&1) )
+      nbits++; 
+
+    n = gcry_mpi_new (nbits);
+
+    p = q = NULL;
+    do {
+      /* select two (very secret) primes */
+      if (p)
+        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 (mpi_cmp (p, q) > 0 ) /* p shall be smaller than q (for calc of u)*/
+        mpi_swap(p,q);
+      /* calculate the modulus */
+      mpi_mul( n, p, q );
+    } while ( mpi_get_nbits(n) != nbits );
+
     /* calculate Euler totient: phi = (p-1)(q-1) */
     t1 = mpi_alloc_secure( mpi_get_nlimbs(p) );
     t2 = mpi_alloc_secure( mpi_get_nlimbs(p) );
@@ -115,14 +131,27 @@ generate( RSA_secret_key *sk, unsigned nbits )
     mpi_mul( phi, t1, t2 );
     gcry_mpi_gcd(g, t1, t2);
     mpi_fdiv_q(f, phi, g);
-    /* multiply them to make the private key */
-    n = gcry_mpi_new ( nbits );
-    mpi_mul( n, p, q );
-    /* find a public exponent  */
-    e = gcry_mpi_new ( 6 );
-    mpi_set_ui( e, 17); /* start with 17 */
-    while( !gcry_mpi_gcd(t1, e, phi) ) /* (while gcd is not 1) */
-       mpi_add_ui( e, e, 2);
+
+    /* 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 );
+    mpi_set_ui( e, 41); 
+    if( !gcry_mpi_gcd(t1, e, phi) ) {
+      mpi_set_ui( e, 257); 
+      if( !gcry_mpi_gcd(t1, e, phi) ) {
+        mpi_set_ui( e, 65537); 
+        while( !gcry_mpi_gcd(t1, e, phi) ) /* (while gcd is not 1) */
+          mpi_add_ui( e, e, 2);
+      }
+    }
+
     /* calculate the secret key d = e^1 mod phi */
     d = gcry_mpi_snew ( nbits );
     mpi_invm(d, e, f );
@@ -131,7 +160,7 @@ generate( RSA_secret_key *sk, unsigned nbits )
     mpi_invm(u, p, q );
 
     if( DBG_CIPHER ) {
-       log_mpidump("  p= ", p );
+        log_mpidump("  p= ", p );
        log_mpidump("  q= ", q );
        log_mpidump("phi= ", phi );
        log_mpidump("  g= ", g );
@@ -455,7 +484,7 @@ _gcry_rsa_get_nbits( int algo, MPI *pkey )
  */
 const char *
 _gcry_rsa_get_info( int algo,
-             int *npkey, int *nskey, int *nenc, int *nsig, int *usage )
+             int *npkey, int *nskey, int *nenc, int *nsig, int *r_usage )
 {
     *npkey = 2;
     *nskey = 6;
@@ -463,9 +492,9 @@ _gcry_rsa_get_info( int algo,
     *nsig = 1;
 
     switch( algo ) {
-      case 1: *usage = GCRY_PK_USAGE_SIGN | GCRY_PK_USAGE_ENCR; return "RSA";
-      case 2: *usage = GCRY_PK_USAGE_ENCR; return "RSA-E";
-      case 3: *usage = GCRY_PK_USAGE_SIGN; return "RSA-S";
-      default:*usage = 0; return NULL;
+      case 1: *r_usage = GCRY_PK_USAGE_SIGN | GCRY_PK_USAGE_ENCR; return "RSA";
+      case 2: *r_usage = GCRY_PK_USAGE_ENCR; return "RSA-E";
+      case 3: *r_usage = GCRY_PK_USAGE_SIGN; return "RSA-S";
+      default:*r_usage = 0; return NULL;
     }
 }