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