Fix exponentiation bug, related fixes

GH #754 exposed a bug in the non-Montgomery exponentiation case.
It turned out then when the fixed window was picked to any value
> 1, the result would be incorrect due to an off by one. This is
the one line fix in powm_fw.cpp

Also fix a bug in bigint_mul which caused incorrect results,
because the output BigInt was not being zeroed out before use. This
is only exposed in rare cases, found (somewhat indirectly) in
OSS-Fuzz #287.

Add more modular exponentiation tests, which would have caught
these issues earlier.

3 files changed, 55 insertions, 3 deletions

diff --git a/src/tests/data/bn/mul.vec b/src/tests/data/bn/mul.vec
index d70428112..a7e5601c7 100644
--- a/src/tests/data/bn/mul.vec
+++ b/src/tests/data/bn/mul.vec
@@ -410,3 +410,7 @@ Output = 0xED478AFD970F5D8E22B1E85E2C186CD98172870A148C78475D57F7B524BD7752FD6F7
 In1 = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
 In2 = 0x4000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001
 Output = 0x4000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000BFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
+
+In1 = 1024
+In2 = 0x918100000000000181fe7e0000000000fffe0001000
+Output = 0x2460400000000000607f9f80000000003fff8000400000
diff --git a/src/tests/data/bn/powmod.vec b/src/tests/data/bn/powmod.vec
index a84659768..024a2d36b 100644
--- a/src/tests/data/bn/powmod.vec
+++ b/src/tests/data/bn/powmod.vec
@@ -1,4 +1,5 @@
 [ModExp]
+
 Base = 0x1
 Exponent = 0x0
 Modulus = 0x2
@@ -193,3 +194,25 @@ Base = 0xF9FFFFF000000FFFFFFFFFFFFFFFC0000000
 Exponent = 0x83FFFF000000000000000003FFFFFFFFFFFF
 Modulus = 0xFFE007FFF9F83FFFFF8F000FFFFFFFFFFFFF
 Output = 0xA917797602DADCC854BD67D27E86BB1D6575
+
+# OSS-Fuzz #287 followed by some variations
+Base = 1024
+Exponent = 0x1000000000000000000000000000000000000000000000000000000000030400000000000004000
+Modulus = 0x40000000000000000000000000000000000000000000000000000000000c100000000000000ffff
+Output = 32
+
+Base = 1024
+Exponent = 0x1000000000000000000000000000000000000000000000000000000000030400000000000004001
+Modulus = 0x40000000000000000000000000000000000000000000000000000000000c100000000000000ffff
+Output = 32768
+
+Base = 1024
+Exponent = 0x1000000000000000000000000000000000000000000000000000000000030400000000000004001
+Modulus = 0x40000000000000000000000000000000000000000000000000000000000c100000000000000fffd
+Output = 0x3a130cf2e4c28710c6661c071e38d642150f28479017f313d2a855564458f9a958753fb286d6b6e
+
+Base = 1024
+Exponent = 0x20000000000000000000000000000000000000000000000000000000000608000000000000080
+Modulus  = 0x40000000000000000000000000000000000000000000000000000000000c100000000000000fffd
+Output = 0x9943fa648c48cb4cd01756bed11e3382aca74d84fb0bf8cf8d56cd4524f80538d4888cbd23b8e2
+
diff --git a/src/tests/test_bigint.cpp b/src/tests/test_bigint.cpp
index 27de5cfcb..ad837cc91 100644
--- a/src/tests/test_bigint.cpp
+++ b/src/tests/test_bigint.cpp
@@ -404,12 +404,37 @@ class BigInt_Powmod_Test : public Text_Based_Test
          {
          Test::Result result("BigInt Powmod");
 
-         const BigInt value = get_req_bn(vars, "Base");
+         const BigInt base = get_req_bn(vars, "Base");
          const BigInt exponent = get_req_bn(vars, "Exponent");
          const BigInt modulus = get_req_bn(vars, "Modulus");
-         const BigInt output = get_req_bn(vars, "Output");
+         const BigInt expected = get_req_bn(vars, "Output");
+
+         result.test_eq("power_mod", Botan::power_mod(base, exponent, modulus), expected);
+
+         Botan::Power_Mod pow_mod1(modulus);
+
+         pow_mod1.set_base(base);
+         pow_mod1.set_exponent(exponent);
+         result.test_eq("pow_mod1", pow_mod1.execute(), expected);
+
+         Botan::Power_Mod pow_mod2(modulus);
 
-         result.test_eq("power_mod", Botan::power_mod(value, exponent, modulus), output);
+         // Reverses ordering which affects window size
+         pow_mod2.set_exponent(exponent);
+         pow_mod2.set_base(base);
+         result.test_eq("pow_mod2", pow_mod2.execute(), expected);
+         result.test_eq("pow_mod2 #2", pow_mod2.execute(), expected);
+
+         if(modulus.is_odd())
+            {
+            // TODO: test different hints
+            // also TODO: remove bogus hinting arguments :)
+            Botan::Power_Mod pow_mod3(modulus, Botan::Power_Mod::NO_HINTS, /*disable_montgomery=*/true);
+
+            pow_mod3.set_exponent(exponent);
+            pow_mod3.set_base(base);
+            result.test_eq("pow_mod_fixed_window", pow_mod3.execute(), expected);
+            }
 
          return result;
          }