Coverage Report

Created: 2020-02-14 15:38

/src/botan/src/lib/math/numbertheory/monty.cpp
Line
Count
Source (jump to first uncovered line)
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
81.4k
   {
16
81.4k
   if(p.is_even() || p < 3)
17
24
      throw Invalid_Argument("Montgomery_Params invalid modulus");
18
81.3k
19
81.3k
   m_p = p;
20
81.3k
   m_p_words = m_p.sig_words();
21
81.3k
   m_p_dash = monty_inverse(m_p.word_at(0));
22
81.3k
23
81.3k
   const BigInt r = BigInt::power_of_2(m_p_words * BOTAN_MP_WORD_BITS);
24
81.3k
25
81.3k
   m_r1 = mod_p.reduce(r);
26
81.3k
   m_r2 = mod_p.square(m_r1);
27
81.3k
   m_r3 = mod_p.multiply(m_r1, m_r2);
28
81.3k
   }
29
30
Montgomery_Params::Montgomery_Params(const BigInt& p)
31
6.50k
   {
32
6.50k
33
6.50k
   if(p.is_negative() || p.is_even())
34
0
      throw Invalid_Argument("Montgomery_Params invalid modulus");
35
6.50k
36
6.50k
   m_p = p;
37
6.50k
   m_p_words = m_p.sig_words();
38
6.50k
   m_p_dash = monty_inverse(m_p.word_at(0));
39
6.50k
40
6.50k
   const BigInt r = BigInt::power_of_2(m_p_words * BOTAN_MP_WORD_BITS);
41
6.50k
42
6.50k
   // It might be faster to use ct_modulo here vs setting up Barrett reduction?
43
6.50k
   Modular_Reducer mod_p(p);
44
6.50k
45
6.50k
   m_r1 = mod_p.reduce(r);
46
6.50k
   m_r2 = mod_p.square(m_r1);
47
6.50k
   m_r3 = mod_p.multiply(m_r1, m_r2);
48
6.50k
   }
49
50
BigInt Montgomery_Params::inv_mod_p(const BigInt& x) const
51
0
   {
52
0
   return ct_inverse_mod_odd_modulus(x, p());
53
0
   }
54
55
BigInt Montgomery_Params::redc(const BigInt& x, secure_vector<word>& ws) const
56
92.4k
   {
57
92.4k
   const size_t output_size = 2*m_p_words + 2;
58
92.4k
59
92.4k
   if(ws.size() < output_size)
60
92.4k
      ws.resize(output_size);
61
92.4k
62
92.4k
   BigInt z = x;
63
92.4k
   z.grow_to(output_size);
64
92.4k
65
92.4k
   bigint_monty_redc(z.mutable_data(),
66
92.4k
                     m_p.data(), m_p_words, m_p_dash,
67
92.4k
                     ws.data(), ws.size());
68
92.4k
69
92.4k
   return z;
70
92.4k
   }
71
72
BigInt Montgomery_Params::mul(const BigInt& x, const BigInt& y,
73
                              secure_vector<word>& ws) const
74
1.30M
   {
75
1.30M
   const size_t output_size = 2*m_p_words + 2;
76
1.30M
77
1.30M
   if(ws.size() < output_size)
78
1.30M
      ws.resize(output_size);
79
1.30M
80
1.30M
   BOTAN_DEBUG_ASSERT(x.sig_words() <= m_p_words);
81
1.30M
   BOTAN_DEBUG_ASSERT(y.sig_words() <= m_p_words);
82
1.30M
83
1.30M
   BigInt z(BigInt::Positive, output_size);
84
1.30M
   bigint_mul(z.mutable_data(), z.size(),
85
1.30M
              x.data(), x.size(), std::min(m_p_words, x.size()),
86
1.30M
              y.data(), y.size(), std::min(m_p_words, y.size()),
87
1.30M
              ws.data(), ws.size());
88
1.30M
89
1.30M
   bigint_monty_redc(z.mutable_data(),
90
1.30M
                     m_p.data(), m_p_words, m_p_dash,
91
1.30M
                     ws.data(), ws.size());
92
1.30M
93
1.30M
   return z;
94
1.30M
   }
95
96
BigInt Montgomery_Params::mul(const BigInt& x,
97
                              const secure_vector<word>& y,
98
                              secure_vector<word>& ws) const
99
0
   {
100
0
   const size_t output_size = 2*m_p_words + 2;
101
0
   if(ws.size() < output_size)
102
0
      ws.resize(output_size);
103
0
   BigInt z(BigInt::Positive, output_size);
104
0
105
0
   BOTAN_DEBUG_ASSERT(x.sig_words() <= m_p_words);
106
0
107
0
   bigint_mul(z.mutable_data(), z.size(),
108
0
              x.data(), x.size(), std::min(m_p_words, x.size()),
109
0
              y.data(), y.size(), std::min(m_p_words, y.size()),
110
0
              ws.data(), ws.size());
111
0
112
0
   bigint_monty_redc(z.mutable_data(),
113
0
                     m_p.data(), m_p_words, m_p_dash,
114
0
                     ws.data(), ws.size());
115
0
116
0
   return z;
117
0
   }
118
119
void Montgomery_Params::mul_by(BigInt& x,
120
                               const secure_vector<word>& y,
121
                               secure_vector<word>& ws) const
122
2.81M
   {
123
2.81M
   const size_t output_size = 2*m_p_words + 2;
124
2.81M
125
2.81M
   if(ws.size() < 2*output_size)
126
0
      ws.resize(2*output_size);
127
2.81M
128
2.81M
   word* z_data = &ws[0];
129
2.81M
   word* ws_data = &ws[output_size];
130
2.81M
131
2.81M
   BOTAN_DEBUG_ASSERT(x.sig_words() <= m_p_words);
132
2.81M
133
2.81M
   bigint_mul(z_data, output_size,
134
2.81M
              x.data(), x.size(), std::min(m_p_words, x.size()),
135
2.81M
              y.data(), y.size(), std::min(m_p_words, y.size()),
136
2.81M
              ws_data, output_size);
137
2.81M
138
2.81M
   bigint_monty_redc(z_data,
139
2.81M
                     m_p.data(), m_p_words, m_p_dash,
140
2.81M
                     ws_data, output_size);
141
2.81M
142
2.81M
   if(x.size() < output_size)
143
0
      x.grow_to(output_size);
144
2.81M
   copy_mem(x.mutable_data(), z_data, output_size);
145
2.81M
   }
146
147
void Montgomery_Params::mul_by(BigInt& x,
148
                               const BigInt& y,
149
                               secure_vector<word>& ws) const
150
151k
   {
151
151k
   const size_t output_size = 2*m_p_words + 2;
152
151k
153
151k
   if(ws.size() < 2*output_size)
154
147
      ws.resize(2*output_size);
155
151k
156
151k
   word* z_data = &ws[0];
157
151k
   word* ws_data = &ws[output_size];
158
151k
159
151k
   BOTAN_DEBUG_ASSERT(x.sig_words() <= m_p_words);
160
151k
161
151k
   bigint_mul(z_data, output_size,
162
151k
              x.data(), x.size(), std::min(m_p_words, x.size()),
163
151k
              y.data(), y.size(), std::min(m_p_words, y.size()),
164
151k
              ws_data, output_size);
165
151k
166
151k
   bigint_monty_redc(z_data,
167
151k
                     m_p.data(), m_p_words, m_p_dash,
168
151k
                     ws_data, output_size);
169
151k
170
151k
   if(x.size() < output_size)
171
130
      x.grow_to(output_size);
172
151k
   copy_mem(x.mutable_data(), z_data, output_size);
173
151k
   }
174
175
BigInt Montgomery_Params::sqr(const BigInt& x, secure_vector<word>& ws) const
176
368
   {
177
368
   const size_t output_size = 2*m_p_words + 2;
178
368
179
368
   if(ws.size() < output_size)
180
184
      ws.resize(output_size);
181
368
182
368
   BigInt z(BigInt::Positive, output_size);
183
368
184
368
   BOTAN_DEBUG_ASSERT(x.sig_words() <= m_p_words);
185
368
186
368
   bigint_sqr(z.mutable_data(), z.size(),
187
368
              x.data(), x.size(), std::min(m_p_words, x.size()),
188
368
              ws.data(), ws.size());
189
368
190
368
   bigint_monty_redc(z.mutable_data(),
191
368
                     m_p.data(), m_p_words, m_p_dash,
192
368
                     ws.data(), ws.size());
193
368
194
368
   return z;
195
368
   }
196
197
void Montgomery_Params::square_this(BigInt& x,
198
                                    secure_vector<word>& ws) const
199
11.7M
   {
200
11.7M
   const size_t output_size = 2*m_p_words + 2;
201
11.7M
202
11.7M
   if(ws.size() < 2*output_size)
203
41.7k
      ws.resize(2*output_size);
204
11.7M
205
11.7M
   word* z_data = &ws[0];
206
11.7M
   word* ws_data = &ws[output_size];
207
11.7M
208
11.7M
   BOTAN_DEBUG_ASSERT(x.sig_words() <= m_p_words);
209
11.7M
210
11.7M
   bigint_sqr(z_data, output_size,
211
11.7M
              x.data(), x.size(), std::min(m_p_words, x.size()),
212
11.7M
              ws_data, output_size);
213
11.7M
214
11.7M
   bigint_monty_redc(z_data,
215
11.7M
                     m_p.data(), m_p_words, m_p_dash,
216
11.7M
                     ws_data, output_size);
217
11.7M
218
11.7M
   if(x.size() < output_size)
219
41.7k
      x.grow_to(output_size);
220
11.7M
   copy_mem(x.mutable_data(), z_data, output_size);
221
11.7M
   }
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
1.39M
   {
228
1.39M
   if(redc_needed == false)
229
1.30M
      {
230
1.30M
      m_v = v;
231
1.30M
      }
232
93.1k
   else
233
93.1k
      {
234
93.1k
      BOTAN_ASSERT_NOMSG(m_v < m_params->p());
235
93.1k
      secure_vector<word> ws;
236
93.1k
      m_v = m_params->mul(v, m_params->R2(), ws);
237
93.1k
      }
238
1.39M
   }
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
0
   {
246
0
   if(redc_needed)
247
0
      {
248
0
      BOTAN_ASSERT_NOMSG(m_v < m_params->p());
249
0
      secure_vector<word> ws;
250
0
      m_v = m_params->mul(m_v, m_params->R2(), ws);
251
0
      }
252
0
   }
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
85.9k
   {
260
85.9k
   if(redc_needed)
261
0
      {
262
0
      BOTAN_ASSERT_NOMSG(m_v < m_params->p());
263
0
      secure_vector<word> ws;
264
0
      m_v = m_params->mul(m_v, m_params->R2(), ws);
265
0
      }
266
85.9k
   }
267
268
void Montgomery_Int::fix_size()
269
1.39M
   {
270
1.39M
   const size_t p_words = m_params->p_words();
271
1.39M
272
1.39M
   if(m_v.sig_words() > p_words)
273
4
      throw Internal_Error("Montgomery_Int::fix_size v too large");
274
1.39M
275
1.39M
   secure_vector<word>& w = m_v.get_word_vector();
276
1.39M
277
1.39M
   if(w.size() != p_words)
278
1.39M
      {
279
1.39M
      w.resize(p_words);
280
1.39M
      w.shrink_to_fit();
281
1.39M
      }
282
1.39M
   }
283
284
bool Montgomery_Int::operator==(const Montgomery_Int& other) const
285
0
   {
286
0
   return m_v == other.m_v && m_params->p() == other.m_params->p();
287
0
   }
288
289
std::vector<uint8_t> Montgomery_Int::serialize() const
290
0
   {
291
0
   std::vector<uint8_t> v(size());
292
0
   BigInt::encode_1363(v.data(), v.size(), value());
293
0
   return v;
294
0
   }
295
296
size_t Montgomery_Int::size() const
297
0
   {
298
0
   return m_params->p().bytes();
299
0
   }
300
301
bool Montgomery_Int::is_one() const
302
0
   {
303
0
   return m_v == m_params->R1();
304
0
   }
305
306
bool Montgomery_Int::is_zero() const
307
0
   {
308
0
   return m_v.is_zero();
309
0
   }
310
311
BigInt Montgomery_Int::value() const
312
92.4k
   {
313
92.4k
   secure_vector<word> ws;
314
92.4k
   return m_params->redc(m_v, ws);
315
92.4k
   }
316
317
Montgomery_Int Montgomery_Int::operator+(const Montgomery_Int& other) const
318
0
   {
319
0
   secure_vector<word> ws;
320
0
   BigInt z = m_v;
321
0
   z.mod_add(other.m_v, m_params->p(), ws);
322
0
   return Montgomery_Int(m_params, z, false);
323
0
   }
324
325
Montgomery_Int Montgomery_Int::operator-(const Montgomery_Int& other) const
326
0
   {
327
0
   secure_vector<word> ws;
328
0
   BigInt z = m_v;
329
0
   z.mod_sub(other.m_v, m_params->p(), ws);
330
0
   return Montgomery_Int(m_params, z, false);
331
0
   }
332
333
Montgomery_Int& Montgomery_Int::operator+=(const Montgomery_Int& other)
334
0
   {
335
0
   secure_vector<word> ws;
336
0
   return this->add(other, ws);
337
0
   }
338
339
Montgomery_Int& Montgomery_Int::add(const Montgomery_Int& other, secure_vector<word>& ws)
340
0
   {
341
0
   m_v.mod_add(other.m_v, m_params->p(), ws);
342
0
   return (*this);
343
0
   }
344
345
Montgomery_Int& Montgomery_Int::operator-=(const Montgomery_Int& other)
346
0
   {
347
0
   secure_vector<word> ws;
348
0
   return this->sub(other, ws);
349
0
   }
350
351
Montgomery_Int& Montgomery_Int::sub(const Montgomery_Int& other, secure_vector<word>& ws)
352
0
   {
353
0
   m_v.mod_sub(other.m_v, m_params->p(), ws);
354
0
   return (*this);
355
0
   }
356
357
Montgomery_Int Montgomery_Int::operator*(const Montgomery_Int& other) const
358
1.21M
   {
359
1.21M
   secure_vector<word> ws;
360
1.21M
   return Montgomery_Int(m_params, m_params->mul(m_v, other.m_v, ws), false);
361
1.21M
   }
362
363
Montgomery_Int Montgomery_Int::mul(const Montgomery_Int& other,
364
                                   secure_vector<word>& ws) const
365
2.02k
   {
366
2.02k
   return Montgomery_Int(m_params, m_params->mul(m_v, other.m_v, ws), false);
367
2.02k
   }
368
369
Montgomery_Int& Montgomery_Int::mul_by(const Montgomery_Int& other,
370
                                       secure_vector<word>& ws)
371
151k
   {
372
151k
   m_params->mul_by(m_v, other.m_v, ws);
373
151k
   return (*this);
374
151k
   }
375
376
Montgomery_Int& Montgomery_Int::mul_by(const secure_vector<word>& other,
377
                                       secure_vector<word>& ws)
378
2.81M
   {
379
2.81M
   m_params->mul_by(m_v, other, ws);
380
2.81M
   return (*this);
381
2.81M
   }
382
383
Montgomery_Int& Montgomery_Int::operator*=(const Montgomery_Int& other)
384
0
   {
385
0
   secure_vector<word> ws;
386
0
   return mul_by(other, ws);
387
0
   }
388
389
Montgomery_Int& Montgomery_Int::operator*=(const secure_vector<word>& other)
390
0
   {
391
0
   secure_vector<word> ws;
392
0
   return mul_by(other, ws);
393
0
   }
394
395
Montgomery_Int& Montgomery_Int::square_this_n_times(secure_vector<word>& ws, size_t n)
396
3.17M
   {
397
14.7M
   for(size_t i = 0; i != n; ++i)
398
11.6M
      m_params->square_this(m_v, ws);
399
3.17M
   return (*this);
400
3.17M
   }
401
402
Montgomery_Int& Montgomery_Int::square_this(secure_vector<word>& ws)
403
148k
   {
404
148k
   m_params->square_this(m_v, ws);
405
148k
   return (*this);
406
148k
   }
407
408
Montgomery_Int Montgomery_Int::square(secure_vector<word>& ws) const
409
368
   {
410
368
   return Montgomery_Int(m_params, m_params->sqr(m_v, ws), false);
411
368
   }
412
413
Montgomery_Int Montgomery_Int::multiplicative_inverse() const
414
0
   {
415
0
   secure_vector<word> ws;
416
0
   const BigInt iv = m_params->mul(m_params->inv_mod_p(m_v), m_params->R3(), ws);
417
0
   return Montgomery_Int(m_params, iv, false);
418
0
   }
419
420
Montgomery_Int Montgomery_Int::additive_inverse() const
421
0
   {
422
0
   return Montgomery_Int(m_params, m_params->p()) - (*this);
423
0
   }
424
425
Montgomery_Int& Montgomery_Int::mul_by_2(secure_vector<word>& ws)
426
0
   {
427
0
   m_v.mod_mul(2, m_params->p(), ws);
428
0
   return (*this);
429
0
   }
430
431
Montgomery_Int& Montgomery_Int::mul_by_3(secure_vector<word>& ws)
432
0
   {
433
0
   m_v.mod_mul(3, m_params->p(), ws);
434
0
   return (*this);
435
0
   }
436
437
Montgomery_Int& Montgomery_Int::mul_by_4(secure_vector<word>& ws)
438
0
   {
439
0
   m_v.mod_mul(4, m_params->p(), ws);
440
0
   return (*this);
441
0
   }
442
443
Montgomery_Int& Montgomery_Int::mul_by_8(secure_vector<word>& ws)
444
0
   {
445
0
   m_v.mod_mul(8, m_params->p(), ws);
446
0
   return (*this);
447
0
   }
448
449
}