diff options
| -rw-r--r-- | src/fuzzer/barrett.cpp | 12 | ||||
| -rw-r--r-- | src/lib/math/bigint/bigint.h | 7 | ||||
| -rw-r--r-- | src/lib/math/numbertheory/reducer.cpp | 52 | ||||
| -rw-r--r-- | src/tests/test_bigint.cpp | 4 |
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)) { |