Add a const-time division algorithm

It is stupid and slow (~50-100x slower than variable time version) but
still useful for protecting critical algorithms.

Not currently used, waiting for OSS-Fuzz to test it for a while before
we commit to it.

2 files changed, 23 insertions, 6 deletions

diff --git a/src/tests/data/bn/divide.vec b/src/tests/data/bn/divide.vec
index a5470f41d..f1220561e 100644
--- a/src/tests/data/bn/divide.vec
+++ b/src/tests/data/bn/divide.vec
@@ -1,8 +1,16 @@
 [Division]
+In1 = 0
+In2 = 5
+Output = 0
+
 In1 = 0x1234567
 In2 = 0x103
 Output = 73701
 
+In1 = -0x1234567
+In2 = 0x103
+Output = -73702
+
 In1 = 0x100000000000000000000000000000000000000000000000000000000000000000000000
 In2 = 0x1000000000000000000000000000000000000000000000000000000000000000000000
 Output = 0x100
diff --git a/src/tests/test_bigint.cpp b/src/tests/test_bigint.cpp
index c7b95b89a..9d8a88497 100644
--- a/src/tests/test_bigint.cpp
+++ b/src/tests/test_bigint.cpp
@@ -9,6 +9,7 @@
 #if defined(BOTAN_HAS_NUMBERTHEORY)
    #include <botan/bigint.h>
    #include <botan/numthry.h>
+   #include <botan/divide.h>
    #include <botan/internal/primality.h>
    #include <botan/reducer.h>
    #include <botan/pow_mod.h>
@@ -404,6 +405,10 @@ class BigInt_Div_Test final : public Text_Based_Test
          e /= b;
          result.test_eq("a /= b", e, 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);
+
          return result;
          }
    };
@@ -421,16 +426,16 @@ class BigInt_Mod_Test final : public Text_Based_Test
 
          const BigInt a = vars.get_req_bn("In1");
          const BigInt b = vars.get_req_bn("In2");
-         const BigInt c = vars.get_req_bn("Output");
+         const BigInt expected = vars.get_req_bn("Output");
 
-         result.test_eq("a % b", a % b, c);
+         result.test_eq("a % b", a % b, expected);
 
          BigInt e = a;
          e %= b;
-         result.test_eq("a %= b", e, c);
+         result.test_eq("a %= b", e, expected);
 
          const Botan::Modular_Reducer mod_b(b);
-         result.test_eq("Barrett", mod_b.reduce(a), c);
+         result.test_eq("Barrett", mod_b.reduce(a), expected);
 
          // if b fits into a Botan::word test %= operator for words
          if(b.sig_words() == 1)
@@ -439,11 +444,15 @@ class BigInt_Mod_Test final : public Text_Based_Test
 
             e = a;
             e %= b_word;
-            result.test_eq("a %= b (as word)", e, c);
+            result.test_eq("a %= b (as word)", e, expected);
 
-            result.test_eq("a % b (as word)", a % b_word, c);
+            result.test_eq("a % b (as word)", a % b_word, 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);
+
          return result;
          }
    };