Botan 2.13.0 Crypto and TLS for C++11

- Main Page
- Namespaces
- Classes
- Files

- File List
- File Members

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