Coverage Report

Created: 2022-06-23 06:44

/src/botan/build/include/botan/bigint.h
Line
Count
Source (jump to first uncovered line)
1
/*
2
* BigInt
3
* (C) 1999-2008,2012,2018 Jack Lloyd
4
*     2007 FlexSecure
5
*
6
* Botan is released under the Simplified BSD License (see license.txt)
7
*/
8
9
#ifndef BOTAN_BIGINT_H_
10
#define BOTAN_BIGINT_H_
11
12
#include <botan/types.h>
13
#include <botan/secmem.h>
14
#include <botan/exceptn.h>
15
#include <iosfwd>
16
17
namespace Botan {
18
19
class RandomNumberGenerator;
20
21
/**
22
* Arbitrary precision integer
23
*/
24
class BOTAN_PUBLIC_API(2,0) BigInt final
25
   {
26
   public:
27
     /**
28
     * Base enumerator for encoding and decoding
29
     */
30
     enum Base { Decimal = 10, Hexadecimal = 16, Binary = 256 };
31
32
     /**
33
     * Sign symbol definitions for positive and negative numbers
34
     */
35
     enum Sign { Negative = 0, Positive = 1 };
36
37
     /**
38
     * Create empty (zero) BigInt
39
     */
40
59.8M
     BigInt() = default;
41
42
     /**
43
     * Create a 0-value BigInt
44
     */
45
2.74M
     static BigInt zero() { return BigInt(); }
46
47
     /**
48
     * Create a 1-value BigInt
49
     */
50
23.8k
     static BigInt one() { return BigInt::from_word(1); }
51
52
     /**
53
     * Create BigInt from an unsigned 64 bit integer
54
     * @param n initial value of this BigInt
55
     */
56
     static BigInt from_u64(uint64_t n);
57
58
     /**
59
     * Create BigInt from a word (limb)
60
     * @param n initial value of this BigInt
61
     */
62
     static BigInt from_word(word n);
63
64
     /**
65
     * Create BigInt from a signed 32 bit integer
66
     * @param n initial value of this BigInt
67
     */
68
     static BigInt from_s32(int32_t n);
69
70
     /**
71
     * Create BigInt from an unsigned 64 bit integer
72
     * @param n initial value of this BigInt
73
     */
74
     BigInt(uint64_t n);
75
76
     /**
77
     * Copy Constructor
78
     * @param other the BigInt to copy
79
     */
80
15.7M
     BigInt(const BigInt& other) = default;
81
82
     /**
83
     * Create BigInt from a string. If the string starts with 0x the
84
     * rest of the string will be interpreted as hexadecimal digits.
85
     * Otherwise, it will be interpreted as a decimal number.
86
     *
87
     * @param str the string to parse for an integer value
88
     */
89
     explicit BigInt(const std::string& str);
90
91
     /**
92
     * Create a BigInt from an integer in a byte array
93
     * @param buf the byte array holding the value
94
     * @param length size of buf
95
     */
96
     BigInt(const uint8_t buf[], size_t length);
97
98
     /**
99
     * Create a BigInt from an integer in a byte array
100
     * @param vec the byte vector holding the value
101
     */
102
     template<typename Alloc>
103
0
     explicit BigInt(const std::vector<uint8_t, Alloc>& vec) : BigInt(vec.data(), vec.size()) {}
Unexecuted instantiation: Botan::BigInt::BigInt<std::__1::allocator<unsigned char> >(std::__1::vector<unsigned char, std::__1::allocator<unsigned char> > const&)
Unexecuted instantiation: Botan::BigInt::BigInt<Botan::secure_allocator<unsigned char> >(std::__1::vector<unsigned char, Botan::secure_allocator<unsigned char> > const&)
104
105
     /**
106
     * Create a BigInt from an integer in a byte array
107
     * @param buf the byte array holding the value
108
     * @param length size of buf
109
     * @param base is the number base of the integer in buf
110
     */
111
     BigInt(const uint8_t buf[], size_t length, Base base);
112
113
     /**
114
     * Create a BigInt from an integer in a byte array
115
     * @param buf the byte array holding the value
116
     * @param length size of buf
117
     * @param max_bits if the resulting integer is more than max_bits,
118
     *        it will be shifted so it is at most max_bits in length.
119
     */
120
     static BigInt from_bytes_with_max_bits(const uint8_t buf[], size_t length,
121
                                            size_t max_bits);
122
123
     /**
124
     * \brief Create a random BigInt of the specified size
125
     *
126
     * @param rng random number generator
127
     * @param bits size in bits
128
     * @param set_high_bit if true, the highest bit is always set
129
     *
130
     * @see randomize
131
     */
132
     BigInt(RandomNumberGenerator& rng, size_t bits, bool set_high_bit = true);
133
134
     /**
135
     * Create BigInt of specified size, all zeros
136
     * @param n size of the internal register in words
137
     */
138
     static BigInt with_capacity(size_t n);
139
140
     /**
141
     * Move constructor
142
     */
143
     BigInt(BigInt&& other)
144
4.21M
        {
145
4.21M
        this->swap(other);
146
4.21M
        }
147
148
80.2M
     ~BigInt() { const_time_unpoison(); }
149
150
     /**
151
     * Move assignment
152
     */
153
     BigInt& operator=(BigInt&& other)
154
19.0M
        {
155
19.0M
        if(this != &other)
156
19.0M
           this->swap(other);
157
158
19.0M
        return (*this);
159
19.0M
        }
160
161
     /**
162
     * Copy assignment
163
     */
164
36.8M
     BigInt& operator=(const BigInt&) = default;
165
166
     /**
167
     * Swap this value with another
168
     * @param other BigInt to swap values with
169
     */
170
     void swap(BigInt& other)
171
154M
        {
172
154M
        m_data.swap(other.m_data);
173
154M
        std::swap(m_signedness, other.m_signedness);
174
154M
        }
175
176
     void swap_reg(secure_vector<word>& reg)
177
128M
        {
178
128M
        m_data.swap(reg);
179
        // sign left unchanged
180
128M
        }
181
182
     /**
183
     * += operator
184
     * @param y the BigInt to add to this
185
     */
186
     BigInt& operator+=(const BigInt& y)
187
3.91M
        {
188
3.91M
        return add(y.data(), y.sig_words(), y.sign());
189
3.91M
        }
190
191
     /**
192
     * += operator
193
     * @param y the word to add to this
194
     */
195
     BigInt& operator+=(word y)
196
4.80k
        {
197
4.80k
        return add(&y, 1, Positive);
198
4.80k
        }
199
200
     /**
201
     * -= operator
202
     * @param y the BigInt to subtract from this
203
     */
204
     BigInt& operator-=(const BigInt& y)
205
5.43M
        {
206
5.43M
        return sub(y.data(), y.sig_words(), y.sign());
207
5.43M
        }
208
209
     /**
210
     * -= operator
211
     * @param y the word to subtract from this
212
     */
213
     BigInt& operator-=(word y)
214
3.43k
        {
215
3.43k
        return sub(&y, 1, Positive);
216
3.43k
        }
217
218
     /**
219
     * *= operator
220
     * @param y the BigInt to multiply with this
221
     */
222
     BigInt& operator*=(const BigInt& y);
223
224
     /**
225
     * *= operator
226
     * @param y the word to multiply with this
227
     */
228
     BigInt& operator*=(word y);
229
230
     /**
231
     * /= operator
232
     * @param y the BigInt to divide this by
233
     */
234
     BigInt& operator/=(const BigInt& y);
235
236
     /**
237
     * Modulo operator
238
     * @param y the modulus to reduce this by
239
     */
240
     BigInt& operator%=(const BigInt& y);
241
242
     /**
243
     * Modulo operator
244
     * @param y the modulus (word) to reduce this by
245
     */
246
     word    operator%=(word y);
247
248
     /**
249
     * Left shift operator
250
     * @param shift the number of bits to shift this left by
251
     */
252
     BigInt& operator<<=(size_t shift);
253
254
     /**
255
     * Right shift operator
256
     * @param shift the number of bits to shift this right by
257
     */
258
     BigInt& operator>>=(size_t shift);
259
260
     /**
261
     * Increment operator
262
     */
263
0
     BigInt& operator++() { return (*this += 1); }
264
265
     /**
266
     * Decrement operator
267
     */
268
0
     BigInt& operator--() { return (*this -= 1); }
269
270
     /**
271
     * Postfix increment operator
272
     */
273
0
     BigInt  operator++(int) { BigInt x = (*this); ++(*this); return x; }
274
275
     /**
276
     * Postfix decrement operator
277
     */
278
0
     BigInt  operator--(int) { BigInt x = (*this); --(*this); return x; }
279
280
     /**
281
     * Unary negation operator
282
     * @return negative this
283
     */
284
     BigInt operator-() const;
285
286
     /**
287
     * ! operator
288
     * @return true iff this is zero, otherwise false
289
     */
290
0
     bool operator !() const { return (!is_nonzero()); }
291
292
     static BigInt add2(const BigInt& x, const word y[], size_t y_words, Sign y_sign);
293
294
     BigInt& add(const word y[], size_t y_words, Sign sign);
295
296
     BigInt& sub(const word y[], size_t y_words, Sign sign)
297
5.43M
        {
298
5.43M
        return add(y, y_words, sign == Positive ? Negative : Positive);
299
5.43M
        }
300
301
     /**
302
     * Multiply this with y
303
     * @param y the BigInt to multiply with this
304
     * @param ws a temp workspace
305
     */
306
     BigInt& mul(const BigInt& y, secure_vector<word>& ws);
307
308
     /**
309
     * Square value of *this
310
     * @param ws a temp workspace
311
     */
312
     BigInt& square(secure_vector<word>& ws);
313
314
     /**
315
     * Set *this to y - *this
316
     * @param y the BigInt to subtract from as a sequence of words
317
     * @param y_words length of y in words
318
     * @param ws a temp workspace
319
     */
320
     BigInt& rev_sub(const word y[], size_t y_words, secure_vector<word>& ws);
321
322
     /**
323
     * Set *this to (*this + y) % mod
324
     * This function assumes *this is >= 0 && < mod
325
     * @param y the BigInt to add - assumed y >= 0 and y < mod
326
     * @param mod the positive modulus
327
     * @param ws a temp workspace
328
     */
329
     BigInt& mod_add(const BigInt& y, const BigInt& mod, secure_vector<word>& ws);
330
331
     /**
332
     * Set *this to (*this - y) % mod
333
     * This function assumes *this is >= 0 && < mod
334
     * @param y the BigInt to subtract - assumed y >= 0 and y < mod
335
     * @param mod the positive modulus
336
     * @param ws a temp workspace
337
     */
338
     BigInt& mod_sub(const BigInt& y, const BigInt& mod, secure_vector<word>& ws);
339
340
     /**
341
     * Set *this to (*this * y) % mod
342
     * This function assumes *this is >= 0 && < mod
343
     * y should be small, less than 16
344
     * @param y the small integer to multiply by
345
     * @param mod the positive modulus
346
     * @param ws a temp workspace
347
     */
348
     BigInt& mod_mul(uint8_t y, const BigInt& mod, secure_vector<word>& ws);
349
350
     /**
351
     * Return *this % mod
352
     *
353
     * Assumes that *this is (if anything) only slightly larger than
354
     * mod and performs repeated subtractions. It should not be used if
355
     * *this is much larger than mod, instead use modulo operator.
356
     */
357
     size_t reduce_below(const BigInt& mod, secure_vector<word> &ws);
358
359
     /**
360
     * Return *this % mod
361
     *
362
     * Assumes that *this is (if anything) only slightly larger than mod and
363
     * performs repeated subtractions. It should not be used if *this is much
364
     * larger than mod, instead use modulo operator.
365
     *
366
     * Performs exactly bound subtractions, so if *this is >= bound*mod then the
367
     * result will not be fully reduced. If bound is zero, nothing happens.
368
     */
369
     void ct_reduce_below(const BigInt& mod, secure_vector<word> &ws, size_t bound);
370
371
     /**
372
     * Zeroize the BigInt. The size of the underlying register is not
373
     * modified.
374
     */
375
2.18M
     void clear() { m_data.set_to_zero(); m_signedness = Positive; }
376
377
     /**
378
     * Compare this to another BigInt
379
     * @param n the BigInt value to compare with
380
     * @param check_signs include sign in comparison?
381
     * @result if (this<n) return -1, if (this>n) return 1, if both
382
     * values are identical return 0 [like Perl's <=> operator]
383
     */
384
     int32_t cmp(const BigInt& n, bool check_signs = true) const;
385
386
     /**
387
     * Compare this to another BigInt
388
     * @param n the BigInt value to compare with
389
     * @result true if this == n or false otherwise
390
     */
391
     bool is_equal(const BigInt& n) const;
392
393
     /**
394
     * Compare this to another BigInt
395
     * @param n the BigInt value to compare with
396
     * @result true if this < n or false otherwise
397
     */
398
     bool is_less_than(const BigInt& n) const;
399
400
     /**
401
     * Compare this to an integer
402
     * @param n the value to compare with
403
     * @result if (this<n) return -1, if (this>n) return 1, if both
404
     * values are identical return 0 [like Perl's <=> operator]
405
     */
406
     int32_t cmp_word(word n) const;
407
408
     /**
409
     * Test if the integer has an even value
410
     * @result true if the integer is even, false otherwise
411
     */
412
220k
     bool is_even() const { return (get_bit(0) == 0); }
413
414
     /**
415
     * Test if the integer has an odd value
416
     * @result true if the integer is odd, false otherwise
417
     */
418
4.00M
     bool is_odd()  const { return (get_bit(0) == 1); }
419
420
     /**
421
     * Test if the integer is not zero
422
     * @result true if the integer is non-zero, false otherwise
423
     */
424
7.86M
     bool is_nonzero() const { return (!is_zero()); }
425
426
     /**
427
     * Test if the integer is zero
428
     * @result true if the integer is zero, false otherwise
429
     */
430
     bool is_zero() const
431
85.8M
        {
432
85.8M
        return (sig_words() == 0);
433
85.8M
        }
434
435
     /**
436
     * Set bit at specified position
437
     * @param n bit position to set
438
     */
439
     void set_bit(size_t n)
440
506k
        {
441
506k
        conditionally_set_bit(n, true);
442
506k
        }
443
444
     /**
445
     * Conditionally set bit at specified position. Note if set_it is
446
     * false, nothing happens, and if the bit is already set, it
447
     * remains set.
448
     *
449
     * @param n bit position to set
450
     * @param set_it if the bit should be set
451
     */
452
     void conditionally_set_bit(size_t n, bool set_it)
453
802M
        {
454
802M
        const size_t which = n / BOTAN_MP_WORD_BITS;
455
802M
        const word mask = static_cast<word>(set_it) << (n % BOTAN_MP_WORD_BITS);
456
802M
        m_data.set_word_at(which, word_at(which) | mask);
457
802M
        }
458
459
     /**
460
     * Clear bit at specified position
461
     * @param n bit position to clear
462
     */
463
     void clear_bit(size_t n);
464
465
     /**
466
     * Clear all but the lowest n bits
467
     * @param n amount of bits to keep
468
     */
469
     void mask_bits(size_t n)
470
277M
        {
471
277M
        m_data.mask_bits(n);
472
277M
        }
473
474
     /**
475
     * Return bit value at specified position
476
     * @param n the bit offset to test
477
     * @result true, if the bit at position n is set, false otherwise
478
     */
479
     bool get_bit(size_t n) const
480
760M
        {
481
760M
        return ((word_at(n / BOTAN_MP_WORD_BITS) >> (n % BOTAN_MP_WORD_BITS)) & 1);
482
760M
        }
483
484
     /**
485
     * Return (a maximum of) 32 bits of the complete value
486
     * @param offset the offset to start extracting
487
     * @param length amount of bits to extract (starting at offset)
488
     * @result the integer extracted from the register starting at
489
     * offset with specified length
490
     */
491
     uint32_t get_substring(size_t offset, size_t length) const;
492
493
     /**
494
     * Convert this value into a uint32_t, if it is in the range
495
     * [0 ... 2**32-1], or otherwise throw an exception.
496
     * @result the value as a uint32_t if conversion is possible
497
     */
498
     uint32_t to_u32bit() const;
499
500
     /**
501
     * Convert this value to a decimal string.
502
     * Warning: decimal conversions are relatively slow
503
     */
504
     std::string to_dec_string() const;
505
506
     /**
507
     * Convert this value to a hexadecimal string.
508
     */
509
     std::string to_hex_string() const;
510
511
     /**
512
     * @param n the offset to get a byte from
513
     * @result byte at offset n
514
     */
515
     uint8_t byte_at(size_t n) const;
516
517
     /**
518
     * Return the word at a specified position of the internal register
519
     * @param n position in the register
520
     * @return value at position n
521
     */
522
     word word_at(size_t n) const
523
3.00G
        {
524
3.00G
        return m_data.get_word_at(n);
525
3.00G
        }
526
527
     void set_word_at(size_t i, word w)
528
150M
        {
529
150M
        m_data.set_word_at(i, w);
530
150M
        }
531
532
     void set_words(const word w[], size_t len)
533
16.3M
        {
534
16.3M
        m_data.set_words(w, len);
535
16.3M
        }
536
537
     /**
538
     * Tests if the sign of the integer is negative
539
     * @result true, iff the integer has a negative sign
540
     */
541
836M
     bool is_negative() const { return (sign() == Negative); }
542
543
     /**
544
     * Tests if the sign of the integer is positive
545
     * @result true, iff the integer has a positive sign
546
     */
547
14.6M
     bool is_positive() const { return (sign() == Positive); }
548
549
     /**
550
     * Return the sign of the integer
551
     * @result the sign of the integer
552
     */
553
980M
     Sign sign() const { return (m_signedness); }
554
555
     /**
556
     * @result the opposite sign of the represented integer value
557
     */
558
     Sign reverse_sign() const
559
2.43M
        {
560
2.43M
        if(sign() == Positive)
561
2.42M
           return Negative;
562
1.76k
        return Positive;
563
2.43M
        }
564
565
     /**
566
     * Flip the sign of this BigInt
567
     */
568
     void flip_sign()
569
24.0k
        {
570
24.0k
        set_sign(reverse_sign());
571
24.0k
        }
572
573
     /**
574
     * Set sign of the integer
575
     * @param sign new Sign to set
576
     */
577
     void set_sign(Sign sign)
578
65.4M
        {
579
65.4M
        if(sign == Negative && is_zero())
580
1.48k
           sign = Positive;
581
582
65.4M
        m_signedness = sign;
583
65.4M
        }
584
585
     /**
586
     * @result absolute (positive) value of this
587
     */
588
     BigInt abs() const;
589
590
     /**
591
     * Give size of internal register
592
     * @result size of internal register in words
593
     */
594
2.48G
     size_t size() const { return m_data.size(); }
595
596
     /**
597
     * Return how many words we need to hold this value
598
     * @result significant words of the represented integer value
599
     */
600
     size_t sig_words() const
601
504M
        {
602
504M
        return m_data.sig_words();
603
504M
        }
604
605
     /**
606
     * Give byte length of the integer
607
     * @result byte length of the represented integer value
608
     */
609
     size_t bytes() const;
610
611
     /**
612
     * Get the bit length of the integer
613
     * @result bit length of the represented integer value
614
     */
615
     size_t bits() const;
616
617
     /**
618
     * Get the number of high bits unset in the top (allocated) word
619
     * of this integer. Returns BOTAN_MP_WORD_BITS only iff *this is
620
     * zero. Ignores sign.
621
     */
622
     size_t top_bits_free() const;
623
624
     /**
625
     * Return a mutable pointer to the register
626
     * @result a pointer to the start of the internal register
627
     */
628
1.65G
     word* mutable_data() { return m_data.mutable_data(); }
629
630
     /**
631
     * Return a const pointer to the register
632
     * @result a pointer to the start of the internal register
633
     */
634
2.01G
     const word* data() const { return m_data.const_data(); }
635
636
     /**
637
     * Don't use this function in application code
638
     */
639
74.1M
     secure_vector<word>& get_word_vector() { return m_data.mutable_vector(); }
640
641
     /**
642
     * Don't use this function in application code
643
     */
644
3.14M
     const secure_vector<word>& get_word_vector() const { return m_data.const_vector(); }
645
646
     /**
647
     * Increase internal register buffer to at least n words
648
     * @param n new size of register
649
     */
650
803M
     void grow_to(size_t n) const { m_data.grow_to(n); }
651
652
0
     void resize(size_t s) { m_data.resize(s); }
653
654
     /**
655
     * Fill BigInt with a random number with size of bitsize
656
     *
657
     * If \p set_high_bit is true, the highest bit will be set, which causes
658
     * the entropy to be \a bits-1. Otherwise the highest bit is randomly chosen
659
     * by the rng, causing the entropy to be \a bits.
660
     *
661
     * @param rng the random number generator to use
662
     * @param bitsize number of bits the created random value should have
663
     * @param set_high_bit if true, the highest bit is always set
664
     */
665
     void randomize(RandomNumberGenerator& rng, size_t bitsize, bool set_high_bit = true);
666
667
     /**
668
     * Store BigInt-value in a given byte array
669
     * @param buf destination byte array for the integer value
670
     */
671
     void binary_encode(uint8_t buf[]) const;
672
673
     /**
674
     * Store BigInt-value in a given byte array. If len is less than
675
     * the size of the value, then it will be truncated. If len is
676
     * greater than the size of the value, it will be zero-padded.
677
     * If len exactly equals this->bytes(), this function behaves identically
678
     * to binary_encode.
679
     *
680
     * @param buf destination byte array for the integer value
681
     * @param len how many bytes to write
682
     */
683
     void binary_encode(uint8_t buf[], size_t len) const;
684
685
     /**
686
     * Read integer value from a byte array with given size
687
     * @param buf byte array buffer containing the integer
688
     * @param length size of buf
689
     */
690
     void binary_decode(const uint8_t buf[], size_t length);
691
692
     /**
693
     * Read integer value from a byte vector
694
     * @param buf the vector to load from
695
     */
696
     template<typename Alloc>
697
     void binary_decode(const std::vector<uint8_t, Alloc>& buf)
698
550k
        {
699
550k
        binary_decode(buf.data(), buf.size());
700
550k
        }
701
702
     /**
703
     * Place the value into out, zero-padding up to size words
704
     * Throw if *this cannot be represented in size words
705
     */
706
     void encode_words(word out[], size_t size) const;
707
708
     /**
709
     * If predicate is true assign other to *this
710
     * Uses a masked operation to avoid side channels
711
     */
712
     void ct_cond_assign(bool predicate, const BigInt& other);
713
714
     /**
715
     * If predicate is true swap *this and other
716
     * Uses a masked operation to avoid side channels
717
     */
718
     void ct_cond_swap(bool predicate, BigInt& other);
719
720
     /**
721
     * If predicate is true add value to *this
722
     */
723
     void ct_cond_add(bool predicate, const BigInt& value);
724
725
     /**
726
     * If predicate is true flip the sign of *this
727
     */
728
     void cond_flip_sign(bool predicate);
729
730
#if defined(BOTAN_HAS_VALGRIND)
731
     void const_time_poison() const;
732
     void const_time_unpoison() const;
733
#else
734
42.8k
     void const_time_poison() const {}
735
80.2M
     void const_time_unpoison() const {}
736
#endif
737
738
     /**
739
     * @param rng a random number generator
740
     * @param min the minimum value (must be non-negative)
741
     * @param max the maximum value (must be non-negative and > min)
742
     * @return random integer in [min,max)
743
     */
744
     static BigInt random_integer(RandomNumberGenerator& rng,
745
                                  const BigInt& min,
746
                                  const BigInt& max);
747
748
     /**
749
     * Create a power of two
750
     * @param n the power of two to create
751
     * @return bigint representing 2^n
752
     */
753
     static BigInt power_of_2(size_t n)
754
84.1k
        {
755
84.1k
        BigInt b;
756
84.1k
        b.set_bit(n);
757
84.1k
        return b;
758
84.1k
        }
759
760
     /**
761
     * Encode the integer value from a BigInt to a std::vector of bytes
762
     * @param n the BigInt to use as integer source
763
     * @result secure_vector of bytes containing the bytes of the integer
764
     */
765
     static std::vector<uint8_t> encode(const BigInt& n)
766
16.1k
        {
767
16.1k
        std::vector<uint8_t> output(n.bytes());
768
16.1k
        n.binary_encode(output.data());
769
16.1k
        return output;
770
16.1k
        }
771
772
     /**
773
     * Encode the integer value from a BigInt to a secure_vector of bytes
774
     * @param n the BigInt to use as integer source
775
     * @result secure_vector of bytes containing the bytes of the integer
776
     */
777
     static secure_vector<uint8_t> encode_locked(const BigInt& n)
778
5.97k
        {
779
5.97k
        secure_vector<uint8_t> output(n.bytes());
780
5.97k
        n.binary_encode(output.data());
781
5.97k
        return output;
782
5.97k
        }
783
784
     /**
785
     * Create a BigInt from an integer in a byte array
786
     * @param buf the binary value to load
787
     * @param length size of buf
788
     * @result BigInt representing the integer in the byte array
789
     */
790
     static BigInt decode(const uint8_t buf[], size_t length)
791
60.2k
        {
792
60.2k
        return BigInt(buf, length);
793
60.2k
        }
794
795
     /**
796
     * Create a BigInt from an integer in a byte array
797
     * @param buf the binary value to load
798
     * @result BigInt representing the integer in the byte array
799
     */
800
     template<typename Alloc>
801
     static BigInt decode(const std::vector<uint8_t, Alloc>& buf)
802
0
        {
803
0
        return BigInt(buf);
804
0
        }
Unexecuted instantiation: Botan::BigInt Botan::BigInt::decode<std::__1::allocator<unsigned char> >(std::__1::vector<unsigned char, std::__1::allocator<unsigned char> > const&)
Unexecuted instantiation: Botan::BigInt Botan::BigInt::decode<Botan::secure_allocator<unsigned char> >(std::__1::vector<unsigned char, Botan::secure_allocator<unsigned char> > const&)
805
806
     /**
807
     * Create a BigInt from an integer in a byte array
808
     * @param buf the binary value to load
809
     * @param length size of buf
810
     * @param base number-base of the integer in buf
811
     * @result BigInt representing the integer in the byte array
812
     */
813
     static BigInt decode(const uint8_t buf[], size_t length,
814
                          Base base);
815
816
     /**
817
     * Create a BigInt from an integer in a byte array
818
     * @param buf the binary value to load
819
     * @param base number-base of the integer in buf
820
     * @result BigInt representing the integer in the byte array
821
     */
822
     template<typename Alloc>
823
     static BigInt decode(const std::vector<uint8_t, Alloc>& buf, Base base)
824
        {
825
        if(base == Binary)
826
           return BigInt(buf);
827
        return BigInt::decode(buf.data(), buf.size(), base);
828
        }
829
830
     /**
831
     * Encode a BigInt to a byte array according to IEEE 1363
832
     * @param n the BigInt to encode
833
     * @param bytes the length of the resulting secure_vector<uint8_t>
834
     * @result a secure_vector<uint8_t> containing the encoded BigInt
835
     */
836
     static secure_vector<uint8_t> encode_1363(const BigInt& n, size_t bytes);
837
838
     static void encode_1363(uint8_t out[], size_t bytes, const BigInt& n);
839
840
     /**
841
     * Encode two BigInt to a byte array according to IEEE 1363
842
     * @param n1 the first BigInt to encode
843
     * @param n2 the second BigInt to encode
844
     * @param bytes the length of the encoding of each single BigInt
845
     * @result a secure_vector<uint8_t> containing the concatenation of the two encoded BigInt
846
     */
847
     static secure_vector<uint8_t> encode_fixed_length_int_pair(const BigInt& n1, const BigInt& n2, size_t bytes);
848
849
   private:
850
851
     class Data
852
        {
853
        public:
854
           word* mutable_data()
855
1.68G
              {
856
1.68G
              invalidate_sig_words();
857
1.68G
              return m_reg.data();
858
1.68G
              }
859
860
           const word* const_data() const
861
2.01G
              {
862
2.01G
              return m_reg.data();
863
2.01G
              }
864
865
           secure_vector<word>& mutable_vector()
866
74.1M
              {
867
74.1M
              invalidate_sig_words();
868
74.1M
              return m_reg;
869
74.1M
              }
870
871
           const secure_vector<word>& const_vector() const
872
3.14M
              {
873
3.14M
              return m_reg;
874
3.14M
              }
875
876
           word get_word_at(size_t n) const
877
3.00G
              {
878
3.00G
              if(n < m_reg.size())
879
2.99G
                 return m_reg[n];
880
3.29M
              return 0;
881
3.00G
              }
882
883
           void set_word_at(size_t i, word w)
884
954M
              {
885
954M
              invalidate_sig_words();
886
954M
              if(i >= m_reg.size())
887
119M
                 {
888
119M
                 if(w == 0)
889
119M
                    return;
890
814k
                 grow_to(i + 1);
891
814k
                 }
892
834M
              m_reg[i] = w;
893
834M
              }
894
895
           void set_words(const word w[], size_t len)
896
16.3M
              {
897
16.3M
              invalidate_sig_words();
898
16.3M
              m_reg.assign(w, w + len);
899
16.3M
              }
900
901
           void set_to_zero()
902
2.18M
              {
903
2.18M
              m_reg.resize(m_reg.capacity());
904
2.18M
              clear_mem(m_reg.data(), m_reg.size());
905
2.18M
              m_sig_words = 0;
906
2.18M
              }
907
908
           void set_size(size_t s)
909
0
              {
910
0
              invalidate_sig_words();
911
0
              clear_mem(m_reg.data(), m_reg.size());
912
0
              m_reg.resize(s + (8 - (s % 8)));
913
0
              }
914
915
           void mask_bits(size_t n)
916
277M
              {
917
277M
              if(n == 0) { return set_to_zero(); }
918
919
277M
              const size_t top_word = n / BOTAN_MP_WORD_BITS;
920
921
              // if(top_word < sig_words()) ?
922
277M
              if(top_word < size())
923
277M
                 {
924
277M
                 const word mask = (static_cast<word>(1) << (n % BOTAN_MP_WORD_BITS)) - 1;
925
277M
                 const size_t len = size() - (top_word + 1);
926
277M
                 if(len > 0)
927
277M
                    {
928
277M
                    clear_mem(&m_reg[top_word+1], len);
929
277M
                    }
930
277M
                 m_reg[top_word] &= mask;
931
277M
                 invalidate_sig_words();
932
277M
                 }
933
277M
              }
934
935
           void grow_to(size_t n) const
936
809M
              {
937
809M
              if(n > size())
938
56.7M
                 {
939
56.7M
                 if(n <= m_reg.capacity())
940
21.2M
                    m_reg.resize(n);
941
35.5M
                 else
942
35.5M
                    m_reg.resize(n + (8 - (n % 8)));
943
56.7M
                 }
944
809M
              }
945
946
3.88G
           size_t size() const { return m_reg.size(); }
947
948
           void shrink_to_fit(size_t min_size = 0)
949
0
              {
950
0
              const size_t words = std::max(min_size, sig_words());
951
0
              m_reg.resize(words);
952
0
              }
953
954
           void resize(size_t s)
955
0
              {
956
0
              m_reg.resize(s);
957
0
              }
958
959
           void swap(Data& other)
960
154M
              {
961
154M
              m_reg.swap(other.m_reg);
962
154M
              std::swap(m_sig_words, other.m_sig_words);
963
154M
              }
964
965
           void swap(secure_vector<word>& reg)
966
129M
              {
967
129M
              m_reg.swap(reg);
968
129M
              invalidate_sig_words();
969
129M
              }
970
971
           void invalidate_sig_words() const
972
3.13G
              {
973
3.13G
              m_sig_words = sig_words_npos;
974
3.13G
              }
975
976
           size_t sig_words() const
977
504M
              {
978
504M
              if(m_sig_words == sig_words_npos)
979
157M
                 {
980
157M
                 m_sig_words = calc_sig_words();
981
157M
                 }
982
346M
              else
983
346M
                 {
984
346M
                 BOTAN_DEBUG_ASSERT(m_sig_words == calc_sig_words());
985
346M
                 }
986
504M
              return m_sig_words;
987
504M
              }
988
        private:
989
           static const size_t sig_words_npos = static_cast<size_t>(-1);
990
991
           size_t calc_sig_words() const;
992
993
           mutable secure_vector<word> m_reg;
994
           mutable size_t m_sig_words = sig_words_npos;
995
        };
996
997
      Data m_data;
998
      Sign m_signedness = Positive;
999
   };
1000
1001
/*
1002
* Arithmetic Operators
1003
*/
1004
inline BigInt operator+(const BigInt& x, const BigInt& y)
1005
1.22M
   {
1006
1.22M
   return BigInt::add2(x, y.data(), y.sig_words(), y.sign());
1007
1.22M
   }
1008
1009
inline BigInt operator+(const BigInt& x, word y)
1010
21.1k
   {
1011
21.1k
   return BigInt::add2(x, &y, 1, BigInt::Positive);
1012
21.1k
   }
1013
1014
inline BigInt operator+(word x, const BigInt& y)
1015
0
   {
1016
0
   return y + x;
1017
0
   }
1018
1019
inline BigInt operator-(const BigInt& x, const BigInt& y)
1020
2.40M
   {
1021
2.40M
   return BigInt::add2(x, y.data(), y.sig_words(), y.reverse_sign());
1022
2.40M
   }
1023
1024
inline BigInt operator-(const BigInt& x, word y)
1025
5.24k
   {
1026
5.24k
   return BigInt::add2(x, &y, 1, BigInt::Negative);
1027
5.24k
   }
1028
1029
BigInt BOTAN_PUBLIC_API(2,0) operator*(const BigInt& x, const BigInt& y);
1030
BigInt BOTAN_PUBLIC_API(2,8) operator*(const BigInt& x, word y);
1031
6.19M
inline BigInt operator*(word x, const BigInt& y) { return y*x; }
1032
1033
BigInt BOTAN_PUBLIC_API(2,0) operator/(const BigInt& x, const BigInt& d);
1034
BigInt BOTAN_PUBLIC_API(2,0) operator/(const BigInt& x, word m);
1035
BigInt BOTAN_PUBLIC_API(2,0) operator%(const BigInt& x, const BigInt& m);
1036
word   BOTAN_PUBLIC_API(2,0) operator%(const BigInt& x, word m);
1037
BigInt BOTAN_PUBLIC_API(2,0) operator<<(const BigInt& x, size_t n);
1038
BigInt BOTAN_PUBLIC_API(2,0) operator>>(const BigInt& x, size_t n);
1039
1040
/*
1041
* Comparison Operators
1042
*/
1043
inline bool operator==(const BigInt& a, const BigInt& b)
1044
242k
   { return a.is_equal(b); }
1045
inline bool operator!=(const BigInt& a, const BigInt& b)
1046
68.0k
   { return !a.is_equal(b); }
1047
inline bool operator<=(const BigInt& a, const BigInt& b)
1048
85.8k
   { return (a.cmp(b) <= 0); }
1049
inline bool operator>=(const BigInt& a, const BigInt& b)
1050
694k
   { return (a.cmp(b) >= 0); }
1051
inline bool operator<(const BigInt& a, const BigInt& b)
1052
3.77M
   { return a.is_less_than(b); }
1053
inline bool operator>(const BigInt& a, const BigInt& b)
1054
3.30M
   { return b.is_less_than(a); }
1055
1056
inline bool operator==(const BigInt& a, word b)
1057
271k
   { return (a.cmp_word(b) == 0); }
1058
inline bool operator!=(const BigInt& a, word b)
1059
2.79M
   { return (a.cmp_word(b) != 0); }
1060
inline bool operator<=(const BigInt& a, word b)
1061
33.9k
   { return (a.cmp_word(b) <= 0); }
1062
inline bool operator>=(const BigInt& a, word b)
1063
30.8k
   { return (a.cmp_word(b) >= 0); }
1064
inline bool operator<(const BigInt& a, word b)
1065
192k
   { return (a.cmp_word(b) < 0); }
1066
inline bool operator>(const BigInt& a, word b)
1067
4.03M
   { return (a.cmp_word(b) > 0); }
1068
1069
/*
1070
* I/O Operators
1071
*/
1072
BOTAN_PUBLIC_API(2,0) std::ostream& operator<<(std::ostream&, const BigInt&);
1073
BOTAN_PUBLIC_API(2,0) std::istream& operator>>(std::istream&, BigInt&);
1074
1075
}
1076
1077
namespace std {
1078
1079
template<>
1080
inline void swap<Botan::BigInt>(Botan::BigInt& x, Botan::BigInt& y)
1081
3.30M
   {
1082
3.30M
   x.swap(y);
1083
3.30M
   }
1084
1085
}
1086
1087
#endif