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