Coverage Report

Created: 2021-05-04 09:02

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