Coverage Report

Created: 2020-05-23 13:54

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