optimized DH group generation process (ported from 3.0.x)

3 files changed, 27 insertions, 21 deletions

diff --git a/NEWS b/NEWS
index 977e3c8d7f..182a0cd0c6 100644
--- a/NEWS
+++ b/NEWS
@@ -3,6 +3,14 @@ Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005,
               2006, 2007, 2008, 2009, 2010, 2011 Free Software Foundation, Inc.
 See the end for copying conditions.
 
+Version 2.12.15 (unreleased)
+
+** libgnutls: Optimized DH generation process (ported from 3.0.x)
+
+** API and ABI modifications:
+
+No changes since last version.
+
 Version 2.12.14 (released 2011-11-08)
 
 ** libgnutls: Corrected fix in gnutls_session_get_data()
diff --git a/lib/nettle/mpi.c b/lib/nettle/mpi.c
index c76705c18f..5c5e9737fe 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,2011 Free Software Foundation, Inc.
  *
  * Author: Nikos Mavrogiannopoulos
  *
@@ -408,7 +407,7 @@ 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 
@@ -441,6 +440,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);
@@ -468,11 +472,11 @@ gen_group (mpz_t * prime, mpz_t * generator, unsigned int nbits)
           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);
+      mpz_setbit (w, 0);
 
-      ret = mpz_probab_prime_p (q, PRIME_CHECK_PARAM);
+      ret = mpz_probab_prime_p (w, PRIME_CHECK_PARAM);
       if (ret > 0)
         {
           break;
@@ -481,30 +485,24 @@ gen_group (mpz_t * prime, mpz_t * generator, unsigned int nbits)
 
   /* now generate w of size p_bytes - q_bytes */
 
-  w_bits = nbits - wrap_nettle_mpi_get_nbits (&q);
-
   _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);
+      mpz_setbit (q, 0);
 
-      ret = mpz_probab_prime_p (w, PRIME_CHECK_PARAM);
+      ret = mpz_probab_prime_p (q, PRIME_CHECK_PARAM);
       if (ret == 0)
         {
           continue;
@@ -522,8 +520,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
    */
diff --git a/tests/Makefile.am b/tests/Makefile.am
index 53012fac70..457926e84a 100644
--- a/tests/Makefile.am
+++ b/tests/Makefile.am
@@ -64,7 +64,7 @@ ctests = simple gc set_pkcs12_cred certder certuniqueid mpi			\
 	crq_key_id x509sign-verify cve-2009-1415 cve-2009-1416		\
 	crq_apis init_roundtrip pkcs12_s2k_pem dn2 mini-eagain		\
 	nul-in-x509-names x509_altname pkcs12_encode mini-x509		\
-	mini-x509-rehandshake rng-fork x509cert #gendh
+	mini-x509-rehandshake rng-fork x509cert gendh
 
 if ENABLE_OPENSSL
 ctests +=  openssl