Some math deprecations

Mostly things that shouldn't be used (like almost Montgomery inverse,
which isn't even constant time) or are very much just for internals
(like the word-wise Montgomery inverse computation used for reduction).

Make variable time division explicit; leaves plain divide as a call
but it forwards to ct_divide now. All callers within the library are
now explicitly consttime or vartime.

Add a shortcut for modulus by one word - this hits quite often
especially in the ECC code

11 files changed, 103 insertions, 60 deletions

diff --git a/src/cli/speed.cpp b/src/cli/speed.cpp
index 0ef453311..b8454d2a7 100644
--- a/src/cli/speed.cpp
+++ b/src/cli/speed.cpp
@@ -1356,7 +1356,7 @@ class Speed final : public Command
                y.randomize(rng(), q_bits);
 
                div_timer->start();
-               Botan::divide(x, y, q1, r1);
+               Botan::vartime_divide(x, y, q1, r1);
                div_timer->stop();
 
                ct_div_timer->start();
@@ -1395,7 +1395,7 @@ class Speed final : public Command
                x.randomize(rng(), n_bits);
 
                div_timer->start();
-               Botan::divide(x, ten, q1, r1);
+               Botan::vartime_divide(x, ten, q1, r1);
                div_timer->stop();
 
                ct_div_timer->start();
diff --git a/src/lib/ffi/ffi_mp.cpp b/src/lib/ffi/ffi_mp.cpp
index 513dbbb0c..68869e6ec 100644
--- a/src/lib/ffi/ffi_mp.cpp
+++ b/src/lib/ffi/ffi_mp.cpp
@@ -192,7 +192,7 @@ int botan_mp_div(botan_mp_t quotient,
    {
    return BOTAN_FFI_DO(Botan::BigInt, quotient, q, {
       Botan::BigInt r;
-      Botan::divide(safe_get(x), safe_get(y), q, r);
+      Botan::vartime_divide(safe_get(x), safe_get(y), q, r);
       safe_get(remainder) = r;
       });
    }
diff --git a/src/lib/math/bigint/big_ops3.cpp b/src/lib/math/bigint/big_ops3.cpp
index 30b27c87b..11804762b 100644
--- a/src/lib/math/bigint/big_ops3.cpp
+++ b/src/lib/math/bigint/big_ops3.cpp
@@ -91,11 +91,37 @@ BigInt operator*(const BigInt& x, word y)
 */
 BigInt operator/(const BigInt& x, const BigInt& y)
    {
-   if(y.sig_words() == 1 && is_power_of_2(y.word_at(0)))
-      return (x >> (y.bits() - 1));
+   if(y.sig_words() == 1)
+      {
+      return x / y.word_at(0);
+      }
 
    BigInt q, r;
-   divide(x, y, q, r);
+   vartime_divide(x, y, q, r);
+   return q;
+   }
+
+/*
+* Division Operator
+*/
+BigInt operator/(const BigInt& x, word y)
+   {
+   if(y == 0)
+      throw BigInt::DivideByZero();
+   else if(y == 1)
+      return x;
+   else if(y == 2)
+      return (x >> 1);
+   else if(y <= 255)
+      {
+      BigInt q;
+      uint8_t r;
+      ct_divide_u8(x, static_cast<uint8_t>(y), q, r);
+      return q;
+      }
+
+   BigInt q, r;
+   vartime_divide(x, y, q, r);
    return q;
    }
 
@@ -111,8 +137,13 @@ BigInt operator%(const BigInt& n, const BigInt& mod)
    if(n.is_positive() && mod.is_positive() && n < mod)
       return n;
 
+   if(mod.sig_words() == 1)
+      {
+      return n % mod.word_at(0);
+      }
+
    BigInt q, r;
-   divide(n, mod, q, r);
+   vartime_divide(n, mod, q, r);
    return r;
    }
 
diff --git a/src/lib/math/bigint/bigint.h b/src/lib/math/bigint/bigint.h
index d04ac045c..33e79d012 100644
--- a/src/lib/math/bigint/bigint.h
+++ b/src/lib/math/bigint/bigint.h
@@ -1097,6 +1097,7 @@ BigInt BOTAN_PUBLIC_API(2,8) 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& d);
+BigInt BOTAN_PUBLIC_API(2,0) operator/(const BigInt& x, word m);
 BigInt BOTAN_PUBLIC_API(2,0) operator%(const BigInt& x, const BigInt& m);
 word   BOTAN_PUBLIC_API(2,0) operator%(const BigInt& x, word m);
 BigInt BOTAN_PUBLIC_API(2,0) operator<<(const BigInt& x, size_t n);
diff --git a/src/lib/math/bigint/divide.cpp b/src/lib/math/bigint/divide.cpp
index fdb920241..0b23e2489 100644
--- a/src/lib/math/bigint/divide.cpp
+++ b/src/lib/math/bigint/divide.cpp
@@ -156,7 +156,7 @@ BigInt ct_modulo(const BigInt& x, const BigInt& y)
 *
 * See Handbook of Applied Cryptography section 14.2.5
 */
-void divide(const BigInt& x, const BigInt& y_arg, BigInt& q_out, BigInt& r_out)
+void vartime_divide(const BigInt& x, const BigInt& y_arg, BigInt& q_out, BigInt& r_out)
    {
    if(y_arg.is_zero())
       throw BigInt::DivideByZero();
diff --git a/src/lib/math/bigint/divide.h b/src/lib/math/bigint/divide.h
index deb6ffdbb..47141b3e7 100644
--- a/src/lib/math/bigint/divide.h
+++ b/src/lib/math/bigint/divide.h
@@ -21,10 +21,10 @@ namespace Botan {
 * @param q will be set to x / y
 * @param r will be set to x % y
 */
-void BOTAN_PUBLIC_API(2,0) divide(const BigInt& x,
-                                  const BigInt& y,
-                                  BigInt& q,
-                                  BigInt& r);
+void BOTAN_UNSTABLE_API vartime_divide(const BigInt& x,
+                                       const BigInt& y,
+                                       BigInt& q,
+                                       BigInt& r);
 
 /**
 * BigInt division, const time variant
@@ -42,6 +42,14 @@ void BOTAN_PUBLIC_API(2,9) ct_divide(const BigInt& x,
                                      BigInt& q,
                                      BigInt& r);
 
+inline void divide(const BigInt& x,
+                   const BigInt& y,
+                   BigInt& q,
+                   BigInt& r)
+   {
+   ct_divide(x, y, q, r);
+   }
+
 /**
 * BigInt division, const time variant
 *
diff --git a/src/lib/math/numbertheory/monty.h b/src/lib/math/numbertheory/monty.h
index e5ab2f9ad..8e0cd342f 100644
--- a/src/lib/math/numbertheory/monty.h
+++ b/src/lib/math/numbertheory/monty.h
@@ -8,6 +8,7 @@
 #define BOTAN_MONTY_INT_H_
 
 #include <botan/bigint.h>
+BOTAN_FUTURE_INTERNAL_HEADER(monty.h)
 
 namespace Botan {
 
diff --git a/src/lib/math/numbertheory/numthry.h b/src/lib/math/numbertheory/numthry.h
index b7f87ee05..be9cd985e 100644
--- a/src/lib/math/numbertheory/numthry.h
+++ b/src/lib/math/numbertheory/numthry.h
@@ -21,9 +21,10 @@ class RandomNumberGenerator;
 * @param c an integer
 * @return (a*b)+c
 */
-BigInt BOTAN_PUBLIC_API(2,0) mul_add(const BigInt& a,
-                                     const BigInt& b,
-                                     const BigInt& c);
+BigInt BOTAN_PUBLIC_API(2,0) BOTAN_DEPRECATED("Just use (a*b)+c")
+   mul_add(const BigInt& a,
+           const BigInt& b,
+           const BigInt& c);
 
 /**
 * Fused subtract-multiply
@@ -32,9 +33,10 @@ BigInt BOTAN_PUBLIC_API(2,0) mul_add(const BigInt& a,
 * @param c an integer
 * @return (a-b)*c
 */
-BigInt BOTAN_PUBLIC_API(2,0) sub_mul(const BigInt& a,
-                                     const BigInt& b,
-                                     const BigInt& c);
+BigInt BOTAN_PUBLIC_API(2,0) BOTAN_DEPRECATED("Just use (a-b)*c")
+   sub_mul(const BigInt& a,
+           const BigInt& b,
+           const BigInt& c);
 
 /**
 * Fused multiply-subtract
@@ -43,9 +45,10 @@ BigInt BOTAN_PUBLIC_API(2,0) sub_mul(const BigInt& a,
 * @param c an integer
 * @return (a*b)-c
 */
-BigInt BOTAN_PUBLIC_API(2,0) mul_sub(const BigInt& a,
-                                     const BigInt& b,
-                                     const BigInt& c);
+BigInt BOTAN_PUBLIC_API(2,0) BOTAN_DEPRECATED("Just use (a*b)-c")
+   mul_sub(const BigInt& a,
+           const BigInt& b,
+           const BigInt& c);
 
 /**
 * Return the absolute value
@@ -109,14 +112,16 @@ BigInt BOTAN_DEPRECATED_API("Use inverse_mod") ct_inverse_mod_odd_modulus(const
 * Returns k, between n and 2n
 * Not const time
 */
-size_t BOTAN_PUBLIC_API(2,0) almost_montgomery_inverse(BigInt& result,
-                                                       const BigInt& a,
-                                                       const BigInt& b);
+size_t BOTAN_PUBLIC_API(2,0) BOTAN_DEPRECATED("Use inverse_mod")
+   almost_montgomery_inverse(BigInt& result,
+                             const BigInt& a,
+                             const BigInt& b);
 
 /**
 * Call almost_montgomery_inverse and correct the result to a^-1 mod b
 */
-BigInt BOTAN_PUBLIC_API(2,0) normalized_montgomery_inverse(const BigInt& a, const BigInt& b);
+BigInt BOTAN_PUBLIC_API(2,0) BOTAN_DEPRECATED("Use inverse_mod")
+   normalized_montgomery_inverse(const BigInt& a, const BigInt& b);
 
 
 /**
@@ -143,7 +148,7 @@ BigInt BOTAN_PUBLIC_API(2,0) power_mod(const BigInt& b,
 
 /**
 * Compute the square root of x modulo a prime using the
-* Shanks-Tonnelli algorithm
+* Tonelli-Shanks algorithm
 *
 * @param x the input
 * @param p the prime
@@ -156,13 +161,14 @@ BigInt BOTAN_PUBLIC_API(2,0) ressol(const BigInt& x, const BigInt& p);
 * is even. If input is odd, then input and 2^n are relatively prime
 * and an inverse exists.
 */
-word BOTAN_PUBLIC_API(2,0) monty_inverse(word input);
+word BOTAN_PUBLIC_API(2,0) BOTAN_DEPRECATED("Use inverse_mod")
+   monty_inverse(word input);
 
 /**
-* @param x a positive integer
-* @return count of the zero bits in x, or, equivalently, the largest
-*         value of n such that 2^n divides x evenly. Returns zero if
-*         n is less than or equal to zero.
+* @param x an integer
+* @return count of the low zero bits in x, or, equivalently, the
+*         largest value of n such that 2^n divides x evenly. Returns
+*         zero if x is equal to zero.
 */
 size_t BOTAN_PUBLIC_API(2,0) low_zero_bits(const BigInt& x);
 
@@ -188,13 +194,16 @@ bool BOTAN_PUBLIC_API(2,0) is_prime(const BigInt& n,
 */
 BigInt BOTAN_PUBLIC_API(2,8) is_perfect_square(const BigInt& x);
 
-inline bool quick_check_prime(const BigInt& n, RandomNumberGenerator& rng)
+inline bool BOTAN_DEPRECATED("Use is_prime")
+   quick_check_prime(const BigInt& n, RandomNumberGenerator& rng)
    { return is_prime(n, rng, 32); }
 
-inline bool check_prime(const BigInt& n, RandomNumberGenerator& rng)
+inline bool BOTAN_DEPRECATED("Use is_prime")
+   check_prime(const BigInt& n, RandomNumberGenerator& rng)
    { return is_prime(n, rng, 56); }
 
-inline bool verify_prime(const BigInt& n, RandomNumberGenerator& rng)
+inline bool BOTAN_DEPRECATED("Use is_prime")
+   verify_prime(const BigInt& n, RandomNumberGenerator& rng)
    { return is_prime(n, rng, 80); }
 
 /**
@@ -248,7 +257,7 @@ BigInt BOTAN_PUBLIC_API(2,0) random_safe_prime(RandomNumberGenerator& rng,
 * @param qbits how long q will be in bits
 * @return random seed used to generate this parameter set
 */
-std::vector<uint8_t> BOTAN_PUBLIC_API(2,0)
+std::vector<uint8_t> BOTAN_PUBLIC_API(2,0) BOTAN_DEPRECATED("Use DL_Group")
 generate_dsa_primes(RandomNumberGenerator& rng,
                     BigInt& p_out, BigInt& q_out,
                     size_t pbits, size_t qbits);
@@ -265,7 +274,7 @@ generate_dsa_primes(RandomNumberGenerator& rng,
 * @return true if seed generated a valid DSA parameter set, otherwise
           false. p_out and q_out are only valid if true was returned.
 */
-bool BOTAN_PUBLIC_API(2,0)
+bool BOTAN_PUBLIC_API(2,0) BOTAN_DEPRECATED("Use DL_Group")
 generate_dsa_primes(RandomNumberGenerator& rng,
                     BigInt& p_out, BigInt& q_out,
                     size_t pbits, size_t qbits,
@@ -278,7 +287,7 @@ generate_dsa_primes(RandomNumberGenerator& rng,
 const size_t PRIME_TABLE_SIZE = 6541;
 
 /**
-* A const array of all primes less than 65535
+* A const array of all odd primes less than 65535
 */
 extern const uint16_t BOTAN_PUBLIC_API(2,0) PRIMES[];
 
diff --git a/src/lib/math/numbertheory/ressol.cpp b/src/lib/math/numbertheory/ressol.cpp
index 9d11ebbc4..de89e0384 100644
--- a/src/lib/math/numbertheory/ressol.cpp
+++ b/src/lib/math/numbertheory/ressol.cpp
@@ -1,6 +1,5 @@
 /*
-* Shanks-Tonnelli (RESSOL)
-* (C) 2007-2008 Falko Strenzke, FlexSecure GmbH
+* (C) 2007,2008 Falko Strenzke, FlexSecure GmbH
 * (C) 2008 Jack Lloyd
 *
 * Botan is released under the Simplified BSD License (see license.txt)
@@ -12,10 +11,13 @@
 namespace Botan {
 
 /*
-* Shanks-Tonnelli algorithm
+* Tonelli-Shanks algorithm
 */
 BigInt ressol(const BigInt& a, const BigInt& p)
    {
+   if(p <= 1 || p.is_even())
+      throw Invalid_Argument("ressol: invalid prime");
+
    if(a == 0)
       return 0;
    else if(a < 0)
@@ -25,16 +27,14 @@ BigInt ressol(const BigInt& a, const BigInt& p)
 
    if(p == 2)
       return a;
-   else if(p <= 1)
-      throw Invalid_Argument("ressol: prime must be > 1 a");
-   else if(p.is_even())
-      throw Invalid_Argument("ressol: invalid prime");
 
    if(jacobi(a, p) != 1) // not a quadratic residue
       return -BigInt(1);
 
-   if(p % 4 == 3)
+   if(p % 4 == 3) // The easy case
+      {
       return power_mod(a, ((p+1) >> 2), p);
+      }
 
    size_t s = low_zero_bits(p - 1);
    BigInt q = p >> s;
diff --git a/src/lib/pubkey/dl_group/dl_group.cpp b/src/lib/pubkey/dl_group/dl_group.cpp
index b6b5d5f44..05f9640e3 100644
--- a/src/lib/pubkey/dl_group/dl_group.cpp
+++ b/src/lib/pubkey/dl_group/dl_group.cpp
@@ -9,6 +9,7 @@
 #include <botan/numthry.h>
 #include <botan/reducer.h>
 #include <botan/monty.h>
+#include <botan/divide.h>
 #include <botan/der_enc.h>
 #include <botan/ber_dec.h>
 #include <botan/pem.h>
@@ -214,9 +215,10 @@ namespace {
 */
 BigInt make_dsa_generator(const BigInt& p, const BigInt& q)
    {
-   const BigInt e = (p - 1) / q;
+   BigInt e, r;
+   vartime_divide(p - 1, q, e, r);
 
-   if(e == 0 || (p - 1) % q > 0)
+   if(e == 0 || r > 0)
       throw Invalid_Argument("make_dsa_generator q does not divide p-1");
 
    for(size_t i = 0; i != PRIME_TABLE_SIZE; ++i)
diff --git a/src/lib/utils/compiler.h b/src/lib/utils/compiler.h
index 22bd07426..832ab8f22 100644
--- a/src/lib/utils/compiler.h
+++ b/src/lib/utils/compiler.h
@@ -103,32 +103,23 @@
 /*
 * Define BOTAN_DEPRECATED
 */
-#if !defined(BOTAN_NO_DEPRECATED_WARNINGS)
+#if !defined(BOTAN_NO_DEPRECATED_WARNINGS) && !defined(BOTAN_IS_BEING_BUILT) && !defined(BOTAN_AMALGAMATION_H_)
 
   #if defined(__clang__)
     #define BOTAN_DEPRECATED(msg) __attribute__ ((deprecated(msg)))
     #define BOTAN_DEPRECATED_HEADER(hdr) _Pragma("message \"this header is deprecated\"")
-
-    #if !defined(BOTAN_IS_BEING_BUILT) && !defined(BOTAN_AMALGAMATION_H_)
-      #define BOTAN_FUTURE_INTERNAL_HEADER(hdr) _Pragma("message \"this header will be made internal in the future\"")
-    #endif
+    #define BOTAN_FUTURE_INTERNAL_HEADER(hdr) _Pragma("message \"this header will be made internal in the future\"")
 
   #elif defined(_MSC_VER)
     #define BOTAN_DEPRECATED(msg) __declspec(deprecated(msg))
     #define BOTAN_DEPRECATED_HEADER(hdr) __pragma(message("this header is deprecated"))
-
-    #if !defined(BOTAN_IS_BEING_BUILT) && !defined(BOTAN_AMALGAMATION_H_)
-      #define BOTAN_FUTURE_INTERNAL_HEADER(hdr) __pragma(message("this header will be made internal in the future"))
-    #endif
+    #define BOTAN_FUTURE_INTERNAL_HEADER(hdr) __pragma(message("this header will be made internal in the future"))
 
   #elif defined(__GNUC__)
     /* msg supported since GCC 4.5, earliest we support is 4.8 */
     #define BOTAN_DEPRECATED(msg) __attribute__ ((deprecated(msg)))
     #define BOTAN_DEPRECATED_HEADER(hdr) _Pragma("GCC warning \"this header is deprecated\"")
-
-    #if !defined(BOTAN_IS_BEING_BUILT) && !defined(BOTAN_AMALGAMATION_H_)
-      #define BOTAN_FUTURE_INTERNAL_HEADER(hdr) _Pragma("GCC warning \"this header will be made internal in the future\"")
-    #endif
+    #define BOTAN_FUTURE_INTERNAL_HEADER(hdr) _Pragma("GCC warning \"this header will be made internal in the future\"")
   #endif
 
 #endif