Botan::Modular_Reducer Class Reference

#include <reducer.h>

Public Member Functions
BigInt	cube (const BigInt &x) const
const BigInt &	get_modulus () const
bool	initialized () const
	Modular_Reducer ()
	Modular_Reducer (const BigInt &mod)
BigInt	multiply (const BigInt &x, const BigInt &y) const
BigInt	multiply (const BigInt &x, const BigInt &y, const BigInt &z) const
void	reduce (BigInt &out, const BigInt &x, secure_vector< word > &ws) const
BigInt	reduce (const BigInt &x) const
BigInt	square (const BigInt &x) const

Detailed Description

Modular Reducer (using Barrett's technique)

Definition at line 20 of file reducer.h.

Constructor & Destructor Documentation

Modular_Reducer() [1/2]

Botan::Modular_Reducer::Modular_Reducer ( )

inline

Definition at line 64 of file reducer.h.

{ m_mod_words = 0; }

Modular_Reducer() [2/2]

Botan::Modular_Reducer::Modular_Reducer ( const BigInt & mod )

explicit

Definition at line 19 of file reducer.cpp.

                                                  {
   if(mod < 0) {
      throw Invalid_Argument("Modular_Reducer: modulus must be positive");
   }
 
   // Left uninitialized if mod == 0
   m_mod_words = 0;
 
   if(mod > 0) {
      m_modulus = mod;
      m_mod_words = m_modulus.sig_words();
 
      // Compute mu = floor(2^{2k} / m)
      m_mu.set_bit(2 * BOTAN_MP_WORD_BITS * m_mod_words);
      m_mu = ct_divide(m_mu, m_modulus);
   }
}

References BOTAN_MP_WORD_BITS, Botan::ct_divide(), Botan::BigInt::set_bit(), and Botan::BigInt::sig_words().

Member Function Documentation

cube()

BigInt Botan::Modular_Reducer::cube ( const BigInt & x ) const

inline

Cube mod p

Parameters

x	the value to cube

Returns

(x * x * x) % p

Definition at line 52 of file reducer.h.

{ return multiply(x, this->square(x)); }

References Botan::square().

Referenced by Botan::EC_Group::verify_group().

get_modulus()

const BigInt & Botan::Modular_Reducer::get_modulus ( ) const

inline

Definition at line 22 of file reducer.h.

{ return m_modulus; }

Referenced by Botan::EC_Point_Base_Point_Precompute::EC_Point_Base_Point_Precompute().

initialized()

bool Botan::Modular_Reducer::initialized ( ) const

inline

Definition at line 62 of file reducer.h.

{ return (m_mod_words != 0); }

Referenced by Botan::Blinder::blind(), and Botan::Blinder::unblind().

multiply() [1/2]

BigInt Botan::Modular_Reducer::multiply ( const BigInt & x, const BigInt & y ) const

inline

Multiply mod p

Parameters

x	the first operand
y	the second operand

Returns

(x * y) % p

Definition at line 32 of file reducer.h.

{ return reduce(x * y); }

References Botan::reduce().

Referenced by Botan::Blinder::blind(), botan_mp_mod_mul(), Botan::is_lucas_probable_prime(), Botan::Montgomery_Params::Montgomery_Params(), Botan::Montgomery_Params::Montgomery_Params(), Botan::EC_Group_Data::multiply_mod_order(), Botan::EC_Group_Data::multiply_mod_order(), Botan::power_mod(), Botan::sqrt_modulo_prime(), Botan::Blinder::unblind(), and Botan::EC_Group::verify_group().

multiply() [2/2]

BigInt Botan::Modular_Reducer::multiply ( const BigInt & x, const BigInt & y, const BigInt & z ) const

inline

Multiply mod p

Returns

(x * y * z) % p

Definition at line 38 of file reducer.h.

{ return multiply(x, multiply(y, z)); }

References multiply().

Referenced by multiply().

reduce() [1/2]

void Botan::Modular_Reducer::reduce	(	BigInt &	out,
		const BigInt &	x,
		secure_vector< word > &	ws ) const

Low level reduction function. Mostly for internal use. Sometimes useful for performance by reducing temporaries Reduce x mod p and place the output in out. ** X and out must not reference each other ** ws is a temporary workspace.

Definition at line 69 of file reducer.cpp.

                                                                                       {
   if(&t1 == &x) {
      throw Invalid_State("Modular_Reducer arguments cannot alias");
   }
   if(m_mod_words == 0) {
      throw Invalid_State("Modular_Reducer: Never initalized");
   }
 
   const size_t x_sw = x.sig_words();
 
   if(x_sw > 2 * m_mod_words) {
      // too big, fall back to slow boat division
      t1 = ct_modulo(x, m_modulus);
      return;
   }
 
   t1 = x;
   t1.set_sign(BigInt::Positive);
   t1 >>= (BOTAN_MP_WORD_BITS * (m_mod_words - 1));
 
   t1.mul(m_mu, ws);
   t1 >>= (BOTAN_MP_WORD_BITS * (m_mod_words + 1));
 
   // TODO add masked mul to avoid computing high bits
   t1.mul(m_modulus, ws);
   t1.mask_bits(BOTAN_MP_WORD_BITS * (m_mod_words + 1));
 
   t1.rev_sub(x._data(), std::min(x_sw, m_mod_words + 1), ws);
 
   /*
   * If t1 < 0 then we must add b^(k+1) where b = 2^w. To avoid a
   * side channel perform the addition unconditionally, with ws set
   * to either b^(k+1) or else 0.
   */
   const word t1_neg = t1.is_negative();
 
   if(ws.size() < m_mod_words + 2) {
      ws.resize(m_mod_words + 2);
   }
   clear_mem(ws.data(), ws.size());
   ws[m_mod_words + 1] = t1_neg;
 
   t1.add(ws.data(), m_mod_words + 2, BigInt::Positive);
 
   // Per HAC this step requires at most 2 subtractions
   t1.ct_reduce_below(m_modulus, ws, 2);
 
   cnd_rev_sub(t1.is_nonzero() && x.is_negative(), t1, m_modulus._data(), m_modulus.size(), ws);
}

References Botan::BigInt::_data(), Botan::BigInt::add(), BOTAN_MP_WORD_BITS, Botan::clear_mem(), Botan::ct_modulo(), Botan::BigInt::ct_reduce_below(), Botan::BigInt::is_negative(), Botan::BigInt::is_nonzero(), Botan::BigInt::mask_bits(), Botan::BigInt::mul(), Botan::BigInt::Positive, Botan::BigInt::rev_sub(), Botan::BigInt::set_sign(), Botan::BigInt::sig_words(), and Botan::BigInt::size().

reduce() [2/2]

BigInt Botan::Modular_Reducer::reduce

(

const BigInt &

x

)

const

Definition at line 37 of file reducer.cpp.

                                                    {
   BigInt r;
   secure_vector<word> ws;
   reduce(r, x, ws);
   return r;
}

References reduce().

Referenced by Botan::DL_Group::DL_Group(), Botan::generate_dsa_primes(), Botan::is_lucas_probable_prime(), Botan::EC_Group_Data::mod_order(), Botan::Montgomery_Params::Montgomery_Params(), Botan::Montgomery_Params::Montgomery_Params(), Botan::EC_Point_Base_Point_Precompute::mul(), Botan::power_mod(), reduce(), and Botan::EC_Group::verify_group().

square()

BigInt Botan::Modular_Reducer::square ( const BigInt & x ) const

inline

Square mod p

Parameters

x	the value to square

Returns

(x * x) % p

Definition at line 45 of file reducer.h.

{ return reduce(Botan::square(x)); }

References Botan::reduce(), and Botan::square().

Referenced by Botan::Blinder::blind(), Botan::is_lucas_probable_prime(), Botan::Montgomery_Params::Montgomery_Params(), Botan::Montgomery_Params::Montgomery_Params(), Botan::passes_miller_rabin_test(), Botan::power_mod(), Botan::sqrt_modulo_prime(), Botan::EC_Group_Data::square_mod_order(), and Botan::EC_Group::verify_group().

---

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

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