Merge GH #1556 Misc BigInt improvements

9 files changed, 205 insertions, 79 deletions

diff --git a/src/lib/math/bigint/big_ops2.cpp b/src/lib/math/bigint/big_ops2.cpp
index 242635257..39f985566 100644
--- a/src/lib/math/bigint/big_ops2.cpp
+++ b/src/lib/math/bigint/big_ops2.cpp
@@ -12,32 +12,29 @@
 
 namespace Botan {
 
-/*
-* Addition Operator
-*/
-BigInt& BigInt::operator+=(const BigInt& y)
+BigInt& BigInt::add(const word y[], size_t y_sw, Sign y_sign)
    {
-   const size_t x_sw = sig_words(), y_sw = y.sig_words();
+   const size_t x_sw = sig_words();
 
-   if(sign() == y.sign())
+   if(sign() == y_sign)
       {
       const size_t reg_size = std::max(x_sw, y_sw) + 1;
 
       if(m_reg.size() < reg_size)
          grow_to(reg_size);
 
-      bigint_add2(mutable_data(), reg_size - 1, y.data(), y_sw);
+      bigint_add2(mutable_data(), reg_size - 1, y, y_sw);
       }
    else
       {
-      const int32_t relative_size = bigint_cmp(data(), x_sw, y.data(), y_sw);
+      const int32_t relative_size = bigint_cmp(data(), x_sw, y, y_sw);
 
       if(relative_size < 0)
          {
          const size_t reg_size = std::max(x_sw, y_sw);
          grow_to(reg_size);
-         bigint_sub2_rev(mutable_data(), y.data(), y_sw);
-         set_sign(y.sign());
+         bigint_sub2_rev(mutable_data(), y, y_sw);
+         set_sign(y_sign);
          }
       else if(relative_size == 0)
          {
@@ -46,37 +43,44 @@ BigInt& BigInt::operator+=(const BigInt& y)
          }
       else if(relative_size > 0)
          {
-         bigint_sub2(mutable_data(), x_sw, y.data(), y_sw);
+         bigint_sub2(mutable_data(), x_sw, y, y_sw);
          }
       }
 
    return (*this);
    }
 
-/*
-* Subtraction Operator
-*/
-BigInt& BigInt::operator-=(const BigInt& y)
+BigInt& BigInt::operator+=(const BigInt& y)
+   {
+   return add(y.data(), y.sig_words(), y.sign());
+   }
+
+BigInt& BigInt::operator+=(word y)
    {
-   const size_t x_sw = sig_words(), y_sw = y.sig_words();
+   return add(&y, 1, Positive);
+   }
+
+BigInt& BigInt::sub(const word y[], size_t y_sw, Sign y_sign)
+   {
+   const size_t x_sw = sig_words();
 
-   int32_t relative_size = bigint_cmp(data(), x_sw, y.data(), y_sw);
+   int32_t relative_size = bigint_cmp(data(), x_sw, y, y_sw);
 
    const size_t reg_size = std::max(x_sw, y_sw) + 1;
    grow_to(reg_size);
 
    if(relative_size < 0)
       {
-      if(sign() == y.sign())
-         bigint_sub2_rev(mutable_data(), y.data(), y_sw);
+      if(sign() == y_sign)
+         bigint_sub2_rev(mutable_data(), y, y_sw);
       else
-         bigint_add2(mutable_data(), reg_size - 1, y.data(), y_sw);
+         bigint_add2(mutable_data(), reg_size - 1, y, y_sw);
 
-      set_sign(y.reverse_sign());
+      set_sign(y_sign == Positive ? Negative : Positive);
       }
    else if(relative_size == 0)
       {
-      if(sign() == y.sign())
+      if(sign() == y_sign)
          {
          clear();
          set_sign(Positive);
@@ -86,15 +90,25 @@ BigInt& BigInt::operator-=(const BigInt& y)
       }
    else if(relative_size > 0)
       {
-      if(sign() == y.sign())
-         bigint_sub2(mutable_data(), x_sw, y.data(), y_sw);
+      if(sign() == y_sign)
+         bigint_sub2(mutable_data(), x_sw, y, y_sw);
       else
-         bigint_add2(mutable_data(), reg_size - 1, y.data(), y_sw);
+         bigint_add2(mutable_data(), reg_size - 1, y, y_sw);
       }
 
    return (*this);
    }
 
+BigInt& BigInt::operator-=(const BigInt& y)
+   {
+   return sub(y.data(), y.sig_words(), y.sign());
+   }
+
+BigInt& BigInt::operator-=(word y)
+   {
+   return sub(&y, 1, Positive);
+   }
+
 BigInt& BigInt::mod_add(const BigInt& s, const BigInt& mod, secure_vector<word>& ws)
    {
    if(this->is_negative() || s.is_negative() || mod.is_negative())
diff --git a/src/lib/math/bigint/big_ops3.cpp b/src/lib/math/bigint/big_ops3.cpp
index ce9047b15..492a69ad0 100644
--- a/src/lib/math/bigint/big_ops3.cpp
+++ b/src/lib/math/bigint/big_ops3.cpp
@@ -14,71 +14,89 @@
 
 namespace Botan {
 
-/*
-* Addition Operator
-*/
-BigInt operator+(const BigInt& x, const BigInt& y)
+namespace {
+
+BigInt bigint_add(const BigInt& x, const word y[], size_t y_sw, BigInt::Sign y_sign)
    {
-   const size_t x_sw = x.sig_words(), y_sw = y.sig_words();
+   const size_t x_sw = x.sig_words();
 
    BigInt z(x.sign(), std::max(x_sw, y_sw) + 1);
 
-   if(x.sign() == y.sign())
-      bigint_add3(z.mutable_data(), x.data(), x_sw, y.data(), y_sw);
+   if(x.sign() == y_sign)
+      bigint_add3(z.mutable_data(), x.data(), x_sw, y, y_sw);
    else
       {
-      int32_t relative_size = bigint_cmp(x.data(), x_sw, y.data(), y_sw);
+      int32_t relative_size = bigint_cmp(x.data(), x_sw, y, y_sw);
 
       if(relative_size < 0)
          {
-         bigint_sub3(z.mutable_data(), y.data(), y_sw, x.data(), x_sw);
-         z.set_sign(y.sign());
+         bigint_sub3(z.mutable_data(), y, y_sw, x.data(), x_sw);
+         z.set_sign(y_sign);
          }
       else if(relative_size == 0)
          z.set_sign(BigInt::Positive);
       else if(relative_size > 0)
-         bigint_sub3(z.mutable_data(), x.data(), x_sw, y.data(), y_sw);
+         bigint_sub3(z.mutable_data(), x.data(), x_sw, y, y_sw);
       }
 
    return z;
    }
 
-/*
-* Subtraction Operator
-*/
-BigInt operator-(const BigInt& x, const BigInt& y)
+BigInt bigint_sub(const BigInt& x, const word y[], size_t y_sw, BigInt::Sign y_sign)
    {
-   const size_t x_sw = x.sig_words(), y_sw = y.sig_words();
+   const size_t x_sw = x.sig_words();
 
-   int32_t relative_size = bigint_cmp(x.data(), x_sw, y.data(), y_sw);
+   int32_t relative_size = bigint_cmp(x.data(), x_sw, y, y_sw);
 
    BigInt z(BigInt::Positive, std::max(x_sw, y_sw) + 1);
 
    if(relative_size < 0)
       {
-      if(x.sign() == y.sign())
-         bigint_sub3(z.mutable_data(), y.data(), y_sw, x.data(), x_sw);
+      if(x.sign() == y_sign)
+         bigint_sub3(z.mutable_data(), y, y_sw, x.data(), x_sw);
       else
-         bigint_add3(z.mutable_data(), x.data(), x_sw, y.data(), y_sw);
-      z.set_sign(y.reverse_sign());
+         bigint_add3(z.mutable_data(), x.data(), x_sw, y, y_sw);
+      z.set_sign(y_sign == BigInt::Positive ? BigInt::Negative : BigInt::Positive);
       }
    else if(relative_size == 0)
       {
-      if(x.sign() != y.sign())
+      if(x.sign() != y_sign)
          bigint_shl2(z.mutable_data(), x.data(), x_sw, 0, 1);
-      z.set_sign(y.reverse_sign());
+      z.set_sign(y_sign == BigInt::Positive ? BigInt::Negative : BigInt::Positive);
       }
    else if(relative_size > 0)
       {
-      if(x.sign() == y.sign())
-         bigint_sub3(z.mutable_data(), x.data(), x_sw, y.data(), y_sw);
+      if(x.sign() == y_sign)
+         bigint_sub3(z.mutable_data(), x.data(), x_sw, y, y_sw);
       else
-         bigint_add3(z.mutable_data(), x.data(), x_sw, y.data(), y_sw);
+         bigint_add3(z.mutable_data(), x.data(), x_sw, y, y_sw);
       z.set_sign(x.sign());
       }
    return z;
    }
 
+}
+
+BigInt operator+(const BigInt& x, const BigInt& y)
+   {
+   return bigint_add(x, y.data(), y.sig_words(), y.sign());
+   }
+
+BigInt operator+(const BigInt& x, word y)
+   {
+   return bigint_add(x, &y, 1, BigInt::Positive);
+   }
+
+BigInt operator-(const BigInt& x, const BigInt& y)
+   {
+   return bigint_sub(x, y.data(), y.sig_words(), y.sign());
+   }
+
+BigInt operator-(const BigInt& x, word y)
+   {
+   return bigint_sub(x, &y, 1, BigInt::Positive);
+   }
+
 /*
 * Multiplication Operator
 */
diff --git a/src/lib/math/bigint/bigint.cpp b/src/lib/math/bigint/bigint.cpp
index 8874195af..39cff666c 100644
--- a/src/lib/math/bigint/bigint.cpp
+++ b/src/lib/math/bigint/bigint.cpp
@@ -113,6 +113,18 @@ BigInt::BigInt(RandomNumberGenerator& rng, size_t bits, bool set_high_bit)
    randomize(rng, bits, set_high_bit);
    }
 
+int32_t BigInt::cmp_word(word other) const
+   {
+   if(is_negative())
+      return -1; // other is positive ...
+
+   const size_t sw = this->sig_words();
+   if(sw > 1)
+      return 1; // must be larger since other is just one word ...
+
+   return bigint_cmp(this->data(), sw, &other, 1);
+   }
+
 /*
 * Comparison Function
 */
diff --git a/src/lib/math/bigint/bigint.h b/src/lib/math/bigint/bigint.h
index bb7a69541..d5bd4ad4f 100644
--- a/src/lib/math/bigint/bigint.h
+++ b/src/lib/math/bigint/bigint.h
@@ -165,12 +165,24 @@ class BOTAN_PUBLIC_API(2,0) BigInt final
      BigInt& operator+=(const BigInt& y);
 
      /**
+     * += operator
+     * @param y the word to add to this
+     */
+     BigInt& operator+=(word y);
+
+     /**
      * -= operator
      * @param y the BigInt to subtract from this
      */
      BigInt& operator-=(const BigInt& y);
 
      /**
+     * -= operator
+     * @param y the word to subtract from this
+     */
+     BigInt& operator-=(word y);
+
+     /**
      * *= operator
      * @param y the BigInt to multiply with this
      */
@@ -306,6 +318,14 @@ class BOTAN_PUBLIC_API(2,0) BigInt final
      int32_t cmp(const BigInt& n, bool check_signs = true) const;
 
      /**
+     * Compare this to an integer
+     * @param n the value to compare with
+     * @result if (this<n) return -1, if (this>n) return 1, if both
+     * values are identical return 0 [like Perl's <=> operator]
+     */
+     int32_t cmp_word(word n) const;
+
+     /**
      * Test if the integer has an even value
      * @result true if the integer is even, false otherwise
      */
@@ -700,6 +720,10 @@ class BOTAN_PUBLIC_API(2,0) BigInt final
         size_t idx);
 
    private:
+
+      BigInt& add(const word y[], size_t y_words, Sign sign);
+      BigInt& sub(const word y[], size_t y_words, Sign sign);
+
       secure_vector<word> m_reg;
       Sign m_signedness = Positive;
    };
@@ -708,7 +732,12 @@ class BOTAN_PUBLIC_API(2,0) BigInt final
 * Arithmetic Operators
 */
 BigInt BOTAN_PUBLIC_API(2,0) operator+(const BigInt& x, const BigInt& y);
+BigInt BOTAN_PUBLIC_API(2,7) operator+(const BigInt& x, word y);
+inline BigInt operator+(word x, const BigInt& y) { return y + x; }
+
 BigInt BOTAN_PUBLIC_API(2,0) operator-(const BigInt& x, const BigInt& y);
+BigInt BOTAN_PUBLIC_API(2,7) operator-(const BigInt& x, word y);
+
 BigInt BOTAN_PUBLIC_API(2,0) operator*(const BigInt& x, const BigInt& y);
 BigInt BOTAN_PUBLIC_API(2,0) operator/(const BigInt& x, const BigInt& d);
 BigInt BOTAN_PUBLIC_API(2,0) operator%(const BigInt& x, const BigInt& m);
@@ -732,6 +761,19 @@ inline bool operator<(const BigInt& a, const BigInt& b)
 inline bool operator>(const BigInt& a, const BigInt& b)
    { return (a.cmp(b) > 0); }
 
+inline bool operator==(const BigInt& a, word b)
+   { return (a.cmp_word(b) == 0); }
+inline bool operator!=(const BigInt& a, word b)
+   { return (a.cmp_word(b) != 0); }
+inline bool operator<=(const BigInt& a, word b)
+   { return (a.cmp_word(b) <= 0); }
+inline bool operator>=(const BigInt& a, word b)
+   { return (a.cmp_word(b) >= 0); }
+inline bool operator<(const BigInt& a, word b)
+   { return (a.cmp_word(b) < 0); }
+inline bool operator>(const BigInt& a, word b)
+   { return (a.cmp_word(b) > 0); }
+
 /*
 * I/O Operators
 */
diff --git a/src/lib/math/numbertheory/make_prm.cpp b/src/lib/math/numbertheory/make_prm.cpp
index 85089c9cb..1979fa550 100644
--- a/src/lib/math/numbertheory/make_prm.cpp
+++ b/src/lib/math/numbertheory/make_prm.cpp
@@ -182,8 +182,13 @@ BigInt generate_rsa_prime(RandomNumberGenerator& keygen_rng,
    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");
+   /*
+   * The restriction on coprime <= 64 bits is arbitrary but generally speaking
+   * very large RSA public exponents are a bad idea both for performance and due
+   * to attacks on small d.
+   */
+   if(coprime <= 1 || coprime.is_even() || coprime.bits() > 64)
+      throw Invalid_Argument("generate_rsa_prime coprime must be small odd positive integer");
 
    const size_t MAX_ATTEMPTS = 32*1024;
 
@@ -218,13 +223,26 @@ BigInt generate_rsa_prime(RandomNumberGenerator& keygen_rng,
             continue;
 
          /*
-         * 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.
+         * Check if p - 1 and coprime are relatively prime by computing the inverse.
+         *
+         * We avoid gcd here because that algorithm is not constant time.
+         * Modular inverse is (for odd modulus anyway).
+         *
+         * We earlier verified that coprime argument is odd. Thus the factors of 2
+         * in (p - 1) cannot possibly be factors in coprime, so remove them from p - 1.
+         * Using an odd modulus allows the const time algorithm to be used.
+         *
+         * This assumes coprime < p - 1 which is always true for RSA.
          */
-         if(inverse_mod(p - 1, coprime).is_zero())
+         BigInt p1 = p - 1;
+         p1 >>= low_zero_bits(p1);
+         if(inverse_mod(coprime, p1).is_zero())
+            {
+            BOTAN_DEBUG_ASSERT(gcd(p1, coprime) > 1);
             continue;
+            }
+
+         BOTAN_DEBUG_ASSERT(gcd(p1, coprime) == 1);
 
          if(p.bits() > bits)
             break;
diff --git a/src/lib/math/numbertheory/numthry.cpp b/src/lib/math/numbertheory/numthry.cpp
index 8cc930175..10f44a1ee 100644
--- a/src/lib/math/numbertheory/numthry.cpp
+++ b/src/lib/math/numbertheory/numthry.cpp
@@ -8,9 +8,11 @@
 #include <botan/numthry.h>
 #include <botan/pow_mod.h>
 #include <botan/reducer.h>
+#include <botan/monty.h>
 #include <botan/internal/bit_ops.h>
 #include <botan/internal/mp_core.h>
 #include <botan/internal/ct_utils.h>
+#include <botan/internal/monty_exp.h>
 #include <algorithm>
 
 namespace Botan {
@@ -46,26 +48,32 @@ size_t low_zero_bits(const BigInt& n)
 */
 BigInt gcd(const BigInt& a, const BigInt& b)
    {
-   if(a.is_zero() || b.is_zero()) return 0;
-   if(a == 1 || b == 1)           return 1;
+   if(a.is_zero() || b.is_zero())
+      return 0;
+   if(a == 1 || b == 1)
+      return 1;
+
+   BigInt X[2] = { a, b };
+   X[0].set_sign(BigInt::Positive);
+   X[1].set_sign(BigInt::Positive);
 
-   BigInt x = a, y = b;
-   x.set_sign(BigInt::Positive);
-   y.set_sign(BigInt::Positive);
-   size_t shift = std::min(low_zero_bits(x), low_zero_bits(y));
+   const size_t shift = std::min(low_zero_bits(X[0]), low_zero_bits(X[1]));
 
-   x >>= shift;
-   y >>= shift;
+   X[0] >>= shift;
+   X[1] >>= shift;
 
-   while(x.is_nonzero())
+   while(X[0].is_nonzero())
       {
-      x >>= low_zero_bits(x);
-      y >>= low_zero_bits(y);
-      if(x >= y) { x -= y; x >>= 1; }
-      else       { y -= x; y >>= 1; }
+      X[0] >>= low_zero_bits(X[0]);
+      X[1] >>= low_zero_bits(X[1]);
+
+      const uint8_t sel = static_cast<uint8_t>(X[0] >= X[1]);
+
+      X[sel^1] -= X[sel];
+      X[sel^1] >>= 1;
       }
 
-   return (y << shift);
+   return (X[1] << shift);
    }
 
 /*
@@ -521,14 +529,20 @@ bool is_prime(const BigInt& n, RandomNumberGenerator& rng,
 
    const BigInt n_minus_1 = n - 1;
    const size_t s = low_zero_bits(n_minus_1);
+   const BigInt nm1_s = n_minus_1 >> s;
 
    const Modular_Reducer mod_n(n);
-   const Fixed_Exponent_Power_Mod pow_mod(n_minus_1 >> s, n);
+   auto monty_n = std::make_shared<Montgomery_Params>(n, mod_n);
+
+   const size_t powm_window = 4;
 
    for(size_t i = 0; i != test_iterations; ++i)
       {
       const BigInt a = BigInt::random_integer(rng, 2, n_minus_1);
-      BigInt y = pow_mod(a);
+
+      auto powm_a_n = monty_precompute(monty_n, a, powm_window);
+
+      BigInt y = monty_execute(*powm_a_n, nm1_s);
 
       if(mr_witness(std::move(y), mod_n, n_minus_1, s))
          return false;
diff --git a/src/lib/pubkey/dsa/dsa.cpp b/src/lib/pubkey/dsa/dsa.cpp
index a3a6b9a52..172804972 100644
--- a/src/lib/pubkey/dsa/dsa.cpp
+++ b/src/lib/pubkey/dsa/dsa.cpp
@@ -8,7 +8,6 @@
 
 #include <botan/dsa.h>
 #include <botan/keypair.h>
-#include <botan/pow_mod.h>
 #include <botan/reducer.h>
 #include <botan/rng.h>
 #include <botan/internal/pk_ops_impl.h>
diff --git a/src/lib/pubkey/rsa/rsa.cpp b/src/lib/pubkey/rsa/rsa.cpp
index ca0f414f5..fdc5b63d0 100644
--- a/src/lib/pubkey/rsa/rsa.cpp
+++ b/src/lib/pubkey/rsa/rsa.cpp
@@ -141,18 +141,19 @@ RSA_PrivateKey::RSA_PrivateKey(RandomNumberGenerator& rng,
 
    m_e = exp;
 
+   const size_t p_bits = (bits + 1) / 2;
+   const size_t q_bits = bits - p_bits;
+
    do
       {
-      const size_t p_bits = (bits + 1) / 2;
-      const size_t q_bits = bits - p_bits;
-
       m_p = generate_rsa_prime(rng, rng, p_bits, m_e);
       m_q = generate_rsa_prime(rng, rng, q_bits, m_e);
       m_n = m_p * m_q;
-
       } while(m_n.bits() != bits);
 
+   // FIXME: lcm calls gcd which is not const time
    const BigInt phi_n = lcm(m_p - 1, m_q - 1);
+   // FIXME: this uses binary ext gcd because phi_n is even
    m_d = inverse_mod(m_e, phi_n);
    m_d1 = m_d % (m_p - 1);
    m_d2 = m_d % (m_q - 1);
diff --git a/src/tests/data/bn/gcd.vec b/src/tests/data/bn/gcd.vec
index c7f630231..4378c9534 100644
--- a/src/tests/data/bn/gcd.vec
+++ b/src/tests/data/bn/gcd.vec
@@ -2,3 +2,11 @@
 X = 259
 Y = 4943984437
 GCD = 259
+
+X = 9298631792927489555577881706641
+Y = 536756618553495860610657489331151
+GCD = 1
+
+X = 10022247630053045674847735694652
+Y = 25956
+GCD = 28