aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--src/cli/speed.cpp45
-rw-r--r--src/fuzzer/divide.cpp8
-rw-r--r--src/lib/math/bigint/bigint.cpp4
-rw-r--r--src/lib/math/bigint/bigint.h15
-rw-r--r--src/lib/math/bigint/divide.cpp36
-rw-r--r--src/lib/math/bigint/divide.h22
-rwxr-xr-xsrc/scripts/test_cli.py2
-rw-r--r--src/tests/data/bn/divide.vec8
-rw-r--r--src/tests/test_bigint.cpp21
9 files changed, 145 insertions, 16 deletions
diff --git a/src/cli/speed.cpp b/src/cli/speed.cpp
index ec6db5c86..59771fb65 100644
--- a/src/cli/speed.cpp
+++ b/src/cli/speed.cpp
@@ -26,6 +26,7 @@
#if defined(BOTAN_HAS_BIGINT)
#include <botan/bigint.h>
+ #include <botan/divide.h>
#endif
#if defined(BOTAN_HAS_BLOCK_CIPHER)
@@ -653,6 +654,10 @@ class Speed final : public Command
{
bench_mp_mul(msec);
}
+ else if(algo == "mp_div")
+ {
+ bench_mp_div(msec);
+ }
#endif
#if defined(BOTAN_HAS_NUMBERTHEORY)
@@ -1263,6 +1268,46 @@ class Speed final : public Command
}
+ void bench_mp_div(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 size_t q_bits = n_bits / 2;
+ const std::string bit_descr = std::to_string(n_bits) + "/" + std::to_string(q_bits);
+
+ 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 y;
+ Botan::BigInt x;
+ Botan::secure_vector<Botan::word> ws;
+
+ Botan::BigInt q1, r1, q2, r2;
+
+ while(ct_div_timer->under(runtime_per_size))
+ {
+ x.randomize(rng(), n_bits);
+ y.randomize(rng(), q_bits);
+
+ div_timer->start();
+ Botan::divide(x, y, q1, r1);
+ div_timer->stop();
+
+ ct_div_timer->start();
+ Botan::ct_divide(x, y, 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 01ec14e28..c0c86f051 100644
--- a/src/fuzzer/divide.cpp
+++ b/src/fuzzer/divide.cpp
@@ -1,5 +1,5 @@
/*
-* (C) 2015,2016 Jack Lloyd
+* (C) 2015,2016,2018 Jack Lloyd
*
* Botan is released under the Simplified BSD License (see license.txt)
*/
@@ -25,5 +25,11 @@ void fuzz(const uint8_t in[], size_t len)
Botan::BigInt 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);
}
diff --git a/src/lib/math/bigint/bigint.cpp b/src/lib/math/bigint/bigint.cpp
index d64082476..0e0dfe0d5 100644
--- a/src/lib/math/bigint/bigint.cpp
+++ b/src/lib/math/bigint/bigint.cpp
@@ -241,7 +241,7 @@ uint32_t BigInt::to_u32bit() const
/*
* Set bit number n
*/
-void BigInt::set_bit(size_t n)
+void BigInt::conditionally_set_bit(size_t n, bool set_it)
{
const size_t which = n / BOTAN_MP_WORD_BITS;
@@ -250,7 +250,7 @@ void BigInt::set_bit(size_t n)
grow_to(which + 1);
}
- const word mask = static_cast<word>(1) << (n % BOTAN_MP_WORD_BITS);
+ const word mask = static_cast<word>(set_it) << (n % BOTAN_MP_WORD_BITS);
m_data.set_word_at(which, word_at(which) | mask);
}
diff --git a/src/lib/math/bigint/bigint.h b/src/lib/math/bigint/bigint.h
index 9b385348e..64f81765a 100644
--- a/src/lib/math/bigint/bigint.h
+++ b/src/lib/math/bigint/bigint.h
@@ -414,7 +414,20 @@ class BOTAN_PUBLIC_API(2,0) BigInt final
* Set bit at specified position
* @param n bit position to set
*/
- void set_bit(size_t n);
+ void set_bit(size_t n)
+ {
+ conditionally_set_bit(n, true);
+ }
+
+ /**
+ * Conditionally set bit at specified position. Note if set_it is
+ * false, nothing happens, and if the bit is already set, it
+ * remains set.
+ *
+ * @param n bit position to set
+ * @param set_it if the bit should be set
+ */
+ void conditionally_set_bit(size_t n, bool set_it);
/**
* Clear bit at specified position
diff --git a/src/lib/math/bigint/divide.cpp b/src/lib/math/bigint/divide.cpp
index 63326d655..64d1537ba 100644
--- a/src/lib/math/bigint/divide.cpp
+++ b/src/lib/math/bigint/divide.cpp
@@ -1,6 +1,6 @@
/*
* Division Algorithm
-* (C) 1999-2007,2012 Jack Lloyd
+* (C) 1999-2007,2012,2018 Jack Lloyd
*
* Botan is released under the Simplified BSD License (see license.txt)
*/
@@ -8,6 +8,7 @@
#include <botan/divide.h>
#include <botan/internal/mp_core.h>
#include <botan/internal/mp_madd.h>
+#include <botan/internal/ct_utils.h>
namespace Botan {
@@ -52,6 +53,36 @@ bool division_check(word q, word y2, word y1,
}
+void ct_divide(const BigInt& x, const BigInt& y, BigInt& q_out, BigInt& r_out)
+ {
+ const size_t x_words = x.sig_words();
+ const size_t y_words = y.sig_words();
+
+ const size_t x_bits = x.bits();
+
+ BigInt q(BigInt::Positive, x_words);
+ BigInt r(BigInt::Positive, y_words);
+
+ 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.conditionally_set_bit(0, x_b);
+
+ // y <= r -> r >= y
+ const auto r_gte_y = bigint_ct_is_lt(y.data(), y_words, r.data(), r.size(), true);
+
+ q.conditionally_set_bit(b, r_gte_y.is_set());
+ bigint_cnd_sub(r_gte_y.value(), r.mutable_data(), r.size(), y.data(), y_words);
+ }
+
+ sign_fixup(x, y, q, r);
+ r_out = r;
+ q_out = q;
+ }
+
/*
* Solve x = q * y + r
*/
@@ -84,7 +115,8 @@ void divide(const BigInt& x, const BigInt& y_arg, BigInt& q, BigInt& r)
y <<= shifts;
r <<= shifts;
- const size_t n = r.sig_words() - 1, t = y_words - 1;
+ const size_t n = r.sig_words() - 1;
+ const size_t t = y_words - 1;
if(n < t)
throw Internal_Error("BigInt division word sizes");
diff --git a/src/lib/math/bigint/divide.h b/src/lib/math/bigint/divide.h
index 03e5ff7c1..d7d72e200 100644
--- a/src/lib/math/bigint/divide.h
+++ b/src/lib/math/bigint/divide.h
@@ -20,9 +20,25 @@ namespace Botan {
* @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);
+ const BigInt& y,
+ 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(const BigInt& x,
+ const BigInt& y,
+ BigInt& q,
+ BigInt& r);
}
diff --git a/src/scripts/test_cli.py b/src/scripts/test_cli.py
index 98423d8de..6445a3669 100755
--- a/src/scripts/test_cli.py
+++ b/src/scripts/test_cli.py
@@ -656,7 +656,7 @@ def cli_speed_tests():
if format_re.match(line) is None:
logging.error("Unexpected line %s", line)
- math_ops = ['mp_mul', 'modexp', 'random_prime', 'inverse_mod', 'rfc3394', 'fpe_fe1',
+ math_ops = ['mp_mul', 'mp_div', 'modexp', 'random_prime', 'inverse_mod', 'rfc3394', 'fpe_fe1',
'bn_redc', 'nistp_redc', 'ecc_mult', 'ecc_ops', 'os2ecp', 'primality_test',
'bcrypt', 'passhash9']
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;
}
};
generated by cgit v1.2.3 (git 2.39.1) at 2024-12-26 13:41:11 +0000