aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--src/lib/math/mp/mp_asm.cpp81
-rw-r--r--src/lib/math/mp/mp_core.h22
-rw-r--r--src/lib/utils/ct_utils.h2
-rw-r--r--src/tests/test_mp.cpp123
-rw-r--r--src/tests/tests.h7
5 files changed, 233 insertions, 2 deletions
diff --git a/src/lib/math/mp/mp_asm.cpp b/src/lib/math/mp/mp_asm.cpp
index b7d90552e..6d60d7e77 100644
--- a/src/lib/math/mp/mp_asm.cpp
+++ b/src/lib/math/mp/mp_asm.cpp
@@ -1,6 +1,6 @@
/*
* MPI Add, Subtract, Word Multiply
-* (C) 1999-2010 Jack Lloyd
+* (C) 1999-2010,2016 Jack Lloyd
* 2006 Luca Piccarreta
*
* Botan is released under the Simplified BSD License (see license.txt)
@@ -9,12 +9,91 @@
#include <botan/internal/mp_core.h>
#include <botan/internal/mp_asmi.h>
#include <botan/internal/mp_core.h>
+#include <botan/internal/ct_utils.h>
#include <botan/exceptn.h>
#include <botan/mem_ops.h>
namespace Botan {
/*
+* If cond == 0, does nothing.
+* If cond > 0, swaps x[0:size] with y[0:size]
+* Runs in constant time
+*/
+void bigint_cnd_swap(word cnd, word x[], word y[], size_t size)
+ {
+ const word mask = CT::expand_mask(cnd);
+
+ CT::poison(x, size);
+ CT::poison(y, size);
+
+ for(size_t i = 0; i != size; ++i)
+ {
+ word a = x[i];
+ word b = y[i];
+ x[i] = CT::select(mask, b, a);
+ y[i] = CT::select(mask, a, b);
+ }
+
+ CT::unpoison(x, size);
+ CT::unpoison(y, size);
+ }
+
+/*
+* If cond > 0 adds x[0:size] to y[0:size] and returns carry
+* Runs in constant time
+*/
+word bigint_cnd_add(word cnd, word x[], const word y[], size_t size)
+ {
+ const word mask = CT::expand_mask(cnd);
+
+ CT::poison(x, size);
+ CT::poison(y, size);
+
+ word carry = 0;
+ for(size_t i = 0; i != size; ++i)
+ {
+ /*
+ Here we are relying on asm version of word_add being
+ a single addcl or equivalent. Fix this.
+ */
+ const word z = word_add(x[i], y[i], &carry);
+ x[i] = CT::select(mask, z, x[i]);
+ }
+
+ CT::unpoison(x, size);
+ CT::unpoison(y, size);
+ CT::unpoison(carry);
+
+ return carry & mask;
+ }
+
+/*
+* If cond > 0 subs x[0:size] to y[0:size] and returns borrow
+* Runs in constant time
+*/
+word bigint_cnd_sub(word cnd, word x[], const word y[], size_t size)
+ {
+ const word mask = CT::expand_mask(cnd);
+
+ CT::poison(x, size);
+ CT::poison(y, size);
+
+ word carry = 0;
+ for(size_t i = 0; i != size; ++i)
+ {
+ const word z = word_sub(x[i], y[i], &carry);
+ x[i] = CT::select(mask, z, x[i]);
+ }
+
+ CT::unpoison(x, size);
+ CT::unpoison(y, size);
+ CT::unpoison(carry);
+
+ return carry & mask;
+ }
+
+/*
* Two Operand Addition, No Carry
*/
word bigint_add2_nc(word x[], size_t x_size, const word y[], size_t y_size)
diff --git a/src/lib/math/mp/mp_core.h b/src/lib/math/mp/mp_core.h
index 9921f1f07..86bc920cf 100644
--- a/src/lib/math/mp/mp_core.h
+++ b/src/lib/math/mp/mp_core.h
@@ -18,6 +18,28 @@ namespace Botan {
*/
const size_t MP_WORD_BITS = BOTAN_MP_WORD_BITS;
+/*
+* If cond == 0, does nothing.
+* If cond > 0, swaps x[0:size] with y[0:size]
+* Runs in constant time
+*/
+BOTAN_DLL
+void bigint_cnd_swap(word cnd, word x[], word y[], size_t size);
+
+/*
+* If cond > 0 adds x[0:size] to y[0:size] and returns carry
+* Runs in constant time
+*/
+BOTAN_DLL
+word bigint_cnd_add(word cnd, word x[], const word y[], size_t size);
+
+/*
+* If cond > 0 subs x[0:size] to y[0:size] and returns borrow
+* Runs in constant time
+*/
+BOTAN_DLL
+word bigint_cnd_sub(word cnd, word x[], const word y[], size_t size);
+
/**
* Two operand addition
* @param x the first operand (and output)
diff --git a/src/lib/utils/ct_utils.h b/src/lib/utils/ct_utils.h
index 3d0d1ac86..401a53e86 100644
--- a/src/lib/utils/ct_utils.h
+++ b/src/lib/utils/ct_utils.h
@@ -68,7 +68,7 @@ template<typename T>
inline void unpoison(T& p)
{
#if defined(BOTAN_HAS_VALGRIND)
- VALGRIND_MAKE_MEM_DEFINED(p, sizeof(T));
+ VALGRIND_MAKE_MEM_DEFINED(&p, sizeof(T));
#else
BOTAN_UNUSED(p);
#endif
diff --git a/src/tests/test_mp.cpp b/src/tests/test_mp.cpp
new file mode 100644
index 000000000..b52d93406
--- /dev/null
+++ b/src/tests/test_mp.cpp
@@ -0,0 +1,123 @@
+/*
+* (C) 2016 Jack Lloyd
+*
+* Botan is released under the Simplified BSD License (see license.txt)
+*/
+
+#include "tests.h"
+
+#if defined(BOTAN_HAS_BIGINT_MP)
+ #include <botan/internal/mp_core.h>
+#endif
+
+namespace Botan_Tests {
+
+namespace {
+
+#if defined(BOTAN_HAS_BIGINT_MP)
+
+class MP_Unit_Tests : public Test
+ {
+ public:
+ std::vector<Test::Result> run() override
+ {
+ std::vector<Test::Result> results;
+
+ results.push_back(test_cnd_swap());
+ results.push_back(test_cnd_add());
+ results.push_back(test_cnd_sub());
+
+ return results;
+ }
+ private:
+ Result test_cnd_add()
+ {
+ Result result("bigint_cnd_add");
+
+ using namespace Botan;
+
+ const word max = MP_WORD_MAX;
+
+ word a = 2;
+ word c = bigint_cnd_add(0, &a, &max, 1);
+
+ result.test_int_eq(a, 2, "No op");
+ result.test_int_eq(c, 0, "No op");
+
+ c = bigint_cnd_add(1, &a, &max, 1);
+
+ result.test_int_eq(a, 1, "Add");
+ result.test_int_eq(c, 1, "Carry");
+
+ // TODO more tests
+
+ return result;
+ }
+
+ Result test_cnd_sub()
+ {
+ Result result("bigint_cnd_sub");
+
+ using namespace Botan;
+
+ word a = 2;
+ word b = 3;
+ word c = bigint_cnd_sub(0, &a, &b, 1);
+
+ result.test_int_eq(a, 2, "No op");
+ result.test_int_eq(c, 0, "No op");
+
+ c = bigint_cnd_sub(1, &a, &b, 1);
+
+ result.test_int_eq(a, MP_WORD_MAX, "Sub");
+ result.test_int_eq(c, 1, "Borrow");
+
+ return result;
+ }
+
+ Result test_cnd_swap()
+ {
+ Result result("bigint_cnd_swap");
+
+ using namespace Botan;
+
+ // null with zero length is ok
+ bigint_cnd_swap(0, nullptr, nullptr, 0);
+ bigint_cnd_swap(1, nullptr, nullptr, 0);
+
+ word x1 = 5, y1 = 9;
+
+ bigint_cnd_swap(0, &x1, &y1, 1);
+ result.test_int_eq(x1, 5, "No swap");
+ bigint_cnd_swap(1, &x1, &y1, 1);
+ result.test_int_eq(x1, 9, "Swap");
+
+ word x5[5] = { 0, 1, 2, 3, 4 };
+ word y5[5] = { 3, 2, 1, 0, 9 };
+
+ // Should only modify first four
+ bigint_cnd_swap(1, x5, y5, 4);
+
+ for(size_t i = 0; i != 4; ++i)
+ {
+ result.test_int_eq(x5[i], 3-i, "Swap x5");
+ }
+ result.test_int_eq(x5[4], 4, "Not touched");
+
+ for(size_t i = 0; i != 4; ++i)
+ {
+ result.test_int_eq(y5[i], i, "Swap y5");
+ }
+ result.test_int_eq(y5[4], 9, "Not touched");
+
+ return result;
+ }
+ };
+
+BOTAN_REGISTER_TEST("mp_unit", MP_Unit_Tests);
+
+#endif
+
+}
+
+}
diff --git a/src/tests/tests.h b/src/tests/tests.h
index 5a075975d..0c561a7d3 100644
--- a/src/tests/tests.h
+++ b/src/tests/tests.h
@@ -174,6 +174,13 @@ class Test
bool test_eq(const std::string& what, bool produced, bool expected);
bool test_eq(const std::string& what, size_t produced, size_t expected);
+
+ template<typename I1, typename I2>
+ bool test_int_eq(I1 x, I2 y, const char* what)
+ {
+ return test_eq(what, static_cast<size_t>(x), static_cast<size_t>(y));
+ }
+
bool test_lt(const std::string& what, size_t produced, size_t expected);
bool test_gte(const std::string& what, size_t produced, size_t expected);
generated by cgit v1.2.3 (git 2.39.1) at 2024-12-22 09:44:26 +0000