Botan  2.13.0
Crypto and TLS for C++11
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 
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 
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 
51  {
52  return ct_inverse_mod_odd_modulus(x, p());
53  }
54 
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 
66  m_p.data(), m_p_words, m_p_dash,
67  ws.data(), ws.size());
68 
69  return z;
70  }
71 
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 
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 
113  m_p.data(), m_p_words, m_p_dash,
114  ws.data(), ws.size());
115 
116  return z;
117  }
118 
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 
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 
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 
191  m_p.data(), m_p_words, m_p_dash,
192  ws.data(), ws.size());
193 
194  return z;
195  }
196 
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());
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());
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());
264  m_v = m_params->mul(m_v, m_params->R2(), ws);
265  }
266  }
267 
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 
276 
277  if(w.size() != p_words)
278  {
279  w.resize(p_words);
280  w.shrink_to_fit();
281  }
282  }
283 
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 
302  {
303  return m_v == m_params->R1();
304  }
305 
307  {
308  return m_v.is_zero();
309  }
310 
312  {
314  return m_params->redc(m_v, ws);
315  }
316 
318  {
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 
326  {
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 
334  {
336  return this->add(other, ws);
337  }
338 
340  {
341  m_v.mod_add(other.m_v, m_params->p(), ws);
342  return (*this);
343  }
344 
346  {
348  return this->sub(other, ws);
349  }
350 
352  {
353  m_v.mod_sub(other.m_v, m_params->p(), ws);
354  return (*this);
355  }
356 
358  {
360  return Montgomery_Int(m_params, m_params->mul(m_v, other.m_v, ws), false);
361  }
362 
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 
371  {
372  m_params->mul_by(m_v, other.m_v, ws);
373  return (*this);
374  }
375 
378  {
379  m_params->mul_by(m_v, other, ws);
380  return (*this);
381  }
382 
384  {
386  return mul_by(other, ws);
387  }
388 
390  {
392  return mul_by(other, ws);
393  }
394 
396  {
397  for(size_t i = 0; i != n; ++i)
398  m_params->square_this(m_v, ws);
399  return (*this);
400  }
401 
403  {
404  m_params->square_this(m_v, ws);
405  return (*this);
406  }
407 
409  {
410  return Montgomery_Int(m_params, m_params->sqr(m_v, ws), false);
411  }
412 
414  {
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 
421  {
422  return Montgomery_Int(m_params, m_params->p()) - (*this);
423  }
424 
426  {
427  m_v.mod_mul(2, m_params->p(), ws);
428  return (*this);
429  }
430 
432  {
433  m_v.mod_mul(3, m_params->p(), ws);
434  return (*this);
435  }
436 
438  {
439  m_v.mod_mul(4, m_params->p(), ws);
440  return (*this);
441  }
442 
444  {
445  m_v.mod_mul(8, m_params->p(), ws);
446  return (*this);
447  }
448 
449 }
void mul_by(BigInt &x, const secure_vector< word > &y, secure_vector< word > &ws) const
Definition: monty.cpp:119
Montgomery_Int multiplicative_inverse() const
Definition: monty.cpp:413
bool is_negative() const
Definition: bigint.h:525
Montgomery_Int & mul_by_8(secure_vector< word > &ws)
Definition: monty.cpp:443
const BigInt & p() const
Definition: monty.h:144
bool operator==(const Montgomery_Int &other) const
Definition: monty.cpp:284
Montgomery_Int operator+(const Montgomery_Int &other) const
Definition: monty.cpp:317
std::vector< uint8_t > serialize() const
Definition: monty.cpp:289
Montgomery_Int & mul_by(const Montgomery_Int &other, secure_vector< word > &ws)
Definition: monty.cpp:369
Montgomery_Int(std::shared_ptr< const Montgomery_Params > params)
Definition: monty.h:27
secure_vector< word > & get_word_vector()
Definition: bigint.h:623
BigInt & mod_sub(const BigInt &y, const BigInt &mod, secure_vector< word > &ws)
Definition: big_ops2.cpp:93
bool is_zero() const
Definition: bigint.h:419
BigInt ct_inverse_mod_odd_modulus(const BigInt &n, const BigInt &mod)
Definition: numthry.cpp:200
word * mutable_data()
Definition: bigint.h:612
#define BOTAN_ASSERT_NOMSG(expr)
Definition: assert.h:68
bool is_even() const
Definition: bigint.h:401
word word_at(size_t n) const
Definition: bigint.h:506
bool is_one() const
Definition: monty.cpp:301
Montgomery_Int & operator-=(const Montgomery_Int &other)
Definition: monty.cpp:345
Montgomery_Int operator-(const Montgomery_Int &other) const
Definition: monty.cpp:325
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
void square_this(BigInt &x, secure_vector< word > &ws) const
Definition: monty.cpp:197
const word * data() const
Definition: bigint.h:618
Montgomery_Int & operator*=(const Montgomery_Int &other)
Definition: monty.cpp:383
Montgomery_Int & mul_by_4(secure_vector< word > &ws)
Definition: monty.cpp:437
size_t size() const
Definition: monty.cpp:296
Montgomery_Int operator*(const Montgomery_Int &other) const
Definition: monty.cpp:357
BigInt mul(const BigInt &x, const BigInt &y, secure_vector< word > &ws) const
Definition: monty.cpp:72
#define BOTAN_DEBUG_ASSERT(expr)
Definition: assert.h:123
BigInt value() const
Definition: monty.cpp:311
BigInt & mod_add(const BigInt &y, const BigInt &mod, secure_vector< word > &ws)
Definition: big_ops2.cpp:50
Montgomery_Int & sub(const Montgomery_Int &other, secure_vector< word > &ws)
Definition: monty.cpp:351
Montgomery_Int & operator+=(const Montgomery_Int &other)
Definition: monty.cpp:333
size_t size() const
Definition: bigint.h:578
Montgomery_Params(const BigInt &p, const Modular_Reducer &mod_p)
Definition: monty.cpp:13
static BigInt power_of_2(size_t n)
Definition: bigint.h:751
Montgomery_Int mul(const Montgomery_Int &other, secure_vector< word > &ws) const
Definition: monty.cpp:363
void copy_mem(T *out, const T *in, size_t n)
Definition: mem_ops.h:132
Definition: alg_id.cpp:13
size_t sig_words() const
Definition: bigint.h:584
BigInt inv_mod_p(const BigInt &x) const
Definition: monty.cpp:50
Montgomery_Int & mul_by_3(secure_vector< word > &ws)
Definition: monty.cpp:431
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
BigInt & mod_mul(uint8_t y, const BigInt &mod, secure_vector< word > &ws)
Definition: big_ops2.cpp:139
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
Montgomery_Int & add(const Montgomery_Int &other, secure_vector< word > &ws)
Definition: monty.cpp:339
Montgomery_Int & square_this(secure_vector< word > &ws)
Definition: monty.cpp:402
word monty_inverse(word a)
Definition: numthry.cpp:419
void grow_to(size_t n) const
Definition: bigint.h:634
Montgomery_Int & square_this_n_times(secure_vector< word > &ws, size_t n)
Definition: monty.cpp:395
BigInt reduce(const BigInt &x) const
Definition: reducer.cpp:37
Montgomery_Int & mul_by_2(secure_vector< word > &ws)
Definition: monty.cpp:425
static secure_vector< uint8_t > encode_1363(const BigInt &n, size_t bytes)
Definition: big_code.cpp:111
BigInt redc(const BigInt &x, secure_vector< word > &ws) const
Definition: monty.cpp:55
std::vector< T, secure_allocator< T > > secure_vector
Definition: secmem.h:65
bool is_zero() const
Definition: monty.cpp:306
BigInt sqr(const BigInt &x, secure_vector< word > &ws) const
Definition: monty.cpp:175
Montgomery_Int additive_inverse() const
Definition: monty.cpp:420
Montgomery_Int square(secure_vector< word > &ws) const
Definition: monty.cpp:408
BigInt square(const BigInt &x) const
Definition: reducer.h:39
BigInt multiply(const BigInt &x, const BigInt &y) const
Definition: reducer.h:31