aboutsummaryrefslogtreecommitdiffstats
path: root/src/lib
diff options
context:
space:
mode:
authorJack Lloyd <[email protected]>2018-12-03 05:47:02 -0500
committerJack Lloyd <[email protected]>2018-12-03 05:47:02 -0500
commit8fa5b4f7d50f48b673be3eb17a335ac1d18de0df (patch)
tree9d8ef9ba74b684113d30335ff3ab3af4209b13b4 /src/lib
parent219a2a26ddd6164fe6dc9f3638bfe167e831fb79 (diff)
parent1670af4bdf6b5139fa218377fa8761e2c4ea0e4a (diff)
Merge GH #1759 Add constant time divide by uint8_t
Diffstat (limited to 'src/lib')
-rw-r--r--src/lib/math/bigint/big_code.cpp13
-rw-r--r--src/lib/math/bigint/divide.cpp37
-rw-r--r--src/lib/math/bigint/divide.h16
3 files changed, 59 insertions, 7 deletions
diff --git a/src/lib/math/bigint/big_code.cpp b/src/lib/math/bigint/big_code.cpp
index 8fd528a14..6d8c61fd5 100644
--- a/src/lib/math/bigint/big_code.cpp
+++ b/src/lib/math/bigint/big_code.cpp
@@ -17,13 +17,13 @@ std::string BigInt::to_dec_string() const
BigInt copy = *this;
copy.set_sign(Positive);
- BigInt remainder;
+ uint8_t remainder;
std::vector<uint8_t> digits;
while(copy > 0)
{
- divide(copy, 10, copy, remainder);
- digits.push_back(static_cast<uint8_t>(remainder.word_at(0)));
+ ct_divide_u8(copy, 10, copy, remainder);
+ digits.push_back(remainder);
}
std::string s;
@@ -68,14 +68,13 @@ void BigInt::encode(uint8_t output[], const BigInt& n, Base base)
else if(base == Decimal)
{
BigInt copy = n;
- BigInt remainder;
+ uint8_t remainder;
copy.set_sign(Positive);
const size_t output_size = n.encoded_size(Decimal);
for(size_t j = 0; j != output_size; ++j)
{
- divide(copy, 10, copy, remainder);
- output[output_size - 1 - j] =
- Charset::digit2char(static_cast<uint8_t>(remainder.word_at(0)));
+ ct_divide_u8(copy, 10, copy, remainder);
+ output[output_size - 1 - j] = Charset::digit2char(remainder);
if(copy.is_zero())
break;
}
diff --git a/src/lib/math/bigint/divide.cpp b/src/lib/math/bigint/divide.cpp
index 0dd0eb174..a11e8b70b 100644
--- a/src/lib/math/bigint/divide.cpp
+++ b/src/lib/math/bigint/divide.cpp
@@ -79,6 +79,43 @@ void ct_divide(const BigInt& x, const BigInt& y, BigInt& q_out, BigInt& r_out)
q_out = q;
}
+void ct_divide_u8(const BigInt& x, uint8_t y, BigInt& q_out, uint8_t& r_out)
+ {
+ const size_t x_words = x.sig_words();
+ const size_t x_bits = x.bits();
+ const size_t y_words = 1;
+
+ BigInt q(BigInt::Positive, x_words);
+ uint32_t r = 0;
+
+ 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 += x_b;
+
+ const auto r_gte_y = CT::Mask<uint32_t>::is_gte(r, y);
+
+ q.conditionally_set_bit(b, r_gte_y.is_set());
+ r = r_gte_y.select(r - y, r);
+ }
+
+ if(x.sign() == BigInt::Negative)
+ {
+ q.flip_sign();
+ if(r != 0)
+ {
+ --q;
+ r = y - r;
+ }
+ }
+
+ r_out = static_cast<uint8_t>(r);
+ q_out = q;
+ }
+
/*
* Solve x = q * y + r
*/
diff --git a/src/lib/math/bigint/divide.h b/src/lib/math/bigint/divide.h
index d7d72e200..d83f4b695 100644
--- a/src/lib/math/bigint/divide.h
+++ b/src/lib/math/bigint/divide.h
@@ -40,6 +40,22 @@ void BOTAN_PUBLIC_API(2,9) ct_divide(const BigInt& x,
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_u8(const BigInt& x,
+ uint8_t y,
+ BigInt& q,
+ uint8_t& r);
+
}
#endif