Botan 2.19.5 Crypto and TLS for C&

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 BigInt & | get_modulus () const
bool | initialized () const
| Modular_Reducer ()
| Modular_Reducer (const BigInt &mod)
BigInt | multiply (const BigInt &x, const BigInt &y) 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 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.

19 {
20 if(mod < 0)
21 throw Invalid_Argument("Modular_Reducer: modulus must be positive");
22
23 // Left uninitialized if mod == 0
24 m_mod_words = 0;
25
26 if(mod > 0)
27 {
28 m_modulus = mod;
29 m_mod_words = m_modulus.sig_words();
30
31 // Compute mu = floor(2^{2k} / m)
32 m_mu.set_bit(2 * BOTAN_MP_WORD_BITS * m_mod_words);
33 m_mu = ct_divide(m_mu, m_modulus);
34 }
35 }
Botan::BigInt::sig_words
size_t sig_words() const
Definition: bigint.h:592
Botan::BigInt::set_bit
void set_bit(size_t n)
Definition: bigint.h:436
Botan::ct_divide
void ct_divide(const BigInt &x, const BigInt &y, BigInt &q_out, BigInt &r_out)
Definition: divide.cpp:52

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

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

References Botan::square().

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

## ◆ 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.

58{ return (m_mod_words != 0); }

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

## ◆ 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.

32 { return reduce(x * y); }
Botan::Modular_Reducer::reduce
BigInt reduce(const BigInt &x) const
Definition: reducer.cpp:37

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().

## ◆ 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 70 of file reducer.cpp.

71 {
72 if(&t1 == &x)
73 throw Invalid_State("Modular_Reducer arguments cannot alias");
74 if(m_mod_words == 0)
75 throw Invalid_State("Modular_Reducer: Never initalized");
76
77 const size_t x_sw = x.sig_words();
78
79 if(x_sw > 2*m_mod_words)
80 {
81 // too big, fall back to slow boat division
82 t1 = ct_modulo(x, m_modulus);
83 return;
84 }
85
86 t1 = x;
87 t1.set_sign(BigInt::Positive);
88 t1 >>= (BOTAN_MP_WORD_BITS * (m_mod_words - 1));
89
90 t1.mul(m_mu, ws);
91 t1 >>= (BOTAN_MP_WORD_BITS * (m_mod_words + 1));
92
93 // TODO add masked mul to avoid computing high bits
94 t1.mul(m_modulus, ws);
95 t1.mask_bits(BOTAN_MP_WORD_BITS * (m_mod_words + 1));
96
97 t1.rev_sub(x.data(), std::min(x_sw, m_mod_words + 1), ws);
98
99 /*
100 * If t1 < 0 then we must add b^(k+1) where b = 2^w. To avoid a
101 * side channel perform the addition unconditionally, with ws set
102 * to either b^(k+1) or else 0.
103 */
104 const word t1_neg = t1.is_negative();
105
106 if(ws.size() < m_mod_words + 2)
107 ws.resize(m_mod_words + 2);
108 clear_mem(ws.data(), ws.size());
109 ws[m_mod_words + 1] = t1_neg;
110
111 t1.add(ws.data(), m_mod_words + 2, BigInt::Positive);
112
113 // Per HAC this step requires at most 2 subtractions
114 t1.ct_reduce_below(m_modulus, ws, 2);
115
116 cnd_rev_sub(t1.is_nonzero() && x.is_negative(), t1, m_modulus.data(), m_modulus.size(), ws);
117 }
Botan::BigInt::size
size_t size() const
Definition: bigint.h:586
Botan::BigInt::data
const word * data() const
Definition: bigint.h:626
Botan::BigInt::Positive
@ Positive
Definition: bigint.h:35
Botan::clear_mem
void clear_mem(T *ptr, size_t n)
Definition: mem_ops.h:115
Botan::ct_modulo
BigInt ct_modulo(const BigInt &x, const BigInt &y)
Definition: divide.cpp:118

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().

## ◆ reduce() [2/2]

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

Definition at line 37 of file reducer.cpp.

38 {
39 BigInt r;
40 secure_vector<word> ws;
41 reduce(r, x, ws);
42 return r;
43 }

References reduce().

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(), 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 39 of file reducer.h.

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

References Botan::square().

Referenced by Botan::Blinder::blind(), Botan::is_lucas_probable_prime(), Botan::Montgomery_Params::Montgomery_Params(), Botan::passes_miller_rabin_test(), Botan::power_mod(), Botan::ressol(), 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