#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	reduce (const BigInt &x) const

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

BigInt	square (const BigInt &x) const

Detailed Description

Modular Reducer (using Barrett's technique)

Definition at line 18 of file reducer.h.

Constructor & Destructor Documentation

◆ Modular_Reducer() [1/2]

Botan::Modular_Reducer::Modular_Reducer ( )

inline

Definition at line 60 of file reducer.h.

60 { m_mod_words = 0; }

◆ Modular_Reducer() [2/2]

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

explicit

Definition at line 18 of file reducer.cpp.

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

    {
    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);
       }
    }

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 47 of file reducer.h.

References Botan::square().

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

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

Botan::Modular_Reducer::square

BigInt square(const BigInt &x) const

Definition: reducer.h:39

Botan::Modular_Reducer::multiply

BigInt multiply(const BigInt &x, const BigInt &y) const

Definition: reducer.h:31

◆ get_modulus()

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

inline

Definition at line 21 of file reducer.h.

21 { return m_modulus; }

◆ initialized()

bool Botan::Modular_Reducer::initialized ( ) const

inline

Definition at line 58 of file reducer.h.

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

58 { return (m_mod_words != 0); }

◆ multiply()

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 31 of file reducer.h.

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

32 { return reduce(x * y); }

Botan::Modular_Reducer::reduce

BigInt reduce(const BigInt &x) const

Definition: reducer.cpp:37

◆ reduce() [1/2]

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

Definition at line 37 of file reducer.cpp.

Referenced by Botan::DL_Group::DL_Group(), Botan::generate_dsa_primes(), Botan::is_lucas_probable_prime(), Botan::Montgomery_Params::Montgomery_Params(), Botan::PointGFp_Base_Point_Precompute::mul(), Botan::power_mod(), and Botan::EC_Group::verify_group().

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

◆ reduce() [2/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 70 of file reducer.cpp.

References Botan::BigInt::add(), Botan::clear_mem(), Botan::ct_modulo(), Botan::BigInt::ct_reduce_below(), Botan::BigInt::data(), 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().

    {
    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);
    }