Initial checkin1.5.6

1 files changed, 177 insertions, 0 deletions

diff --git a/src/make_prm.cpp b/src/make_prm.cpp
new file mode 100644
index 000000000..2874cb365
--- /dev/null
+++ b/src/make_prm.cpp
@@ -0,0 +1,177 @@
+/*************************************************
+* Prime Generation Source File                   *
+* (C) 1999-2006 The Botan Project                *
+*************************************************/
+
+#include <botan/numthry.h>
+#include <botan/lookup.h>
+#include <botan/bit_ops.h>
+#include <botan/parsing.h>
+#include <botan/rng.h>
+#include <botan/ui.h>
+#include <algorithm>
+#include <memory>
+
+namespace Botan {
+
+namespace {
+
+/*************************************************
+* Increment the seed by one                      *
+*************************************************/
+void increment(SecureVector<byte>& seed)
+   {
+   for(u32bit j = seed.size(); j > 0; --j)
+      if(++seed[j-1])
+         break;
+   }
+
+}
+
+/*************************************************
+* Attempt DSA prime generation with given seed   *
+*************************************************/
+bool generate_dsa_primes(BigInt& p, BigInt& q, const byte const_seed[],
+                         u32bit seed_len, u32bit pbits, u32bit counter_start)
+   {
+   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));
+
+   std::auto_ptr<HashFunction> sha1(get_hash("SHA-1"));
+
+   SecureVector<byte> seed(const_seed, seed_len);
+
+   SecureVector<byte> qhash = sha1->process(seed);
+   increment(seed);
+   SecureVector<byte> qhash2 = sha1->process(seed);
+   xor_buf(qhash, qhash2, qhash.size());
+
+   qhash[0] |= 0x80;
+   qhash[19] |= 0x01;
+   q.binary_decode(qhash, qhash.size());
+   if(!is_prime(q))
+      return false;
+   UI::pulse(UI::PRIME_FOUND);
+
+   u32bit n = (pbits-1) / 160, b = (pbits-1) % 160;
+   SecureVector<byte> W(20 * (n+1));
+   BigInt X;
+
+   for(u32bit j = 0; j != counter_start; ++j)
+      for(u32bit k = 0; k != n + 1; ++k)
+         increment(seed);
+
+   for(u32bit j = 0; j != 4096 - counter_start; ++j)
+      {
+      UI::pulse(UI::PRIME_SEARCHING);
+
+      for(u32bit k = 0; k != n + 1; ++k)
+         {
+         increment(seed);
+         sha1->update(seed);
+         sha1->final(W + 20 * (n-k));
+         }
+      X.binary_decode(W + (20 - 1 - b/8), W.size() - (20 - 1 - b/8));
+      X.set_bit(pbits-1);
+
+      p = X - (X % (2*q) - 1);
+
+      if(p.bits() == pbits && is_prime(p))
+         {
+         UI::pulse(UI::PRIME_FOUND);
+         return true;
+         }
+      }
+   return false;
+   }
+
+/*************************************************
+* Generate DSA Primes                            *
+*************************************************/
+SecureVector<byte> generate_dsa_primes(BigInt& p, BigInt& q, u32bit pbits)
+   {
+   SecureVector<byte> seed(20);
+
+   while(true)
+      {
+      Global_RNG::randomize(seed, seed.size());
+      UI::pulse(UI::PRIME_SEARCHING);
+      if(generate_dsa_primes(p, q, seed, seed.size(), pbits))
+         return seed;
+      }
+   }
+
+/*************************************************
+* Generate a random prime                        *
+*************************************************/
+BigInt random_prime(u32bit bits, const BigInt& coprime,
+                    u32bit equiv, u32bit modulo)
+   {
+   if(bits <= 48)
+      throw Invalid_Argument("random_prime: Can't make a prime of " +
+                             to_string(bits) + " bits");
+
+   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)
+      {
+      UI::pulse(UI::PRIME_SEARCHING);
+
+      BigInt p = random_integer(bits);
+      p.set_bit(bits - 2);
+      p.set_bit(0);
+
+      if(p % modulo != equiv)
+         p += (modulo - p % modulo) + equiv;
+
+      const u32bit sieve_size = std::min(bits / 2, PRIME_TABLE_SIZE);
+      SecureVector<u32bit> sieve(sieve_size);
+
+      for(u32bit j = 0; j != sieve.size(); ++j)
+         {
+         sieve[j] = p % PRIMES[j];
+         UI::pulse(UI::PRIME_SIEVING);
+         }
+
+      u32bit counter = 0;
+      while(true)
+         {
+         if(counter == 4096 || p.bits() > bits)
+            break;
+
+         UI::pulse(UI::PRIME_SEARCHING);
+
+         bool passes_sieve = true;
+         ++counter;
+         p += modulo;
+
+         for(u32bit j = 0; j != sieve.size(); ++j)
+            {
+            sieve[j] = (sieve[j] + modulo) % PRIMES[j];
+            UI::pulse(UI::PRIME_SIEVING);
+            if(sieve[j] == 0)
+               passes_sieve = false;
+            }
+
+         if(!passes_sieve || gcd(p - 1, coprime) != 1)
+            continue;
+         UI::pulse(UI::PRIME_PASSED_SIEVE);
+         if(passes_mr_tests(p))
+            {
+            UI::pulse(UI::PRIME_FOUND);
+            return p;
+            }
+         }
+      }
+   }
+
+}