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