From e5477c449830e099afc7c495ba738570ab7aabf8 Mon Sep 17 00:00:00 2001 From: Jack Lloyd Date: Wed, 26 Dec 2018 09:15:54 -0500 Subject: Fix Barrett reduction input bound In the long ago when I wrote the Barrett code I must have missed that Barrett works for any input < 2^2k where k is the word size of the modulus. Fixing this has several nice effects, it is faster because it replaces a multiprecision comparison with a single size_t compare, and now the branch does not reveal information about the input or modulus, but only their word lengths, which is not considered sensitive. Fixing this allows reverting the change make in a57ce5a4fd2 and now RSA signing is even slightly faster than in 2.8, rather than 30% slower. --- src/lib/math/numbertheory/reducer.cpp | 8 ++++---- 1 file changed, 4 insertions(+), 4 deletions(-) (limited to 'src/lib/math/numbertheory/reducer.cpp') diff --git a/src/lib/math/numbertheory/reducer.cpp b/src/lib/math/numbertheory/reducer.cpp index c37a1daeb..deb3874d3 100644 --- a/src/lib/math/numbertheory/reducer.cpp +++ b/src/lib/math/numbertheory/reducer.cpp @@ -28,9 +28,9 @@ Modular_Reducer::Modular_Reducer(const BigInt& mod) m_modulus = mod; m_mod_words = m_modulus.sig_words(); - m_modulus_2 = Botan::square(m_modulus); - - m_mu = ct_divide(BigInt::power_of_2(2 * BOTAN_MP_WORD_BITS * m_mod_words), m_modulus); + // Compute mu = floor(2^{2k} / m) + m_mu.set_bit(2 * BOTAN_MP_WORD_BITS * m_mod_words); + m_mu = ct_divide(m_mu, m_modulus); } } @@ -76,7 +76,7 @@ void Modular_Reducer::reduce(BigInt& t1, const BigInt& x, secure_vector& w const size_t x_sw = x.sig_words(); - if(x.cmp(m_modulus_2, false) >= 0) + if(x_sw > 2*m_mod_words) { // too big, fall back to slow boat division t1 = ct_modulo(x, m_modulus); -- cgit v1.2.3