Add a constant time divide variant for dividing by uint8_t

Originally wrote it for div-by-word but that ends up requiring a dword
type which we don't always have. And uint8_t covers the most important
cases of n = 10 and n = 58 (whenever I get around to writing base58).
We could portably support up to div-by-uint32, but I don't think we need it.

Nicely for n = 10, this is actually faster than the variable time division.

7 files changed, 146 insertions, 12 deletions

diff --git a/src/cli/speed.cpp b/src/cli/speed.cpp
index 59771fb65..4ec4c0f31 100644
--- a/src/cli/speed.cpp
+++ b/src/cli/speed.cpp
@@ -658,6 +658,10 @@ class Speed final : public Command
                {
                bench_mp_div(msec);
                }
+            else if(algo == "mp_div10")
+               {
+               bench_mp_div10(msec);
+               }
 #endif
 
 #if defined(BOTAN_HAS_NUMBERTHEORY)
@@ -1308,6 +1312,45 @@ class Speed final : public Command
             }
          }
 
+      void bench_mp_div10(const std::chrono::milliseconds runtime)
+         {
+         std::chrono::milliseconds runtime_per_size = runtime;
+
+         for(size_t n_bits : { 256, 384, 512, 768, 1024, 1536, 2048, 3072, 4096 })
+            {
+            const std::string bit_descr = std::to_string(n_bits) + "/10";
+
+            std::unique_ptr<Timer> div_timer = make_timer("BigInt div " + bit_descr);
+            std::unique_ptr<Timer> ct_div_timer = make_timer("BigInt ct_div " + bit_descr);
+
+            Botan::BigInt x;
+            Botan::secure_vector<Botan::word> ws;
+
+            const Botan::BigInt ten(10);
+            Botan::BigInt q1, r1, q2;
+            uint8_t r2;
+
+            while(ct_div_timer->under(runtime_per_size))
+               {
+               x.randomize(rng(), n_bits);
+
+               div_timer->start();
+               Botan::divide(x, ten, q1, r1);
+               div_timer->stop();
+
+               ct_div_timer->start();
+               Botan::ct_divide_u8(x, 10, q2, r2);
+               ct_div_timer->stop();
+
+               BOTAN_ASSERT_EQUAL(q1, q2, "Quotient ok");
+               BOTAN_ASSERT_EQUAL(r1, r2, "Remainder ok");
+               }
+
+            record_result(div_timer);
+            record_result(ct_div_timer);
+            }
+         }
+
 #endif
 
 #if defined(BOTAN_HAS_DL_GROUP)
diff --git a/src/fuzzer/divide.cpp b/src/fuzzer/divide.cpp
index c0c86f051..b6342ff7d 100644
--- a/src/fuzzer/divide.cpp
+++ b/src/fuzzer/divide.cpp
@@ -11,25 +11,42 @@ void fuzz(const uint8_t in[], size_t len)
    if(len % 2 == 1 || len > 2*4096/8)
       return;
 
-   const Botan::BigInt x = Botan::BigInt::decode(in, len / 2);
-   const Botan::BigInt y = Botan::BigInt::decode(in + len / 2, len / 2);
+   // Save on allocations by making these static
+   static Botan::BigInt x, y, q, r, ct_q, ct_r, z;
+
+   x = Botan::BigInt::decode(in, len / 2);
+   y = Botan::BigInt::decode(in + len / 2, len / 2);
 
    if(y == 0)
       return;
 
-   Botan::BigInt q, r;
    Botan::divide(x, y, q, r);
 
    FUZZER_ASSERT_TRUE(r < y);
 
-   Botan::BigInt z = q*y + r;
+   z = q*y + r;
 
    FUZZER_ASSERT_EQUAL(z, x);
 
-   Botan::BigInt ct_q, ct_r;
    Botan::ct_divide(x, y, ct_q, ct_r);
 
    FUZZER_ASSERT_EQUAL(q, ct_q);
    FUZZER_ASSERT_EQUAL(r, ct_r);
+
+   // Now divide by just low byte of y
+
+   y = y.byte_at(0);
+   if(y == 0)
+      y = 251;
+   Botan::divide(x, y, q, r);
+
+   z = q*y + r;
+   FUZZER_ASSERT_EQUAL(z, x);
+
+   uint8_t r8;
+   Botan::ct_divide_u8(x, y.byte_at(0), ct_q, r8);
+   FUZZER_ASSERT_EQUAL(ct_q, q);
+   FUZZER_ASSERT_EQUAL(r8, r.byte_at(0));
+
    }
 
diff --git a/src/lib/math/bigint/big_code.cpp b/src/lib/math/bigint/big_code.cpp
index 8fd528a14..6d8c61fd5 100644
--- a/src/lib/math/bigint/big_code.cpp
+++ b/src/lib/math/bigint/big_code.cpp
@@ -17,13 +17,13 @@ std::string BigInt::to_dec_string() const
    BigInt copy = *this;
    copy.set_sign(Positive);
 
-   BigInt remainder;
+   uint8_t remainder;
    std::vector<uint8_t> digits;
 
    while(copy > 0)
       {
-      divide(copy, 10, copy, remainder);
-      digits.push_back(static_cast<uint8_t>(remainder.word_at(0)));
+      ct_divide_u8(copy, 10, copy, remainder);
+      digits.push_back(remainder);
       }
 
    std::string s;
@@ -68,14 +68,13 @@ void BigInt::encode(uint8_t output[], const BigInt& n, Base base)
    else if(base == Decimal)
       {
       BigInt copy = n;
-      BigInt remainder;
+      uint8_t remainder;
       copy.set_sign(Positive);
       const size_t output_size = n.encoded_size(Decimal);
       for(size_t j = 0; j != output_size; ++j)
          {
-         divide(copy, 10, copy, remainder);
-         output[output_size - 1 - j] =
-            Charset::digit2char(static_cast<uint8_t>(remainder.word_at(0)));
+         ct_divide_u8(copy, 10, copy, remainder);
+         output[output_size - 1 - j] = Charset::digit2char(remainder);
          if(copy.is_zero())
             break;
          }
diff --git a/src/lib/math/bigint/divide.cpp b/src/lib/math/bigint/divide.cpp
index 64d1537ba..c2e89a724 100644
--- a/src/lib/math/bigint/divide.cpp
+++ b/src/lib/math/bigint/divide.cpp
@@ -83,6 +83,43 @@ void ct_divide(const BigInt& x, const BigInt& y, BigInt& q_out, BigInt& r_out)
    q_out = q;
    }
 
+void ct_divide_u8(const BigInt& x, uint8_t y, BigInt& q_out, uint8_t& r_out)
+   {
+   const size_t x_words = x.sig_words();
+   const size_t x_bits = x.bits();
+   const size_t y_words = 1;
+
+   BigInt q(BigInt::Positive, x_words);
+   uint32_t r = 0;
+
+   for(size_t i = 0; i != x_bits; ++i)
+      {
+      const size_t b = x_bits - 1 - i;
+      const bool x_b = x.get_bit(b);
+
+      r *= 2;
+      r += x_b;
+
+      const auto r_gte_y = CT::Mask<uint32_t>::is_gte(r, y);
+
+      q.conditionally_set_bit(b, r_gte_y.is_set());
+      r = r_gte_y.select(r - y, r);
+      }
+
+   if(x.sign() == BigInt::Negative)
+      {
+      q.flip_sign();
+      if(r != 0)
+         {
+         --q;
+         r = y - r;
+         }
+      }
+
+   r_out = static_cast<uint8_t>(r);
+   q_out = q;
+   }
+
 /*
 * Solve x = q * y + r
 */
diff --git a/src/lib/math/bigint/divide.h b/src/lib/math/bigint/divide.h
index d7d72e200..d83f4b695 100644
--- a/src/lib/math/bigint/divide.h
+++ b/src/lib/math/bigint/divide.h
@@ -40,6 +40,22 @@ void BOTAN_PUBLIC_API(2,9) ct_divide(const BigInt& x,
                                      BigInt& q,
                                      BigInt& r);
 
+/**
+* BigInt division, const time variant
+*
+* This runs with control flow independent of the values of x/y.
+* Warning: the loop bounds still leak the sizes of x and y.
+*
+* @param x an integer
+* @param y a non-zero integer
+* @param q will be set to x / y
+* @param r will be set to x % y
+*/
+void BOTAN_PUBLIC_API(2,9) ct_divide_u8(const BigInt& x,
+                                        uint8_t y,
+                                        BigInt& q,
+                                        uint8_t& r);
+
 }
 
 #endif
diff --git a/src/tests/data/bn/divide.vec b/src/tests/data/bn/divide.vec
index f1220561e..0a6dd2423 100644
--- a/src/tests/data/bn/divide.vec
+++ b/src/tests/data/bn/divide.vec
@@ -159,3 +159,7 @@ In1 = 0x123F71E77499975C79EE4C4F7B275A4410863CEDC3E244724D5AF83A8A2DD73C5D5913E9
 In2 = 0x78B294AD98589FDCC2D53FCB0FC9F0E70E4E30323832D5669F66E15
 Output = 0x26B426C03F76F97048D5DE0B8D9DBD02F4DC
 
+In1 = 1996953214196350189568
+In2 = 13331618315827609940
+Output = 149
+
diff --git a/src/tests/test_bigint.cpp b/src/tests/test_bigint.cpp
index 9d8a88497..d85115e03 100644
--- a/src/tests/test_bigint.cpp
+++ b/src/tests/test_bigint.cpp
@@ -405,6 +405,16 @@ class BigInt_Div_Test final : public Text_Based_Test
          e /= b;
          result.test_eq("a /= b", e, c);
 
+         if(b.bytes() == 1)
+            {
+            const uint8_t b8 = b.byte_at(0);
+
+            Botan::BigInt ct_q;
+            uint8_t ct_r;
+            Botan::ct_divide_u8(a, b8, ct_q, ct_r);
+            result.test_eq("ct_divide_u8 q", ct_q, c);
+            }
+
          Botan::BigInt ct_q, ct_r;
          Botan::ct_divide(a, b, ct_q, ct_r);
          result.test_eq("ct_divide q", ct_q, c);
@@ -449,6 +459,14 @@ class BigInt_Mod_Test final : public Text_Based_Test
             result.test_eq("a % b (as word)", a % b_word, expected);
             }
 
+         if(b.bytes() == 1)
+            {
+            Botan::BigInt ct_q;
+            Botan::uint8_t ct_r;
+            Botan::ct_divide_u8(a, b.byte_at(0), ct_q, ct_r);
+            result.test_eq("ct_divide_u8 r", ct_r, expected);
+            }
+
          Botan::BigInt ct_q, ct_r;
          Botan::ct_divide(a, b, ct_q, ct_r);
          result.test_eq("ct_divide r", ct_r, expected);