Add prime and dl_group command line tools.

Some cleanups in random_prime. Increase probability in prime tests from
1/2**64 to 1/2**128. Also break out of the sieve loop early if it has
failed.

4 files changed, 177 insertions, 14 deletions

diff --git a/doc/news.rst b/doc/news.rst
index 99ff04238..9eddabd5c 100644
--- a/doc/news.rst
+++ b/doc/news.rst
@@ -22,6 +22,8 @@ Version 1.11.22, Not Yet Released
   system RNG or an AutoSeeded_RNG, depending on availability, which this
   additional type allows.
 
+* New command line tools `dl_group` and `prime`
+
 * The `configure.py` option `--no-autoload` is now also available
   under the more understandable name `--minimized-build`.
 
diff --git a/src/cmd/dl_group.cpp b/src/cmd/dl_group.cpp
new file mode 100644
index 000000000..2db65ded2
--- /dev/null
+++ b/src/cmd/dl_group.cpp
@@ -0,0 +1,85 @@
+/*
+* (C) 2015 Jack Lloyd
+*
+* Botan is released under the Simplified BSD License (see license.txt)
+*/
+
+#include "apps.h"
+
+#if defined(BOTAN_HAS_DL_GROUP)
+
+#include <botan/dl_group.h>
+#include <fstream>
+
+namespace {
+
+std::string read_file_contents(const std::string& filename)
+   {
+   std::ifstream in(filename.c_str());
+   if(!in.good())
+      throw std::runtime_error("Failure reading " + filename);
+
+   std::vector<std::string> contents;
+   size_t total_size = 0;
+   while(in.good())
+      {
+      std::string line;
+      std::getline(in, line);
+      total_size += line.size();
+      contents.push_back(std::move(line));
+      }
+
+   std::string res;
+   contents.reserve(total_size);
+   for(auto&& line : contents)
+      res += line;
+   return res;
+   }
+
+int dl_group(int argc, char* argv[])
+   {
+   if(argc < 2)
+      {
+      std::cout << "Usage: " << argv[0] << " [create bits|info file]" << std::endl;
+      return 1;
+      }
+
+   const std::string cmd = argv[1];
+
+   if(cmd == "create")
+      {
+      AutoSeeded_RNG rng;
+      const size_t bits = to_u32bit(argv[2]);
+
+      const DL_Group::PrimeType prime_type = DL_Group::Strong;
+      //const DL_Group::PrimeType prime_type = DL_Group::Prime_Subgroup;
+
+      DL_Group grp(rng, prime_type, bits);
+
+      std::cout << grp.PEM_encode(DL_Group::DSA_PARAMETERS);
+      }
+   else if(cmd == "info")
+      {
+      DL_Group grp;
+      std::string pem = read_file_contents(argv[2]);
+      std::cout << pem << "\n";
+
+      std::cout << "DL_Group " << grp.get_p().bits() << " bits\n";
+      std::cout << "p=" << grp.get_p() << "\n";
+      std::cout << "q=" << grp.get_q() << "\n";
+      std::cout << "g=" << grp.get_g() << "\n";
+      }
+   else
+      {
+      std::cout << "ERROR: Unknown command\n";
+      return 1;
+      }
+
+   return 0;
+   }
+
+REGISTER_APP(dl_group);
+
+}
+
+#endif
diff --git a/src/cmd/prime.cpp b/src/cmd/prime.cpp
new file mode 100644
index 000000000..61f535dd7
--- /dev/null
+++ b/src/cmd/prime.cpp
@@ -0,0 +1,48 @@
+/*
+* (C) 2015 Jack Lloyd
+*
+* Botan is released under the Simplified BSD License (see license.txt)
+*/
+
+#include "apps.h"
+
+#if defined(BOTAN_HAS_NUMBERTHEORY)
+
+#include <botan/numthry.h>
+
+#include <algorithm>
+#include <iostream>
+
+namespace {
+
+int prime(int argc, char* argv[])
+   {
+   if(argc < 2)
+      {
+      std::cout << "Usage: " << argv[0] << " bits count" << std::endl;
+      return 1;
+      }
+
+   AutoSeeded_RNG rng;
+   const size_t bits = to_u32bit(argv[1]);
+   const size_t cnt = argv[2] != nullptr ? to_u32bit(argv[2]) : 1;
+
+   for(size_t i = 0; i != cnt; ++i)
+      {
+      const BigInt p = random_prime(rng, bits);
+      std::cout << p << "\n";
+
+      if(p.bits() != bits)
+         {
+         std::cout << "Result not exactly requested bit size, got " << p.bits() << "\n";
+         }
+      }
+
+   return 0;
+   }
+
+}
+
+REGISTER_APP(prime);
+
+#endif
diff --git a/src/lib/math/numbertheory/make_prm.cpp b/src/lib/math/numbertheory/make_prm.cpp
index 1333fdf04..3d82adf06 100644
--- a/src/lib/math/numbertheory/make_prm.cpp
+++ b/src/lib/math/numbertheory/make_prm.cpp
@@ -18,22 +18,37 @@ BigInt random_prime(RandomNumberGenerator& rng,
                     size_t bits, const BigInt& coprime,
                     size_t equiv, size_t modulo)
    {
+   if(coprime <= 0)
+      {
+      throw Invalid_Argument("random_prime: coprime must be > 0");
+      }
+   if(modulo % 2 == 1 || modulo == 0)
+      {
+      throw Invalid_Argument("random_prime: Invalid modulo value");
+      }
+   if(equiv >= modulo || equiv % 2 == 0)
+      {
+      throw Invalid_Argument("random_prime: equiv must be < modulo, and odd");
+      }
+
+   // Handle small values:
    if(bits <= 1)
+      {
       throw Invalid_Argument("random_prime: Can't make a prime of " +
                              std::to_string(bits) + " bits");
+      }
    else if(bits == 2)
+      {
       return ((rng.next_byte() % 2) ? 2 : 3);
+      }
    else if(bits == 3)
+      {
       return ((rng.next_byte() % 2) ? 5 : 7);
+      }
    else if(bits == 4)
+      {
       return ((rng.next_byte() % 2) ? 11 : 13);
-
-   if(coprime <= 0)
-      throw Invalid_Argument("random_prime: coprime must be > 0");
-   if(modulo % 2 == 1 || modulo == 0)
-      throw Invalid_Argument("random_prime: Invalid modulo value");
-   if(equiv >= modulo || equiv % 2 == 0)
-      throw Invalid_Argument("random_prime: equiv must be < modulo, and odd");
+      }
 
    while(true)
       {
@@ -56,27 +71,39 @@ BigInt random_prime(RandomNumberGenerator& rng,
       size_t counter = 0;
       while(true)
          {
-         if(counter == 4096 || p.bits() > bits)
-            break;
-
-         bool passes_sieve = true;
          ++counter;
+
+         if(counter >= 4096)
+            {
+            break; // don't try forever, choose a new starting point
+            }
+
          p += modulo;
 
          if(p.bits() > bits)
             break;
 
+         bool passes_sieve = true;
          for(size_t j = 0; j != sieve.size(); ++j)
             {
             sieve[j] = (sieve[j] + modulo) % PRIMES[j];
             if(sieve[j] == 0)
+               {
                passes_sieve = false;
+               break;
+               }
             }
 
-         if(!passes_sieve || gcd(p - 1, coprime) != 1)
+         if(!passes_sieve)
+            continue;
+
+         if(gcd(p - 1, coprime) != 1)
             continue;
-         if(is_prime(p, rng, 64, true))
+
+         if(is_prime(p, rng, 128, true))
+            {
             return p;
+            }
          }
       }
    }
@@ -93,7 +120,8 @@ BigInt random_safe_prime(RandomNumberGenerator& rng, size_t bits)
    BigInt p;
    do
       p = (random_prime(rng, bits - 1) << 1) + 1;
-   while(!is_prime(p, rng, 64, true));
+   while(!is_prime(p, rng, 128, true));
+
    return p;
    }