Botan  2.19.1
Crypto and TLS for C++11
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 */
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  */
554  void flip_sign()
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 */
1070 inline BigInt operator+(const BigInt& x, const BigInt& y)
1071  {
1072  return BigInt::add2(x, y.data(), y.sig_words(), y.sign());
1073  }
1074 
1075 inline BigInt operator+(const BigInt& x, word y)
1076  {
1077  return BigInt::add2(x, &y, 1, BigInt::Positive);
1078  }
1079 
1080 inline BigInt operator+(word x, const BigInt& y)
1081  {
1082  return y + x;
1083  }
1084 
1085 inline BigInt operator-(const BigInt& x, const BigInt& y)
1086  {
1087  return BigInt::add2(x, y.data(), y.sig_words(), y.reverse_sign());
1088  }
1089 
1090 inline BigInt operator-(const BigInt& x, word y)
1091  {
1092  return BigInt::add2(x, &y, 1, BigInt::Negative);
1093  }
1094 
1095 BigInt BOTAN_PUBLIC_API(2,0) operator*(const BigInt& x, const BigInt& y);
1096 BigInt BOTAN_PUBLIC_API(2,8) operator*(const BigInt& x, word y);
1097 inline BigInt operator*(word x, const BigInt& y) { return y*x; }
1098 
1099 BigInt BOTAN_PUBLIC_API(2,0) operator/(const BigInt& x, const BigInt& d);
1100 BigInt BOTAN_PUBLIC_API(2,0) operator/(const BigInt& x, word m);
1101 BigInt BOTAN_PUBLIC_API(2,0) operator%(const BigInt& x, const BigInt& m);
1102 word BOTAN_PUBLIC_API(2,0) operator%(const BigInt& x, word m);
1103 BigInt BOTAN_PUBLIC_API(2,0) operator<<(const BigInt& x, size_t n);
1104 BigInt BOTAN_PUBLIC_API(2,0) operator>>(const BigInt& x, size_t n);
1105 
1106 /*
1107 * Comparison Operators
1108 */
1109 inline bool operator==(const BigInt& a, const BigInt& b)
1110  { return a.is_equal(b); }
1111 inline bool operator!=(const BigInt& a, const BigInt& b)
1112  { return !a.is_equal(b); }
1113 inline bool operator<=(const BigInt& a, const BigInt& b)
1114  { return (a.cmp(b) <= 0); }
1115 inline bool operator>=(const BigInt& a, const BigInt& b)
1116  { return (a.cmp(b) >= 0); }
1117 inline bool operator<(const BigInt& a, const BigInt& b)
1118  { return a.is_less_than(b); }
1119 inline bool operator>(const BigInt& a, const BigInt& b)
1120  { return b.is_less_than(a); }
1121 
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 inline bool operator<=(const BigInt& a, word b)
1127  { return (a.cmp_word(b) <= 0); }
1128 inline bool operator>=(const BigInt& a, word b)
1129  { return (a.cmp_word(b) >= 0); }
1130 inline bool operator<(const BigInt& a, word b)
1131  { return (a.cmp_word(b) < 0); }
1132 inline bool operator>(const BigInt& a, word b)
1133  { return (a.cmp_word(b) > 0); }
1134 
1135 /*
1136 * I/O Operators
1137 */
1138 BOTAN_PUBLIC_API(2,0) std::ostream& operator<<(std::ostream&, const BigInt&);
1139 BOTAN_PUBLIC_API(2,0) std::istream& operator>>(std::istream&, BigInt&);
1140 
1141 }
1142 
1143 namespace std {
1144 
1145 template<>
1146 inline void swap<Botan::BigInt>(Botan::BigInt& x, Botan::BigInt& y)
1147  {
1148  x.swap(y);
1149  }
1150 
1151 }
1152 
1153 #endif
word word_at(size_t n) const
Definition: bigint.h:508
void binary_encode(uint8_t buf[]) const
Definition: bigint.cpp:399
size_t sig_words() const
Definition: bigint.h:586
bool operator!=(const AlgorithmIdentifier &a1, const AlgorithmIdentifier &a2)
Definition: alg_id.cpp:82
bool is_odd() const
Definition: bigint.h:409
bool is_even() const
Definition: bigint.h:403
BigInt(BigInt &&other)
Definition: bigint.h:134
BigInt operator--(int)
Definition: bigint.h:269
bool is_equal(const BigInt &n) const
Definition: bigint.cpp:149
BigInt & operator+=(const BigInt &y)
Definition: bigint.h:177
void resize(size_t s)
Definition: bigint.h:647
BigInt & operator--()
Definition: bigint.h:259
void binary_decode(const std::vector< uint8_t, Alloc > &buf)
Definition: bigint.h:692
void clear_mem(T *ptr, size_t n)
Definition: mem_ops.h:115
void set_bit(size_t n)
Definition: bigint.h:430
static std::vector< uint8_t > encode(const BigInt &n)
Definition: bigint.h:770
void const_time_unpoison() const
Definition: bigint.h:740
int(* final)(unsigned char *, CTX *)
secure_vector< word > & get_word_vector()
Definition: bigint.h:625
#define BOTAN_PUBLIC_API(maj, min)
Definition: compiler.h:31
OID operator+(const OID &oid, uint32_t new_comp)
Definition: asn1_oid.cpp:122
Definition: bigint.h:1143
Sign reverse_sign() const
Definition: bigint.h:544
word * mutable_data()
Definition: bigint.h:614
void swap_reg(secure_vector< word > &reg)
Definition: bigint.h:167
BigInt operator-(const BigInt &x, const BigInt &y)
Definition: bigint.h:1085
bool is_negative() const
Definition: bigint.h:527
size_t size() const
Definition: bigint.h:580
void swap(BigInt &other)
Definition: bigint.h:161
uint32_t to_u32bit(const std::string &str)
Definition: parsing.cpp:35
void mask_bits(size_t n)
Definition: bigint.h:455
bool is_nonzero() const
Definition: bigint.h:415
static secure_vector< uint8_t > encode_locked(const BigInt &n)
Definition: bigint.h:782
BigInt & operator++()
Definition: bigint.h:254
int32_t cmp(const BigInt &n, bool check_signs=true) const
Definition: bigint.cpp:130
bool operator<(const OID &a, const OID &b)
Definition: asn1_oid.cpp:132
BigInt abs(const BigInt &n)
Definition: numthry.h:58
std::vector< T, secure_allocator< T >> secure_vector
Definition: secmem.h:65
std::string encode(const uint8_t der[], size_t length, const std::string &label, size_t width)
Definition: pem.cpp:43
BigInt operator++(int)
Definition: bigint.h:264
bool operator>=(const ASN1_Time &, const ASN1_Time &)
Definition: asn1_time.cpp:282
#define BOTAN_DEBUG_ASSERT(expr)
Definition: assert.h:123
const secure_vector< word > & get_word_vector() const
Definition: bigint.h:630
BigInt square(const BigInt &x)
Definition: mp_numth.cpp:19
const word * data() const
Definition: bigint.h:620
bool operator>(const ASN1_Time &, const ASN1_Time &)
Definition: asn1_time.cpp:287
secure_vector< uint8_t > decode(DataSource &source, std::string &label)
Definition: pem.cpp:68
void set_words(const word w[], size_t len)
Definition: bigint.h:518
static BigInt power_of_2(size_t n)
Definition: bigint.h:758
Definition: alg_id.cpp:13
static BigInt decode(const std::vector< uint8_t, Alloc > &buf)
Definition: bigint.h:816
void clear()
Definition: bigint.h:366
bool operator<=(const ASN1_Time &, const ASN1_Time &)
Definition: asn1_time.cpp:280
static BigInt decode(const uint8_t buf[], size_t length)
Definition: bigint.h:805
BigInt(const std::vector< uint8_t, Alloc > &vec)
Definition: bigint.h:87
void grow_to(size_t n) const
Definition: bigint.h:636
bool is_positive() const
Definition: bigint.h:533
BigInt & sub(const word y[], size_t y_words, Sign sign)
Definition: bigint.h:287
void set_word_at(size_t i, word w)
Definition: bigint.h:513
bool is_less_than(const BigInt &n) const
Definition: bigint.cpp:158
BigInt & operator=(BigInt &&other)
Definition: bigint.h:144
bool operator==(const AlgorithmIdentifier &a1, const AlgorithmIdentifier &a2)
Definition: alg_id.cpp:65
bool get_bit(size_t n) const
Definition: bigint.h:465
void flip_sign()
Definition: bigint.h:554
int32_t cmp_word(word n) const
Definition: bigint.cpp:115
bool is_zero() const
Definition: bigint.h:421
static BigInt add2(const BigInt &x, const word y[], size_t y_words, Sign y_sign)
Definition: big_ops3.cpp:18
BigInt & operator-=(word y)
Definition: bigint.h:204
void set_sign(Sign sign)
Definition: bigint.h:563
BigInt & operator+=(word y)
Definition: bigint.h:186
BigInt & operator-=(const BigInt &y)
Definition: bigint.h:195
Sign sign() const
Definition: bigint.h:539
void const_time_poison() const
Definition: bigint.h:739
size_t bytes() const
Definition: bigint.cpp:281