Alter one of the constructors of DL_Group to take a parameter specifying

how big q should be.

Add FIPS 186-3 DSA parameter generation, this allows for generating larger
(2048 and 3072 bit) DSA keys. At this time there do not seem to be official
test vectors for 186-3, and I have not checked against other implementations.
Tests will be constructed using the latest OpenSSL snapshot.

3 files changed, 61 insertions, 40 deletions

diff --git a/include/dl_group.h b/include/dl_group.h
index 6cd46c1c4..9c503b5f3 100644
--- a/include/dl_group.h
+++ b/include/dl_group.h
@@ -33,15 +33,16 @@ class DL_Group
 
       DL_Group();
       DL_Group(const std::string&);
-      DL_Group(u32bit, PrimeType = Strong);
+      DL_Group(PrimeType, u32bit, u32bit = 0);
       DL_Group(const MemoryRegion<byte>&, u32bit = 1024, u32bit = 0);
       DL_Group(const BigInt&, const BigInt&);
       DL_Group(const BigInt&, const BigInt&, const BigInt&);
    private:
       static BigInt make_dsa_generator(const BigInt&, const BigInt&);
-      static SecureVector<byte> generate_dsa_primes(BigInt&, BigInt&, u32bit);
-      static bool generate_dsa_primes(BigInt&, BigInt&, const byte[], u32bit,
-                                      u32bit, u32bit = 0);
+      static SecureVector<byte> generate_dsa_primes(BigInt&, BigInt&,
+                                                    u32bit, u32bit);
+      static bool generate_dsa_primes(BigInt&, BigInt&, u32bit, u32bit,
+                                      const MemoryRegion<byte>&);
 
       void init_check() const;
       void initialize(const BigInt&, const BigInt&, const BigInt&);
diff --git a/src/dl_group.cpp b/src/dl_group.cpp
index 78a2952be..9d50458dd 100644
--- a/src/dl_group.cpp
+++ b/src/dl_group.cpp
@@ -35,7 +35,7 @@ DL_Group::DL_Group(const std::string& type)
 /*************************************************
 * DL_Group Constructor                           *
 *************************************************/
-DL_Group::DL_Group(u32bit pbits, PrimeType type)
+DL_Group::DL_Group(PrimeType type, u32bit pbits, u32bit qbits)
    {
    if(pbits < 512)
       throw Invalid_Argument("DL_Group: prime size " + to_string(pbits) +
@@ -51,7 +51,9 @@ DL_Group::DL_Group(u32bit pbits, PrimeType type)
       {
       if(type == Prime_Subgroup)
          {
-         const u32bit qbits = 2 * dl_work_factor(pbits);
+         if(!qbits)
+            qbits = 2 * dl_work_factor(pbits);
+
          q = random_prime(qbits);
          BigInt X;
          while(p.bits() != pbits || !is_prime(p))
@@ -61,7 +63,10 @@ DL_Group::DL_Group(u32bit pbits, PrimeType type)
             }
          }
       else
-         generate_dsa_primes(p, q, pbits);
+         {
+         qbits = qbits ? qbits : ((pbits == 1024) ? 160 : 256);
+         generate_dsa_primes(p, q, pbits, qbits);
+         }
 
       g = make_dsa_generator(p, q);
       }
@@ -72,9 +77,9 @@ DL_Group::DL_Group(u32bit pbits, PrimeType type)
 /*************************************************
 * DL_Group Constructor                           *
 *************************************************/
-DL_Group::DL_Group(const MemoryRegion<byte>& seed, u32bit pbits, u32bit start)
+DL_Group::DL_Group(const MemoryRegion<byte>& seed, u32bit pbits, u32bit qbits)
    {
-   if(!generate_dsa_primes(p, q, seed.begin(), seed.size(), pbits, start))
+   if(!generate_dsa_primes(p, q, pbits, qbits, seed))
       throw Invalid_Argument("DL_Group: The seed/counter given does not "
                              "generate a DSA group");
 
diff --git a/src/dsa_gen.cpp b/src/dsa_gen.cpp
index 996cb550e..4eecb146d 100644
--- a/src/dsa_gen.cpp
+++ b/src/dsa_gen.cpp
@@ -27,57 +27,71 @@ void increment(SecureVector<byte>& seed)
          break;
    }
 
+/*************************************************
+* Check if this size is allowed by FIPS 186-3    *
+*************************************************/
+bool fips186_3_valid_size(u32bit pbits, u32bit qbits)
+   {
+   if(pbits == 1024 && qbits == 160)
+      return true;
+   if(pbits == 2048 && qbits == 256)
+      return true;
+   if(pbits == 3072 && qbits == 256)
+      return true;
+   return false;
+   }
+
 }
 
 /*************************************************
 * Attempt DSA prime generation with given seed   *
 *************************************************/
 bool DL_Group::generate_dsa_primes(BigInt& p, BigInt& q,
-                                   const byte const_seed[], u32bit seed_len,
-                                   u32bit pbits, u32bit counter_start)
+                                   u32bit pbits, u32bit qbits,
+                                   const MemoryRegion<byte>& seed_c)
    {
-   if(seed_len < 20)
-      throw Invalid_Argument("DSA prime generation needs a seed "
-                             "at least 160 bits long");
-   if((pbits % 64 != 0) || (pbits > 1024) || (pbits < 512))
-      throw Invalid_Argument("DSA prime generation algorithm does not support "
-                             "prime size " + to_string(pbits));
+   if(!fips186_3_valid_size(pbits, qbits))
+      throw Invalid_Argument(
+         "FIPS 186-3 does not allow DSA domain parameters of " +
+         to_string(pbits) + "/" + to_string(qbits) + " bits long");
+
+   if(seed_c.size() * 8 < qbits)
+      throw Invalid_Argument(
+         "Generating a DSA parameter set with a " + to_string(qbits) +
+         "long q requires a seed at least as many bits long");
 
-   std::auto_ptr<HashFunction> sha1(get_hash("SHA-1"));
+   std::auto_ptr<HashFunction> hash(get_hash("SHA-" + to_string(qbits)));
 
-   SecureVector<byte> seed(const_seed, seed_len);
+   const u32bit HASH_SIZE = hash->OUTPUT_LENGTH;
 
-   SecureVector<byte> qhash = sha1->process(seed);
-   increment(seed);
-   SecureVector<byte> qhash2 = sha1->process(seed);
-   xor_buf(qhash, qhash2, qhash.size());
+   SecureVector<byte> seed = seed_c;
+
+   q.binary_decode(hash->process(seed));
+   q.set_bit(qbits-1);
+   q.set_bit(0);
 
-   qhash[0] |= 0x80;
-   qhash[19] |= 0x01;
-   q.binary_decode(qhash, qhash.size());
    if(!is_prime(q))
       return false;
+
    global_state().pulse(PRIME_FOUND);
 
-   u32bit n = (pbits-1) / 160, b = (pbits-1) % 160;
-   SecureVector<byte> W(20 * (n+1));
-   BigInt X;
+   const u32bit n = (pbits-1) / (HASH_SIZE * 8), b = (pbits-1) % (HASH_SIZE * 8);
 
-   for(u32bit j = 0; j != counter_start; ++j)
-      for(u32bit k = 0; k != n + 1; ++k)
-         increment(seed);
+   BigInt X;
+   SecureVector<byte> V(HASH_SIZE * (n+1));
 
-   for(u32bit j = 0; j != 4096 - counter_start; ++j)
+   for(u32bit j = 0; j != 4096; ++j)
       {
       global_state().pulse(PRIME_SEARCHING);
 
-      for(u32bit k = 0; k != n + 1; ++k)
+      for(u32bit k = 0; k <= n; ++k)
          {
          increment(seed);
-         sha1->update(seed);
-         sha1->final(W + 20 * (n-k));
+         hash->update(seed);
+         hash->final(V + HASH_SIZE * (n-k));
          }
-      X.binary_decode(W + (20 - 1 - b/8), W.size() - (20 - 1 - b/8));
+
+      X.binary_decode(V + (HASH_SIZE - 1 - b/8), V.size() - (HASH_SIZE - 1 - b/8));
       X.set_bit(pbits-1);
 
       p = X - (X % (2*q) - 1);
@@ -95,15 +109,16 @@ bool DL_Group::generate_dsa_primes(BigInt& p, BigInt& q,
 * Generate DSA Primes                            *
 *************************************************/
 SecureVector<byte> DL_Group::generate_dsa_primes(BigInt& p, BigInt& q,
-                                                 u32bit pbits)
+                                                 u32bit pbits, u32bit qbits)
    {
-   SecureVector<byte> seed(20);
+   SecureVector<byte> seed(qbits/8);
 
    while(true)
       {
       Global_RNG::randomize(seed, seed.size());
       global_state().pulse(PRIME_SEARCHING);
-      if(generate_dsa_primes(p, q, seed, seed.size(), pbits, 0))
+
+      if(generate_dsa_primes(p, q, pbits, qbits, seed))
          return seed;
       }
    }