aboutsummaryrefslogtreecommitdiffstats
path: root/src/lib/math
diff options
context:
space:
mode:
Diffstat (limited to 'src/lib/math')
-rw-r--r--src/lib/math/bigint/bigint.h7
-rw-r--r--src/lib/math/numbertheory/reducer.cpp52
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;
}
}