7#include <botan/internal/barrett.h>
9#include <botan/internal/ct_utils.h>
10#include <botan/internal/divide.h>
11#include <botan/internal/mp_core.h>
15Barrett_Reduction::Barrett_Reduction(
const BigInt& m,
BigInt mu,
size_t mw) :
16 m_modulus(m), m_mu(std::move(mu)), m_mod_words(mw), m_modulus_bits(m.bits()) {
18 m_modulus.grow_to(m_mod_words + 8);
19 m_mu.grow_to(m_mod_words + 8);
30 return Barrett_Reduction(mod,
ct_divide_pow2k(mu_bits, mod), mod_words);
65 if(ws.size() < 2 * (mod_words + 2)) {
66 ws.resize(2 * (mod_words + 2));
82 secure_vector<word> r(2 * mu_words + 2);
84 copy_mem(r.data(), x_words.data() + (mod_words - 1), mod_words + 1);
90 const size_t q2_size = 2 * mu_words + 2;
92 secure_vector<word> q2(q2_size);
95 q2.data(), q2.size(), r.data(), r.size(), mod_words + 1, mu.
_data(), mu.
size(), mu_words, ws.data(), ws.size());
102 q2.size() - (mod_words + 1),
112 clear_mem(std::span{r}.subspan(mod_words + 1));
117 const int32_t relative_size =
bigint_cmp(r.data(), mod_words + 1, x_words.data(), mod_words + 1);
119 bigint_sub_abs(r.data(), r.data(), x_words.data(), mod_words + 1, ws.data());
127 for(
size_t i = 0; i != mod_words + 1; ++i) {
130 ws[mod_words + 1] =
word_sub(
static_cast<word>(1), r[mod_words + 1], &borrow);
133 CT::Mask<word>::is_equal(
static_cast<word>(relative_size), 1).select_n(r.data(), ws.data(), r.data(), mod_words + 2);
138 const size_t bound = 2;
141 for(
size_t i = 0; i != bound; ++i) {
142 borrow =
bigint_sub3(ws.data(), r.data(), mod_words + 1, modulus.
_data(), mod_words);
143 CT::Mask<word>::is_zero(borrow).select_n(r.data(), ws.data(), r.data(), mod_words + 1);
149 CT::unpoison(x_words);
151 return BigInt::_from_words(r);
154CT::Choice acceptable_barrett_input(
const BigInt& x,
const BigInt& modulus) {
155 auto x_is_positive = CT::Choice::from_int(
static_cast<uint32_t
>(x.is_positive()));
156 auto x_lt_mod =
bigint_ct_is_lt(x._data(), x.size(), modulus._data(), modulus.sig_words()).as_choice();
157 return x_is_positive && x_lt_mod;
163 BOTAN_ARG_CHECK(acceptable_barrett_input(x, m_modulus).as_bool(),
"Invalid x param for Barrett multiply");
164 BOTAN_ARG_CHECK(acceptable_barrett_input(y, m_modulus).as_bool(),
"Invalid y param for Barrett multiply");
173 std::min(x.
size(), m_mod_words),
176 std::min(y.
size(), m_mod_words),
180 return barrett_reduce(m_mod_words, m_modulus, m_mu, xy, ws);
184 BOTAN_ARG_CHECK(acceptable_barrett_input(x, m_modulus).as_bool(),
"Invalid x param for Barrett square");
191 return barrett_reduce(m_mod_words, m_modulus, m_mu, x2, ws);
198 BOTAN_ARG_CHECK(x_sw <= 2 * m_mod_words,
"Argument is too large for Barrett reduction");
203 return barrett_reduce(m_mod_words, m_modulus, m_mu, x.
_as_span(), ws);
#define BOTAN_ASSERT_NOMSG(expr)
#define BOTAN_ARG_CHECK(expr, msg)
static Barrett_Reduction for_public_modulus(const BigInt &m)
static Barrett_Reduction for_secret_modulus(const BigInt &m)
BigInt reduce(const BigInt &x) const
BigInt multiply(const BigInt &x, const BigInt &y) const
BigInt square(const BigInt &x) const
void grow_to(size_t n) const
static BigInt power_of_2(size_t n)
const word * _data() const
std::span< const word > _as_span() const
constexpr auto word_sub(W x, W y, W *carry) -> W
void bigint_sqr(word z[], size_t z_size, const word x[], size_t x_size, size_t x_sw, word workspace[], size_t ws_size)
constexpr auto bigint_sub3(W z[], const W x[], size_t x_size, const W y[], size_t y_size) -> W
void bigint_mul(word z[], size_t z_size, const word x[], size_t x_size, size_t x_sw, const word y[], size_t y_size, size_t y_sw, word workspace[], size_t ws_size)
constexpr int32_t bigint_cmp(const W x[], size_t x_size, const W y[], size_t y_size)
BigInt ct_divide_pow2k(size_t k, const BigInt &y)
constexpr auto bigint_sub_abs(W z[], const W x[], const W y[], size_t N, W ws[]) -> CT::Mask< W >
constexpr auto bigint_ct_is_lt(const W x[], size_t x_size, const W y[], size_t y_size, bool lt_or_equal=false) -> CT::Mask< W >
std::vector< T, secure_allocator< T > > secure_vector
std::conditional_t< HasNative64BitRegisters, std::uint64_t, uint32_t > word