aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorJack Lloyd <[email protected]>2018-06-05 21:05:27 -0400
committerJack Lloyd <[email protected]>2018-06-05 21:05:27 -0400
commit97b645e1ad4dba19e3ec45d896c4e31317f96a1c (patch)
treeaff2479b03bf6aab292450d1b47847ff34b22b7a
parentb67c70c2e307049512a1e153e555a16314923e90 (diff)
parentc0cdcb3164d379851a995cd2b3d51944888d90df (diff)
Merge GH #1599 Fix bug in Barrett reduction of negative numbers
-rw-r--r--src/fuzzer/barrett.cpp12
-rw-r--r--src/lib/math/bigint/bigint.h7
-rw-r--r--src/lib/math/numbertheory/reducer.cpp52
-rw-r--r--src/tests/test_bigint.cpp4
4 files changed, 45 insertions, 30 deletions
diff --git a/src/fuzzer/barrett.cpp b/src/fuzzer/barrett.cpp
index 1c5d88f87..09aed517e 100644
--- a/src/fuzzer/barrett.cpp
+++ b/src/fuzzer/barrett.cpp
@@ -12,20 +12,24 @@ void fuzz(const uint8_t in[], size_t len)
{
static const size_t max_bits = 2048;
- if(len % 2 != 0)
+ if(len <= 1 || len % 3 != 1)
return;
- const size_t part_size = len / 2;
+ const size_t part_size = len / 3;
if(part_size * 8 > max_bits)
return;
- const Botan::BigInt x = Botan::BigInt::decode(in, part_size);
- const Botan::BigInt p = Botan::BigInt::decode(in + part_size, part_size);
+ uint8_t flags = in[0];
+ Botan::BigInt x = Botan::BigInt::decode(in + 1, part_size * 2);
+ const Botan::BigInt p = Botan::BigInt::decode(in + 1 + part_size * 2, part_size);
if(p.is_zero())
return;
+ if(flags & 1)
+ x.flip_sign();
+
const Botan::BigInt ref = x % p;
const Botan::Modular_Reducer mod_p(p);
diff --git a/src/lib/math/bigint/bigint.h b/src/lib/math/bigint/bigint.h
index 64ab24e7d..0b826c8f5 100644
--- a/src/lib/math/bigint/bigint.h
+++ b/src/lib/math/bigint/bigint.h
@@ -256,6 +256,9 @@ class BOTAN_PUBLIC_API(2,0) BigInt final
*/
bool operator !() const { return (!is_nonzero()); }
+ BigInt& add(const word y[], size_t y_words, Sign sign);
+ BigInt& sub(const word y[], size_t y_words, Sign sign);
+
/**
* Multiply this with y
* @param y the BigInt to multiply with this
@@ -724,10 +727,6 @@ class BOTAN_PUBLIC_API(2,0) BigInt final
size_t idx);
private:
-
- BigInt& add(const word y[], size_t y_words, Sign sign);
- BigInt& sub(const word y[], size_t y_words, Sign sign);
-
secure_vector<word> m_reg;
Sign m_signedness = Positive;
};
diff --git a/src/lib/math/numbertheory/reducer.cpp b/src/lib/math/numbertheory/reducer.cpp
index 9dbcfb9a3..b59a8d989 100644
--- a/src/lib/math/numbertheory/reducer.cpp
+++ b/src/lib/math/numbertheory/reducer.cpp
@@ -1,6 +1,6 @@
/*
* Modular Reducer
-* (C) 1999-2011 Jack Lloyd
+* (C) 1999-2011,2018 Jack Lloyd
*
* Botan is released under the Simplified BSD License (see license.txt)
*/
@@ -35,43 +35,51 @@ BigInt Modular_Reducer::reduce(const BigInt& x) const
const size_t x_sw = x.sig_words();
- if(x_sw < m_mod_words || x.cmp(m_modulus, false) < 0)
+ if(x_sw >= (2*m_mod_words - 1) && x.cmp(m_modulus_2, false) >= 0)
+ {
+ // too big, fall back to normal division
+ return (x % m_modulus);
+ }
+
+ if(x_sw < m_mod_words - 1)
{
if(x.is_negative())
return x + m_modulus; // make positive
return x;
}
- else if(x.cmp(m_modulus_2, false) < 0)
- {
- secure_vector<word> ws;
- BigInt t1(x.data() + m_mod_words - 1, x_sw - (m_mod_words - 1));
+ secure_vector<word> ws;
- t1.mul(m_mu, ws);
- t1 >>= (BOTAN_MP_WORD_BITS * (m_mod_words + 1));
+ BigInt t1(x.data() + (m_mod_words - 1), x_sw - (m_mod_words - 1));
- t1.mul(m_modulus, ws);
- t1.mask_bits(BOTAN_MP_WORD_BITS * (m_mod_words + 1));
+ t1.mul(m_mu, ws);
+ t1 >>= (BOTAN_MP_WORD_BITS * (m_mod_words + 1));
- t1.rev_sub(x.data(), std::min(x_sw, m_mod_words + 1), ws);
+ // TODO add masked mul to avoid computing high bits
+ t1.mul(m_modulus, ws);
+ t1.mask_bits(BOTAN_MP_WORD_BITS * (m_mod_words + 1));
- if(t1.is_negative())
- {
- t1 += BigInt::power_of_2(BOTAN_MP_WORD_BITS * (m_mod_words + 1));
- }
+ t1.rev_sub(x.data(), std::min(x_sw, m_mod_words + 1), ws);
- t1.reduce_below(m_modulus, ws);
+ if(t1.is_negative())
+ {
+ if(ws.size() < m_mod_words + 2)
+ ws.resize(m_mod_words + 2);
+ clear_mem(ws.data(), ws.size());
- if(x.is_negative())
- t1.rev_sub(m_modulus.data(), m_modulus.size(), ws);
+ ws[m_mod_words + 1] = 1;
- return t1;
+ t1.add(ws.data(), m_mod_words + 2, BigInt::Positive);
}
- else
+
+ t1.reduce_below(m_modulus, ws);
+
+ if(x.is_negative() && t1.is_nonzero())
{
- // too big, fall back to normal division
- return (x % m_modulus);
+ t1.rev_sub(m_modulus.data(), m_modulus.size(), ws);
}
+
+ return t1;
}
}
diff --git a/src/tests/test_bigint.cpp b/src/tests/test_bigint.cpp
index b62fa307d..8074a4f3b 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/reducer.h>
#include <botan/pow_mod.h>
#include <botan/parsing.h>
#include "test_rng.h"
@@ -398,6 +399,9 @@ class BigInt_Mod_Test final : public Text_Based_Test
e %= b;
result.test_eq("a %= b", e, c);
+ const Botan::Modular_Reducer mod_b(b);
+ result.test_eq("Barrett", mod_b.reduce(a), c);
+
// if b fits into a Botan::word test %= operator for words
if(b.bytes() <= sizeof(Botan::word))
{