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