Botan 3.0.0-alpha0
Crypto and TLS for C&
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)
 
 Montgomery_Params (const BigInt &p, const Modular_Reducer &mod_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 BigInt &y, secure_vector< word > &ws) const
 
void mul_by (BigInt &x, const secure_vector< word > &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 138 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 44 of file monty.cpp.

46 {
47 if(p.is_even() || p < 3)
48 throw Invalid_Argument("Montgomery_Params invalid modulus");
49
50 m_p = p;
51 m_p_words = m_p.sig_words();
52 m_p_dash = monty_inverse(m_p.word_at(0));
53
54 const BigInt r = BigInt::power_of_2(m_p_words * BOTAN_MP_WORD_BITS);
55
56 m_r1 = mod_p.reduce(r);
57 m_r2 = mod_p.square(m_r1);
58 m_r3 = mod_p.multiply(m_r1, m_r2);
59 }
size_t sig_words() const
Definition: bigint.h:600
word word_at(size_t n) const
Definition: bigint.h:522
bool is_even() const
Definition: bigint.h:412
static BigInt power_of_2(size_t n)
Definition: bigint.h:753
BigInt & square(secure_vector< word > &ws)
Definition: big_ops2.cpp:198
const BigInt & p() const
Definition: monty.h:153
#define BOTAN_MP_WORD_BITS
Definition: build.h:52
word monty_inverse(word a)
Definition: monty.cpp:15

References BOTAN_MP_WORD_BITS, 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().

◆ 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 61 of file monty.cpp.

62 {
63 if(p.is_even() || p < 3)
64 throw Invalid_Argument("Montgomery_Params invalid modulus");
65
66 m_p = p;
67 m_p_words = m_p.sig_words();
68 m_p_dash = monty_inverse(m_p.word_at(0));
69
70 const BigInt r = BigInt::power_of_2(m_p_words * BOTAN_MP_WORD_BITS);
71
72 // It might be faster to use ct_modulo here vs setting up Barrett reduction?
73 Modular_Reducer mod_p(p);
74
75 m_r1 = mod_p.reduce(r);
76 m_r2 = mod_p.square(m_r1);
77 m_r3 = mod_p.multiply(m_r1, m_r2);
78 }

References BOTAN_MP_WORD_BITS, 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().

Member Function Documentation

◆ inv_mod_p()

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

Definition at line 80 of file monty.cpp.

81 {
82 // TODO use Montgomery inverse here?
83 return inverse_mod(x, p());
84 }
BigInt inverse_mod(const BigInt &n, const BigInt &mod)
Definition: mod_inv.cpp:177

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

◆ mul() [1/2]

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

Definition at line 103 of file monty.cpp.

105 {
106 const size_t output_size = 2*m_p_words + 2;
107
108 if(ws.size() < output_size)
109 ws.resize(output_size);
110
111 BOTAN_DEBUG_ASSERT(x.sig_words() <= m_p_words);
112 BOTAN_DEBUG_ASSERT(y.sig_words() <= m_p_words);
113
114 BigInt z = BigInt::with_capacity(output_size);
115 bigint_mul(z.mutable_data(), z.size(),
116 x.data(), x.size(), std::min(m_p_words, x.size()),
117 y.data(), y.size(), std::min(m_p_words, y.size()),
118 ws.data(), ws.size());
119
120 bigint_monty_redc(z.mutable_data(),
121 m_p.data(), m_p_words, m_p_dash,
122 ws.data(), ws.size());
123
124 return z;
125 }
#define BOTAN_DEBUG_ASSERT(expr)
Definition: assert.h:122
const word * data() const
Definition: bigint.h:634
static BigInt with_capacity(size_t n)
Definition: bigint.cpp:60
void bigint_monty_redc(word z[], const word p[], size_t p_size, word p_dash, word ws[], size_t ws_size)
Definition: mp_core.h:818
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:297

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

◆ mul() [2/2]

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

Definition at line 127 of file monty.cpp.

130 {
131 const size_t output_size = 2*m_p_words + 2;
132 if(ws.size() < output_size)
133 ws.resize(output_size);
134 BigInt z = BigInt::with_capacity(output_size);
135
136 BOTAN_DEBUG_ASSERT(x.sig_words() <= m_p_words);
137
138 bigint_mul(z.mutable_data(), z.size(),
139 x.data(), x.size(), std::min(m_p_words, x.size()),
140 y.data(), y.size(), std::min(m_p_words, y.size()),
141 ws.data(), ws.size());
142
143 bigint_monty_redc(z.mutable_data(),
144 m_p.data(), m_p_words, m_p_dash,
145 ws.data(), ws.size());
146
147 return z;
148 }

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

◆ mul_by() [1/2]

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

Definition at line 178 of file monty.cpp.

181 {
182 const size_t output_size = 2*m_p_words + 2;
183
184 if(ws.size() < 2*output_size)
185 ws.resize(2*output_size);
186
187 word* z_data = &ws[0];
188 word* ws_data = &ws[output_size];
189
190 BOTAN_DEBUG_ASSERT(x.sig_words() <= m_p_words);
191
192 bigint_mul(z_data, output_size,
193 x.data(), x.size(), std::min(m_p_words, x.size()),
194 y.data(), y.size(), std::min(m_p_words, y.size()),
195 ws_data, output_size);
196
197 bigint_monty_redc(z_data,
198 m_p.data(), m_p_words, m_p_dash,
199 ws_data, output_size);
200
201 if(x.size() < output_size)
202 x.grow_to(output_size);
203 copy_mem(x.mutable_data(), z_data, output_size);
204 }
constexpr void copy_mem(T *out, const T *in, size_t n)
Definition: mem_ops.h:126

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

◆ mul_by() [2/2]

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

Definition at line 150 of file monty.cpp.

153 {
154 const size_t output_size = 2*m_p_words + 2;
155
156 if(ws.size() < 2*output_size)
157 ws.resize(2*output_size);
158
159 word* z_data = &ws[0];
160 word* ws_data = &ws[output_size];
161
162 BOTAN_DEBUG_ASSERT(x.sig_words() <= m_p_words);
163
164 bigint_mul(z_data, output_size,
165 x.data(), x.size(), std::min(m_p_words, x.size()),
166 y.data(), y.size(), std::min(m_p_words, y.size()),
167 ws_data, output_size);
168
169 bigint_monty_redc(z_data,
170 m_p.data(), m_p_words, m_p_dash,
171 ws_data, output_size);
172
173 if(x.size() < output_size)
174 x.grow_to(output_size);
175 copy_mem(x.mutable_data(), z_data, output_size);
176 }

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

◆ p()

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

Definition at line 153 of file monty.h.

153{ return m_p; }

Referenced by inv_mod_p(), and Montgomery_Params().

◆ p_dash()

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

Definition at line 158 of file monty.h.

158{ return m_p_dash; }

◆ p_words()

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

Definition at line 160 of file monty.h.

160{ return m_p_words; }

◆ R1()

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

Definition at line 154 of file monty.h.

154{ return m_r1; }

◆ R2()

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

Definition at line 155 of file monty.h.

155{ return m_r2; }

◆ R3()

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

Definition at line 156 of file monty.h.

156{ return m_r3; }

◆ redc()

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

Definition at line 86 of file monty.cpp.

87 {
88 const size_t output_size = 2*m_p_words + 2;
89
90 if(ws.size() < output_size)
91 ws.resize(output_size);
92
93 BigInt z = x;
94 z.grow_to(output_size);
95
96 bigint_monty_redc(z.mutable_data(),
97 m_p.data(), m_p_words, m_p_dash,
98 ws.data(), ws.size());
99
100 return z;
101 }

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

◆ sqr()

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

Definition at line 206 of file monty.cpp.

207 {
208 const size_t output_size = 2*m_p_words + 2;
209
210 if(ws.size() < output_size)
211 ws.resize(output_size);
212
213 BigInt z = BigInt::with_capacity(output_size);
214
215 BOTAN_DEBUG_ASSERT(x.sig_words() <= m_p_words);
216
217 bigint_sqr(z.mutable_data(), z.size(),
218 x.data(), x.size(), std::min(m_p_words, x.size()),
219 ws.data(), ws.size());
220
221 bigint_monty_redc(z.mutable_data(),
222 m_p.data(), m_p_words, m_p_dash,
223 ws.data(), ws.size());
224
225 return z;
226 }
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:356

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

◆ square_this()

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

Definition at line 228 of file monty.cpp.

230 {
231 const size_t output_size = 2*m_p_words + 2;
232
233 if(ws.size() < 2*output_size)
234 ws.resize(2*output_size);
235
236 word* z_data = &ws[0];
237 word* ws_data = &ws[output_size];
238
239 BOTAN_DEBUG_ASSERT(x.sig_words() <= m_p_words);
240
241 bigint_sqr(z_data, output_size,
242 x.data(), x.size(), std::min(m_p_words, x.size()),
243 ws_data, output_size);
244
245 bigint_monty_redc(z_data,
246 m_p.data(), m_p_words, m_p_dash,
247 ws_data, output_size);
248
249 if(x.size() < output_size)
250 x.grow_to(output_size);
251 copy_mem(x.mutable_data(), z_data, output_size);
252 }

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


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