Optimizations in DH parameter generation.

The larger prime is find first and the big loop needs to
find a smaller prime, increasing performance.
The _gnutls_rnd() function is now inline and GNUTLS_RND_NONCE doesn't update random generator state.

20 files changed, 73 insertions, 65 deletions

diff --git a/lib/auth/psk_passwd.c b/lib/auth/psk_passwd.c
index 7a02c6c907..195454dac6 100644
--- a/lib/auth/psk_passwd.c
+++ b/lib/auth/psk_passwd.c
@@ -107,7 +107,7 @@ _randomize_psk (gnutls_datum_t * psk)
 
   psk->size = 16;
 
-  ret = gnutls_rnd (GNUTLS_RND_NONCE, (char *) psk->data, 16);
+  ret = _gnutls_rnd (GNUTLS_RND_NONCE, (char *) psk->data, 16);
   if (ret < 0)
     {
       gnutls_assert ();
diff --git a/lib/auth/rsa.c b/lib/auth/rsa.c
index a9a88aa872..030ed35dde 100644
--- a/lib/auth/rsa.c
+++ b/lib/auth/rsa.c
@@ -213,7 +213,7 @@ proc_rsa_client_kx (gnutls_session_t session, opaque * data,
 
       /* we do not need strong random numbers here.
        */
-      ret = gnutls_rnd (GNUTLS_RND_NONCE, session->key->key.data,
+      ret = _gnutls_rnd (GNUTLS_RND_NONCE, session->key->key.data,
                          session->key->key.size);
       if (ret < 0)
         {
@@ -268,7 +268,7 @@ _gnutls_gen_rsa_client_kx (gnutls_session_t session, gnutls_buffer_st* data)
       return GNUTLS_E_MEMORY_ERROR;
     }
 
-  ret = gnutls_rnd (GNUTLS_RND_RANDOM, session->key->key.data,
+  ret = _gnutls_rnd (GNUTLS_RND_RANDOM, session->key->key.data,
                      session->key->key.size);
   if (ret < 0)
     {
diff --git a/lib/auth/rsa_export.c b/lib/auth/rsa_export.c
index 28ef8c67ca..959f72c672 100644
--- a/lib/auth/rsa_export.c
+++ b/lib/auth/rsa_export.c
@@ -204,7 +204,7 @@ proc_rsa_export_client_kx (gnutls_session_t session, opaque * data,
 
       /* we do not need strong random numbers here.
        */
-      ret = gnutls_rnd (GNUTLS_RND_NONCE, session->key->key.data,
+      ret = _gnutls_rnd (GNUTLS_RND_NONCE, session->key->key.data,
                          session->key->key.size);
       if (ret < 0)
         {
diff --git a/lib/auth/srp_passwd.c b/lib/auth/srp_passwd.c
index 7ced10179f..19972201c6 100644
--- a/lib/auth/srp_passwd.c
+++ b/lib/auth/srp_passwd.c
@@ -404,7 +404,7 @@ _randomize_pwd_entry (SRP_PWD_ENTRY * entry)
       return GNUTLS_E_INTERNAL_ERROR;
     }
 
-  ret = gnutls_rnd (GNUTLS_RND_NONCE, &rnd, 1);
+  ret = _gnutls_rnd (GNUTLS_RND_NONCE, &rnd, 1);
   if (ret < 0)
     {
       gnutls_assert ();
@@ -421,7 +421,7 @@ _randomize_pwd_entry (SRP_PWD_ENTRY * entry)
       return GNUTLS_E_MEMORY_ERROR;
     }
 
-  ret = gnutls_rnd (GNUTLS_RND_RANDOM, entry->v.data, 20);
+  ret = _gnutls_rnd (GNUTLS_RND_RANDOM, entry->v.data, 20);
   if (ret < 0)
     {
       gnutls_assert ();
@@ -435,7 +435,7 @@ _randomize_pwd_entry (SRP_PWD_ENTRY * entry)
       return GNUTLS_E_MEMORY_ERROR;
     }
 
-  ret = gnutls_rnd (GNUTLS_RND_NONCE, entry->salt.data, entry->salt.size);
+  ret = _gnutls_rnd (GNUTLS_RND_NONCE, entry->salt.data, entry->salt.size);
   if (ret < 0)
     {
       gnutls_assert ();
diff --git a/lib/crypto-api.c b/lib/crypto-api.c
index ce9d02bdec..260f942217 100644
--- a/lib/crypto-api.c
+++ b/lib/crypto-api.c
@@ -538,7 +538,7 @@ gnutls_key_generate (gnutls_datum_t * key, unsigned int key_size)
       return GNUTLS_E_MEMORY_ERROR;
     }
 
-  ret = gnutls_rnd (GNUTLS_RND_RANDOM, key->data, key->size);
+  ret = _gnutls_rnd (GNUTLS_RND_RANDOM, key->data, key->size);
   if (ret < 0)
     {
       gnutls_assert ();
diff --git a/lib/ext/session_ticket.c b/lib/ext/session_ticket.c
index 51b21caf2b..8da06361ce 100644
--- a/lib/ext/session_ticket.c
+++ b/lib/ext/session_ticket.c
@@ -555,7 +555,7 @@ gnutls_session_ticket_enable_server (gnutls_session_t session,
     }
   epriv.ptr = priv;
 
-  ret = gnutls_rnd (GNUTLS_RND_NONCE, priv->session_ticket_IV, IV_SIZE);
+  ret = _gnutls_rnd (GNUTLS_RND_NONCE, priv->session_ticket_IV, IV_SIZE);
   if (ret < 0)
     {
       gnutls_assert ();
diff --git a/lib/gnutls_cipher.c b/lib/gnutls_cipher.c
index ed4ac8be8d..c15784342c 100644
--- a/lib/gnutls_cipher.c
+++ b/lib/gnutls_cipher.c
@@ -213,7 +213,7 @@ calc_enc_length (gnutls_session_t session, int data_size,
 
       break;
     case CIPHER_BLOCK:
-      ret = gnutls_rnd (GNUTLS_RND_NONCE, &rnd, 1);
+      ret = _gnutls_rnd (GNUTLS_RND_NONCE, &rnd, 1);
       if (ret < 0)
         return gnutls_assert_val(ret);
 
@@ -351,7 +351,7 @@ compressed_to_ciphertext (gnutls_session_t session,
         {
           /* copy the random IV.
            */
-          ret = gnutls_rnd (GNUTLS_RND_NONCE, data_ptr, blocksize);
+          ret = _gnutls_rnd (GNUTLS_RND_NONCE, data_ptr, blocksize);
           if (ret < 0)
             return gnutls_assert_val(ret);
 
diff --git a/lib/gnutls_handshake.c b/lib/gnutls_handshake.c
index 153818e324..16056487e8 100644
--- a/lib/gnutls_handshake.c
+++ b/lib/gnutls_handshake.c
@@ -313,7 +313,7 @@ _gnutls_tls_create_random (opaque * dst)
   /* generate server random value */
   _gnutls_write_uint32 (tim, dst);
 
-  ret = gnutls_rnd (GNUTLS_RND_NONCE, &dst[4], GNUTLS_RANDOM_SIZE - 4);
+  ret = _gnutls_rnd (GNUTLS_RND_NONCE, &dst[4], GNUTLS_RANDOM_SIZE - 4);
   if (ret < 0)
     {
       gnutls_assert ();
@@ -2847,7 +2847,7 @@ _gnutls_generate_session_id (opaque * session_id, uint8_t * len)
 
   *len = TLS_MAX_SESSION_ID_SIZE;
 
-  ret = gnutls_rnd (GNUTLS_RND_NONCE, session_id, *len);
+  ret = _gnutls_rnd (GNUTLS_RND_NONCE, session_id, *len);
   if (ret < 0)
     {
       gnutls_assert ();
diff --git a/lib/gnutls_mpi.c b/lib/gnutls_mpi.c
index b2cde7a3be..681d63f415 100644
--- a/lib/gnutls_mpi.c
+++ b/lib/gnutls_mpi.c
@@ -66,7 +66,7 @@ _gnutls_mpi_randomize (bigint_t r, unsigned int bits,
     }
 
 
-  ret = gnutls_rnd (level, buf, size);
+  ret = _gnutls_rnd (level, buf, size);
   if (ret < 0)
     {
       gnutls_assert ();
diff --git a/lib/gnutls_pk.c b/lib/gnutls_pk.c
index 59eb9478c5..ef3bfc634e 100644
--- a/lib/gnutls_pk.c
+++ b/lib/gnutls_pk.c
@@ -91,7 +91,7 @@ _gnutls_pkcs1_rsa_encrypt (gnutls_datum_t * ciphertext,
           return GNUTLS_E_INTERNAL_ERROR;
         }
 
-      ret = gnutls_rnd (GNUTLS_RND_RANDOM, ps, psize);
+      ret = _gnutls_rnd (GNUTLS_RND_RANDOM, ps, psize);
       if (ret < 0)
         {
           gnutls_assert ();
@@ -101,7 +101,7 @@ _gnutls_pkcs1_rsa_encrypt (gnutls_datum_t * ciphertext,
       for (i = 0; i < psize; i++)
         while (ps[i] == 0)
           {
-            ret = gnutls_rnd (GNUTLS_RND_RANDOM, &ps[i], 1);
+            ret = _gnutls_rnd (GNUTLS_RND_RANDOM, &ps[i], 1);
             if (ret < 0)
               {
                 gnutls_assert ();
diff --git a/lib/nettle/gnettle.h b/lib/nettle/gnettle.h
index 768590c73d..f82531c55e 100644
--- a/lib/nettle/gnettle.h
+++ b/lib/nettle/gnettle.h
@@ -1,2 +1 @@
 #define PRIME_CHECK_PARAM 8
-
diff --git a/lib/nettle/mpi.c b/lib/nettle/mpi.c
index a09549e206..292af1d6c9 100644
--- a/lib/nettle/mpi.c
+++ b/lib/nettle/mpi.c
@@ -1,6 +1,5 @@
 /*
- * Copyright (C) 2010 Free
- * Software Foundation, Inc.
+ * Copyright (C) 2010 Free Software Foundation, Inc.
  *
  * Author: Nikos Mavrogiannopoulos
  *
@@ -406,11 +405,12 @@ wrap_nettle_prime_check (bigint_t pp)
 
 /* generate a prime of the form p=2qw+1
  * The algorithm is simple but probably it has to be modified to gcrypt's
- * since it is really really slow. Nature did not want 2qw+1 to be prime.
+ * since it is slow. Nature did not want 2qw+1 to be prime.
  * The generator will be the generator of a subgroup of order q-1.
  *
  * Algorithm based on the algorithm in "A Computational Introduction to Number 
  * Theory and Algebra" by V. Shoup, sec 11.1 Finding a generator for Z^{*}_p
+ *
  */
 inline static int
 gen_group (mpz_t * prime, mpz_t * generator, unsigned int nbits)
@@ -439,6 +439,11 @@ gen_group (mpz_t * prime, mpz_t * generator, unsigned int nbits)
   if (nbits % 8 != 0)
     p_bytes++;
 
+  w_bits = nbits - q_bytes * 8;
+  w_bytes = w_bits / 8;
+  if (w_bits % 8 != 0)
+    w_bytes++;
+
   _gnutls_debug_log
     ("Generating group of prime of %u bits and format of 2wq+1. q_size=%u bits\n",
      nbits, q_bytes * 8);
@@ -459,50 +464,44 @@ gen_group (mpz_t * prime, mpz_t * generator, unsigned int nbits)
    */
   for (;;)
     {
-      ret = gnutls_rnd (GNUTLS_RND_RANDOM, buffer, q_bytes);
+      ret = _gnutls_rnd (GNUTLS_RND_RANDOM, buffer, w_bytes);
       if (ret < 0)
         {
           gnutls_assert ();
           goto fail;
         }
 
-      nettle_mpz_set_str_256_u (q, q_bytes, buffer);
+      nettle_mpz_set_str_256_u (w, w_bytes, buffer);
       /* always odd */
       mpz_setbit (q, 0);
 
-      ret = mpz_probab_prime_p (q, PRIME_CHECK_PARAM);
+      ret = mpz_probab_prime_p (w, PRIME_CHECK_PARAM);
       if (ret > 0)
         {
           break;
         }
     }
 
-  /* now generate w of size p_bytes - q_bytes */
-
-  w_bits = nbits - wrap_nettle_mpi_get_nbits (&q);
+  /* now generate q of size p_bytes - w_bytes */
 
   _gnutls_debug_log
-    ("Found prime q of %u bits. Will look for w of %u bits...\n",
-     wrap_nettle_mpi_get_nbits (&q), w_bits);
-
-  w_bytes = w_bits / 8;
-  if (w_bits % 8 != 0)
-    w_bytes++;
+    ("Found prime w of %u bits. Will look for q of %u bits...\n",
+     wrap_nettle_mpi_get_nbits (&w), q_bytes*8);
 
   for (;;)
     {
-      ret = gnutls_rnd (GNUTLS_RND_RANDOM, buffer, w_bytes);
+      ret = _gnutls_rnd (GNUTLS_RND_RANDOM, buffer, q_bytes);
       if (ret < 0)
         {
           gnutls_assert ();
           return ret;
         }
 
-      nettle_mpz_set_str_256_u (w, w_bytes, buffer);
+      nettle_mpz_set_str_256_u (q, q_bytes, buffer);
       /* always odd */
       mpz_setbit (w, 0);
 
-      ret = mpz_probab_prime_p (w, PRIME_CHECK_PARAM);
+      ret = mpz_probab_prime_p (q, PRIME_CHECK_PARAM);
       if (ret == 0)
         {
           continue;
@@ -520,8 +519,8 @@ gen_group (mpz_t * prime, mpz_t * generator, unsigned int nbits)
         }
     }
 
-  _gnutls_debug_log ("Found prime w of %u bits. Looking for generator...\n",
-                     wrap_nettle_mpi_get_nbits (&w));
+  _gnutls_debug_log ("Found prime q of %u bits. Looking for generator...\n",
+                     wrap_nettle_mpi_get_nbits (&q));
 
   /* finally a prime! Let calculate generator
    */
@@ -539,7 +538,7 @@ gen_group (mpz_t * prime, mpz_t * generator, unsigned int nbits)
 
   for (;;)
     {
-      ret = gnutls_rnd (GNUTLS_RND_RANDOM, buffer, r_bytes);
+      ret = _gnutls_rnd (GNUTLS_RND_NONCE, buffer, r_bytes);
       if (ret < 0)
         {
           gnutls_assert ();
diff --git a/lib/nettle/pk.c b/lib/nettle/pk.c
index 5221aa66f0..7e73d51abf 100644
--- a/lib/nettle/pk.c
+++ b/lib/nettle/pk.c
@@ -48,7 +48,7 @@ static inline int is_supported_curve(int curve);
 static void
 rnd_func (void *_ctx, unsigned length, uint8_t * data)
 {
-  gnutls_rnd (GNUTLS_RND_RANDOM, data, length);
+  _gnutls_rnd (GNUTLS_RND_RANDOM, data, length);
 }
 
 static void
diff --git a/lib/nettle/rnd.c b/lib/nettle/rnd.c
index 6e7c69aca7..3f611f1db2 100644
--- a/lib/nettle/rnd.c
+++ b/lib/nettle/rnd.c
@@ -447,20 +447,23 @@ wrap_nettle_rnd (void *_ctx, int level, void *data, size_t datasize)
 
   RND_LOCK;
 
-  ret = do_trivia_source (0);
-  if (ret < 0)
+  if (level != GNUTLS_RND_NONCE)
     {
-      RND_UNLOCK;
-      gnutls_assert ();
-      return ret;
-    }
+      ret = do_trivia_source (0);
+      if (ret < 0)
+        {
+          RND_UNLOCK;
+          gnutls_assert ();
+          return ret;
+        }
 
-  ret = do_device_source (0);
-  if (ret < 0)
-    {
-      RND_UNLOCK;
-      gnutls_assert ();
-      return ret;
+      ret = do_device_source (0);
+      if (ret < 0)
+        {
+          RND_UNLOCK;
+          gnutls_assert ();
+          return ret;
+        }
     }
 
   yarrow256_random (&yctx, datasize, data);
diff --git a/lib/opencdk/misc.c b/lib/opencdk/misc.c
index 5b6c838bbb..17e4eabc91 100644
--- a/lib/opencdk/misc.c
+++ b/lib/opencdk/misc.c
@@ -186,7 +186,7 @@ _cdk_tmpfile (void)
   FILE *fp;
   int fd, i;
 
-  gnutls_rnd (GNUTLS_RND_NONCE, rnd, DIM (rnd));
+  _gnutls_rnd (GNUTLS_RND_NONCE, rnd, DIM (rnd));
   for (i = 0; i < DIM (rnd) - 1; i++)
     {
       char c = letters[(unsigned char) rnd[i] % 26];
diff --git a/lib/pkcs11_secret.c b/lib/pkcs11_secret.c
index ae408cca95..1d74232ba6 100644
--- a/lib/pkcs11_secret.c
+++ b/lib/pkcs11_secret.c
@@ -70,7 +70,7 @@ gnutls_pkcs11_copy_secret_key (const char *token_url, gnutls_datum_t * key,
     }
 
   /* generate a unique ID */
-  ret = gnutls_rnd (GNUTLS_RND_NONCE, id, sizeof (id));
+  ret = _gnutls_rnd (GNUTLS_RND_NONCE, id, sizeof (id));
   if (ret < 0)
     {
       gnutls_assert ();
diff --git a/lib/random.c b/lib/random.c
index 5088e6ac47..bfbb27de3d 100644
--- a/lib/random.c
+++ b/lib/random.c
@@ -27,14 +27,14 @@
 #include <gnutls_errors.h>
 #include <random.h>
 
-static void *rnd_ctx;
+void *gnutls_rnd_ctx;
 
 int
 _gnutls_rnd_init (void)
 {
   if (_gnutls_rnd_ops.init != NULL)
     {
-      if (_gnutls_rnd_ops.init (&rnd_ctx) < 0)
+      if (_gnutls_rnd_ops.init (&gnutls_rnd_ctx) < 0)
         {
           gnutls_assert ();
           return GNUTLS_E_RANDOM_FAILED;
@@ -49,7 +49,7 @@ _gnutls_rnd_deinit (void)
 {
   if (_gnutls_rnd_ops.deinit != NULL)
     {
-      _gnutls_rnd_ops.deinit (rnd_ctx);
+      _gnutls_rnd_ops.deinit (gnutls_rnd_ctx);
     }
 
   return;
@@ -71,9 +71,5 @@ _gnutls_rnd_deinit (void)
 int
 gnutls_rnd (gnutls_rnd_level_t level, void *data, size_t len)
 {
-  if (len > 0)
-    {
-      return _gnutls_rnd_ops.rnd (rnd_ctx, level, data, len);
-    }
-  return 0;
+  return _gnutls_rnd(level, data, len);
 }
diff --git a/lib/random.h b/lib/random.h
index 5f82c2fcec..921f8dc922 100644
--- a/lib/random.h
+++ b/lib/random.h
@@ -27,8 +27,19 @@
 #include <crypto-backend.h>
 
 extern int crypto_rnd_prio;
+extern void* gnutls_rnd_ctx;
 extern gnutls_crypto_rnd_st _gnutls_rnd_ops;
 
+inline static int
+_gnutls_rnd (gnutls_rnd_level_t level, void *data, size_t len)
+{
+  if (len > 0)
+    {
+      return _gnutls_rnd_ops.rnd (gnutls_rnd_ctx, level, data, len);
+    }
+  return 0;
+}
+
 void _gnutls_rnd_deinit (void);
 int _gnutls_rnd_init (void);
 
diff --git a/lib/x509/pkcs12.c b/lib/x509/pkcs12.c
index 3e93d3c2c1..4d9963ca1c 100644
--- a/lib/x509/pkcs12.c
+++ b/lib/x509/pkcs12.c
@@ -878,7 +878,7 @@ gnutls_pkcs12_generate_mac (gnutls_pkcs12_t pkcs12, const char *pass)
 
   /* Generate the salt.
    */
-  result = gnutls_rnd (GNUTLS_RND_NONCE, salt, sizeof (salt));
+  result = _gnutls_rnd (GNUTLS_RND_NONCE, salt, sizeof (salt));
   if (result < 0)
     {
       gnutls_assert ();
diff --git a/lib/x509/privkey_pkcs8.c b/lib/x509/privkey_pkcs8.c
index b9d2eca5cb..4421c73971 100644
--- a/lib/x509/privkey_pkcs8.c
+++ b/lib/x509/privkey_pkcs8.c
@@ -1901,7 +1901,7 @@ generate_key (schema_id schema,
   opaque rnd[2];
   int ret;
 
-  ret = gnutls_rnd (GNUTLS_RND_RANDOM, rnd, 2);
+  ret = _gnutls_rnd (GNUTLS_RND_RANDOM, rnd, 2);
   if (ret < 0)
     {
       gnutls_assert ();
@@ -1944,7 +1944,7 @@ generate_key (schema_id schema,
       return GNUTLS_E_INVALID_REQUEST;
     }
 
-  ret = gnutls_rnd (GNUTLS_RND_RANDOM, kdf_params->salt,
+  ret = _gnutls_rnd (GNUTLS_RND_RANDOM, kdf_params->salt,
                      kdf_params->salt_size);
   if (ret < 0)
     {
@@ -1986,7 +1986,7 @@ generate_key (schema_id schema,
 
       if (enc_params->iv_size)
         {
-          ret = gnutls_rnd (GNUTLS_RND_NONCE,
+          ret = _gnutls_rnd (GNUTLS_RND_NONCE,
                              enc_params->iv, enc_params->iv_size);
           if (ret < 0)
             {