Botan 3.0.0-alpha0
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/types.h>
13#include <botan/secmem.h>
14#include <botan/exceptn.h>
15#include <iosfwd>
16
17namespace Botan {
18
19class RandomNumberGenerator;
20
21/**
22* Arbitrary precision integer
23*/
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 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(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 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 * @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 {
145 this->swap(other);
146 }
147
148 ~BigInt() { const_time_unpoison(); }
149
150 /**
151 * Move assignment
152 */
154 {
155 if(this != &other)
156 this->swap(other);
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 {
172 m_data.swap(other.m_data);
173 std::swap(m_signedness, other.m_signedness);
174 }
175
177 {
178 m_data.swap(reg);
179 // sign left unchanged
180 }
181
182 /**
183 * += operator
184 * @param y the BigInt to add to this
185 */
187 {
188 return add(y.data(), y.sig_words(), y.sign());
189 }
190
191 /**
192 * += operator
193 * @param y the word to add to this
194 */
196 {
197 return add(&y, 1, Positive);
198 }
199
200 /**
201 * -= operator
202 * @param y the BigInt to subtract from this
203 */
205 {
206 return sub(y.data(), y.sig_words(), y.sign());
207 }
208
209 /**
210 * -= operator
211 * @param y the word to subtract from this
212 */
214 {
215 return sub(&y, 1, Positive);
216 }
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 BigInt& operator++() { return (*this += 1); }
264
265 /**
266 * Decrement operator
267 */
268 BigInt& operator--() { return (*this -= 1); }
269
270 /**
271 * Postfix increment operator
272 */
273 BigInt operator++(int) { BigInt x = (*this); ++(*this); return x; }
274
275 /**
276 * Postfix decrement operator
277 */
278 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 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 {
298 return add(y, y_words, sign == Positive ? Negative : Positive);
299 }
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 */
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 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 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 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 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 {
432 return (sig_words() == 0);
433 }
434
435 /**
436 * Set bit at specified position
437 * @param n bit position to set
438 */
439 void set_bit(size_t n)
440 {
441 conditionally_set_bit(n, true);
442 }
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 {
454 const size_t which = n / BOTAN_MP_WORD_BITS;
455 const word mask = static_cast<word>(set_it) << (n % BOTAN_MP_WORD_BITS);
456 m_data.set_word_at(which, word_at(which) | mask);
457 }
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 {
471 m_data.mask_bits(n);
472 }
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 {
481 return ((word_at(n / BOTAN_MP_WORD_BITS) >> (n % BOTAN_MP_WORD_BITS)) & 1);
482 }
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 {
524 return m_data.get_word_at(n);
525 }
526
527 void set_word_at(size_t i, word w)
528 {
529 m_data.set_word_at(i, w);
530 }
531
532 void set_words(const word w[], size_t len)
533 {
534 m_data.set_words(w, len);
535 }
536
537 /**
538 * Tests if the sign of the integer is negative
539 * @result true, iff the integer has a negative sign
540 */
541 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 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 Sign sign() const { return (m_signedness); }
554
555 /**
556 * @result the opposite sign of the represented integer value
557 */
559 {
560 if(sign() == Positive)
561 return Negative;
562 return Positive;
563 }
564
565 /**
566 * Flip the sign of this BigInt
567 */
569 {
570 set_sign(reverse_sign());
571 }
572
573 /**
574 * Set sign of the integer
575 * @param sign new Sign to set
576 */
577 void set_sign(Sign sign)
578 {
579 if(sign == Negative && is_zero())
580 sign = Positive;
581
582 m_signedness = sign;
583 }
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 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 {
602 return m_data.sig_words();
603 }
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 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 const word* data() const { return m_data.const_data(); }
635
636 /**
637 * Don't use this function in application code
638 */
639 secure_vector<word>& get_word_vector() { return m_data.mutable_vector(); }
640
641 /**
642 * Don't use this function in application code
643 */
644 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 void grow_to(size_t n) const { m_data.grow_to(n); }
651
652 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 {
699 binary_decode(buf.data(), buf.size());
700 }
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 void const_time_poison() const {}
735 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 {
755 BigInt b;
756 b.set_bit(n);
757 return b;
758 }
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 {
767 std::vector<uint8_t> output(n.bytes());
768 n.binary_encode(output.data());
769 return output;
770 }
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 */
778 {
779 secure_vector<uint8_t> output(n.bytes());
780 n.binary_encode(output.data());
781 return output;
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 * @result BigInt representing the integer in the byte array
789 */
790 static BigInt decode(const uint8_t buf[], size_t length)
791 {
792 return BigInt(buf, length);
793 }
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 {
803 return BigInt(buf);
804 }
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 {
856 invalidate_sig_words();
857 return m_reg.data();
858 }
859
860 const word* const_data() const
861 {
862 return m_reg.data();
863 }
864
865 secure_vector<word>& mutable_vector()
866 {
867 invalidate_sig_words();
868 return m_reg;
869 }
870
871 const secure_vector<word>& const_vector() const
872 {
873 return m_reg;
874 }
875
876 word get_word_at(size_t n) const
877 {
878 if(n < m_reg.size())
879 return m_reg[n];
880 return 0;
881 }
882
883 void set_word_at(size_t i, word w)
884 {
885 invalidate_sig_words();
886 if(i >= m_reg.size())
887 {
888 if(w == 0)
889 return;
890 grow_to(i + 1);
891 }
892 m_reg[i] = w;
893 }
894
895 void set_words(const word w[], size_t len)
896 {
897 invalidate_sig_words();
898 m_reg.assign(w, w + len);
899 }
900
901 void set_to_zero()
902 {
903 m_reg.resize(m_reg.capacity());
904 clear_mem(m_reg.data(), m_reg.size());
905 m_sig_words = 0;
906 }
907
908 void set_size(size_t s)
909 {
910 invalidate_sig_words();
911 clear_mem(m_reg.data(), m_reg.size());
912 m_reg.resize(s + (8 - (s % 8)));
913 }
914
915 void mask_bits(size_t n)
916 {
917 if(n == 0) { return set_to_zero(); }
918
919 const size_t top_word = n / BOTAN_MP_WORD_BITS;
920
921 // if(top_word < sig_words()) ?
922 if(top_word < size())
923 {
924 const word mask = (static_cast<word>(1) << (n % BOTAN_MP_WORD_BITS)) - 1;
925 const size_t len = size() - (top_word + 1);
926 if(len > 0)
927 {
928 clear_mem(&m_reg[top_word+1], len);
929 }
930 m_reg[top_word] &= mask;
931 invalidate_sig_words();
932 }
933 }
934
935 void grow_to(size_t n) const
936 {
937 if(n > size())
938 {
939 if(n <= m_reg.capacity())
940 m_reg.resize(n);
941 else
942 m_reg.resize(n + (8 - (n % 8)));
943 }
944 }
945
946 size_t size() const { return m_reg.size(); }
947
948 void shrink_to_fit(size_t min_size = 0)
949 {
950 const size_t words = std::max(min_size, sig_words());
951 m_reg.resize(words);
952 }
953
954 void resize(size_t s)
955 {
956 m_reg.resize(s);
957 }
958
959 void swap(Data& other)
960 {
961 m_reg.swap(other.m_reg);
962 std::swap(m_sig_words, other.m_sig_words);
963 }
964
965 void swap(secure_vector<word>& reg)
966 {
967 m_reg.swap(reg);
968 invalidate_sig_words();
969 }
970
971 void invalidate_sig_words() const
972 {
973 m_sig_words = sig_words_npos;
974 }
975
976 size_t sig_words() const
977 {
978 if(m_sig_words == sig_words_npos)
979 {
980 m_sig_words = calc_sig_words();
981 }
982 else
983 {
984 BOTAN_DEBUG_ASSERT(m_sig_words == calc_sig_words());
985 }
986 return m_sig_words;
987 }
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*/
1004inline BigInt operator+(const BigInt& x, const BigInt& y)
1005 {
1006 return BigInt::add2(x, y.data(), y.sig_words(), y.sign());
1007 }
1008
1009inline BigInt operator+(const BigInt& x, word y)
1010 {
1011 return BigInt::add2(x, &y, 1, BigInt::Positive);
1012 }
1013
1014inline BigInt operator+(word x, const BigInt& y)
1015 {
1016 return y + x;
1017 }
1018
1019inline BigInt operator-(const BigInt& x, const BigInt& y)
1020 {
1021 return BigInt::add2(x, y.data(), y.sig_words(), y.reverse_sign());
1022 }
1023
1024inline BigInt operator-(const BigInt& x, word y)
1025 {
1026 return BigInt::add2(x, &y, 1, BigInt::Negative);
1027 }
1028
1029BigInt BOTAN_PUBLIC_API(2,0) operator*(const BigInt& x, const BigInt& y);
1030BigInt BOTAN_PUBLIC_API(2,8) operator*(const BigInt& x, word y);
1031inline BigInt operator*(word x, const BigInt& y) { return y*x; }
1032
1033BigInt BOTAN_PUBLIC_API(2,0) operator/(const BigInt& x, const BigInt& d);
1034BigInt BOTAN_PUBLIC_API(2,0) operator/(const BigInt& x, word m);
1035BigInt BOTAN_PUBLIC_API(2,0) operator%(const BigInt& x, const BigInt& m);
1036word BOTAN_PUBLIC_API(2,0) operator%(const BigInt& x, word m);
1037BigInt BOTAN_PUBLIC_API(2,0) operator<<(const BigInt& x, size_t n);
1038BigInt BOTAN_PUBLIC_API(2,0) operator>>(const BigInt& x, size_t n);
1039
1040/*
1041* Comparison Operators
1042*/
1043inline bool operator==(const BigInt& a, const BigInt& b)
1044 { return a.is_equal(b); }
1045inline bool operator!=(const BigInt& a, const BigInt& b)
1046 { return !a.is_equal(b); }
1047inline bool operator<=(const BigInt& a, const BigInt& b)
1048 { return (a.cmp(b) <= 0); }
1049inline bool operator>=(const BigInt& a, const BigInt& b)
1050 { return (a.cmp(b) >= 0); }
1051inline bool operator<(const BigInt& a, const BigInt& b)
1052 { return a.is_less_than(b); }
1053inline bool operator>(const BigInt& a, const BigInt& b)
1054 { return b.is_less_than(a); }
1055
1056inline bool operator==(const BigInt& a, word b)
1057 { return (a.cmp_word(b) == 0); }
1058inline bool operator!=(const BigInt& a, word b)
1059 { return (a.cmp_word(b) != 0); }
1060inline bool operator<=(const BigInt& a, word b)
1061 { return (a.cmp_word(b) <= 0); }
1062inline bool operator>=(const BigInt& a, word b)
1063 { return (a.cmp_word(b) >= 0); }
1064inline bool operator<(const BigInt& a, word b)
1065 { return (a.cmp_word(b) < 0); }
1066inline bool operator>(const BigInt& a, word b)
1067 { return (a.cmp_word(b) > 0); }
1068
1069/*
1070* I/O Operators
1071*/
1072BOTAN_PUBLIC_API(2,0) std::ostream& operator<<(std::ostream&, const BigInt&);
1073BOTAN_PUBLIC_API(2,0) std::istream& operator>>(std::istream&, BigInt&);
1074
1075}
1076
1077namespace std {
1078
1079template<>
1080inline void swap<Botan::BigInt>(Botan::BigInt& x, Botan::BigInt& y)
1081 {
1082 x.swap(y);
1083 }
1084
1085}
1086
1087#endif
#define BOTAN_DEBUG_ASSERT(expr)
Definition: assert.h:122
static BigInt decode(const std::vector< uint8_t, Alloc > &buf)
Definition: bigint.h:801
BigInt & operator++()
Definition: bigint.h:263
void swap(BigInt &other)
Definition: bigint.h:170
static BigInt zero()
Definition: bigint.h:45
size_t sig_words() const
Definition: bigint.h:600
void conditionally_set_bit(size_t n, bool set_it)
Definition: bigint.h:452
bool is_odd() const
Definition: bigint.h:418
BigInt()=default
bool is_equal(const BigInt &n) const
Definition: bigint.cpp:172
static BigInt decode(const uint8_t buf[], size_t length)
Definition: bigint.h:790
BigInt & sub(const word y[], size_t y_words, Sign sign)
Definition: bigint.h:296
secure_vector< word > & get_word_vector()
Definition: bigint.h:639
void set_word_at(size_t i, word w)
Definition: bigint.h:527
word * mutable_data()
Definition: bigint.h:628
BigInt(const BigInt &other)=default
size_t size() const
Definition: bigint.h:594
void grow_to(size_t n) const
Definition: bigint.h:650
Sign reverse_sign() const
Definition: bigint.h:558
const secure_vector< word > & get_word_vector() const
Definition: bigint.h:644
void resize(size_t s)
Definition: bigint.h:652
void flip_sign()
Definition: bigint.h:568
static BigInt add2(const BigInt &x, const word y[], size_t y_words, Sign y_sign)
Definition: big_ops3.cpp:18
void set_words(const word w[], size_t len)
Definition: bigint.h:532
bool is_less_than(const BigInt &n) const
Definition: bigint.cpp:181
int32_t cmp(const BigInt &n, bool check_signs=true) const
Definition: bigint.cpp:153
BigInt & operator+=(word y)
Definition: bigint.h:195
const word * data() const
Definition: bigint.h:634
BigInt & operator=(BigInt &&other)
Definition: bigint.h:153
static secure_vector< uint8_t > encode_locked(const BigInt &n)
Definition: bigint.h:777
void binary_encode(uint8_t buf[]) const
Definition: bigint.cpp:395
static BigInt one()
Definition: bigint.h:50
word word_at(size_t n) const
Definition: bigint.h:522
BigInt & operator-=(const BigInt &y)
Definition: bigint.h:204
void set_bit(size_t n)
Definition: bigint.h:439
void binary_decode(const std::vector< uint8_t, Alloc > &buf)
Definition: bigint.h:697
int32_t cmp_word(word n) const
Definition: bigint.cpp:138
void mask_bits(size_t n)
Definition: bigint.h:469
static std::vector< uint8_t > encode(const BigInt &n)
Definition: bigint.h:765
BigInt operator--(int)
Definition: bigint.h:278
bool is_even() const
Definition: bigint.h:412
BigInt(BigInt &&other)
Definition: bigint.h:143
static BigInt power_of_2(size_t n)
Definition: bigint.h:753
BigInt & operator-=(word y)
Definition: bigint.h:213
BigInt & operator+=(const BigInt &y)
Definition: bigint.h:186
void clear()
Definition: bigint.h:375
Sign sign() const
Definition: bigint.h:553
void const_time_poison() const
Definition: bigint.h:734
BigInt & operator=(const BigInt &)=default
BigInt & operator--()
Definition: bigint.h:268
static BigInt from_word(word n)
Definition: bigint.cpp:43
bool is_zero() const
Definition: bigint.h:430
BigInt operator++(int)
Definition: bigint.h:273
static BigInt decode(const std::vector< uint8_t, Alloc > &buf, Base base)
Definition: bigint.h:823
bool is_negative() const
Definition: bigint.h:541
size_t bytes() const
Definition: bigint.cpp:294
bool is_nonzero() const
Definition: bigint.h:424
void const_time_unpoison() const
Definition: bigint.h:735
BigInt(const std::vector< uint8_t, Alloc > &vec)
Definition: bigint.h:103
bool is_positive() const
Definition: bigint.h:547
bool get_bit(size_t n) const
Definition: bigint.h:479
void swap_reg(secure_vector< word > &reg)
Definition: bigint.h:176
void set_sign(Sign sign)
Definition: bigint.h:577
int(* final)(unsigned char *, CTX *)
#define BOTAN_PUBLIC_API(maj, min)
Definition: compiler.h:31
#define BOTAN_MP_WORD_BITS
Definition: build.h:52
PolynomialVector b
Definition: kyber.cpp:821
secure_vector< uint8_t > decode(DataSource &source, std::string &label)
Definition: pem.cpp:66
Definition: alg_id.cpp:13
bool operator>=(const ASN1_Time &, const ASN1_Time &)
Definition: asn1_time.cpp:271
bool operator<=(const ASN1_Time &, const ASN1_Time &)
Definition: asn1_time.cpp:269
bool operator<(const OID &a, const OID &b)
Definition: asn1_oid.cpp:130
BigInt square(const BigInt &x)
Definition: numthry.cpp:170
bool operator>(const ASN1_Time &, const ASN1_Time &)
Definition: asn1_time.cpp:276
BigInt abs(const BigInt &n)
Definition: numthry.h:22
BigInt operator-(const BigInt &x, const BigInt &y)
Definition: bigint.h:1019
bool operator!=(const AlgorithmIdentifier &a1, const AlgorithmIdentifier &a2)
Definition: alg_id.cpp:82
OID operator+(const OID &oid, uint32_t new_comp)
Definition: asn1_oid.cpp:120
bool operator==(const AlgorithmIdentifier &a1, const AlgorithmIdentifier &a2)
Definition: alg_id.cpp:65
std::vector< T, secure_allocator< T > > secure_vector
Definition: secmem.h:65
uint32_t to_u32bit(const std::string &str)
Definition: parsing.cpp:29
constexpr void clear_mem(T *ptr, size_t n)
Definition: mem_ops.h:115
Definition: bigint.h:1077