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