Botan::Montgomery_Int Class Reference

#include <monty.h>

Public Member Functions
void	_const_time_poison () const
void	_const_time_unpoison () const
const Montgomery_Params &	_params () 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	operator+ (const Montgomery_Int &other) const
Montgomery_Int	operator- (const Montgomery_Int &other) const
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 103 of file monty.h.

Constructor & Destructor Documentation

Montgomery_Int() [1/3]

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

inlineexplicit

Create a zero-initialized Montgomery_Int

Definition at line 108 of file monty.h.

: m_params(params) {}

Referenced by from_wide_int(), mul(), mul_by(), mul_by(), one(), 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 212 of file monty.cpp.

                                                                                                 :
      m_params(params), m_v(m_params.p_words()) {
   BOTAN_ASSERT_NOMSG(v < m_params.p());
 
   const size_t p_size = m_params.p_words();
 
   auto v_span = v._as_span();
 
   if(v_span.size() > p_size) {
      // Safe to truncate the span since we already checked v < p
      v_span = v_span.first(p_size);
   }
 
   BOTAN_ASSERT_NOMSG(m_v.size() >= v_span.size());
 
   copy_mem(std::span{m_v}.first(v_span.size()), v_span);
 
   if(redc_needed) {
      secure_vector<word> ws;
      this->mul_by(m_params.R2()._as_span().first(p_size), ws);
   }
}

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

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 235 of file monty.cpp.

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

References BOTAN_ARG_CHECK.

Member Function Documentation

_const_time_poison()

void Botan::Montgomery_Int::_const_time_poison ( ) const

inline

Definition at line 159 of file monty.h.

{ CT::poison(m_v); }

References Botan::CT::poison().

_const_time_unpoison()

void Botan::Montgomery_Int::_const_time_unpoison ( ) const

inline

Definition at line 161 of file monty.h.

{ CT::unpoison(m_v); }

References Botan::CT::unpoison().

_params()

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

inline

Definition at line 163 of file monty.h.

{ return m_params; }

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 206 of file monty.cpp.

                                                                                             {
   secure_vector<word> ws;
   auto redc_x = params.mul(params.redc(x, ws), params.R3(), ws);
   return Montgomery_Int(params, redc_x, false);
}

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

mul()

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

Definition at line 291 of file monty.cpp.

                                                                                             {
   BOTAN_STATE_CHECK(other.m_params == m_params);
 
   const size_t p_size = m_params.p_words();
   BOTAN_ASSERT_NOMSG(m_v.size() == p_size && other.m_v.size() == p_size);
 
   if(ws.size() < 2 * p_size) {
      ws.resize(2 * p_size);
   }
 
   secure_vector<word> z(2 * p_size);
 
   bigint_mul(z.data(), z.size(), m_v.data(), p_size, p_size, other.m_v.data(), p_size, p_size, ws.data(), ws.size());
 
   bigint_monty_redc_inplace(z.data(), m_params.p()._data(), p_size, m_params.p_dash(), ws.data(), ws.size());
   z.resize(p_size);  // truncate off high zero words
 
   return Montgomery_Int(m_params, std::move(z));
}

References Botan::bigint_monty_redc_inplace(), Botan::bigint_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 311 of file monty.cpp.

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

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 316 of file monty.cpp.

                                                                                         {
   const size_t p_size = m_params.p_words();
   BOTAN_ASSERT_NOMSG(m_v.size() == p_size && other.size() == p_size);
 
   if(ws.size() < 2 * p_size) {
      ws.resize(2 * p_size);
   }
 
   auto do_mul_by = [&](std::span<word> z) {
      bigint_mul(z.data(), z.size(), m_v.data(), p_size, p_size, other.data(), p_size, p_size, ws.data(), ws.size());
 
      bigint_monty_redc_inplace(z.data(), m_params.p()._data(), p_size, m_params.p_dash(), ws.data(), ws.size());
 
      copy_mem(m_v, z.first(p_size));
   };
 
   if(p_size <= MontgomeryUseStackLimit) {
      std::array<word, 2 * MontgomeryUseStackLimit> z{};
      do_mul_by(z);
   } else {
      secure_vector<word> z(2 * p_size);
      do_mul_by(z);
   }
 
   return (*this);
}

References Botan::bigint_monty_redc_inplace(), Botan::bigint_mul(), BOTAN_ASSERT_NOMSG, Botan::copy_mem(), and Montgomery_Int().

one()

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

static

Return the value 1 in Montgomery form

Definition at line 202 of file monty.cpp.

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

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 256 of file monty.cpp.

                                                                          {
   BOTAN_STATE_CHECK(other.m_params == m_params);
 
   const size_t p_size = m_params.p_words();
   BOTAN_ASSERT_NOMSG(m_v.size() == p_size && other.m_v.size() == p_size);
 
   secure_vector<word> z(2 * p_size);
 
   word* r = std::span{z}.first(p_size).data();
   word* t = std::span{z}.last(p_size).data();
 
   // t = this + other
   const word carry = bigint_add3(t, m_v.data(), p_size, other.m_v.data(), p_size);
 
   // Conditionally subtract r = t - p
   bigint_monty_maybe_sub(p_size, r, carry, t, m_params.p()._data());
 
   z.resize(p_size);  // truncate leaving only r
   return Montgomery_Int(m_params, std::move(z));
}

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

operator-()

Montgomery_Int Botan::Montgomery_Int::operator-

(

const Montgomery_Int &

other

)

const

Definition at line 277 of file monty.cpp.

                                                                          {
   BOTAN_STATE_CHECK(other.m_params == m_params);
 
   const size_t p_size = m_params.p_words();
   BOTAN_ASSERT_NOMSG(m_v.size() == p_size && other.m_v.size() == p_size);
 
   secure_vector<word> t(p_size);
   const word borrow = bigint_sub3(t.data(), m_v.data(), p_size, other.m_v.data(), p_size);
 
   bigint_cnd_add(borrow, t.data(), m_params.p()._data(), p_size);
 
   return Montgomery_Int(m_params, std::move(t));
}

References Botan::bigint_cnd_add(), Botan::bigint_sub3(), 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 143 of file monty.h.

{ return m_v; }

serialize()

std::vector< uint8_t > Botan::Montgomery_Int::serialize

(

)

const

Definition at line 240 of file monty.cpp.

                                                   {
   return value().serialize();
}

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

square()

Montgomery_Int Botan::Montgomery_Int::square

(

secure_vector< word > &

ws

)

const

Definition at line 372 of file monty.cpp.

                                                                   {
   auto z = (*this);
   z.square_this_n_times(ws, 1);
   return z;
}

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 343 of file monty.cpp.

                                                                                     {
   const size_t p_size = m_params.p_words();
   BOTAN_ASSERT_NOMSG(m_v.size() == p_size);
 
   if(ws.size() < 2 * p_size) {
      ws.resize(2 * p_size);
   }
 
   auto do_sqr_n = [&](std::span<word> z) {
      for(size_t i = 0; i != n; ++i) {
         bigint_sqr(z.data(), 2 * p_size, m_v.data(), p_size, p_size, ws.data(), ws.size());
 
         bigint_monty_redc_inplace(z.data(), m_params.p()._data(), p_size, m_params.p_dash(), ws.data(), ws.size());
 
         copy_mem(m_v, std::span{z}.first(p_size));
      }
   };
 
   if(p_size <= MontgomeryUseStackLimit) {
      std::array<word, 2 * MontgomeryUseStackLimit> z{};
      do_sqr_n(z);
   } else {
      secure_vector<word> z(2 * p_size);
      do_sqr_n(z);
   }
 
   return (*this);
}

References Botan::bigint_monty_redc_inplace(), Botan::bigint_sqr(), BOTAN_ASSERT_NOMSG, Botan::copy_mem(), 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 244 of file monty.cpp.

                                   {
   secure_vector<word> ws(m_params.p_words());
 
   secure_vector<word> z = m_v;
   z.resize(2 * m_params.p_words());  // zero extend
 
   bigint_monty_redc_inplace(
      z.data(), m_params.p()._data(), m_params.p_words(), m_params.p_dash(), ws.data(), ws.size());
 
   return BigInt::_from_words(z);
}

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

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

---

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

• src/lib/math/numbertheory/monty.h
• src/lib/math/numbertheory/monty.cpp