diff options
author | Jack Lloyd <jack@randombit.net> | 2018-12-07 11:54:49 -0500 |
---|---|---|
committer | Jack Lloyd <jack@randombit.net> | 2018-12-07 11:54:49 -0500 |
commit | efad37ca79d9749e4492a07d61f0356aad221193 (patch) | |
tree | 2c9a4ebf8820f9e95f936d0f72ed9ebc605d81c4 /src/lib/math | |
parent | dbadf2e21b9925b593beab95bead38b94622c4f4 (diff) | |
parent | e7038bf0c5a8e083555c2ce4e00a11a74e55cf0a (diff) |
Merge GH #1773 Add BigInt::ct_reduce_below
Diffstat (limited to 'src/lib/math')
-rw-r--r-- | src/lib/math/bigint/bigint.cpp | 27 | ||||
-rw-r--r-- | src/lib/math/bigint/bigint.h | 12 | ||||
-rw-r--r-- | src/lib/math/numbertheory/reducer.cpp | 3 |
3 files changed, 39 insertions, 3 deletions
diff --git a/src/lib/math/bigint/bigint.cpp b/src/lib/math/bigint/bigint.cpp index dd5ee6ac3..a760be4e8 100644 --- a/src/lib/math/bigint/bigint.cpp +++ b/src/lib/math/bigint/bigint.cpp @@ -320,8 +320,8 @@ BigInt BigInt::operator-() const size_t BigInt::reduce_below(const BigInt& p, secure_vector<word>& ws) { - if(p.is_negative()) - throw Invalid_Argument("BigInt::reduce_below mod must be positive"); + if(p.is_negative() || this->is_negative()) + throw Invalid_Argument("BigInt::reduce_below both values must be positive"); const size_t p_words = p.sig_words(); @@ -348,6 +348,29 @@ size_t BigInt::reduce_below(const BigInt& p, secure_vector<word>& ws) return reductions; } +void BigInt::ct_reduce_below(const BigInt& mod, secure_vector<word>& ws, size_t bound) + { + if(mod.is_negative() || this->is_negative()) + throw Invalid_Argument("BigInt::ct_reduce_below both values must be positive"); + + const size_t mod_words = mod.sig_words(); + + grow_to(mod_words); + + const size_t sz = size(); + + ws.resize(sz); + + clear_mem(ws.data(), sz); + + for(size_t i = 0; i != bound; ++i) + { + word borrow = bigint_sub3(ws.data(), data(), sz, mod.data(), mod_words); + + CT::Mask<word>::is_zero(borrow).select_n(mutable_data(), ws.data(), data(), sz); + } + } + /* * Return the absolute value of this number */ diff --git a/src/lib/math/bigint/bigint.h b/src/lib/math/bigint/bigint.h index 31eee4c3c..a987fffda 100644 --- a/src/lib/math/bigint/bigint.h +++ b/src/lib/math/bigint/bigint.h @@ -347,6 +347,18 @@ class BOTAN_PUBLIC_API(2,0) BigInt final size_t reduce_below(const BigInt& mod, secure_vector<word> &ws); /** + * Return *this % mod + * + * Assumes that *this is (if anything) only slightly larger than mod and + * performs repeated subtractions. It should not be used if *this is much + * larger than mod, instead use modulo operator. + * + * Performs exactly bound subtractions, so if *this is >= bound*mod then the + * result will not be fully reduced. If bound is zero, nothing happens. + */ + void ct_reduce_below(const BigInt& mod, secure_vector<word> &ws, size_t bound); + + /** * Zeroize the BigInt. The size of the underlying register is not * modified. */ diff --git a/src/lib/math/numbertheory/reducer.cpp b/src/lib/math/numbertheory/reducer.cpp index 0468d004b..ec0071eac 100644 --- a/src/lib/math/numbertheory/reducer.cpp +++ b/src/lib/math/numbertheory/reducer.cpp @@ -84,7 +84,8 @@ void Modular_Reducer::reduce(BigInt& t1, const BigInt& x, secure_vector<word>& w t1.add(ws.data(), m_mod_words + 2, BigInt::Positive); - t1.reduce_below(m_modulus, ws); + // Per HAC this step requires at most 2 subtractions + t1.ct_reduce_below(m_modulus, ws, 2); if(x.is_negative() && t1.is_nonzero()) { |