Botan 3.7.1
Crypto and TLS for C&
Botan::Modular_Reducer Class Referencefinal

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

Static Public Member Functions

static Modular_Reducer for_public_modulus (const BigInt &m)
 
static Modular_Reducer for_secret_modulus (const BigInt &m)
 

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

67{ m_mod_words = 0; }

Referenced by for_public_modulus(), and for_secret_modulus().

◆ Modular_Reducer() [2/2]

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

Accepts m == 0 and leaves the Modular_Reducer in an uninitialized state

Definition at line 19 of file reducer.cpp.

19 {
20 if(mod < 0) {
21 throw Invalid_Argument("Modular_Reducer: modulus must be positive");
22 }
23
24 // Left uninitialized if mod == 0
25 m_mod_words = 0;
26
27 if(mod > 0) {
29 }
30}
static Modular_Reducer for_secret_modulus(const BigInt &m)
Definition reducer.cpp:32

References for_secret_modulus().

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

52{ return multiply(x, this->square(x)); }
BigInt square(const BigInt &x) const
Definition reducer.cpp:61
BigInt multiply(const BigInt &x, const BigInt &y) const
Definition reducer.h:32

References Botan::square().

◆ for_public_modulus()

Modular_Reducer Botan::Modular_Reducer::for_public_modulus ( const BigInt & m)
static

Requires that m > 0

Definition at line 43 of file reducer.cpp.

43 {
44 BOTAN_ARG_CHECK(!mod.is_zero(), "Modulus cannot be zero");
45 BOTAN_ARG_CHECK(!mod.is_negative(), "Modulus cannot be negative");
46
47 size_t mod_words = mod.sig_words();
48
49 // Compute mu = floor(2^{2k} / m)
50 const size_t mu_bits = 2 * BOTAN_MP_WORD_BITS * mod_words;
51 return Modular_Reducer(mod, BigInt::power_of_2(mu_bits) / mod, mod_words);
52}
#define BOTAN_ARG_CHECK(expr, msg)
Definition assert.h:29
static BigInt power_of_2(size_t n)
Definition bigint.h:830
#define BOTAN_MP_WORD_BITS
Definition build.h:71

References BOTAN_ARG_CHECK, BOTAN_MP_WORD_BITS, Botan::BigInt::is_negative(), Botan::BigInt::is_zero(), Modular_Reducer(), Botan::BigInt::power_of_2(), and Botan::BigInt::sig_words().

Referenced by Botan::DL_Group::DL_Group(), Botan::EC_Group::EC_Group(), Botan::FPE_FE1::FPE_FE1(), Botan::generate_dsa_primes(), Botan::sqrt_modulo_prime(), and Botan::EC_Group::verify_group().

◆ for_secret_modulus()

Modular_Reducer Botan::Modular_Reducer::for_secret_modulus ( const BigInt & m)
static

Requires that m > 0

Definition at line 32 of file reducer.cpp.

32 {
33 BOTAN_ARG_CHECK(!mod.is_zero(), "Modulus cannot be zero");
34 BOTAN_ARG_CHECK(!mod.is_negative(), "Modulus cannot be negative");
35
36 size_t mod_words = mod.sig_words();
37
38 // Compute mu = floor(2^{2k} / m)
39 const size_t mu_bits = 2 * BOTAN_MP_WORD_BITS * mod_words;
40 return Modular_Reducer(mod, ct_divide_pow2k(mu_bits, mod), mod_words);
41}
BigInt ct_divide_pow2k(size_t k, const BigInt &y)
Definition divide.cpp:80

References BOTAN_ARG_CHECK, BOTAN_MP_WORD_BITS, Botan::ct_divide_pow2k(), Botan::BigInt::is_negative(), Botan::BigInt::is_zero(), Modular_Reducer(), and Botan::BigInt::sig_words().

Referenced by botan_mp_mod_mul(), Botan::generate_rsa_prime(), Botan::is_prime(), Modular_Reducer(), Botan::Montgomery_Params::Montgomery_Params(), Botan::power_mod(), and Botan::random_prime().

◆ get_modulus()

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

Definition at line 22 of file reducer.h.

22{ 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 65 of file reducer.h.

65{ return (m_mod_words != 0); }

◆ multiply() [1/2]

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

Multiply mod p

Parameters
xthe first operand
ythe second operand
Returns
(x * y) % p

Definition at line 32 of file reducer.h.

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

References Botan::reduce().

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

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

38{ 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.

Warning
X and out must not reference each other

ws is a temporary workspace.

Definition at line 95 of file reducer.cpp.

95 {
96 if(&t1 == &x) {
97 throw Invalid_State("Modular_Reducer arguments cannot alias");
98 }
99 if(m_mod_words == 0) {
100 throw Invalid_State("Modular_Reducer: Never initalized");
101 }
102
103 const size_t x_sw = x.sig_words();
104
105 if(x_sw > 2 * m_mod_words) {
106 // too big, fall back to slow boat division
107 t1 = ct_modulo(x, m_modulus);
108 return;
109 }
110
111 t1 = x;
112 t1.set_sign(BigInt::Positive);
113 t1 >>= (BOTAN_MP_WORD_BITS * (m_mod_words - 1));
114
115 t1.mul(m_mu, ws);
116 t1 >>= (BOTAN_MP_WORD_BITS * (m_mod_words + 1));
117
118 // TODO add masked mul to avoid computing high bits
119 t1.mul(m_modulus, ws);
120 t1.mask_bits(BOTAN_MP_WORD_BITS * (m_mod_words + 1));
121
122 t1.rev_sub(x._data(), std::min(x_sw, m_mod_words + 1), ws);
123
124 /*
125 * If t1 < 0 then we must add b^(k+1) where b = 2^w. To avoid a
126 * side channel perform the addition unconditionally, with ws set
127 * to either b^(k+1) or else 0.
128 */
129 const word t1_neg = t1.is_negative();
130
131 if(ws.size() < m_mod_words + 2) {
132 ws.resize(m_mod_words + 2);
133 }
134 clear_mem(ws.data(), ws.size());
135 ws[m_mod_words + 1] = t1_neg;
136
137 t1.add(ws.data(), m_mod_words + 2, BigInt::Positive);
138
139 // Per HAC this step requires at most 2 subtractions
140 t1.ct_reduce_below(m_modulus, ws, 2);
141
142 cnd_rev_sub(t1.is_nonzero() && x.is_negative(), t1, m_modulus._data(), m_modulus.size(), ws);
143}
size_t size() const
Definition bigint.h:610
const word * _data() const
Definition bigint.h:936
BigInt ct_modulo(const BigInt &x, const BigInt &y)
Definition divide.cpp:181
constexpr void clear_mem(T *ptr, size_t n)
Definition mem_ops.h:121

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 54 of file reducer.cpp.

54 {
55 BigInt r;
57 reduce(r, x, ws);
58 return r;
59}
std::vector< T, secure_allocator< T > > secure_vector
Definition secmem.h:61

References reduce().

Referenced by Botan::is_lucas_probable_prime(), Botan::Montgomery_Params::Montgomery_Params(), Botan::EC_Point_Base_Point_Precompute::mul(), reduce(), and square().

◆ square()

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

Square mod p

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

Definition at line 61 of file reducer.cpp.

61 {
63 BigInt x2 = x;
64 x2.square(ws);
65 BigInt r;
66 reduce(r, x2, ws);
67 return r;
68}

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

Referenced by Botan::Blinder::blind(), Botan::is_lucas_probable_prime(), Botan::Montgomery_Params::Montgomery_Params(), and Botan::passes_miller_rabin_test().


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