diff options
Diffstat (limited to 'src/lib')
-rw-r--r-- | src/lib/math/bigint/bigint.cpp | 9 | ||||
-rw-r--r-- | src/lib/math/bigint/bigint.h | 7 | ||||
-rw-r--r-- | src/lib/math/numbertheory/numthry.cpp | 38 | ||||
-rw-r--r-- | src/lib/math/numbertheory/primality.cpp | 9 |
4 files changed, 38 insertions, 25 deletions
diff --git a/src/lib/math/bigint/bigint.cpp b/src/lib/math/bigint/bigint.cpp index 3ada94dce..fac82defa 100644 --- a/src/lib/math/bigint/bigint.cpp +++ b/src/lib/math/bigint/bigint.cpp @@ -453,6 +453,15 @@ void BigInt::binary_decode(const uint8_t buf[], size_t length) m_data.swap(reg); } +void BigInt::ct_cond_add(bool predicate, const BigInt& value) + { + this->grow_to(1 + value.sig_words()); + + bigint_cnd_add(static_cast<word>(predicate), + this->mutable_data(), this->size(), + value.data(), value.sig_words()); + } + void BigInt::ct_cond_swap(bool predicate, BigInt& other) { const size_t max_words = std::max(size(), other.size()); diff --git a/src/lib/math/bigint/bigint.h b/src/lib/math/bigint/bigint.h index ac0a57038..9fda4ceb0 100644 --- a/src/lib/math/bigint/bigint.h +++ b/src/lib/math/bigint/bigint.h @@ -721,6 +721,11 @@ class BOTAN_PUBLIC_API(2,0) BigInt final void ct_cond_swap(bool predicate, BigInt& other); /** + * If predicate is true add value to *this + */ + void ct_cond_add(bool predicate, const BigInt& value); + + /** * If predicate is true flip the sign of *this */ void cond_flip_sign(bool predicate); @@ -982,7 +987,7 @@ class BOTAN_PUBLIC_API(2,0) BigInt final { const word mask = (static_cast<word>(1) << (n % BOTAN_MP_WORD_BITS)) - 1; const size_t len = size() - (top_word + 1); - if (len > 0) + if(len > 0) { clear_mem(&m_reg[top_word+1], len); } diff --git a/src/lib/math/numbertheory/numthry.cpp b/src/lib/math/numbertheory/numthry.cpp index 9fbaf8429..7c6e398a8 100644 --- a/src/lib/math/numbertheory/numthry.cpp +++ b/src/lib/math/numbertheory/numthry.cpp @@ -10,6 +10,7 @@ #include <botan/monty.h> #include <botan/divide.h> #include <botan/rng.h> +#include <botan/internal/ct_utils.h> #include <botan/internal/mp_core.h> #include <botan/internal/monty_exp.h> #include <botan/internal/primality.h> @@ -39,23 +40,25 @@ size_t low_zero_bits(const BigInt& n) { size_t low_zero = 0; - if(n.is_positive() && n.is_nonzero()) + auto seen_nonempty_word = CT::Mask<word>::cleared(); + + for(size_t i = 0; i != n.size(); ++i) { - for(size_t i = 0; i != n.size(); ++i) - { - const word x = n.word_at(i); - - if(x) - { - low_zero += ctz(x); - break; - } - else - low_zero += BOTAN_MP_WORD_BITS; - } + const word x = n.word_at(i); + + // ctz(0) will return sizeof(word) + const size_t tz_x = ctz(x); + + // if x > 0 we want to count tz_x in total but not any + // further words, so set the mask after the addition + low_zero += seen_nonempty_word.if_not_set_return(tz_x); + + seen_nonempty_word |= CT::Mask<word>::expand(x); } - return low_zero; + // if we saw no words with x > 0 then n == 0 and the value we have + // computed is meaningless. Instead return 0 in that case. + return seen_nonempty_word.if_set_return(low_zero); } /* @@ -68,6 +71,8 @@ BigInt gcd(const BigInt& a, const BigInt& b) if(a == 1 || b == 1) return 1; + // See https://gcd.cr.yp.to/safegcd-20190413.pdf fig 1.2 + BigInt f = a; BigInt g = b; f.set_sign(BigInt::Positive); @@ -100,10 +105,7 @@ BigInt gcd(const BigInt& a, const BigInt& b) delta += 1; - t = g; - t += f; - g.ct_cond_assign(g.is_odd(), t); - + g.ct_cond_add(g.is_odd(), f); g >>= 1; } diff --git a/src/lib/math/numbertheory/primality.cpp b/src/lib/math/numbertheory/primality.cpp index 028e2a7ef..eb2be42b1 100644 --- a/src/lib/math/numbertheory/primality.cpp +++ b/src/lib/math/numbertheory/primality.cpp @@ -67,8 +67,7 @@ bool is_lucas_probable_prime(const BigInt& C, const Modular_Reducer& mod_C) Ut = mod_C.multiply(U, V); Vt = mod_C.reduce(mod_C.square(V) + mod_C.multiply(D, mod_C.square(U))); - if(Vt.is_odd()) - Vt += C; + Vt.ct_cond_add(Vt.is_odd(), C); Vt >>= 1; Vt = mod_C.reduce(Vt); @@ -76,13 +75,11 @@ bool is_lucas_probable_prime(const BigInt& C, const Modular_Reducer& mod_C) V = Vt; U2 = mod_C.reduce(Ut + Vt); - if(U2.is_odd()) - U2 += C; + U2.ct_cond_add(U2.is_odd(), C); U2 >>= 1; V2 = mod_C.reduce(Vt + Ut*D); - if(V2.is_odd()) - V2 += C; + V2.ct_cond_add(V2.is_odd(), C); V2 >>= 1; U.ct_cond_assign(k_bit, U2); |