For odd moduli use a input-independent modular inverse algorithm.

Also adds a (not const time) implementation of almost Montgomery reduction.

2 files changed, 44 insertions, 2 deletions

diff --git a/src/tests/test_bigint.cpp b/src/tests/test_bigint.cpp
index 671c76bff..1a615c374 100644
--- a/src/tests/test_bigint.cpp
+++ b/src/tests/test_bigint.cpp
@@ -448,8 +448,18 @@ class BigInt_InvMod_Test : public Text_Based_Test
 
          if(a_inv > 1)
             {
-            const Botan::BigInt z = (a * a_inv) % mod;
-            result.test_eq("inverse ok", z, 1);
+            result.test_eq("inverse ok", (a * a_inv) % mod, 1);
+            }
+
+         if(mod.is_odd())
+            {
+            result.test_eq("normalized_montgomery_inverse",
+                           normalized_montgomery_inverse(a, mod),
+                           expected);
+
+            result.test_eq("ct_inverse_odd_modulus",
+                           ct_inverse_mod_odd_modulus(a, mod),
+                           expected);
             }
 
          return result;
diff --git a/src/tests/test_mp.cpp b/src/tests/test_mp.cpp
index b52d93406..cbaf465a4 100644
--- a/src/tests/test_mp.cpp
+++ b/src/tests/test_mp.cpp
@@ -26,6 +26,7 @@ class MP_Unit_Tests : public Test
          results.push_back(test_cnd_swap());
          results.push_back(test_cnd_add());
          results.push_back(test_cnd_sub());
+         results.push_back(test_cnd_abs());
 
          return results;
          }
@@ -75,6 +76,37 @@ class MP_Unit_Tests : public Test
          return result;
          }
 
+      Result test_cnd_abs()
+         {
+         Result result("bigint_cnd_abs");
+
+         using namespace Botan;
+
+         word x1 = MP_WORD_MAX;
+         bigint_cnd_abs(1, &x1, 1);
+         result.test_int_eq(x1, 1, "Abs");
+
+         x1 = 0;
+         bigint_cnd_abs(1, &x1, 1);
+         result.test_int_eq(x1, 0, "Abs");
+
+         x1 = 1;
+         bigint_cnd_abs(1, &x1, 1);
+         result.test_int_eq(x1, MP_WORD_MAX, "Abs");
+
+         x1 = 1;
+         bigint_cnd_abs(0, &x1, 1);
+         result.test_int_eq(x1, 1, "No change");
+
+         word x2[2] = { MP_WORD_MAX, MP_WORD_MAX };
+
+         bigint_cnd_abs(1, x2, 2);
+         result.test_int_eq(x2[0], 1, "Abs");
+         result.test_int_eq(x2[1], 0, "Abs");
+
+         return result;
+         }
+
       Result test_cnd_swap()
          {
          Result result("bigint_cnd_swap");