diff options
Diffstat (limited to 'src/lib/math')
-rw-r--r-- | src/lib/math/bigint/bigint.h | 7 | ||||
-rw-r--r-- | src/lib/math/numbertheory/reducer.cpp | 52 |
2 files changed, 33 insertions, 26 deletions
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; } } |