Botan  2.15.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  // TODO use Montgomery inverse here?
53  return inverse_mod(x, p());
54  }
55 
57  {
58  const size_t output_size = 2*m_p_words + 2;
59 
60  if(ws.size() < output_size)
61  ws.resize(output_size);
62 
63  BigInt z = x;
64  z.grow_to(output_size);
65 
67  m_p.data(), m_p_words, m_p_dash,
68  ws.data(), ws.size());
69 
70  return z;
71  }
72 
74  secure_vector<word>& ws) const
75  {
76  const size_t output_size = 2*m_p_words + 2;
77 
78  if(ws.size() < output_size)
79  ws.resize(output_size);
80 
81  BOTAN_DEBUG_ASSERT(x.sig_words() <= m_p_words);
82  BOTAN_DEBUG_ASSERT(y.sig_words() <= m_p_words);
83 
84  BigInt z(BigInt::Positive, output_size);
85  bigint_mul(z.mutable_data(), z.size(),
86  x.data(), x.size(), std::min(m_p_words, x.size()),
87  y.data(), y.size(), std::min(m_p_words, y.size()),
88  ws.data(), ws.size());
89 
90  bigint_monty_redc(z.mutable_data(),
91  m_p.data(), m_p_words, m_p_dash,
92  ws.data(), ws.size());
93 
94  return z;
95  }
96 
98  const secure_vector<word>& y,
99  secure_vector<word>& ws) const
100  {
101  const size_t output_size = 2*m_p_words + 2;
102  if(ws.size() < output_size)
103  ws.resize(output_size);
104  BigInt z(BigInt::Positive, output_size);
105 
106  BOTAN_DEBUG_ASSERT(x.sig_words() <= m_p_words);
107 
108  bigint_mul(z.mutable_data(), z.size(),
109  x.data(), x.size(), std::min(m_p_words, x.size()),
110  y.data(), y.size(), std::min(m_p_words, y.size()),
111  ws.data(), ws.size());
112 
114  m_p.data(), m_p_words, m_p_dash,
115  ws.data(), ws.size());
116 
117  return z;
118  }
119 
121  const secure_vector<word>& y,
122  secure_vector<word>& ws) const
123  {
124  const size_t output_size = 2*m_p_words + 2;
125 
126  if(ws.size() < 2*output_size)
127  ws.resize(2*output_size);
128 
129  word* z_data = &ws[0];
130  word* ws_data = &ws[output_size];
131 
132  BOTAN_DEBUG_ASSERT(x.sig_words() <= m_p_words);
133 
134  bigint_mul(z_data, output_size,
135  x.data(), x.size(), std::min(m_p_words, x.size()),
136  y.data(), y.size(), std::min(m_p_words, y.size()),
137  ws_data, output_size);
138 
139  bigint_monty_redc(z_data,
140  m_p.data(), m_p_words, m_p_dash,
141  ws_data, output_size);
142 
143  if(x.size() < output_size)
144  x.grow_to(output_size);
145  copy_mem(x.mutable_data(), z_data, output_size);
146  }
147 
149  const BigInt& y,
150  secure_vector<word>& ws) const
151  {
152  const size_t output_size = 2*m_p_words + 2;
153 
154  if(ws.size() < 2*output_size)
155  ws.resize(2*output_size);
156 
157  word* z_data = &ws[0];
158  word* ws_data = &ws[output_size];
159 
160  BOTAN_DEBUG_ASSERT(x.sig_words() <= m_p_words);
161 
162  bigint_mul(z_data, output_size,
163  x.data(), x.size(), std::min(m_p_words, x.size()),
164  y.data(), y.size(), std::min(m_p_words, y.size()),
165  ws_data, output_size);
166 
167  bigint_monty_redc(z_data,
168  m_p.data(), m_p_words, m_p_dash,
169  ws_data, output_size);
170 
171  if(x.size() < output_size)
172  x.grow_to(output_size);
173  copy_mem(x.mutable_data(), z_data, output_size);
174  }
175 
177  {
178  const size_t output_size = 2*m_p_words + 2;
179 
180  if(ws.size() < output_size)
181  ws.resize(output_size);
182 
183  BigInt z(BigInt::Positive, output_size);
184 
185  BOTAN_DEBUG_ASSERT(x.sig_words() <= m_p_words);
186 
187  bigint_sqr(z.mutable_data(), z.size(),
188  x.data(), x.size(), std::min(m_p_words, x.size()),
189  ws.data(), ws.size());
190 
192  m_p.data(), m_p_words, m_p_dash,
193  ws.data(), ws.size());
194 
195  return z;
196  }
197 
199  secure_vector<word>& ws) const
200  {
201  const size_t output_size = 2*m_p_words + 2;
202 
203  if(ws.size() < 2*output_size)
204  ws.resize(2*output_size);
205 
206  word* z_data = &ws[0];
207  word* ws_data = &ws[output_size];
208 
209  BOTAN_DEBUG_ASSERT(x.sig_words() <= m_p_words);
210 
211  bigint_sqr(z_data, output_size,
212  x.data(), x.size(), std::min(m_p_words, x.size()),
213  ws_data, output_size);
214 
215  bigint_monty_redc(z_data,
216  m_p.data(), m_p_words, m_p_dash,
217  ws_data, output_size);
218 
219  if(x.size() < output_size)
220  x.grow_to(output_size);
221  copy_mem(x.mutable_data(), z_data, output_size);
222  }
223 
224 Montgomery_Int::Montgomery_Int(const std::shared_ptr<const Montgomery_Params> params,
225  const BigInt& v,
226  bool redc_needed) :
227  m_params(params)
228  {
229  if(redc_needed == false)
230  {
231  m_v = v;
232  }
233  else
234  {
235  BOTAN_ASSERT_NOMSG(m_v < m_params->p());
237  m_v = m_params->mul(v, m_params->R2(), ws);
238  }
239  }
240 
241 Montgomery_Int::Montgomery_Int(std::shared_ptr<const Montgomery_Params> params,
242  const uint8_t bits[], size_t len,
243  bool redc_needed) :
244  m_params(params),
245  m_v(bits, len)
246  {
247  if(redc_needed)
248  {
249  BOTAN_ASSERT_NOMSG(m_v < m_params->p());
251  m_v = m_params->mul(m_v, m_params->R2(), ws);
252  }
253  }
254 
255 Montgomery_Int::Montgomery_Int(std::shared_ptr<const Montgomery_Params> params,
256  const word words[], size_t len,
257  bool redc_needed) :
258  m_params(params),
259  m_v(words, len)
260  {
261  if(redc_needed)
262  {
263  BOTAN_ASSERT_NOMSG(m_v < m_params->p());
265  m_v = m_params->mul(m_v, m_params->R2(), ws);
266  }
267  }
268 
270  {
271  const size_t p_words = m_params->p_words();
272 
273  if(m_v.sig_words() > p_words)
274  throw Internal_Error("Montgomery_Int::fix_size v too large");
275 
276  m_v.grow_to(p_words);
277  }
278 
280  {
281  return m_v == other.m_v && m_params->p() == other.m_params->p();
282  }
283 
284 std::vector<uint8_t> Montgomery_Int::serialize() const
285  {
286  std::vector<uint8_t> v(size());
287  BigInt::encode_1363(v.data(), v.size(), value());
288  return v;
289  }
290 
291 size_t Montgomery_Int::size() const
292  {
293  return m_params->p().bytes();
294  }
295 
297  {
298  return m_v == m_params->R1();
299  }
300 
302  {
303  return m_v.is_zero();
304  }
305 
307  {
309  return m_params->redc(m_v, ws);
310  }
311 
313  {
315  BigInt z = m_v;
316  z.mod_add(other.m_v, m_params->p(), ws);
317  return Montgomery_Int(m_params, z, false);
318  }
319 
321  {
323  BigInt z = m_v;
324  z.mod_sub(other.m_v, m_params->p(), ws);
325  return Montgomery_Int(m_params, z, false);
326  }
327 
329  {
331  return this->add(other, ws);
332  }
333 
335  {
336  m_v.mod_add(other.m_v, m_params->p(), ws);
337  return (*this);
338  }
339 
341  {
343  return this->sub(other, ws);
344  }
345 
347  {
348  m_v.mod_sub(other.m_v, m_params->p(), ws);
349  return (*this);
350  }
351 
353  {
355  return Montgomery_Int(m_params, m_params->mul(m_v, other.m_v, ws), false);
356  }
357 
359  secure_vector<word>& ws) const
360  {
361  return Montgomery_Int(m_params, m_params->mul(m_v, other.m_v, ws), false);
362  }
363 
366  {
367  m_params->mul_by(m_v, other.m_v, ws);
368  return (*this);
369  }
370 
373  {
374  m_params->mul_by(m_v, other, ws);
375  return (*this);
376  }
377 
379  {
381  return mul_by(other, ws);
382  }
383 
385  {
387  return mul_by(other, ws);
388  }
389 
391  {
392  for(size_t i = 0; i != n; ++i)
393  m_params->square_this(m_v, ws);
394  return (*this);
395  }
396 
398  {
399  m_params->square_this(m_v, ws);
400  return (*this);
401  }
402 
404  {
405  return Montgomery_Int(m_params, m_params->sqr(m_v, ws), false);
406  }
407 
409  {
411  const BigInt iv = m_params->mul(m_params->inv_mod_p(m_v), m_params->R3(), ws);
412  return Montgomery_Int(m_params, iv, false);
413  }
414 
416  {
417  return Montgomery_Int(m_params, m_params->p()) - (*this);
418  }
419 
421  {
422  m_v.mod_mul(2, m_params->p(), ws);
423  return (*this);
424  }
425 
427  {
428  m_v.mod_mul(3, m_params->p(), ws);
429  return (*this);
430  }
431 
433  {
434  m_v.mod_mul(4, m_params->p(), ws);
435  return (*this);
436  }
437 
439  {
440  m_v.mod_mul(8, m_params->p(), ws);
441  return (*this);
442  }
443 
444 }
void mul_by(BigInt &x, const secure_vector< word > &y, secure_vector< word > &ws) const
Definition: monty.cpp:120
Montgomery_Int multiplicative_inverse() const
Definition: monty.cpp:408
bool is_negative() const
Definition: bigint.h:527
Montgomery_Int & mul_by_8(secure_vector< word > &ws)
Definition: monty.cpp:438
const BigInt & p() const
Definition: monty.h:144
bool operator==(const Montgomery_Int &other) const
Definition: monty.cpp:279
Montgomery_Int operator+(const Montgomery_Int &other) const
Definition: monty.cpp:312
std::vector< uint8_t > serialize() const
Definition: monty.cpp:284
Montgomery_Int & mul_by(const Montgomery_Int &other, secure_vector< word > &ws)
Definition: monty.cpp:364
Montgomery_Int(std::shared_ptr< const Montgomery_Params > params)
Definition: monty.h:27
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:421
word * mutable_data()
Definition: bigint.h:614
#define BOTAN_ASSERT_NOMSG(expr)
Definition: assert.h:68
bool is_even() const
Definition: bigint.h:403
word word_at(size_t n) const
Definition: bigint.h:508
bool is_one() const
Definition: monty.cpp:296
Montgomery_Int & operator-=(const Montgomery_Int &other)
Definition: monty.cpp:340
Montgomery_Int operator-(const Montgomery_Int &other) const
Definition: monty.cpp:320
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:198
const word * data() const
Definition: bigint.h:620
Montgomery_Int & operator*=(const Montgomery_Int &other)
Definition: monty.cpp:378
Montgomery_Int & mul_by_4(secure_vector< word > &ws)
Definition: monty.cpp:432
size_t size() const
Definition: monty.cpp:291
Montgomery_Int operator*(const Montgomery_Int &other) const
Definition: monty.cpp:352
BigInt mul(const BigInt &x, const BigInt &y, secure_vector< word > &ws) const
Definition: monty.cpp:73
#define BOTAN_DEBUG_ASSERT(expr)
Definition: assert.h:123
BigInt value() const
Definition: monty.cpp:306
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:346
BigInt inverse_mod(const BigInt &n, const BigInt &mod)
Definition: mod_inv.cpp:250
Montgomery_Int & operator+=(const Montgomery_Int &other)
Definition: monty.cpp:328
size_t size() const
Definition: bigint.h:580
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:758
Montgomery_Int mul(const Montgomery_Int &other, secure_vector< word > &ws) const
Definition: monty.cpp:358
void copy_mem(T *out, const T *in, size_t n)
Definition: mem_ops.h:133
Definition: alg_id.cpp:13
size_t sig_words() const
Definition: bigint.h:586
BigInt inv_mod_p(const BigInt &x) const
Definition: monty.cpp:50
Montgomery_Int & mul_by_3(secure_vector< word > &ws)
Definition: monty.cpp:426
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:120
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:334
Montgomery_Int & square_this(secure_vector< word > &ws)
Definition: monty.cpp:397
word monty_inverse(word a)
Definition: mod_inv.cpp:327
void grow_to(size_t n) const
Definition: bigint.h:636
Montgomery_Int & square_this_n_times(secure_vector< word > &ws, size_t n)
Definition: monty.cpp:390
BigInt reduce(const BigInt &x) const
Definition: reducer.cpp:37
Montgomery_Int & mul_by_2(secure_vector< word > &ws)
Definition: monty.cpp:420
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:56
std::vector< T, secure_allocator< T > > secure_vector
Definition: secmem.h:65
bool is_zero() const
Definition: monty.cpp:301
BigInt sqr(const BigInt &x, secure_vector< word > &ws) const
Definition: monty.cpp:176
Montgomery_Int additive_inverse() const
Definition: monty.cpp:415
Montgomery_Int square(secure_vector< word > &ws) const
Definition: monty.cpp:403
BigInt square(const BigInt &x) const
Definition: reducer.h:39
BigInt multiply(const BigInt &x, const BigInt &y) const
Definition: reducer.h:31