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