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