Botan 3.14.1
Crypto and TLS for C&
Botan::Montgomery_Int Class Referencefinal

#include <monty.h>

Public Member Functions

void _const_time_poison () const
void _const_time_unpoison () const
const Montgomery_Params & _params () const
void ct_cond_assign (bool predicate, const Montgomery_Int &other)
void ct_cond_negate (bool predicate)
Montgomery_Int & div2 ()
bool is_zero () const
 Montgomery_Int (const Montgomery_Params &params)
 Montgomery_Int (const Montgomery_Params &params, const BigInt &v, bool redc_needed=true)
 Montgomery_Int (const Montgomery_Params &params, std::span< const word > words)
Montgomery_Int mul (const Montgomery_Int &other, secure_vector< word > &ws) const
Montgomery_Int & mul_by (const Montgomery_Int &other, secure_vector< word > &ws)
Montgomery_Int & mul_by (std::span< const word > other, secure_vector< word > &ws)
Montgomery_Int & mul_by_word (word d)
Montgomery_Int operator+ (const Montgomery_Int &other) const
Montgomery_Int & operator+= (const Montgomery_Int &other)
Montgomery_Int operator- (const Montgomery_Int &other) const
Montgomery_Int & operator-= (const Montgomery_Int &other)
const secure_vector< word > & repr () const
std::vector< uint8_t > serialize () const
Montgomery_Int square (secure_vector< word > &ws) const
Montgomery_Int & square_this_n_times (secure_vector< word > &ws, size_t n)
BigInt value () const

Static Public Member Functions

static Montgomery_Int from_wide_int (const Montgomery_Params &params, const BigInt &x)
static Montgomery_Int one (const Montgomery_Params &params)

Detailed Description

The Montgomery representation of an integer

Definition at line 124 of file monty.h.

Constructor & Destructor Documentation

◆ Montgomery_Int() [1/3]

Botan::Montgomery_Int::Montgomery_Int ( const Montgomery_Params & params)
explicit

Create a zero-initialized Montgomery_Int

Definition at line 230 of file monty.cpp.

230: m_params(params), m_v(m_params.p_words()) {}

Referenced by ct_cond_assign(), div2(), from_wide_int(), mul(), mul_by(), mul_by(), mul_by_word(), one(), operator+(), operator+=(), operator-(), operator-=(), square(), and square_this_n_times().

◆ Montgomery_Int() [2/3]

Botan::Montgomery_Int::Montgomery_Int ( const Montgomery_Params & params,
const BigInt & v,
bool redc_needed = true )

Create a Montgomery_Int from a BigInt

Definition at line 247 of file monty.cpp.

247 :
248 m_params(params), m_v(m_params.p_words()) {
249 BOTAN_ARG_CHECK(v.signum() >= 0 && v < m_params.p(), "Input out of range");
250
251 const size_t p_size = m_params.p_words();
252
253 auto v_span = v._as_span();
254
255 if(v_span.size() > p_size) {
256 // Safe to truncate the span since we already checked v < p
257 v_span = v_span.first(p_size);
258 }
259
260 BOTAN_ASSERT_NOMSG(m_v.size() >= v_span.size());
261
262 copy_mem(std::span{m_v}.first(v_span.size()), v_span);
263
264 if(redc_needed) {
266 this->mul_by(m_params.R2()._as_span().first(p_size), ws);
267 }
268}
#define BOTAN_ASSERT_NOMSG(expr)
Definition assert.h:82
#define BOTAN_ARG_CHECK(expr, msg)
Definition assert.h:33
Montgomery_Int & mul_by(const Montgomery_Int &other, secure_vector< word > &ws)
Definition monty.cpp:344
constexpr void copy_mem(T *out, const T *in, size_t n)
Definition mem_ops.h:144
std::vector< T, secure_allocator< T > > secure_vector
Definition secmem.h:128

References Botan::BigInt::_as_span(), BOTAN_ARG_CHECK, BOTAN_ASSERT_NOMSG, Botan::copy_mem(), mul_by(), and Botan::BigInt::signum().

◆ Montgomery_Int() [3/3]

Botan::Montgomery_Int::Montgomery_Int ( const Montgomery_Params & params,
std::span< const word > words )

Create a Montgomery_Int

The span must be exactly p_words long and encoding a value less than p already in Montgomery form

Definition at line 270 of file monty.cpp.

270 :
271 m_params(params), m_v(words.begin(), words.end()) {
272 BOTAN_ARG_CHECK(m_v.size() == m_params.p_words(), "Invalid input span");
273}

References BOTAN_ARG_CHECK.

Member Function Documentation

◆ _const_time_poison()

void Botan::Montgomery_Int::_const_time_poison ( ) const
inline

Definition at line 212 of file monty.h.

212{ CT::poison(m_v); }
constexpr void poison(const T *p, size_t n)
Definition ct_utils.h:56

References Botan::CT::poison().

◆ _const_time_unpoison()

void Botan::Montgomery_Int::_const_time_unpoison ( ) const
inline

Definition at line 214 of file monty.h.

214{ CT::unpoison(m_v); }
constexpr void unpoison(const T *p, size_t n)
Definition ct_utils.h:67

References Botan::CT::unpoison().

◆ _params()

const Montgomery_Params & Botan::Montgomery_Int::_params ( ) const
inline

Definition at line 216 of file monty.h.

216{ return m_params; }

Referenced by Botan::make_monty_exp_avx512().

◆ ct_cond_assign()

void Botan::Montgomery_Int::ct_cond_assign ( bool predicate,
const Montgomery_Int & other )

If predicate is true assign other to this, in constant time

Definition at line 495 of file monty.cpp.

495 {
496 BOTAN_STATE_CHECK(other.m_params == m_params);
497 BOTAN_ASSERT_NOMSG(m_v.size() == other.m_v.size());
498 CT::conditional_assign_mem(static_cast<word>(predicate), m_v.data(), other.m_v.data(), m_v.size());
499}
#define BOTAN_STATE_CHECK(expr)
Definition assert.h:49
constexpr Mask< T > conditional_assign_mem(T cnd, T *dest, const T *src, size_t elems)
Definition ct_utils.h:754
std::conditional_t< HasNative64BitRegisters, std::uint64_t, uint32_t > word
The native machine word, used as the limb type for multiprecision integers.
Definition types.h:131

References BOTAN_ASSERT_NOMSG, BOTAN_STATE_CHECK, Botan::CT::conditional_assign_mem(), and Montgomery_Int().

◆ ct_cond_negate()

void Botan::Montgomery_Int::ct_cond_negate ( bool predicate)

If predicate is true negate this modulo p, in constant time

Definition at line 474 of file monty.cpp.

474 {
475 const size_t p_size = m_params.p_words();
476 BOTAN_ASSERT_NOMSG(m_v.size() == p_size);
477
478 // The negation of zero is zero, not p
479 const auto negate = CT::Mask<word>::expand_bool(predicate) & ~CT::all_zeros(m_v.data(), p_size);
480
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);
484 };
485
486 if(p_size <= MontgomeryUseStackLimit) {
487 std::array<word, MontgomeryUseStackLimit> t{};
488 do_negate(std::span{t}.first(p_size));
489 } else {
490 secure_vector<word> t(p_size);
491 do_negate(t);
492 }
493}
static constexpr Mask< T > expand_bool(bool v)
Definition ct_utils.h:402
constexpr auto bigint_sub3(W z[], const W x[], size_t x_size, const W y[], size_t y_size) -> W
Definition mp_core.h:196

References Botan::bigint_sub3(), BOTAN_ASSERT_NOMSG, and Botan::CT::Mask< T >::expand_bool().

◆ div2()

Montgomery_Int & Botan::Montgomery_Int::div2 ( )

Divide by 2 modulo p

Definition at line 458 of file monty.cpp.

458 {
459 const size_t p_size = m_params.p_words();
460 BOTAN_ASSERT_NOMSG(m_v.size() == p_size);
461 constexpr size_t WB = WordInfo<word>::bits;
462
463 // If odd, add p (also odd) to make the value even; the sum is below 2p
464 const word carry = bigint_cnd_add(m_v[0] & 1, m_v.data(), m_params.p()._data(), p_size);
465
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));
468 }
469 m_v[p_size - 1] = (m_v[p_size - 1] >> 1) | (carry << (WB - 1));
470
471 return (*this);
472}
constexpr W bigint_cnd_add(W cnd, W x[], const W y[], size_t size)
Definition mp_core.h:49

References Botan::bigint_cnd_add(), BOTAN_ASSERT_NOMSG, and Montgomery_Int().

◆ from_wide_int()

Montgomery_Int Botan::Montgomery_Int::from_wide_int ( const Montgomery_Params & params,
const BigInt & x )
static

Wide reduction - input can be at most 2*bytes long

Definition at line 241 of file monty.cpp.

241 {
243 const auto redc_x = params.mul(params.redc(x, ws), params.R3(), ws);
244 return Montgomery_Int(params, redc_x, false);
245}
Montgomery_Int(const Montgomery_Params &params)
Definition monty.cpp:230

References Montgomery_Int(), Botan::Montgomery_Params::mul(), Botan::Montgomery_Params::R3(), and Botan::Montgomery_Params::redc().

◆ is_zero()

bool Botan::Montgomery_Int::is_zero ( ) const

Definition at line 501 of file monty.cpp.

501 {
502 return CT::all_zeros(m_v.data(), m_v.size()).as_bool();
503}
constexpr CT::Mask< T > all_zeros(const T elem[], size_t len)
Definition ct_utils.h:790

References Botan::CT::all_zeros().

◆ mul()

Montgomery_Int Botan::Montgomery_Int::mul ( const Montgomery_Int & other,
secure_vector< word > & ws ) const

Definition at line 326 of file monty.cpp.

326 {
327 BOTAN_STATE_CHECK(other.m_params == m_params);
328
329 const size_t p_size = m_params.p_words();
330 BOTAN_ASSERT_NOMSG(m_v.size() == p_size && other.m_v.size() == p_size);
331
332 if(ws.size() < 4 * p_size) {
333 ws.resize(4 * p_size);
334 }
335
336 secure_vector<word> z(p_size);
337
339 z.data(), m_v.data(), other.m_v.data(), m_params.p()._data(), p_size, m_params.p_dash(), ws.data(), ws.size());
340
341 return Montgomery_Int(m_params, std::move(z));
342}
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)
Definition mp_monty.cpp:143

References Botan::bigint_monty_mul(), BOTAN_ASSERT_NOMSG, BOTAN_STATE_CHECK, and Montgomery_Int().

Referenced by Botan::monty_multi_exp().

◆ mul_by() [1/2]

Montgomery_Int & Botan::Montgomery_Int::mul_by ( const Montgomery_Int & other,
secure_vector< word > & ws )

Definition at line 344 of file monty.cpp.

344 {
345 BOTAN_STATE_CHECK(other.m_params == m_params);
346 return this->mul_by(std::span{other.m_v}, ws);
347}

References BOTAN_STATE_CHECK, Montgomery_Int(), and mul_by().

Referenced by Montgomery_Int(), Botan::monty_multi_exp(), and mul_by().

◆ mul_by() [2/2]

Montgomery_Int & Botan::Montgomery_Int::mul_by ( std::span< const word > other,
secure_vector< word > & ws )

Definition at line 349 of file monty.cpp.

349 {
350 const size_t p_size = m_params.p_words();
351 BOTAN_ASSERT_NOMSG(m_v.size() == p_size && other.size() == p_size);
352
353 if(ws.size() < 4 * p_size) {
354 ws.resize(4 * p_size);
355 }
356
358 m_v.data(), m_v.data(), other.data(), m_params.p()._data(), p_size, m_params.p_dash(), ws.data(), ws.size());
359
360 return (*this);
361}

References Botan::bigint_monty_mul(), BOTAN_ASSERT_NOMSG, and Montgomery_Int().

◆ mul_by_word()

Montgomery_Int & Botan::Montgomery_Int::mul_by_word ( word d)

Multiply by an integer d (which is not in Montgomery form)

Requires 0 <= d < 2^(WB-2), where WB is the word size in bits (so d < 2^62 with 64-bit words, or d < 2^30 with 32-bit words). Larger values throw Invalid_Argument.

This is constant time with respect to the values of this, d, and p

Definition at line 414 of file monty.cpp.

414 {
415 constexpr size_t WB = WordInfo<word>::bits;
416
417 BOTAN_ARG_CHECK(!CT::Mask<word>::expand(d >> (WB - 2)).as_bool(), "Multiplier too large");
418
419 const size_t p_size = m_params.p_words();
420 BOTAN_ASSERT_NOMSG(m_v.size() == p_size);
421
422 const word* p = m_params.p()._data();
423
424 const auto do_mul = [&](std::span<word> t) {
425 // t = x*d, which is less than d*p < 2^(bits(p) - 2 + WB)
426 bigint_linmul3(t.data(), m_v.data(), p_size, d);
427
428 /*
429 * Estimate q = floor(t/p) as floor(T*mu / 2^(WB+1)), where T is the WB bits
430 * of t starting at bit bits(p) - 2 and mu = floor(2^(bits(p) - 1 + WB) / p).
431 * The estimate is never too high, and is low by at most one.
432 */
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));
437
438 word q = 0;
439 word_madd2(T, m_params.p_top_mu(), &q);
440 q >>= 1;
441
442 // Now t - q*p < 2*p
443 const word t_hi = t[p_size] - bigint_submul(t.data(), p, p_size, q);
444 bigint_monty_maybe_sub(p_size, m_v.data(), t_hi, t.data(), p);
445 };
446
447 if(p_size <= MontgomeryUseStackLimit) {
448 std::array<word, MontgomeryUseStackLimit + 1> t{};
449 do_mul(std::span{t}.first(p_size + 1));
450 } else {
451 secure_vector<word> t(p_size + 1);
452 do_mul(t);
453 }
454
455 return (*this);
456}
static constexpr Mask< T > expand(T v)
Definition ct_utils.h:397
constexpr void bigint_linmul3(W z[], const W x[], size_t x_size, W y)
Definition mp_core.h:420
constexpr auto bigint_submul(W z[], const W y[], size_t N, W q) -> W
Definition mp_core.h:443
constexpr auto word_madd2(W a, W b, W *c) -> W
Definition mp_asmi.h:111
constexpr void bigint_monty_maybe_sub(size_t N, W z[], W x0, const W x[], const W p[])
Definition mp_core.h:229

References Botan::bigint_linmul3(), Botan::bigint_monty_maybe_sub(), Botan::bigint_submul(), BOTAN_ARG_CHECK, BOTAN_ASSERT_NOMSG, Botan::CT::Mask< T >::expand(), Montgomery_Int(), and Botan::word_madd2().

◆ one()

Montgomery_Int Botan::Montgomery_Int::one ( const Montgomery_Params & params)
static

Return the value 1 in Montgomery form

Definition at line 237 of file monty.cpp.

237 {
238 return Montgomery_Int(params, params.R1(), false);
239}

References Montgomery_Int(), and Botan::Montgomery_Params::R1().

Referenced by Botan::monty_multi_exp().

◆ operator+()

Montgomery_Int Botan::Montgomery_Int::operator+ ( const Montgomery_Int & other) const

Definition at line 291 of file monty.cpp.

291 {
292 BOTAN_STATE_CHECK(other.m_params == m_params);
293
294 const size_t p_size = m_params.p_words();
295 BOTAN_ASSERT_NOMSG(m_v.size() == p_size && other.m_v.size() == p_size);
296
297 secure_vector<word> z(2 * p_size);
298
299 word* r = std::span{z}.first(p_size).data();
300 word* t = std::span{z}.last(p_size).data();
301
302 // t = this + other
303 const word carry = bigint_add3(t, m_v.data(), p_size, other.m_v.data(), p_size);
304
305 // Conditionally subtract r = t - p
306 bigint_monty_maybe_sub(p_size, r, carry, t, m_params.p()._data());
307
308 z.resize(p_size); // truncate leaving only r
309 return Montgomery_Int(m_params, std::move(z));
310}
constexpr auto bigint_add3(W z[], const W x[], size_t x_size, const W y[], size_t y_size) -> W
Definition mp_core.h:124

References Botan::bigint_add3(), Botan::bigint_monty_maybe_sub(), BOTAN_ASSERT_NOMSG, BOTAN_STATE_CHECK, and Montgomery_Int().

◆ operator+=()

Montgomery_Int & Botan::Montgomery_Int::operator+= ( const Montgomery_Int & other)

Definition at line 396 of file monty.cpp.

396 {
397 BOTAN_STATE_CHECK(other.m_params == m_params);
398 this->add_mod_p(other.m_v);
399 return (*this);
400}

References BOTAN_STATE_CHECK, and Montgomery_Int().

◆ operator-()

Montgomery_Int Botan::Montgomery_Int::operator- ( const Montgomery_Int & other) const

Definition at line 312 of file monty.cpp.

312 {
313 BOTAN_STATE_CHECK(other.m_params == m_params);
314
315 const size_t p_size = m_params.p_words();
316 BOTAN_ASSERT_NOMSG(m_v.size() == p_size && other.m_v.size() == p_size);
317
318 secure_vector<word> t(p_size);
319 const word borrow = bigint_sub3(t.data(), m_v.data(), p_size, other.m_v.data(), p_size);
320
321 bigint_cnd_add(borrow, t.data(), m_params.p()._data(), p_size);
322
323 return Montgomery_Int(m_params, std::move(t));
324}

References Botan::bigint_cnd_add(), Botan::bigint_sub3(), BOTAN_ASSERT_NOMSG, BOTAN_STATE_CHECK, and Montgomery_Int().

◆ operator-=()

Montgomery_Int & Botan::Montgomery_Int::operator-= ( const Montgomery_Int & other)

Definition at line 402 of file monty.cpp.

402 {
403 BOTAN_STATE_CHECK(other.m_params == m_params);
404
405 const size_t p_size = m_params.p_words();
406 BOTAN_ASSERT_NOMSG(m_v.size() == p_size && other.m_v.size() == p_size);
407
408 const word borrow = bigint_sub2(m_v.data(), p_size, other.m_v.data(), p_size);
409 bigint_cnd_add(borrow, m_v.data(), m_params.p()._data(), p_size);
410
411 return (*this);
412}
constexpr auto bigint_sub2(W x[], size_t x_size, const W y[], size_t y_size) -> W
Definition mp_core.h:152

References Botan::bigint_cnd_add(), Botan::bigint_sub2(), BOTAN_ASSERT_NOMSG, BOTAN_STATE_CHECK, and Montgomery_Int().

◆ repr()

const secure_vector< word > & Botan::Montgomery_Int::repr ( ) const
inline

Return the Montgomery representation

Definition at line 164 of file monty.h.

164{ return m_v; }

◆ serialize()

std::vector< uint8_t > Botan::Montgomery_Int::serialize ( ) const

Definition at line 275 of file monty.cpp.

275 {
276 return value().serialize();
277}
T serialize(size_t len) const
Definition bigint.h:790
BigInt value() const
Definition monty.cpp:279

References Botan::BigInt::serialize(), and value().

◆ square()

Montgomery_Int Botan::Montgomery_Int::square ( secure_vector< word > & ws) const

Definition at line 505 of file monty.cpp.

505 {
506 auto z = (*this);
507 z.square_this_n_times(ws, 1);
508 return z;
509}

References Montgomery_Int(), and square_this_n_times().

Referenced by Botan::monty_multi_exp().

◆ square_this_n_times()

Montgomery_Int & Botan::Montgomery_Int::square_this_n_times ( secure_vector< word > & ws,
size_t n )

Definition at line 363 of file monty.cpp.

363 {
364 const size_t p_size = m_params.p_words();
365 BOTAN_ASSERT_NOMSG(m_v.size() == p_size);
366
367 if(ws.size() < 4 * p_size) {
368 ws.resize(4 * p_size);
369 }
370
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());
373 }
374
375 return (*this);
376}
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)
Definition mp_monty.cpp:159

References Botan::bigint_monty_sqr(), BOTAN_ASSERT_NOMSG, and Montgomery_Int().

Referenced by Botan::monty_multi_exp(), and square().

◆ value()

BigInt Botan::Montgomery_Int::value ( ) const

Return the value to normal mod-p space

Definition at line 279 of file monty.cpp.

279 {
280 secure_vector<word> ws(m_params.p_words());
281
282 secure_vector<word> z = m_v;
283 z.resize(2 * m_params.p_words()); // zero extend
284
286 z.data(), m_params.p()._data(), m_params.p_words(), m_params.p_dash(), ws.data(), ws.size());
287
288 return BigInt::_from_words(z);
289}
static BigInt _from_words(secure_vector< word > &words)
Definition bigint.h:1052
void bigint_monty_redc_inplace(word z[], const word p[], size_t p_size, word p_dash, word ws[], size_t ws_size)
Definition mp_core.h:1111

References Botan::BigInt::_from_words(), and Botan::bigint_monty_redc_inplace().

Referenced by Botan::DL_Group::multi_exponentiate(), Botan::power_mod(), serialize(), and Botan::sqrt_modulo_prime().


The documentation for this class was generated from the following files: