Avoid potential side channel when generating RSA primes

Add a new function dedicated to generating RSA primes.

Don't test for p.bits() > bits until the very end - rarely happens,
and speeds up prime generation quite noticably.

Add Miller-Rabin error probabilities for 1/2**128, which again
speeds up RSA keygen and DL param gen quite a bit.

3 files changed, 173 insertions, 41 deletions

diff --git a/src/lib/math/numbertheory/make_prm.cpp b/src/lib/math/numbertheory/make_prm.cpp
index bd0ae8e92..85089c9cb 100644
--- a/src/lib/math/numbertheory/make_prm.cpp
+++ b/src/lib/math/numbertheory/make_prm.cpp
@@ -12,6 +12,61 @@
 
 namespace Botan {
 
+namespace {
+
+class Prime_Sieve
+   {
+   public:
+      Prime_Sieve(const BigInt& init_value) : m_sieve(PRIME_TABLE_SIZE)
+         {
+         for(size_t i = 0; i != m_sieve.size(); ++i)
+            m_sieve[i] = static_cast<uint16_t>(init_value % PRIMES[i]);
+         }
+
+      void step(word increment)
+         {
+         for(size_t i = 0; i != m_sieve.size(); ++i)
+            {
+            m_sieve[i] = (m_sieve[i] + increment) % PRIMES[i];
+            }
+         }
+
+      bool passes(bool check_2p1 = false) const
+         {
+         for(size_t i = 0; i != m_sieve.size(); ++i)
+            {
+            /*
+            In this case, p is a multiple of PRIMES[i]
+            */
+            if(m_sieve[i] == 0)
+               return false;
+
+            if(check_2p1)
+               {
+               /*
+               In this case, 2*p+1 will be a multiple of PRIMES[i]
+
+               So if potentially generating a safe prime, we want to
+               avoid this value because 2*p+1 will certainly not be prime.
+
+               See "Safe Prime Generation with a Combined Sieve" M. Wiener
+               https://eprint.iacr.org/2003/186.pdf
+               */
+               if(m_sieve[i] == (PRIMES[i] - 1) / 2)
+                  return false;
+               }
+            }
+
+         return true;
+         }
+
+   private:
+      std::vector<uint16_t> m_sieve;
+   };
+
+}
+
+
 /*
 * Generate a random prime
 */
@@ -64,7 +119,6 @@ BigInt random_prime(RandomNumberGenerator& rng,
          }
       }
 
-   secure_vector<uint16_t> sieve(PRIME_TABLE_SIZE);
    const size_t MAX_ATTEMPTS = 32*1024;
 
    while(true)
@@ -79,8 +133,7 @@ BigInt random_prime(RandomNumberGenerator& rng,
       // Force p to be equal to equiv mod modulo
       p += (modulo - (p % modulo)) + equiv;
 
-      for(size_t i = 0; i != sieve.size(); ++i)
-         sieve[i] = static_cast<uint16_t>(p % PRIMES[i]);
+      Prime_Sieve sieve(p);
 
       size_t counter = 0;
       while(true)
@@ -94,46 +147,89 @@ BigInt random_prime(RandomNumberGenerator& rng,
 
          p += modulo;
 
-         if(p.bits() > bits)
-            break;
+         sieve.step(modulo);
 
-         // Now that p is updated, update the sieve
-         for(size_t i = 0; i != sieve.size(); ++i)
-            {
-            sieve[i] = (sieve[i] + modulo) % PRIMES[i];
-            }
+         if(sieve.passes(true) == false)
+            continue;
 
-         bool passes_sieve = true;
-         for(size_t i = 0; passes_sieve && (i != sieve.size()); ++i)
+         if(coprime > 1)
             {
             /*
-            In this case, p is a multiple of PRIMES[i]
+            * Check if gcd(p - 1, coprime) != 1 by computing the inverse. The
+            * gcd algorithm is not constant time, but modular inverse is (for
+            * odd modulus anyway). This avoids a side channel attack against RSA
+            * key generation, though RSA keygen should be using generate_rsa_prime.
             */
-            if(sieve[i] == 0)
-               passes_sieve = false;
+            if(inverse_mod(p - 1, coprime).is_zero())
+               continue;
+            }
 
-            /*
-            In this case, 2*p+1 will be a multiple of PRIMES[i]
+         if(p.bits() > bits)
+            break;
 
-            So if generating a safe prime, we want to avoid this value
-            because 2*p+1 will not be useful. Since the check is cheap to
-            do and doesn't seem to affect the overall distribution of the
-            generated primes overmuch it's used in all cases.
+         if(is_prime(p, rng, prob, true))
+            return p;
+         }
+      }
+   }
 
-            See "Safe Prime Generation with a Combined Sieve" M. Wiener
-            https://eprint.iacr.org/2003/186.pdf
-            */
-            if(sieve[i] == (PRIMES[i] - 1) / 2)
-               passes_sieve = false;
+BigInt generate_rsa_prime(RandomNumberGenerator& keygen_rng,
+                          RandomNumberGenerator& prime_test_rng,
+                          size_t bits,
+                          const BigInt& coprime,
+                          size_t prob)
+   {
+   if(bits < 512)
+      throw Invalid_Argument("generate_rsa_prime bits too small");
+
+   if(coprime <= 1 || coprime.is_even())
+      throw Invalid_Argument("generate_rsa_prime coprime must be odd positive integer");
+
+   const size_t MAX_ATTEMPTS = 32*1024;
+
+   while(true)
+      {
+      BigInt p(keygen_rng, bits);
+
+      // Force lowest and two top bits on
+      p.set_bit(bits - 1);
+      p.set_bit(bits - 2);
+      p.set_bit(0);
+
+      Prime_Sieve sieve(p);
+
+      const word step = 2;
+
+      size_t counter = 0;
+      while(true)
+         {
+         ++counter;
+
+         if(counter > MAX_ATTEMPTS)
+            {
+            break; // don't try forever, choose a new starting point
             }
 
-         if(!passes_sieve)
+         p += step;
+
+         sieve.step(step);
+
+         if(sieve.passes() == false)
             continue;
 
-         if(coprime > 0 && gcd(p - 1, coprime) != 1)
+         /*
+         * Check if gcd(p - 1, coprime) != 1 by computing the inverse. The
+         * gcd algorithm is not constant time, but modular inverse is (for
+         * odd modulus anyway). This avoids a side channel attack against RSA
+         * key generation.
+         */
+         if(inverse_mod(p - 1, coprime).is_zero())
             continue;
 
-         if(is_prime(p, rng, prob, true))
+         if(p.bits() > bits)
+            break;
+
+         if(is_prime(p, prime_test_rng, prob, true))
             return p;
          }
       }
@@ -156,7 +252,7 @@ BigInt random_safe_prime(RandomNumberGenerator& rng, size_t bits)
 
       Otherwise [q == 1 (mod 3) case], 2*q+1 == 3 (mod 3) and not prime.
       */
-      q = random_prime(rng, bits - 1, 1, 2, 3, 8);
+      q = random_prime(rng, bits - 1, 0, 2, 3, 8);
       p = (q << 1) + 1;
 
       if(is_prime(p, rng, 128, true))
@@ -165,7 +261,6 @@ BigInt random_safe_prime(RandomNumberGenerator& rng, size_t bits)
          if(is_prime(q, rng, 128, true))
             return p;
          }
-
       }
    }
 
diff --git a/src/lib/math/numbertheory/numthry.cpp b/src/lib/math/numbertheory/numthry.cpp
index 76d7936bc..8cc930175 100644
--- a/src/lib/math/numbertheory/numthry.cpp
+++ b/src/lib/math/numbertheory/numthry.cpp
@@ -453,22 +453,44 @@ size_t mr_test_iterations(size_t n_bits, size_t prob, bool random)
    const size_t base = (prob + 2) / 2; // worst case 4^-t error rate
 
    /*
+   * If the candidate prime was maliciously constructed, we can't rely
+   * on arguments based on p being random.
+   */
+   if(random == false)
+      return base;
+
+   /*
    * For randomly chosen numbers we can use the estimates from
    * http://www.math.dartmouth.edu/~carlp/PDF/paper88.pdf
    *
    * These values are derived from the inequality for p(k,t) given on
    * the second page.
    */
-   if(random && prob <= 80)
+   if(random)
       {
-      if(n_bits >= 1536)
-         return 2; // < 2^-89
-      if(n_bits >= 1024)
-         return 4; // < 2^-89
-      if(n_bits >= 512)
-         return 5; // < 2^-80
-      if(n_bits >= 256)
-         return 11; // < 2^-80
+      if(prob <= 80)
+         {
+         if(n_bits >= 1536)
+            return 2; // < 2^-89
+         if(n_bits >= 1024)
+            return 3; // < 2^-89
+         if(n_bits >= 512)
+            return 5; // < 2^-80
+         if(n_bits >= 256)
+            return 11; // < 2^-80
+         }
+
+      if(prob <= 128)
+         {
+         if(n_bits >= 1536)
+            return 4; // < 2^-133
+         if(n_bits >= 1024)
+            return 6; // < 2^-133
+         if(n_bits >= 512)
+            return 12; // < 2^-129
+         if(n_bits >= 256)
+            return 28; // < 2^-128
+         }
       }
 
    return base;
diff --git a/src/lib/math/numbertheory/numthry.h b/src/lib/math/numbertheory/numthry.h
index 61da93bcd..7097979bd 100644
--- a/src/lib/math/numbertheory/numthry.h
+++ b/src/lib/math/numbertheory/numthry.h
@@ -189,7 +189,7 @@ inline bool verify_prime(const BigInt& n, RandomNumberGenerator& rng)
 
 
 /**
-* Randomly generate a prime
+* Randomly generate a prime suitable for discrete logarithm parameters
 * @param rng a random number generator
 * @param bits how large the resulting prime should be in bits
 * @param coprime a positive integer that (prime - 1) should be coprime to
@@ -207,6 +207,21 @@ BigInt BOTAN_PUBLIC_API(2,0) random_prime(RandomNumberGenerator& rng,
                                           size_t prob = 128);
 
 /**
+* Generate a prime suitable for RSA p/q
+* @param keygen_rng a random number generator
+* @param prime_test_rng a random number generator
+* @param bits how large the resulting prime should be in bits (must be >= 512)
+* @param coprime a positive integer that (prime - 1) should be coprime to
+* @param prob use test so false positive is bounded by 1/2**prob
+* @return random prime with the specified criteria
+*/
+BigInt BOTAN_PUBLIC_API(2,7) generate_rsa_prime(RandomNumberGenerator& keygen_rng,
+                                                RandomNumberGenerator& prime_test_rng,
+                                                size_t bits,
+                                                const BigInt& coprime,
+                                                size_t prob = 128);
+
+/**
 * Return a 'safe' prime, of the form p=2*q+1 with q prime
 * @param rng a random number generator
 * @param bits is how long the resulting prime should be