Botan  2.13.0
Crypto and TLS for C++11
Public Member Functions | List of all members
Botan::Montgomery_Params Class Referencefinal

#include <monty.h>

Public Member Functions

BigInt inv_mod_p (const BigInt &x) const
 
 Montgomery_Params (const BigInt &p, const Modular_Reducer &mod_p)
 
 Montgomery_Params (const BigInt &p)
 
BigInt mul (const BigInt &x, const BigInt &y, secure_vector< word > &ws) const
 
BigInt mul (const BigInt &x, const secure_vector< word > &y, secure_vector< word > &ws) const
 
void mul_by (BigInt &x, const secure_vector< word > &y, secure_vector< word > &ws) const
 
void mul_by (BigInt &x, const BigInt &y, secure_vector< word > &ws) const
 
const BigIntp () const
 
word p_dash () const
 
size_t p_words () const
 
const BigIntR1 () const
 
const BigIntR2 () const
 
const BigIntR3 () const
 
BigInt redc (const BigInt &x, secure_vector< word > &ws) const
 
BigInt sqr (const BigInt &x, secure_vector< word > &ws) const
 
void square_this (BigInt &x, secure_vector< word > &ws) const
 

Detailed Description

Parameters for Montgomery Reduction

Definition at line 129 of file monty.h.

Constructor & Destructor Documentation

◆ Montgomery_Params() [1/2]

Botan::Montgomery_Params::Montgomery_Params ( const BigInt p,
const Modular_Reducer mod_p 
)

Initialize a set of Montgomery reduction parameters. These values can be shared by all values in a specific Montgomery domain.

Definition at line 13 of file monty.cpp.

References Botan::BigInt::is_even(), Botan::monty_inverse(), Botan::Modular_Reducer::multiply(), p(), Botan::BigInt::power_of_2(), Botan::Modular_Reducer::reduce(), Botan::BigInt::sig_words(), Botan::Modular_Reducer::square(), and Botan::BigInt::word_at().

15  {
16  if(p.is_even() || p < 3)
17  throw Invalid_Argument("Montgomery_Params invalid modulus");
18 
19  m_p = p;
20  m_p_words = m_p.sig_words();
21  m_p_dash = monty_inverse(m_p.word_at(0));
22 
23  const BigInt r = BigInt::power_of_2(m_p_words * BOTAN_MP_WORD_BITS);
24 
25  m_r1 = mod_p.reduce(r);
26  m_r2 = mod_p.square(m_r1);
27  m_r3 = mod_p.multiply(m_r1, m_r2);
28  }
const BigInt & p() const
Definition: monty.h:144
bool is_even() const
Definition: bigint.h:401
word word_at(size_t n) const
Definition: bigint.h:506
static BigInt power_of_2(size_t n)
Definition: bigint.h:751
BigInt & square(secure_vector< word > &ws)
Definition: big_ops2.cpp:216
size_t sig_words() const
Definition: bigint.h:584
word monty_inverse(word a)
Definition: numthry.cpp:419

◆ Montgomery_Params() [2/2]

Botan::Montgomery_Params::Montgomery_Params ( const BigInt p)

Initialize a set of Montgomery reduction parameters. These values can be shared by all values in a specific Montgomery domain.

Definition at line 30 of file monty.cpp.

References Botan::BigInt::is_even(), Botan::BigInt::is_negative(), Botan::monty_inverse(), Botan::Modular_Reducer::multiply(), p(), Botan::BigInt::power_of_2(), Botan::Modular_Reducer::reduce(), Botan::BigInt::sig_words(), Botan::Modular_Reducer::square(), and Botan::BigInt::word_at().

31  {
32 
33  if(p.is_negative() || p.is_even())
34  throw Invalid_Argument("Montgomery_Params invalid modulus");
35 
36  m_p = p;
37  m_p_words = m_p.sig_words();
38  m_p_dash = monty_inverse(m_p.word_at(0));
39 
40  const BigInt r = BigInt::power_of_2(m_p_words * BOTAN_MP_WORD_BITS);
41 
42  // It might be faster to use ct_modulo here vs setting up Barrett reduction?
43  Modular_Reducer mod_p(p);
44 
45  m_r1 = mod_p.reduce(r);
46  m_r2 = mod_p.square(m_r1);
47  m_r3 = mod_p.multiply(m_r1, m_r2);
48  }
bool is_negative() const
Definition: bigint.h:525
const BigInt & p() const
Definition: monty.h:144
bool is_even() const
Definition: bigint.h:401
word word_at(size_t n) const
Definition: bigint.h:506
static BigInt power_of_2(size_t n)
Definition: bigint.h:751
BigInt & square(secure_vector< word > &ws)
Definition: big_ops2.cpp:216
size_t sig_words() const
Definition: bigint.h:584
word monty_inverse(word a)
Definition: numthry.cpp:419

Member Function Documentation

◆ inv_mod_p()

BigInt Botan::Montgomery_Params::inv_mod_p ( const BigInt x) const

Definition at line 50 of file monty.cpp.

References Botan::ct_inverse_mod_odd_modulus(), and p().

51  {
52  return ct_inverse_mod_odd_modulus(x, p());
53  }
const BigInt & p() const
Definition: monty.h:144
BigInt ct_inverse_mod_odd_modulus(const BigInt &n, const BigInt &mod)
Definition: numthry.cpp:200

◆ mul() [1/2]

BigInt Botan::Montgomery_Params::mul ( const BigInt x,
const BigInt y,
secure_vector< word > &  ws 
) const

Definition at line 72 of file monty.cpp.

References Botan::bigint_monty_redc(), Botan::bigint_mul(), BOTAN_DEBUG_ASSERT, Botan::BigInt::data(), Botan::BigInt::Positive, Botan::BigInt::sig_words(), and Botan::BigInt::size().

74  {
75  const size_t output_size = 2*m_p_words + 2;
76 
77  if(ws.size() < output_size)
78  ws.resize(output_size);
79 
80  BOTAN_DEBUG_ASSERT(x.sig_words() <= m_p_words);
81  BOTAN_DEBUG_ASSERT(y.sig_words() <= m_p_words);
82 
83  BigInt z(BigInt::Positive, output_size);
84  bigint_mul(z.mutable_data(), z.size(),
85  x.data(), x.size(), std::min(m_p_words, x.size()),
86  y.data(), y.size(), std::min(m_p_words, y.size()),
87  ws.data(), ws.size());
88 
89  bigint_monty_redc(z.mutable_data(),
90  m_p.data(), m_p_words, m_p_dash,
91  ws.data(), ws.size());
92 
93  return z;
94  }
const word * data() const
Definition: bigint.h:618
#define BOTAN_DEBUG_ASSERT(expr)
Definition: assert.h:123
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:298
void bigint_monty_redc(word z[], const word p[], size_t p_size, word p_dash, word workspace[], size_t ws_size)
Definition: mp_monty.cpp:109

◆ mul() [2/2]

BigInt Botan::Montgomery_Params::mul ( const BigInt x,
const secure_vector< word > &  y,
secure_vector< word > &  ws 
) const

Definition at line 96 of file monty.cpp.

References Botan::bigint_monty_redc(), Botan::bigint_mul(), BOTAN_DEBUG_ASSERT, Botan::BigInt::data(), Botan::BigInt::mutable_data(), Botan::BigInt::Positive, Botan::BigInt::sig_words(), and Botan::BigInt::size().

99  {
100  const size_t output_size = 2*m_p_words + 2;
101  if(ws.size() < output_size)
102  ws.resize(output_size);
103  BigInt z(BigInt::Positive, output_size);
104 
105  BOTAN_DEBUG_ASSERT(x.sig_words() <= m_p_words);
106 
107  bigint_mul(z.mutable_data(), z.size(),
108  x.data(), x.size(), std::min(m_p_words, x.size()),
109  y.data(), y.size(), std::min(m_p_words, y.size()),
110  ws.data(), ws.size());
111 
112  bigint_monty_redc(z.mutable_data(),
113  m_p.data(), m_p_words, m_p_dash,
114  ws.data(), ws.size());
115 
116  return z;
117  }
const word * data() const
Definition: bigint.h:618
#define BOTAN_DEBUG_ASSERT(expr)
Definition: assert.h:123
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:298
void bigint_monty_redc(word z[], const word p[], size_t p_size, word p_dash, word workspace[], size_t ws_size)
Definition: mp_monty.cpp:109

◆ mul_by() [1/2]

void Botan::Montgomery_Params::mul_by ( BigInt x,
const secure_vector< word > &  y,
secure_vector< word > &  ws 
) const

Definition at line 119 of file monty.cpp.

References Botan::bigint_monty_redc(), Botan::bigint_mul(), BOTAN_DEBUG_ASSERT, Botan::copy_mem(), Botan::BigInt::data(), Botan::BigInt::grow_to(), Botan::BigInt::mutable_data(), Botan::BigInt::sig_words(), and Botan::BigInt::size().

122  {
123  const size_t output_size = 2*m_p_words + 2;
124 
125  if(ws.size() < 2*output_size)
126  ws.resize(2*output_size);
127 
128  word* z_data = &ws[0];
129  word* ws_data = &ws[output_size];
130 
131  BOTAN_DEBUG_ASSERT(x.sig_words() <= m_p_words);
132 
133  bigint_mul(z_data, output_size,
134  x.data(), x.size(), std::min(m_p_words, x.size()),
135  y.data(), y.size(), std::min(m_p_words, y.size()),
136  ws_data, output_size);
137 
138  bigint_monty_redc(z_data,
139  m_p.data(), m_p_words, m_p_dash,
140  ws_data, output_size);
141 
142  if(x.size() < output_size)
143  x.grow_to(output_size);
144  copy_mem(x.mutable_data(), z_data, output_size);
145  }
const word * data() const
Definition: bigint.h:618
#define BOTAN_DEBUG_ASSERT(expr)
Definition: assert.h:123
void copy_mem(T *out, const T *in, size_t n)
Definition: mem_ops.h:132
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:298
void bigint_monty_redc(word z[], const word p[], size_t p_size, word p_dash, word workspace[], size_t ws_size)
Definition: mp_monty.cpp:109

◆ mul_by() [2/2]

void Botan::Montgomery_Params::mul_by ( BigInt x,
const BigInt y,
secure_vector< word > &  ws 
) const

Definition at line 147 of file monty.cpp.

References Botan::bigint_monty_redc(), Botan::bigint_mul(), BOTAN_DEBUG_ASSERT, Botan::copy_mem(), Botan::BigInt::data(), Botan::BigInt::grow_to(), Botan::BigInt::mutable_data(), Botan::BigInt::sig_words(), and Botan::BigInt::size().

150  {
151  const size_t output_size = 2*m_p_words + 2;
152 
153  if(ws.size() < 2*output_size)
154  ws.resize(2*output_size);
155 
156  word* z_data = &ws[0];
157  word* ws_data = &ws[output_size];
158 
159  BOTAN_DEBUG_ASSERT(x.sig_words() <= m_p_words);
160 
161  bigint_mul(z_data, output_size,
162  x.data(), x.size(), std::min(m_p_words, x.size()),
163  y.data(), y.size(), std::min(m_p_words, y.size()),
164  ws_data, output_size);
165 
166  bigint_monty_redc(z_data,
167  m_p.data(), m_p_words, m_p_dash,
168  ws_data, output_size);
169 
170  if(x.size() < output_size)
171  x.grow_to(output_size);
172  copy_mem(x.mutable_data(), z_data, output_size);
173  }
const word * data() const
Definition: bigint.h:618
#define BOTAN_DEBUG_ASSERT(expr)
Definition: assert.h:123
void copy_mem(T *out, const T *in, size_t n)
Definition: mem_ops.h:132
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:298
void bigint_monty_redc(word z[], const word p[], size_t p_size, word p_dash, word workspace[], size_t ws_size)
Definition: mp_monty.cpp:109

◆ p()

const BigInt& Botan::Montgomery_Params::p ( ) const
inline

Definition at line 144 of file monty.h.

Referenced by inv_mod_p(), and Montgomery_Params().

144 { return m_p; }

◆ p_dash()

word Botan::Montgomery_Params::p_dash ( ) const
inline

Definition at line 149 of file monty.h.

149 { return m_p_dash; }

◆ p_words()

size_t Botan::Montgomery_Params::p_words ( ) const
inline

Definition at line 151 of file monty.h.

151 { return m_p_words; }

◆ R1()

const BigInt& Botan::Montgomery_Params::R1 ( ) const
inline

Definition at line 145 of file monty.h.

145 { return m_r1; }

◆ R2()

const BigInt& Botan::Montgomery_Params::R2 ( ) const
inline

Definition at line 146 of file monty.h.

146 { return m_r2; }

◆ R3()

const BigInt& Botan::Montgomery_Params::R3 ( ) const
inline

Definition at line 147 of file monty.h.

147 { return m_r3; }

◆ redc()

BigInt Botan::Montgomery_Params::redc ( const BigInt x,
secure_vector< word > &  ws 
) const

Definition at line 55 of file monty.cpp.

References Botan::bigint_monty_redc(), Botan::BigInt::data(), Botan::BigInt::grow_to(), and Botan::BigInt::mutable_data().

56  {
57  const size_t output_size = 2*m_p_words + 2;
58 
59  if(ws.size() < output_size)
60  ws.resize(output_size);
61 
62  BigInt z = x;
63  z.grow_to(output_size);
64 
65  bigint_monty_redc(z.mutable_data(),
66  m_p.data(), m_p_words, m_p_dash,
67  ws.data(), ws.size());
68 
69  return z;
70  }
const word * data() const
Definition: bigint.h:618
void bigint_monty_redc(word z[], const word p[], size_t p_size, word p_dash, word workspace[], size_t ws_size)
Definition: mp_monty.cpp:109

◆ sqr()

BigInt Botan::Montgomery_Params::sqr ( const BigInt x,
secure_vector< word > &  ws 
) const

Definition at line 175 of file monty.cpp.

References Botan::bigint_monty_redc(), Botan::bigint_sqr(), BOTAN_DEBUG_ASSERT, Botan::BigInt::data(), Botan::BigInt::mutable_data(), Botan::BigInt::Positive, Botan::BigInt::sig_words(), and Botan::BigInt::size().

176  {
177  const size_t output_size = 2*m_p_words + 2;
178 
179  if(ws.size() < output_size)
180  ws.resize(output_size);
181 
182  BigInt z(BigInt::Positive, output_size);
183 
184  BOTAN_DEBUG_ASSERT(x.sig_words() <= m_p_words);
185 
186  bigint_sqr(z.mutable_data(), z.size(),
187  x.data(), x.size(), std::min(m_p_words, x.size()),
188  ws.data(), ws.size());
189 
190  bigint_monty_redc(z.mutable_data(),
191  m_p.data(), m_p_words, m_p_dash,
192  ws.data(), ws.size());
193 
194  return z;
195  }
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:357
const word * data() const
Definition: bigint.h:618
#define BOTAN_DEBUG_ASSERT(expr)
Definition: assert.h:123
void bigint_monty_redc(word z[], const word p[], size_t p_size, word p_dash, word workspace[], size_t ws_size)
Definition: mp_monty.cpp:109

◆ square_this()

void Botan::Montgomery_Params::square_this ( BigInt x,
secure_vector< word > &  ws 
) const

Definition at line 197 of file monty.cpp.

References Botan::bigint_monty_redc(), Botan::bigint_sqr(), BOTAN_DEBUG_ASSERT, Botan::copy_mem(), Botan::BigInt::data(), Botan::BigInt::grow_to(), Botan::BigInt::mutable_data(), Botan::BigInt::sig_words(), and Botan::BigInt::size().

199  {
200  const size_t output_size = 2*m_p_words + 2;
201 
202  if(ws.size() < 2*output_size)
203  ws.resize(2*output_size);
204 
205  word* z_data = &ws[0];
206  word* ws_data = &ws[output_size];
207 
208  BOTAN_DEBUG_ASSERT(x.sig_words() <= m_p_words);
209 
210  bigint_sqr(z_data, output_size,
211  x.data(), x.size(), std::min(m_p_words, x.size()),
212  ws_data, output_size);
213 
214  bigint_monty_redc(z_data,
215  m_p.data(), m_p_words, m_p_dash,
216  ws_data, output_size);
217 
218  if(x.size() < output_size)
219  x.grow_to(output_size);
220  copy_mem(x.mutable_data(), z_data, output_size);
221  }
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:357
const word * data() const
Definition: bigint.h:618
#define BOTAN_DEBUG_ASSERT(expr)
Definition: assert.h:123
void copy_mem(T *out, const T *in, size_t n)
Definition: mem_ops.h:132
void bigint_monty_redc(word z[], const word p[], size_t p_size, word p_dash, word workspace[], size_t ws_size)
Definition: mp_monty.cpp:109

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