Coverage Report

Created: 2021-02-21 07:20

/src/botan/src/lib/math/bigint/bigint.cpp
Line
Count
Source (jump to first uncovered line)
1
/*
2
* BigInt Base
3
* (C) 1999-2011,2012,2014,2019 Jack Lloyd
4
*
5
* Botan is released under the Simplified BSD License (see license.txt)
6
*/
7
8
#include <botan/bigint.h>
9
#include <botan/internal/mp_core.h>
10
#include <botan/internal/rounding.h>
11
#include <botan/internal/bit_ops.h>
12
#include <botan/internal/ct_utils.h>
13
#include <botan/internal/loadstor.h>
14
15
namespace Botan {
16
17
BigInt::BigInt(const word words[], size_t length)
18
1.28k
   {
19
1.28k
   m_data.set_words(words, length);
20
1.28k
   }
21
22
/*
23
* Construct a BigInt from a regular number
24
*/
25
BigInt::BigInt(uint64_t n)
26
2.97M
   {
27
2.97M
   if(n > 0)
28
565k
      {
29
#if BOTAN_MP_WORD_BITS == 32
30
      m_data.set_word_at(0, static_cast<word>(n));
31
      m_data.set_word_at(1, static_cast<word>(n >> 32));
32
#else
33
565k
      m_data.set_word_at(0, n);
34
565k
#endif
35
565k
      }
36
37
2.97M
   }
38
39
/*
40
* Construct a BigInt of the specified size
41
*/
42
BigInt::BigInt(Sign s, size_t size)
43
14.6M
   {
44
14.6M
   m_data.set_size(size);
45
14.6M
   m_signedness = s;
46
14.6M
   }
47
48
/*
49
* Construct a BigInt from a string
50
*/
51
BigInt::BigInt(const std::string& str)
52
6.95k
   {
53
6.95k
   Base base = Decimal;
54
6.95k
   size_t markers = 0;
55
6.95k
   bool negative = false;
56
57
6.95k
   if(str.length() > 0 && str[0] == '-')
58
0
      {
59
0
      markers += 1;
60
0
      negative = true;
61
0
      }
62
63
6.95k
   if(str.length() > markers + 2 && str[markers    ] == '0' &&
64
6.95k
                                    str[markers + 1] == 'x')
65
6.95k
      {
66
6.95k
      markers += 2;
67
6.95k
      base = Hexadecimal;
68
6.95k
      }
69
70
6.95k
   *this = decode(cast_char_ptr_to_uint8(str.data()) + markers,
71
6.95k
                  str.length() - markers, base);
72
73
6.95k
   if(negative) set_sign(Negative);
74
6.95k
   else         set_sign(Positive);
75
6.95k
   }
76
77
BigInt::BigInt(const uint8_t input[], size_t length)
78
107k
   {
79
107k
   binary_decode(input, length);
80
107k
   }
81
82
/*
83
* Construct a BigInt from an encoded BigInt
84
*/
85
BigInt::BigInt(const uint8_t input[], size_t length, Base base)
86
0
   {
87
0
   *this = decode(input, length, base);
88
0
   }
89
90
BigInt::BigInt(const uint8_t buf[], size_t length, size_t max_bits)
91
491
   {
92
491
   if(8 * length > max_bits)
93
22
      length = (max_bits + 7) / 8;
94
95
491
   binary_decode(buf, length);
96
97
491
   if(8 * length > max_bits)
98
22
      *this >>= (8 - (max_bits % 8));
99
491
   }
100
101
/*
102
* Construct a BigInt from an encoded BigInt
103
*/
104
BigInt::BigInt(RandomNumberGenerator& rng, size_t bits, bool set_high_bit)
105
50.8k
   {
106
50.8k
   randomize(rng, bits, set_high_bit);
107
50.8k
   }
108
109
uint8_t BigInt::byte_at(size_t n) const
110
65.4k
   {
111
65.4k
   return get_byte(sizeof(word) - (n % sizeof(word)) - 1,
112
65.4k
                   word_at(n / sizeof(word)));
113
65.4k
   }
114
115
int32_t BigInt::cmp_word(word other) const
116
6.64M
   {
117
6.64M
   if(is_negative())
118
11.0k
      return -1; // other is positive ...
119
120
6.63M
   const size_t sw = this->sig_words();
121
6.63M
   if(sw > 1)
122
5.97M
      return 1; // must be larger since other is just one word ...
123
124
657k
   return bigint_cmp(this->data(), sw, &other, 1);
125
657k
   }
126
127
/*
128
* Comparison Function
129
*/
130
int32_t BigInt::cmp(const BigInt& other, bool check_signs) const
131
634k
   {
132
634k
   if(check_signs)
133
634k
      {
134
634k
      if(other.is_positive() && this->is_negative())
135
0
         return -1;
136
137
634k
      if(other.is_negative() && this->is_positive())
138
0
         return 1;
139
140
634k
      if(other.is_negative() && this->is_negative())
141
0
         return (-bigint_cmp(this->data(), this->size(),
142
0
                             other.data(), other.size()));
143
634k
      }
144
145
634k
   return bigint_cmp(this->data(), this->size(),
146
634k
                     other.data(), other.size());
147
634k
   }
148
149
bool BigInt::is_equal(const BigInt& other) const
150
236k
   {
151
236k
   if(this->sign() != other.sign())
152
0
      return false;
153
154
236k
   return bigint_ct_is_eq(this->data(), this->sig_words(),
155
236k
                          other.data(), other.sig_words()).is_set();
156
236k
   }
157
158
bool BigInt::is_less_than(const BigInt& other) const
159
5.62M
   {
160
5.62M
   if(this->is_negative() && other.is_positive())
161
77
      return true;
162
163
5.62M
   if(this->is_positive() && other.is_negative())
164
0
      return false;
165
166
5.62M
   if(other.is_negative() && this->is_negative())
167
0
      {
168
0
      return !bigint_ct_is_lt(other.data(), other.sig_words(),
169
0
                              this->data(), this->sig_words(), true).is_set();
170
0
      }
171
172
5.62M
   return bigint_ct_is_lt(this->data(), this->sig_words(),
173
5.62M
                          other.data(), other.sig_words()).is_set();
174
5.62M
   }
175
176
void BigInt::encode_words(word out[], size_t size) const
177
3.59M
   {
178
3.59M
   const size_t words = sig_words();
179
180
3.59M
   if(words > size)
181
0
      throw Encoding_Error("BigInt::encode_words value too large to encode");
182
183
3.59M
   clear_mem(out, size);
184
3.59M
   copy_mem(out, data(), words);
185
3.59M
   }
186
187
size_t BigInt::Data::calc_sig_words() const
188
122M
   {
189
122M
   const size_t sz = m_reg.size();
190
122M
   size_t sig = sz;
191
192
122M
   word sub = 1;
193
194
3.73G
   for(size_t i = 0; i != sz; ++i)
195
3.61G
      {
196
3.61G
      const word w = m_reg[sz - i - 1];
197
3.61G
      sub &= ct_is_zero(w);
198
3.61G
      sig -= sub;
199
3.61G
      }
200
201
   /*
202
   * This depends on the data so is poisoned, but unpoison it here as
203
   * later conditionals are made on the size.
204
   */
205
122M
   CT::unpoison(sig);
206
207
122M
   return sig;
208
122M
   }
209
210
/*
211
* Return bits {offset...offset+length}
212
*/
213
uint32_t BigInt::get_substring(size_t offset, size_t length) const
214
11.6M
   {
215
11.6M
   if(length == 0 || length > 32)
216
0
      throw Invalid_Argument("BigInt::get_substring invalid substring length");
217
218
11.6M
   const uint32_t mask = 0xFFFFFFFF >> (32 - length);
219
220
11.6M
   const size_t word_offset = offset / BOTAN_MP_WORD_BITS;
221
11.6M
   const size_t wshift = (offset % BOTAN_MP_WORD_BITS);
222
223
   /*
224
   * The substring is contained within one or at most two words. The
225
   * offset and length are not secret, so we can perform conditional
226
   * operations on those values.
227
   */
228
11.6M
   const word w0 = word_at(word_offset);
229
230
11.6M
   if(wshift == 0 || (offset + length) / BOTAN_MP_WORD_BITS == word_offset)
231
11.0M
      {
232
11.0M
      return static_cast<uint32_t>(w0 >> wshift) & mask;
233
11.0M
      }
234
591k
   else
235
591k
      {
236
591k
      const word w1 = word_at(word_offset + 1);
237
591k
      return static_cast<uint32_t>((w0 >> wshift) | (w1 << (BOTAN_MP_WORD_BITS - wshift))) & mask;
238
591k
      }
239
11.6M
   }
240
241
/*
242
* Convert this number to a uint32_t, if possible
243
*/
244
uint32_t BigInt::to_u32bit() const
245
0
   {
246
0
   if(is_negative())
247
0
      throw Encoding_Error("BigInt::to_u32bit: Number is negative");
248
0
   if(bits() > 32)
249
0
      throw Encoding_Error("BigInt::to_u32bit: Number is too big to convert");
250
251
0
   uint32_t out = 0;
252
0
   for(size_t i = 0; i != 4; ++i)
253
0
      out = (out << 8) | byte_at(3-i);
254
0
   return out;
255
0
   }
256
257
/*
258
* Set bit number n
259
*/
260
void BigInt::conditionally_set_bit(size_t n, bool set_it)
261
92.1M
   {
262
92.1M
   const size_t which = n / BOTAN_MP_WORD_BITS;
263
92.1M
   const word mask = static_cast<word>(set_it) << (n % BOTAN_MP_WORD_BITS);
264
92.1M
   m_data.set_word_at(which, word_at(which) | mask);
265
92.1M
   }
266
267
/*
268
* Clear bit number n
269
*/
270
void BigInt::clear_bit(size_t n)
271
0
   {
272
0
   const size_t which = n / BOTAN_MP_WORD_BITS;
273
274
0
   if(which < size())
275
0
      {
276
0
      const word mask = ~(static_cast<word>(1) << (n % BOTAN_MP_WORD_BITS));
277
0
      m_data.set_word_at(which, word_at(which) & mask);
278
0
      }
279
0
   }
280
281
size_t BigInt::bytes() const
282
156k
   {
283
156k
   return round_up(bits(), 8) / 8;
284
156k
   }
285
286
size_t BigInt::top_bits_free() const
287
7.14M
   {
288
7.14M
   const size_t words = sig_words();
289
290
7.14M
   const word top_word = word_at(words - 1);
291
7.14M
   const size_t bits_used = high_bit(top_word);
292
7.14M
   CT::unpoison(bits_used);
293
7.14M
   return BOTAN_MP_WORD_BITS - bits_used;
294
7.14M
   }
295
296
size_t BigInt::bits() const
297
579k
   {
298
579k
   const size_t words = sig_words();
299
300
579k
   if(words == 0)
301
13.7k
      return 0;
302
303
565k
   const size_t full_words = (words - 1) * BOTAN_MP_WORD_BITS;
304
565k
   const size_t top_bits = BOTAN_MP_WORD_BITS - top_bits_free();
305
306
565k
   return full_words + top_bits;
307
565k
   }
308
309
/*
310
* Return the negation of this number
311
*/
312
BigInt BigInt::operator-() const
313
9.99k
   {
314
9.99k
   BigInt x = (*this);
315
9.99k
   x.flip_sign();
316
9.99k
   return x;
317
9.99k
   }
318
319
size_t BigInt::reduce_below(const BigInt& p, secure_vector<word>& ws)
320
52.1M
   {
321
52.1M
   if(p.is_negative() || this->is_negative())
322
0
      throw Invalid_Argument("BigInt::reduce_below both values must be positive");
323
324
52.1M
   const size_t p_words = p.sig_words();
325
326
52.1M
   if(size() < p_words + 1)
327
6.71k
      grow_to(p_words + 1);
328
329
52.1M
   if(ws.size() < p_words + 1)
330
2.19M
      ws.resize(p_words + 1);
331
332
52.1M
   clear_mem(ws.data(), ws.size());
333
334
52.1M
   size_t reductions = 0;
335
336
52.1M
   for(;;)
337
133M
      {
338
133M
      word borrow = bigint_sub3(ws.data(), data(), p_words + 1, p.data(), p_words);
339
133M
      if(borrow)
340
52.1M
         break;
341
342
81.1M
      ++reductions;
343
81.1M
      swap_reg(ws);
344
81.1M
      }
345
346
52.1M
   return reductions;
347
52.1M
   }
348
349
void BigInt::ct_reduce_below(const BigInt& mod, secure_vector<word>& ws, size_t bound)
350
5.43M
   {
351
5.43M
   if(mod.is_negative() || this->is_negative())
352
0
      throw Invalid_Argument("BigInt::ct_reduce_below both values must be positive");
353
354
5.43M
   const size_t mod_words = mod.sig_words();
355
356
5.43M
   grow_to(mod_words);
357
358
5.43M
   const size_t sz = size();
359
360
5.43M
   ws.resize(sz);
361
362
5.43M
   clear_mem(ws.data(), sz);
363
364
16.2M
   for(size_t i = 0; i != bound; ++i)
365
10.8M
      {
366
10.8M
      word borrow = bigint_sub3(ws.data(), data(), sz, mod.data(), mod_words);
367
368
10.8M
      CT::Mask<word>::is_zero(borrow).select_n(mutable_data(), ws.data(), data(), sz);
369
10.8M
      }
370
5.43M
   }
371
372
/*
373
* Return the absolute value of this number
374
*/
375
BigInt BigInt::abs() const
376
1.19k
   {
377
1.19k
   BigInt x = (*this);
378
1.19k
   x.set_sign(Positive);
379
1.19k
   return x;
380
1.19k
   }
381
382
void BigInt::binary_encode(uint8_t buf[]) const
383
37.0k
   {
384
37.0k
   this->binary_encode(buf, bytes());
385
37.0k
   }
386
387
/*
388
* Encode this number into bytes
389
*/
390
void BigInt::binary_encode(uint8_t output[], size_t len) const
391
87.1k
   {
392
87.1k
   const size_t full_words = len / sizeof(word);
393
87.1k
   const size_t extra_bytes = len % sizeof(word);
394
395
651k
   for(size_t i = 0; i != full_words; ++i)
396
564k
      {
397
564k
      const word w = word_at(i);
398
564k
      store_be(w, output + (len - (i+1)*sizeof(word)));
399
564k
      }
400
401
87.1k
   if(extra_bytes > 0)
402
48.3k
      {
403
48.3k
      const word w = word_at(full_words);
404
405
172k
      for(size_t i = 0; i != extra_bytes; ++i)
406
124k
         {
407
124k
         output[extra_bytes - i - 1] = get_byte(sizeof(word) - i - 1, w);
408
124k
         }
409
48.3k
      }
410
87.1k
   }
411
412
/*
413
* Set this number to the value in buf
414
*/
415
void BigInt::binary_decode(const uint8_t buf[], size_t length)
416
551k
   {
417
551k
   clear();
418
419
551k
   const size_t full_words = length / sizeof(word);
420
551k
   const size_t extra_bytes = length % sizeof(word);
421
422
339k
   secure_vector<word> reg((round_up(full_words + (extra_bytes > 0 ? 1 : 0), 8)));
423
424
3.85M
   for(size_t i = 0; i != full_words; ++i)
425
3.29M
      {
426
3.29M
      reg[i] = load_be<word>(buf + length - sizeof(word)*(i+1), 0);
427
3.29M
      }
428
429
551k
   if(extra_bytes > 0)
430
211k
      {
431
546k
      for(size_t i = 0; i != extra_bytes; ++i)
432
334k
         reg[full_words] = (reg[full_words] << 8) | buf[i];
433
211k
      }
434
435
551k
   m_data.swap(reg);
436
551k
   }
437
438
void BigInt::ct_cond_add(bool predicate, const BigInt& value)
439
817k
   {
440
817k
   if(this->is_negative() || value.is_negative())
441
0
      throw Invalid_Argument("BigInt::ct_cond_add requires both values to be positive");
442
817k
   this->grow_to(1 + value.sig_words());
443
444
817k
   bigint_cnd_add(static_cast<word>(predicate),
445
817k
                  this->mutable_data(), this->size(),
446
817k
                  value.data(), value.sig_words());
447
817k
   }
448
449
void BigInt::ct_cond_swap(bool predicate, BigInt& other)
450
47.1M
   {
451
47.1M
   const size_t max_words = std::max(size(), other.size());
452
47.1M
   grow_to(max_words);
453
47.1M
   other.grow_to(max_words);
454
455
47.1M
   bigint_cnd_swap(predicate, this->mutable_data(), other.mutable_data(), max_words);
456
47.1M
   }
457
458
void BigInt::cond_flip_sign(bool predicate)
459
15.4M
   {
460
   // This code is assuming Negative == 0, Positive == 1
461
462
15.4M
   const auto mask = CT::Mask<uint8_t>::expand(predicate);
463
464
15.4M
   const uint8_t current_sign = static_cast<uint8_t>(sign());
465
466
15.4M
   const uint8_t new_sign = mask.select(current_sign ^ 1, current_sign);
467
468
15.4M
   set_sign(static_cast<Sign>(new_sign));
469
15.4M
   }
470
471
void BigInt::ct_cond_assign(bool predicate, const BigInt& other)
472
1.24M
   {
473
1.24M
   const size_t t_words = size();
474
1.24M
   const size_t o_words = other.size();
475
476
1.24M
   if(o_words < t_words)
477
21.7k
      grow_to(o_words);
478
479
1.24M
   const size_t r_words = std::max(t_words, o_words);
480
481
1.24M
   const auto mask = CT::Mask<word>::expand(predicate);
482
483
27.1M
   for(size_t i = 0; i != r_words; ++i)
484
25.8M
      {
485
25.8M
      const word o_word = other.word_at(i);
486
25.8M
      const word t_word = this->word_at(i);
487
25.8M
      this->set_word_at(i, mask.select(o_word, t_word));
488
25.8M
      }
489
490
1.24M
   const bool different_sign = sign() != other.sign();
491
1.24M
   cond_flip_sign(predicate && different_sign);
492
1.24M
   }
493
494
#if defined(BOTAN_HAS_VALGRIND)
495
void BigInt::const_time_poison() const
496
   {
497
   CT::poison(m_data.const_data(), m_data.size());
498
   }
499
500
void BigInt::const_time_unpoison() const
501
   {
502
   CT::unpoison(m_data.const_data(), m_data.size());
503
   }
504
#endif
505
506
}