Botan 3.14.1
Crypto and TLS for C&
Botan::Barrett_Reduction Class Referencefinal

#include <barrett.h>

Public Member Functions

BigInt cube (const BigInt &x) const
size_t modulus_bits () const
const BigInt & mu () const
BigInt multiply (const BigInt &x, const BigInt &y) const
BigInt reduce (const BigInt &x) const
BigInt square (const BigInt &x) const

Static Public Member Functions

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

Detailed Description

Barrett Reduction

Definition at line 17 of file barrett.h.

Member Function Documentation

◆ cube()

BigInt Botan::Barrett_Reduction::cube ( const BigInt & x) const
inline

Cube mod p

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

TODO(Botan4) remove this, last few remaining callers go away in Botan4

Definition at line 66 of file barrett.h.

66{ return this->multiply(x, this->square(x)); }
BigInt multiply(const BigInt &x, const BigInt &y) const
Definition barrett.cpp:146
BigInt square(const BigInt &x) const
Definition barrett.cpp:167

◆ for_public_modulus()

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

Setup for reduction where the modulus itself is public

Currently implemented identically to for_secret_modulus; the distinction documents the caller's intent

Requires that m > 0

Definition at line 33 of file barrett.cpp.

33 {
35}
static Barrett_Reduction for_secret_modulus(const BigInt &m)
Definition barrett.cpp:23

References for_public_modulus(), and for_secret_modulus().

Referenced by Botan::EC_Group::EC_Group(), Botan::EC_Group_Data::EC_Group_Data(), for_public_modulus(), Botan::EC_Group::register_custom_group(), Botan::sqrt_modulo_prime(), and Botan::EC_Group::verify_group().

◆ for_secret_modulus()

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

Setup for reduction where the modulus itself is secret.

Requires that m > 0

Definition at line 23 of file barrett.cpp.

23 {
24 BOTAN_ARG_CHECK(mod.signum() > 0, "Modulus must be positive");
25
26 const size_t mod_words = mod.sig_words();
27
28 // Compute mu = floor(2^{2k} / m)
29 const size_t mu_bits = 2 * WordInfo<word>::bits * mod_words;
30 return Barrett_Reduction(mod, ct_divide_pow2k(mu_bits, mod), mod_words);
31}
#define BOTAN_ARG_CHECK(expr, msg)
Definition assert.h:33
BigInt ct_divide_pow2k(size_t k, const BigInt &y)
Definition divide.cpp:194

References BOTAN_ARG_CHECK, Botan::ct_divide_pow2k(), for_secret_modulus(), Botan::BigInt::sig_words(), and Botan::BigInt::signum().

Referenced by botan_mp_mod_mul(), for_public_modulus(), for_secret_modulus(), and Botan::power_mod().

◆ modulus_bits()

size_t Botan::Barrett_Reduction::modulus_bits ( ) const
inline

Return length of the modulus in bits

Definition at line 71 of file barrett.h.

71{ return m_modulus_bits; }

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

◆ mu()

const BigInt & Botan::Barrett_Reduction::mu ( ) const
inline

Return mu = floor(2^(2*WB*k) / m), where WB is the word size in bits and k is the number of words in the modulus m

Definition at line 77 of file barrett.h.

77{ return m_mu; }

◆ multiply()

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

Multiply mod p

Parameters
xthe first operand in [0..p)
ythe second operand in [0..p)
Returns
(x * y) % p

Definition at line 146 of file barrett.cpp.

146 {
147 BOTAN_ARG_CHECK(acceptable_barrett_input(x, m_modulus).as_bool(), "Invalid x param for Barrett multiply");
148 BOTAN_ARG_CHECK(acceptable_barrett_input(y, m_modulus).as_bool(), "Invalid y param for Barrett multiply");
149
150 secure_vector<word> ws(2 * (m_mod_words + 2));
151 secure_vector<word> xy(2 * m_mod_words);
152
153 bigint_mul(xy.data(),
154 xy.size(),
155 x._data(),
156 x.size(),
157 std::min(x.size(), m_mod_words),
158 y._data(),
159 y.size(),
160 std::min(y.size(), m_mod_words),
161 ws.data(),
162 ws.size());
163
164 return barrett_reduce(m_mod_words, m_modulus, m_mu, xy, ws);
165}
void bigint_mul(word z[], size_t z_size, const word x[], size_t x_size, size_t x_sw, const word y[], size_t y_size, size_t y_sw, word workspace[], size_t ws_size)
Definition mp_karat.cpp:283
std::vector< T, secure_allocator< T > > secure_vector
Definition secmem.h:128

References Botan::BigInt::_data(), Botan::bigint_mul(), BOTAN_ARG_CHECK, multiply(), and Botan::BigInt::size().

Referenced by multiply().

◆ reduce()

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

Perform modular reduction of x

The parameter must be greater than or equal to zero, and less than 2^(2*b), where b is the bitlength of the modulus.

Definition at line 178 of file barrett.cpp.

178 {
179 BOTAN_ARG_CHECK(x.signum() >= 0, "Argument must be non-negative");
180
181 const size_t x_sw = x.sig_words();
182 BOTAN_ARG_CHECK(x_sw <= 2 * m_mod_words, "Argument is too large for Barrett reduction");
183
184 x.grow_to(2 * m_mod_words);
185
187 return barrett_reduce(m_mod_words, m_modulus, m_mu, x._as_span(), ws);
188}

References Botan::BigInt::_as_span(), BOTAN_ARG_CHECK, Botan::BigInt::grow_to(), reduce(), Botan::BigInt::sig_words(), and Botan::BigInt::signum().

Referenced by reduce().

◆ square()

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

Square mod p

Parameters
xa value to square must be in [0..p)
Returns
(x * x) % p

Definition at line 167 of file barrett.cpp.

167 {
168 BOTAN_ARG_CHECK(acceptable_barrett_input(x, m_modulus).as_bool(), "Invalid x param for Barrett square");
169
170 secure_vector<word> ws(2 * (m_mod_words + 2));
171 secure_vector<word> x2(2 * m_mod_words);
172
173 bigint_sqr(x2.data(), x2.size(), x._data(), x.size(), std::min(x.size(), m_mod_words), ws.data(), ws.size());
174
175 return barrett_reduce(m_mod_words, m_modulus, m_mu, x2, ws);
176}
void bigint_sqr(word z[], size_t z_size, const word x[], size_t x_size, size_t x_sw, word workspace[], size_t ws_size)
Definition mp_karat.cpp:327

References Botan::BigInt::_data(), Botan::bigint_sqr(), BOTAN_ARG_CHECK, Botan::BigInt::size(), and square().

Referenced by square().


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