Botan 3.0.0
Crypto and TLS for C&
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/internal/monty.h>
8#include <botan/reducer.h>
9#include <botan/internal/mp_core.h>
10
11#include <utility>
12
13namespace Botan {
14
15word monty_inverse(word a)
16 {
17 if(a % 2 == 0)
18 throw Invalid_Argument("monty_inverse only valid for odd integers");
19
20 /*
21 * From "A New Algorithm for Inversion mod p^k" by Çetin Kaya Koç
22 * https://eprint.iacr.org/2017/411.pdf sections 5 and 7.
23 */
24
25 word b = 1;
26 word r = 0;
27
28 for(size_t i = 0; i != BOTAN_MP_WORD_BITS; ++i)
29 {
30 const word bi = b % 2;
31 r >>= 1;
32 r += bi << (BOTAN_MP_WORD_BITS - 1);
33
34 b -= a * bi;
35 b >>= 1;
36 }
37
38 // Now invert in addition space
39 r = (MP_WORD_MAX - r) + 1;
40
41 return r;
42 }
43
45 const Modular_Reducer& mod_p)
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 }
60
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 }
79
81 {
82 // TODO use Montgomery inverse here?
83 return inverse_mod(x, p());
84 }
85
87 {
88 const size_t output_size = m_p_words + 1;
89
90 if(ws.size() < output_size)
91 ws.resize(output_size);
92
93 BigInt z = x;
94 z.grow_to(2*m_p_words);
95
97 m_p.data(), m_p_words, m_p_dash,
98 ws.data(), ws.size());
99
100 return z;
101 }
102
104 secure_vector<word>& ws) const
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);
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
121 m_p.data(), m_p_words, m_p_dash,
122 ws.data(), ws.size());
123
124 return z;
125 }
126
128 const secure_vector<word>& y,
129 secure_vector<word>& ws) const
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
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
144 m_p.data(), m_p_words, m_p_dash,
145 ws.data(), ws.size());
146
147 return z;
148 }
149
151 const secure_vector<word>& y,
152 secure_vector<word>& ws) const
153 {
154 const size_t output_size = 2*m_p_words;
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 }
177
179 const BigInt& y,
180 secure_vector<word>& ws) const
181 {
182 const size_t output_size = 2*m_p_words;
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 }
205
207 {
208 const size_t output_size = 2*m_p_words;
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
218 x.data(), x.size(), std::min(m_p_words, x.size()),
219 ws.data(), ws.size());
220
222 m_p.data(), m_p_words, m_p_dash,
223 ws.data(), ws.size());
224
225 return z;
226 }
227
229 secure_vector<word>& ws) const
230 {
231 const size_t output_size = 2*m_p_words;
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 }
253
254Montgomery_Int::Montgomery_Int(const std::shared_ptr<const Montgomery_Params>& params,
255 const BigInt& v,
256 bool redc_needed) :
257 m_params(params)
258 {
259 if(redc_needed == false)
260 {
261 m_v = v;
262 }
263 else
264 {
265 BOTAN_ASSERT_NOMSG(m_v < m_params->p());
267 m_v = m_params->mul(v, m_params->R2(), ws);
268 }
269 }
270
271Montgomery_Int::Montgomery_Int(const std::shared_ptr<const Montgomery_Params>& params,
272 const uint8_t bits[], size_t len,
273 bool redc_needed) :
274 m_params(params),
275 m_v(bits, len)
276 {
277 if(redc_needed)
278 {
279 BOTAN_ASSERT_NOMSG(m_v < m_params->p());
281 m_v = m_params->mul(m_v, m_params->R2(), ws);
282 }
283 }
284
285Montgomery_Int::Montgomery_Int(std::shared_ptr<const Montgomery_Params> params,
286 const word words[], size_t len,
287 bool redc_needed) :
288 m_params(std::move(params))
289 {
290 m_v.set_words(words, len);
291
292 if(redc_needed)
293 {
294 BOTAN_ASSERT_NOMSG(m_v < m_params->p());
296 m_v = m_params->mul(m_v, m_params->R2(), ws);
297 }
298 }
299
301 {
302 const size_t p_words = m_params->p_words();
303
304 if(m_v.sig_words() > p_words)
305 throw Internal_Error("Montgomery_Int::fix_size v too large");
306
307 m_v.grow_to(p_words);
308 }
309
311 {
312 return m_v == other.m_v && m_params->p() == other.m_params->p();
313 }
314
315std::vector<uint8_t> Montgomery_Int::serialize() const
316 {
317 std::vector<uint8_t> v(size());
318 BigInt::encode_1363(v.data(), v.size(), value());
319 return v;
320 }
321
323 {
324 return m_params->p().bytes();
325 }
326
328 {
329 return m_v == m_params->R1();
330 }
331
333 {
334 return m_v.is_zero();
335 }
336
338 {
340 return m_params->redc(m_v, ws);
341 }
342
344 {
346 BigInt z = m_v;
347 z.mod_add(other.m_v, m_params->p(), ws);
348 return Montgomery_Int(m_params, z, false);
349 }
350
352 {
354 BigInt z = m_v;
355 z.mod_sub(other.m_v, m_params->p(), ws);
356 return Montgomery_Int(m_params, z, false);
357 }
358
360 {
362 return this->add(other, ws);
363 }
364
366 {
367 m_v.mod_add(other.m_v, m_params->p(), ws);
368 return (*this);
369 }
370
372 {
374 return this->sub(other, ws);
375 }
376
378 {
379 m_v.mod_sub(other.m_v, m_params->p(), ws);
380 return (*this);
381 }
382
384 {
386 return Montgomery_Int(m_params, m_params->mul(m_v, other.m_v, ws), false);
387 }
388
390 secure_vector<word>& ws) const
391 {
392 return Montgomery_Int(m_params, m_params->mul(m_v, other.m_v, ws), false);
393 }
394
397 {
398 m_params->mul_by(m_v, other.m_v, ws);
399 return (*this);
400 }
401
404 {
405 m_params->mul_by(m_v, other, ws);
406 return (*this);
407 }
408
410 {
412 return mul_by(other, ws);
413 }
414
416 {
418 return mul_by(other, ws);
419 }
420
422 {
423 for(size_t i = 0; i != n; ++i)
424 m_params->square_this(m_v, ws);
425 return (*this);
426 }
427
429 {
430 m_params->square_this(m_v, ws);
431 return (*this);
432 }
433
435 {
436 return Montgomery_Int(m_params, m_params->sqr(m_v, ws), false);
437 }
438
440 {
441 return Montgomery_Int(m_params, m_params->sqr(m_v, ws), false);
442 }
443
445 {
447 const BigInt iv = m_params->mul(m_params->inv_mod_p(m_v), m_params->R3(), ws);
448 return Montgomery_Int(m_params, iv, false);
449 }
450
452 {
453 return Montgomery_Int(m_params, m_params->p()) - (*this);
454 }
455
457 {
458 m_v.mod_mul(2, m_params->p(), ws);
459 return (*this);
460 }
461
463 {
464 m_v.mod_mul(3, m_params->p(), ws);
465 return (*this);
466 }
467
469 {
470 m_v.mod_mul(4, m_params->p(), ws);
471 return (*this);
472 }
473
475 {
476 m_v.mod_mul(8, m_params->p(), ws);
477 return (*this);
478 }
479
480}
static SIMD_4x64 y
#define BOTAN_ASSERT_NOMSG(expr)
Definition: assert.h:67
#define BOTAN_DEBUG_ASSERT(expr)
Definition: assert.h:122
BigInt & mod_mul(uint8_t y, const BigInt &mod, secure_vector< word > &ws)
Definition: big_ops2.cpp:121
size_t sig_words() const
Definition: bigint.h:615
word * mutable_data()
Definition: bigint.h:643
size_t size() const
Definition: bigint.h:609
void grow_to(size_t n) const
Definition: bigint.h:665
void set_words(const word w[], size_t len)
Definition: bigint.h:547
BigInt & mod_add(const BigInt &y, const BigInt &mod, secure_vector< word > &ws)
Definition: big_ops2.cpp:50
const word * data() const
Definition: bigint.h:649
word word_at(size_t n) const
Definition: bigint.h:537
BigInt & mod_sub(const BigInt &y, const BigInt &mod, secure_vector< word > &ws)
Definition: big_ops2.cpp:94
bool is_even() const
Definition: bigint.h:416
static BigInt power_of_2(size_t n)
Definition: bigint.h:768
static secure_vector< uint8_t > encode_1363(const BigInt &n, size_t bytes)
Definition: big_code.cpp:107
bool is_zero() const
Definition: bigint.h:434
static BigInt with_capacity(size_t n)
Definition: bigint.cpp:60
BigInt square(const BigInt &x) const
Definition: reducer.h:46
BigInt multiply(const BigInt &x, const BigInt &y) const
Definition: reducer.h:31
BigInt reduce(const BigInt &x) const
Definition: reducer.cpp:37
size_t size() const
Definition: monty.cpp:322
Montgomery_Int & operator*=(const Montgomery_Int &other)
Definition: monty.cpp:409
Montgomery_Int(std::shared_ptr< const Montgomery_Params > params)
Definition: monty.h:34
bool operator==(const Montgomery_Int &other) const
Definition: monty.cpp:310
bool is_one() const
Definition: monty.cpp:327
Montgomery_Int & add(const Montgomery_Int &other, secure_vector< word > &ws)
Definition: monty.cpp:365
Montgomery_Int & operator+=(const Montgomery_Int &other)
Definition: monty.cpp:359
Montgomery_Int & operator-=(const Montgomery_Int &other)
Definition: monty.cpp:371
Montgomery_Int square(secure_vector< word > &ws) const
Definition: monty.cpp:434
Montgomery_Int cube(secure_vector< word > &ws) const
Definition: monty.cpp:439
Montgomery_Int additive_inverse() const
Definition: monty.cpp:451
Montgomery_Int operator*(const Montgomery_Int &other) const
Definition: monty.cpp:383
Montgomery_Int & mul_by_3(secure_vector< word > &ws)
Definition: monty.cpp:462
Montgomery_Int & mul_by_8(secure_vector< word > &ws)
Definition: monty.cpp:474
Montgomery_Int & mul_by_2(secure_vector< word > &ws)
Definition: monty.cpp:456
Montgomery_Int & sub(const Montgomery_Int &other, secure_vector< word > &ws)
Definition: monty.cpp:377
Montgomery_Int operator-(const Montgomery_Int &other) const
Definition: monty.cpp:351
Montgomery_Int operator+(const Montgomery_Int &other) const
Definition: monty.cpp:343
bool is_zero() const
Definition: monty.cpp:332
BigInt value() const
Definition: monty.cpp:337
Montgomery_Int & square_this_n_times(secure_vector< word > &ws, size_t n)
Definition: monty.cpp:421
Montgomery_Int & mul_by_4(secure_vector< word > &ws)
Definition: monty.cpp:468
Montgomery_Int & square_this(secure_vector< word > &ws)
Definition: monty.cpp:428
Montgomery_Int multiplicative_inverse() const
Definition: monty.cpp:444
Montgomery_Int mul(const Montgomery_Int &other, secure_vector< word > &ws) const
Definition: monty.cpp:389
Montgomery_Int & mul_by(const Montgomery_Int &other, secure_vector< word > &ws)
Definition: monty.cpp:395
std::vector< uint8_t > serialize() const
Definition: monty.cpp:315
BigInt redc(const BigInt &x, secure_vector< word > &ws) const
Definition: monty.cpp:86
void mul_by(BigInt &x, const secure_vector< word > &y, secure_vector< word > &ws) const
Definition: monty.cpp:150
BigInt mul(const BigInt &x, const BigInt &y, secure_vector< word > &ws) const
Definition: monty.cpp:103
BigInt sqr(const BigInt &x, secure_vector< word > &ws) const
Definition: monty.cpp:206
BigInt inv_mod_p(const BigInt &x) const
Definition: monty.cpp:80
Montgomery_Params(const BigInt &p, const Modular_Reducer &mod_p)
Definition: monty.cpp:44
void square_this(BigInt &x, secure_vector< word > &ws) const
Definition: monty.cpp:228
const BigInt & p() const
Definition: monty.h:153
#define BOTAN_MP_WORD_BITS
Definition: build.h:50
Definition: alg_id.cpp:12
const word MP_WORD_MAX
Definition: mp_core.h:22
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:823
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
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
word monty_inverse(word a)
Definition: monty.cpp:15
constexpr void copy_mem(T *out, const T *in, size_t n)
Definition: mem_ops.h:126
BigInt inverse_mod(const BigInt &n, const BigInt &mod)
Definition: mod_inv.cpp:177
std::vector< T, secure_allocator< T > > secure_vector
Definition: secmem.h:64
Definition: bigint.h:1092