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