7#include <botan/internal/monty.h>
9#include <botan/exceptn.h>
10#include <botan/mem_ops.h>
11#include <botan/internal/barrett.h>
12#include <botan/internal/bit_ops.h>
13#include <botan/internal/ct_utils.h>
14#include <botan/internal/mp_core.h>
23constexpr size_t MontgomeryUseStackLimit = 32;
31bool ranges_overlap(
const word* a,
size_t na,
const word* b,
size_t nb) {
32 if(na == 0 || nb == 0) {
35 const std::less<const word*> lt;
36 return lt(a, b + nb) && lt(b, a + na);
43 throw Invalid_Argument(
"Montgomery_Params invalid modulus");
47 m_p_bits = m_p.bits();
48 m_p_words = m_p.sig_words();
53 (mod_p.mu() >> (2 * WordInfo<word>::bits * m_p_words - (m_p_bits - 1 + WordInfo<word>::bits))).word_at(0);
57 m_r1 = mod_p.reduce(r);
58 m_r2 = mod_p.square(m_r1);
59 m_r3 = mod_p.multiply(m_r1, m_r2);
68 m_data(std::make_shared<Data>(
p, mod_p)) {}
74 if(this->m_data == other.m_data) {
78 return (this->m_data->p() == other.m_data->p());
82 const size_t p_size = this->
p_words();
84 if(ws.size() < p_size) {
97 const size_t p_size = this->
p_words();
99 this->
mul(z, x, y, ws);
104 BOTAN_ARG_CHECK(&z != &x && &z != &y,
"Montgomery_Params::mul output must not alias inputs");
106 const size_t p_size = this->
p_words();
108 if(ws.size() < 2 * p_size) {
109 ws.resize(2 * p_size);
115 if(z.
size() < 2 * p_size) {
123 std::min(p_size, x.
size()),
126 std::min(p_size, y.
size()),
134 BOTAN_ARG_CHECK(&z != &x,
"Montgomery_Params::mul output must not alias x");
136 "Montgomery_Params::mul output must not overlap y");
138 const size_t p_size = this->
p_words();
140 if(ws.size() < 2 * p_size) {
141 ws.resize(2 * p_size);
143 if(z.
size() < 2 * p_size) {
153 std::min(p_size, x.
size()),
156 std::min(p_size, y.size()),
164 const size_t p_size = this->
p_words();
166 if(ws.size() < 4 * p_size) {
167 ws.resize(4 * p_size);
170 word* z_data = ws.data();
171 word* ws_data = &ws[2 * p_size];
179 std::min(p_size, x.
size()),
182 std::min(p_size, y.
size()),
188 if(x.
size() < 2 * p_size) {
200 const size_t p_size = this->
p_words();
207 BOTAN_ARG_CHECK(&z != &x,
"Montgomery_Params::sqr output must not alias input");
213 "Montgomery_Params::sqr output must not overlap input");
215 const size_t p_size = this->
p_words();
217 if(ws.size() < 2 * p_size) {
218 ws.resize(2 * p_size);
221 if(z.
size() < 2 * p_size) {
233 m_params(params), m_v(std::move(words)) {
243 const auto redc_x = params.
mul(params.
redc(x, ws), params.
R3(), ws);
248 m_params(params), m_v(m_params.p_words()) {
251 const size_t p_size = m_params.p_words();
255 if(v_span.size() > p_size) {
257 v_span = v_span.first(p_size);
262 copy_mem(std::span{m_v}.first(v_span.size()), v_span);
266 this->
mul_by(m_params.R2()._as_span().first(p_size), ws);
271 m_params(params), m_v(words.begin(), words.end()) {
272 BOTAN_ARG_CHECK(m_v.size() == m_params.p_words(),
"Invalid input span");
283 z.resize(2 * m_params.p_words());
286 z.data(), m_params.p()._data(), m_params.p_words(), m_params.p_dash(), ws.data(), ws.size());
294 const size_t p_size = m_params.p_words();
299 word* r = std::span{z}.first(p_size).data();
300 word* t = std::span{z}.last(p_size).data();
303 const word carry =
bigint_add3(t, m_v.data(), p_size, other.m_v.data(), p_size);
315 const size_t p_size = m_params.p_words();
319 const word borrow =
bigint_sub3(t.data(), m_v.data(), p_size, other.m_v.data(), p_size);
329 const size_t p_size = m_params.p_words();
332 if(ws.size() < 4 * p_size) {
333 ws.resize(4 * p_size);
339 z.data(), m_v.data(), other.m_v.data(), m_params.p()._data(), p_size, m_params.p_dash(), ws.data(), ws.size());
346 return this->
mul_by(std::span{other.m_v}, ws);
350 const size_t p_size = m_params.p_words();
353 if(ws.size() < 4 * p_size) {
354 ws.resize(4 * p_size);
358 m_v.data(), m_v.data(), other.data(), m_params.p()._data(), p_size, m_params.p_dash(), ws.data(), ws.size());
364 const size_t p_size = m_params.p_words();
367 if(ws.size() < 4 * p_size) {
368 ws.resize(4 * p_size);
371 for(
size_t i = 0; i != n; ++i) {
372 bigint_monty_sqr(m_v.data(), m_v.data(), m_params.p()._data(), p_size, m_params.p_dash(), ws.data(), ws.size());
378void Montgomery_Int::add_mod_p(std::span<const word> other) {
379 const size_t p_size = m_params.
p_words();
382 const auto do_add = [&](std::span<word> t) {
383 const word carry =
bigint_add3(t.data(), m_v.data(), p_size, other.data(), p_size);
387 if(p_size <= MontgomeryUseStackLimit) {
388 std::array<word, MontgomeryUseStackLimit> t{};
389 do_add(std::span{t}.first(p_size));
398 this->add_mod_p(other.m_v);
405 const size_t p_size = m_params.p_words();
408 const word borrow =
bigint_sub2(m_v.data(), p_size, other.m_v.data(), p_size);
419 const size_t p_size = m_params.p_words();
422 const word* p = m_params.p()._data();
424 const auto do_mul = [&](std::span<word> t) {
433 const size_t pos = m_params.p_bits() - 2;
434 const size_t pos_word = pos / WB;
435 const size_t pos_bit = pos % WB;
436 const word T = (t[pos_word] >> pos_bit) | ((t[pos_word + 1] << 1) << (WB - 1 - pos_bit));
447 if(p_size <= MontgomeryUseStackLimit) {
448 std::array<word, MontgomeryUseStackLimit + 1> t{};
449 do_mul(std::span{t}.first(p_size + 1));
459 const size_t p_size = m_params.p_words();
464 const word carry =
bigint_cnd_add(m_v[0] & 1, m_v.data(), m_params.p()._data(), p_size);
466 for(
size_t i = 0; i != p_size - 1; ++i) {
467 m_v[i] = (m_v[i] >> 1) | (m_v[i + 1] << (WB - 1));
469 m_v[p_size - 1] = (m_v[p_size - 1] >> 1) | (carry << (WB - 1));
475 const size_t p_size = m_params.p_words();
481 const auto do_negate = [&](std::span<word> t) {
482 bigint_sub3(t.data(), m_params.p()._data(), p_size, m_v.data(), p_size);
483 negate.select_n(m_v.data(), t.data(), m_v.data(), p_size);
486 if(p_size <= MontgomeryUseStackLimit) {
487 std::array<word, MontgomeryUseStackLimit> t{};
488 do_negate(std::span{t}.first(p_size));
#define BOTAN_ASSERT_NOMSG(expr)
#define BOTAN_DEBUG_ASSERT(expr)
#define BOTAN_STATE_CHECK(expr)
#define BOTAN_ARG_CHECK(expr, msg)
void grow_to(size_t n) const
static BigInt _from_words(secure_vector< word > &words)
static BigInt power_of_2(size_t n)
const word * _data() const
T serialize(size_t len) const
static BigInt with_capacity(size_t n)
std::span< const word > _as_span() const
static constexpr Mask< T > expand(T v)
static constexpr Mask< T > expand_bool(bool v)
static Montgomery_Int from_wide_int(const Montgomery_Params ¶ms, const BigInt &x)
Montgomery_Int & operator+=(const Montgomery_Int &other)
Montgomery_Int & operator-=(const Montgomery_Int &other)
Montgomery_Int square(secure_vector< word > &ws) const
void ct_cond_assign(bool predicate, const Montgomery_Int &other)
static Montgomery_Int one(const Montgomery_Params ¶ms)
Montgomery_Int operator-(const Montgomery_Int &other) const
Montgomery_Int(const Montgomery_Params ¶ms)
Montgomery_Int operator+(const Montgomery_Int &other) const
void ct_cond_negate(bool predicate)
Montgomery_Int & square_this_n_times(secure_vector< word > &ws, size_t n)
Montgomery_Int & mul_by_word(word d)
Montgomery_Int mul(const Montgomery_Int &other, secure_vector< word > &ws) const
Montgomery_Int & mul_by(const Montgomery_Int &other, secure_vector< word > &ws)
std::vector< uint8_t > serialize() const
BigInt redc(const BigInt &x, secure_vector< word > &ws) const
BigInt sqr(const BigInt &x, secure_vector< word > &ws) const
void mul(BigInt &z, const BigInt &x, const BigInt &y, secure_vector< word > &ws) const
bool operator==(const Montgomery_Params &other) const
void mul_by(BigInt &x, const BigInt &y, secure_vector< word > &ws) const
Montgomery_Params(const BigInt &p, const Barrett_Reduction &mod_p)
const BigInt & R3() const
const BigInt & R1() const
constexpr decltype(auto) driveby_unpoison(T &&v)
constexpr CT::Mask< T > all_zeros(const T elem[], size_t len)
constexpr Mask< T > conditional_assign_mem(T cnd, T *dest, const T *src, size_t elems)
constexpr void bigint_linmul3(W z[], const W x[], size_t x_size, W y)
BOTAN_TEST_API void bigint_monty_mul(word z[], const word x[], const word y[], const word p[], size_t p_size, word p_dash, word ws[], size_t ws_size)
constexpr auto bigint_add3(W z[], const W x[], size_t x_size, const W y[], size_t y_size) -> W
constexpr auto bigint_submul(W z[], const W y[], size_t N, W q) -> W
constexpr auto word_madd2(W a, W b, W *c) -> 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
constexpr auto monty_inverse(W a) -> 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 void copy_mem(T *out, const T *in, size_t n)
void bigint_monty_redc_inplace(word z[], const word p[], size_t p_size, word p_dash, word ws[], size_t ws_size)
constexpr W bigint_cnd_add(W cnd, W x[], const W y[], size_t size)
constexpr void bigint_monty_maybe_sub(size_t N, W z[], W x0, const W x[], const W p[])
BOTAN_TEST_API void bigint_monty_sqr(word z[], const word x[], const word p[], size_t p_size, word p_dash, word ws[], size_t ws_size)
std::vector< T, secure_allocator< T > > secure_vector
constexpr auto bigint_sub2(W x[], size_t x_size, const W y[], size_t y_size) -> W
std::conditional_t< HasNative64BitRegisters, std::uint64_t, uint32_t > word
The native machine word, used as the limb type for multiprecision integers.