Botan 2.13.0 Crypto and TLS for C++11

- Main Page
- Namespaces
- Classes
- Files

- File List
- File Members

monty.cpp
Go to the documentation of this file.
1 /*
2 * (C) 2018 Jack Lloyd
3 *
4 * Botan is released under the Simplified BSD License (see license.txt)
5 */
6
7 #include <botan/monty.h>
8 #include <botan/reducer.h>
9 #include <botan/internal/mp_core.h>
10
11 namespace Botan {
12
13 Montgomery_Params::Montgomery_Params(const BigInt& p,
14 const Modular_Reducer& mod_p)
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 }
29
30 Montgomery_Params::Montgomery_Params(const BigInt& p)
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 }
49
50 BigInt Montgomery_Params::inv_mod_p(const BigInt& x) const
51 {
52 return ct_inverse_mod_odd_modulus(x, p());
53 }
54
55 BigInt Montgomery_Params::redc(const BigInt& x, secure_vector<word>& ws) const
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 }
71
72 BigInt Montgomery_Params::mul(const BigInt& x, const BigInt& y,
73 secure_vector<word>& ws) const
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 }
95
96 BigInt Montgomery_Params::mul(const BigInt& x,
97 const secure_vector<word>& y,
98 secure_vector<word>& ws) const
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 }
118
119 void Montgomery_Params::mul_by(BigInt& x,
120 const secure_vector<word>& y,
121 secure_vector<word>& ws) const
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 }
146
147 void Montgomery_Params::mul_by(BigInt& x,
148 const BigInt& y,
149 secure_vector<word>& ws) const
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 }
174
175 BigInt Montgomery_Params::sqr(const BigInt& x, secure_vector<word>& ws) const
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 }
196
197 void Montgomery_Params::square_this(BigInt& x,
198 secure_vector<word>& ws) const
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 }
222
223 Montgomery_Int::Montgomery_Int(const std::shared_ptr<const Montgomery_Params> params,
224 const BigInt& v,
225 bool redc_needed) :
226 m_params(params)
227 {
228 if(redc_needed == false)
229 {
230 m_v = v;
231 }
232 else
233 {
234 BOTAN_ASSERT_NOMSG(m_v < m_params->p());
235 secure_vector<word> ws;
236 m_v = m_params->mul(v, m_params->R2(), ws);
237 }
238 }
239
240 Montgomery_Int::Montgomery_Int(std::shared_ptr<const Montgomery_Params> params,
241 const uint8_t bits[], size_t len,
242 bool redc_needed) :
243 m_params(params),
244 m_v(bits, len)
245 {
246 if(redc_needed)
247 {
248 BOTAN_ASSERT_NOMSG(m_v < m_params->p());
249 secure_vector<word> ws;
250 m_v = m_params->mul(m_v, m_params->R2(), ws);
251 }
252 }
253
254 Montgomery_Int::Montgomery_Int(std::shared_ptr<const Montgomery_Params> params,
255 const word words[], size_t len,
256 bool redc_needed) :
257 m_params(params),
258 m_v(words, len)
259 {
260 if(redc_needed)
261 {
262 BOTAN_ASSERT_NOMSG(m_v < m_params->p());
263 secure_vector<word> ws;
264 m_v = m_params->mul(m_v, m_params->R2(), ws);
265 }
266 }
267
268 void Montgomery_Int::fix_size()
269 {
270 const size_t p_words = m_params->p_words();
271
272 if(m_v.sig_words() > p_words)
273 throw Internal_Error("Montgomery_Int::fix_size v too large");
274
275 secure_vector<word>& w = m_v.get_word_vector();
276
277 if(w.size() != p_words)
278 {
279 w.resize(p_words);
280 w.shrink_to_fit();
281 }
282 }
283
284 bool Montgomery_Int::operator==(const Montgomery_Int& other) const
285 {
286 return m_v == other.m_v && m_params->p() == other.m_params->p();
287 }
288
289 std::vector<uint8_t> Montgomery_Int::serialize() const
290 {
291 std::vector<uint8_t> v(size());
292 BigInt::encode_1363(v.data(), v.size(), value());
293 return v;
294 }
295
296 size_t Montgomery_Int::size() const
297 {
298 return m_params->p().bytes();
299 }
300
301 bool Montgomery_Int::is_one() const
302 {
303 return m_v == m_params->R1();
304 }
305
306 bool Montgomery_Int::is_zero() const
307 {
308 return m_v.is_zero();
309 }
310
311 BigInt Montgomery_Int::value() const
312 {
313 secure_vector<word> ws;
314 return m_params->redc(m_v, ws);
315 }
316
317 Montgomery_Int Montgomery_Int::operator+(const Montgomery_Int& other) const
318 {
319 secure_vector<word> ws;
320 BigInt z = m_v;
321 z.mod_add(other.m_v, m_params->p(), ws);
322 return Montgomery_Int(m_params, z, false);
323 }
324
325 Montgomery_Int Montgomery_Int::operator-(const Montgomery_Int& other) const
326 {
327 secure_vector<word> ws;
328 BigInt z = m_v;
329 z.mod_sub(other.m_v, m_params->p(), ws);
330 return Montgomery_Int(m_params, z, false);
331 }
332
333 Montgomery_Int& Montgomery_Int::operator+=(const Montgomery_Int& other)
334 {
335 secure_vector<word> ws;
336 return this->add(other, ws);
337 }
338
339 Montgomery_Int& Montgomery_Int::add(const Montgomery_Int& other, secure_vector<word>& ws)
340 {
341 m_v.mod_add(other.m_v, m_params->p(), ws);
342 return (*this);
343 }
344
345 Montgomery_Int& Montgomery_Int::operator-=(const Montgomery_Int& other)
346 {
347 secure_vector<word> ws;
348 return this->sub(other, ws);
349 }
350
351 Montgomery_Int& Montgomery_Int::sub(const Montgomery_Int& other, secure_vector<word>& ws)
352 {
353 m_v.mod_sub(other.m_v, m_params->p(), ws);
354 return (*this);
355 }
356
357 Montgomery_Int Montgomery_Int::operator*(const Montgomery_Int& other) const
358 {
359 secure_vector<word> ws;
360 return Montgomery_Int(m_params, m_params->mul(m_v, other.m_v, ws), false);
361 }
362
363 Montgomery_Int Montgomery_Int::mul(const Montgomery_Int& other,
364 secure_vector<word>& ws) const
365 {
366 return Montgomery_Int(m_params, m_params->mul(m_v, other.m_v, ws), false);
367 }
368
369 Montgomery_Int& Montgomery_Int::mul_by(const Montgomery_Int& other,
370 secure_vector<word>& ws)
371 {
372 m_params->mul_by(m_v, other.m_v, ws);
373 return (*this);
374 }
375
376 Montgomery_Int& Montgomery_Int::mul_by(const secure_vector<word>& other,
377 secure_vector<word>& ws)
378 {
379 m_params->mul_by(m_v, other, ws);
380 return (*this);
381 }
382
383 Montgomery_Int& Montgomery_Int::operator*=(const Montgomery_Int& other)
384 {
385 secure_vector<word> ws;
386 return mul_by(other, ws);
387 }
388
389 Montgomery_Int& Montgomery_Int::operator*=(const secure_vector<word>& other)
390 {
391 secure_vector<word> ws;
392 return mul_by(other, ws);
393 }
394
395 Montgomery_Int& Montgomery_Int::square_this_n_times(secure_vector<word>& ws, size_t n)
396 {
397 for(size_t i = 0; i != n; ++i)
398 m_params->square_this(m_v, ws);
399 return (*this);
400 }
401
402 Montgomery_Int& Montgomery_Int::square_this(secure_vector<word>& ws)
403 {
404 m_params->square_this(m_v, ws);
405 return (*this);
406 }
407
408 Montgomery_Int Montgomery_Int::square(secure_vector<word>& ws) const
409 {
410 return Montgomery_Int(m_params, m_params->sqr(m_v, ws), false);
411 }
412
413 Montgomery_Int Montgomery_Int::multiplicative_inverse() const
414 {
415 secure_vector<word> ws;
416 const BigInt iv = m_params->mul(m_params->inv_mod_p(m_v), m_params->R3(), ws);
417 return Montgomery_Int(m_params, iv, false);
418 }
419
420 Montgomery_Int Montgomery_Int::additive_inverse() const
421 {
422 return Montgomery_Int(m_params, m_params->p()) - (*this);
423 }
424
425 Montgomery_Int& Montgomery_Int::mul_by_2(secure_vector<word>& ws)
426 {
427 m_v.mod_mul(2, m_params->p(), ws);
428 return (*this);
429 }
430
431 Montgomery_Int& Montgomery_Int::mul_by_3(secure_vector<word>& ws)
432 {
433 m_v.mod_mul(3, m_params->p(), ws);
434 return (*this);
435 }
436
437 Montgomery_Int& Montgomery_Int::mul_by_4(secure_vector<word>& ws)
438 {
439 m_v.mod_mul(4, m_params->p(), ws);
440 return (*this);
441 }
442
443 Montgomery_Int& Montgomery_Int::mul_by_8(secure_vector<word>& ws)
444 {
445 m_v.mod_mul(8, m_params->p(), ws);
446 return (*this);
447 }
448
449 }
Botan::BigInt::word_at
word word_at(size_t n) const
Definition: bigint.h:506
Botan::BigInt::sig_words
size_t sig_words() const
Definition: bigint.h:584
Botan::Invalid_Argument
Definition: exceptn.h:136
Botan::BigInt::is_even
bool is_even() const
Definition: bigint.h:401
Botan::Montgomery_Int::operator-
Montgomery_Int operator-(const Montgomery_Int &other) const
Definition: monty.cpp:325
Botan::Montgomery_Int::additive_inverse
Montgomery_Int additive_inverse() const
Definition: monty.cpp:420
Botan::Montgomery_Params::p
const BigInt & p() const
Definition: monty.h:144
Botan::Montgomery_Int::mul_by_8
Montgomery_Int & mul_by_8(secure_vector< word > &ws)
Definition: monty.cpp:443
Botan::BigInt
Definition: bigint.h:24
Botan::BigInt::Positive
Definition: bigint.h:35
Botan::Montgomery_Int::multiplicative_inverse
Montgomery_Int multiplicative_inverse() const
Definition: monty.cpp:413
Botan::Montgomery_Int::mul_by
Montgomery_Int & mul_by(const Montgomery_Int &other, secure_vector< word > &ws)
Definition: monty.cpp:369
Botan::Montgomery_Int::Montgomery_Int
Montgomery_Int(std::shared_ptr< const Montgomery_Params > params)
Definition: monty.h:27
Botan::BigInt::get_word_vector
secure_vector< word > & get_word_vector()
Definition: bigint.h:623
Botan::BigInt::mod_sub
BigInt & mod_sub(const BigInt &y, const BigInt &mod, secure_vector< word > &ws)
Definition: big_ops2.cpp:93
Botan::Montgomery_Int::serialize
std::vector< uint8_t > serialize() const
Definition: monty.cpp:289
Botan::ct_inverse_mod_odd_modulus
BigInt ct_inverse_mod_odd_modulus(const BigInt &n, const BigInt &mod)
Definition: numthry.cpp:200
Botan::Montgomery_Int::operator+
Montgomery_Int operator+(const Montgomery_Int &other) const
Definition: monty.cpp:317
Botan::Internal_Error
Definition: exceptn.h:341
Botan::BigInt::mutable_data
word * mutable_data()
Definition: bigint.h:612
BOTAN_ASSERT_NOMSG
#define BOTAN_ASSERT_NOMSG(expr)
Definition: assert.h:68
Botan::BigInt::is_negative
bool is_negative() const
Definition: bigint.h:525
Botan::BigInt::size
size_t size() const
Definition: bigint.h:578
Botan::Montgomery_Int::operator-=
Montgomery_Int & operator-=(const Montgomery_Int &other)
Definition: monty.cpp:345
Botan::Montgomery_Int::size
size_t size() const
Definition: monty.cpp:296
Botan::bigint_sqr
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
Botan::Montgomery_Params::redc
BigInt redc(const BigInt &x, secure_vector< word > &ws) const
Definition: monty.cpp:55
Botan::Montgomery_Int::square
Montgomery_Int square(secure_vector< word > &ws) const
Definition: monty.cpp:408
Botan::Montgomery_Params::mul
BigInt mul(const BigInt &x, const BigInt &y, secure_vector< word > &ws) const
Definition: monty.cpp:72
Botan::Montgomery_Params::mul_by
void mul_by(BigInt &x, const secure_vector< word > &y, secure_vector< word > &ws) const
Definition: monty.cpp:119
Botan::Montgomery_Int::operator*=
Montgomery_Int & operator*=(const Montgomery_Int &other)
Definition: monty.cpp:383
Botan::Montgomery_Int::mul_by_4
Montgomery_Int & mul_by_4(secure_vector< word > &ws)
Definition: monty.cpp:437
Botan::secure_vector
std::vector< T, secure_allocator< T >> secure_vector
Definition: secmem.h:65
BOTAN_DEBUG_ASSERT
#define BOTAN_DEBUG_ASSERT(expr)
Definition: assert.h:123
Botan::Montgomery_Int::is_one
bool is_one() const
Definition: monty.cpp:301
Botan::Montgomery_Params::sqr
BigInt sqr(const BigInt &x, secure_vector< word > &ws) const
Definition: monty.cpp:175
Botan::Modular_Reducer::multiply
BigInt multiply(const BigInt &x, const BigInt &y) const
Definition: reducer.h:31
Botan::Montgomery_Int::operator*
Montgomery_Int operator*(const Montgomery_Int &other) const
Definition: monty.cpp:357
Botan::BigInt::mod_add
BigInt & mod_add(const BigInt &y, const BigInt &mod, secure_vector< word > &ws)
Definition: big_ops2.cpp:50
Botan::Montgomery_Int::sub
Montgomery_Int & sub(const Montgomery_Int &other, secure_vector< word > &ws)
Definition: monty.cpp:351
Botan::Montgomery_Int::operator+=
Montgomery_Int & operator+=(const Montgomery_Int &other)
Definition: monty.cpp:333
Botan::Montgomery_Params::square_this
void square_this(BigInt &x, secure_vector< word > &ws) const
Definition: monty.cpp:197
Botan::Montgomery_Int::mul
Montgomery_Int mul(const Montgomery_Int &other, secure_vector< word > &ws) const
Definition: monty.cpp:363
Botan::BigInt::data
const word * data() const
Definition: bigint.h:618
Botan::Montgomery_Params::Montgomery_Params
Montgomery_Params(const BigInt &p, const Modular_Reducer &mod_p)
Definition: monty.cpp:13
Botan::BigInt::power_of_2
static BigInt power_of_2(size_t n)
Definition: bigint.h:751
Botan::copy_mem
void copy_mem(T *out, const T *in, size_t n)
Definition: mem_ops.h:132
Botan
Definition: alg_id.cpp:13
Botan::Montgomery_Int::mul_by_3
Montgomery_Int & mul_by_3(secure_vector< word > &ws)
Definition: monty.cpp:431
Botan::Modular_Reducer::reduce
BigInt reduce(const BigInt &x) const
Definition: reducer.cpp:37
Botan::bigint_mul
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
Botan::BigInt::mod_mul
BigInt & mod_mul(uint8_t y, const BigInt &mod, secure_vector< word > &ws)
Definition: big_ops2.cpp:139
Botan::bigint_monty_redc
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
Botan::Montgomery_Int::add
Montgomery_Int & add(const Montgomery_Int &other, secure_vector< word > &ws)
Definition: monty.cpp:339
Botan::Montgomery_Int::fix_size
void fix_size()
Definition: monty.cpp:268
Botan::Montgomery_Int::square_this
Montgomery_Int & square_this(secure_vector< word > &ws)
Definition: monty.cpp:402
Botan::monty_inverse
word monty_inverse(word a)
Definition: numthry.cpp:419
Botan::Montgomery_Int::operator==
bool operator==(const Montgomery_Int &other) const
Definition: monty.cpp:284
Botan::Montgomery_Int::square_this_n_times
Montgomery_Int & square_this_n_times(secure_vector< word > &ws, size_t n)
Definition: monty.cpp:395
Botan::BigInt::grow_to
void grow_to(size_t n) const
Definition: bigint.h:634
Botan::Montgomery_Int::mul_by_2
Montgomery_Int & mul_by_2(secure_vector< word > &ws)
Definition: monty.cpp:425
Botan::BigInt::encode_1363
static secure_vector< uint8_t > encode_1363(const BigInt &n, size_t bytes)
Definition: big_code.cpp:111
Botan::Montgomery_Int::is_zero
bool is_zero() const
Definition: monty.cpp:306
Botan::Montgomery_Params::inv_mod_p
BigInt inv_mod_p(const BigInt &x) const
Definition: monty.cpp:50
Botan::BigInt::is_zero
bool is_zero() const
Definition: bigint.h:419
Botan::Modular_Reducer::square
BigInt square(const BigInt &x) const
Definition: reducer.h:39
Botan::Modular_Reducer
Definition: reducer.h:18
Botan::Montgomery_Int::value
BigInt value() const
Definition: monty.cpp:311
Botan::Montgomery_Int
Definition: monty.h:21