Botan  2.8.0
Crypto and TLS for C++11
Public Member Functions | List of all members
Botan::Modular_Reducer Class Reference

#include <reducer.h>

Public Member Functions

BigInt cube (const BigInt &x) const
 
const BigIntget_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 54 of file reducer.h.

54 { m_mod_words = 0; }

◆ Modular_Reducer() [2/2]

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

Definition at line 16 of file reducer.cpp.

References Botan::BigInt::power_of_2(), Botan::BigInt::sig_words(), and Botan::square().

17  {
18  if(mod < 0)
19  throw Invalid_Argument("Modular_Reducer: modulus must be positive");
20 
21  // Left uninitialized if mod == 0
22  m_mod_words = 0;
23 
24  if(mod > 0)
25  {
26  m_modulus = mod;
27  m_mod_words = m_modulus.sig_words();
28 
29  m_modulus_2 = Botan::square(m_modulus);
30 
31  m_mu = BigInt::power_of_2(2 * BOTAN_MP_WORD_BITS * m_mod_words) / m_modulus;
32  }
33  }
BigInt square(const BigInt &x)
Definition: mp_numth.cpp:19
static BigInt power_of_2(size_t n)
Definition: bigint.h:666
size_t sig_words() const
Definition: bigint.h:537

Member Function Documentation

◆ cube()

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

Cube mod p

Parameters
xthe 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)); }
BigInt square(const BigInt &x) const
Definition: reducer.h:39
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 52 of file reducer.h.

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

52 { return (m_mod_words != 0); }

◆ multiply()

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

◆ reduce() [1/2]

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

Definition at line 35 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(), and Botan::EC_Group::verify_group().

36  {
37  BigInt r;
38  secure_vector<word> ws;
39  reduce(r, x, ws);
40  return r;
41  }
BigInt reduce(const BigInt &x) const
Definition: reducer.cpp:35

◆ reduce() [2/2]

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

Definition at line 43 of file reducer.cpp.

References Botan::BigInt::add(), Botan::clear_mem(), Botan::BigInt::cmp(), Botan::BigInt::data(), Botan::BigInt::is_negative(), Botan::BigInt::is_nonzero(), Botan::BigInt::mask_bits(), Botan::BigInt::mul(), Botan::BigInt::Positive, Botan::BigInt::reduce_below(), Botan::BigInt::rev_sub(), Botan::BigInt::set_sign(), Botan::BigInt::sig_words(), and Botan::BigInt::size().

44  {
45  if(&t1 == &x)
46  throw Invalid_State("Modular_Reducer arguments cannot alias");
47  if(m_mod_words == 0)
48  throw Invalid_State("Modular_Reducer: Never initalized");
49 
50  const size_t x_sw = x.sig_words();
51 
52  if(x_sw >= (2*m_mod_words - 1) && x.cmp(m_modulus_2, false) >= 0)
53  {
54  // too big, fall back to normal division
55  t1 = x % m_modulus;
56  return;
57  }
58 
59  t1 = x;
61  t1 >>= (BOTAN_MP_WORD_BITS * (m_mod_words - 1));
62 
63  t1.mul(m_mu, ws);
64  t1 >>= (BOTAN_MP_WORD_BITS * (m_mod_words + 1));
65 
66  // TODO add masked mul to avoid computing high bits
67  t1.mul(m_modulus, ws);
68  t1.mask_bits(BOTAN_MP_WORD_BITS * (m_mod_words + 1));
69 
70  t1.rev_sub(x.data(), std::min(x_sw, m_mod_words + 1), ws);
71 
72  /*
73  * If t1 < 0 then we must add b^(k+1) where b = 2^w. To avoid a
74  * side channel perform the addition unconditionally, with ws set
75  * to either b^(k+1) or else 0.
76  */
77  const word t1_neg = t1.is_negative();
78 
79  if(ws.size() < m_mod_words + 2)
80  ws.resize(m_mod_words + 2);
81  clear_mem(ws.data(), ws.size());
82  ws[m_mod_words + 1] = t1_neg;
83 
84  t1.add(ws.data(), m_mod_words + 2, BigInt::Positive);
85 
86  t1.reduce_below(m_modulus, ws);
87 
88  if(x.is_negative() && t1.is_nonzero())
89  {
90  t1.rev_sub(m_modulus.data(), m_modulus.size(), ws);
91  }
92  }
void clear_mem(T *ptr, size_t n)
Definition: mem_ops.h:97
const word * data() const
Definition: bigint.h:569
size_t size() const
Definition: bigint.h:531
void set_sign(Sign sign)
Definition: bigint.h:514

◆ square()

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

Square mod p

Parameters
xthe value to square
Returns
(x * x) % p

Definition at line 39 of file reducer.h.

References Botan::square().

Referenced by Botan::Blinder::blind(), Botan::Fixed_Window_Exponentiator::execute(), Botan::is_lucas_probable_prime(), Botan::Montgomery_Params::Montgomery_Params(), Botan::passes_miller_rabin_test(), Botan::ressol(), and Botan::EC_Group::verify_group().

40  { return reduce(Botan::square(x)); }
BigInt square(const BigInt &x)
Definition: mp_numth.cpp:19
BigInt reduce(const BigInt &x) const
Definition: reducer.cpp:35

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