Botan  2.1.0
Crypto and TLS for C++11
bigint.h
Go to the documentation of this file.
1 /*
2 * BigInt
3 * (C) 1999-2008,2012 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/rng.h>
13 #include <botan/secmem.h>
14 #include <botan/mp_types.h>
15 #include <botan/loadstor.h>
16 #include <iosfwd>
17 
18 namespace Botan {
19 
20 /**
21 * Arbitrary precision integer
22 */
23 class BOTAN_DLL BigInt
24  {
25  public:
26  /**
27  * Base enumerator for encoding and decoding
28  */
29  enum Base { Decimal = 10, Hexadecimal = 16, Binary = 256 };
30 
31  /**
32  * Sign symbol definitions for positive and negative numbers
33  */
34  enum Sign { Negative = 0, Positive = 1 };
35 
36  /**
37  * DivideByZero Exception
38  */
39  struct BOTAN_DLL DivideByZero : public Exception
40  { DivideByZero() : Exception("BigInt divide by zero") {} };
41 
42  /**
43  * Create empty BigInt
44  */
45  BigInt() = default;
46 
47  /**
48  * Create BigInt from 64 bit integer
49  * @param n initial value of this BigInt
50  */
51  BigInt(uint64_t n);
52 
53  /**
54  * Copy Constructor
55  * @param other the BigInt to copy
56  */
57  BigInt(const BigInt& other);
58 
59  /**
60  * Create BigInt from a string. If the string starts with 0x the
61  * rest of the string will be interpreted as hexadecimal digits.
62  * Otherwise, it will be interpreted as a decimal number.
63  *
64  * @param str the string to parse for an integer value
65  */
66  BigInt(const std::string& str);
67 
68  /**
69  * Create a BigInt from an integer in a byte array
70  * @param buf the byte array holding the value
71  * @param length size of buf
72  * @param base is the number base of the integer in buf
73  */
74  BigInt(const uint8_t buf[], size_t length, Base base = Binary);
75 
76  /**
77  * \brief Create a random BigInt of the specified size
78  *
79  * @param rng random number generator
80  * @param bits size in bits
81  * @param set_high_bit if true, the highest bit is always set
82  *
83  * @see randomize
84  */
85  BigInt(RandomNumberGenerator& rng, size_t bits, bool set_high_bit = true);
86 
87  /**
88  * Create BigInt of specified size, all zeros
89  * @param sign the sign
90  * @param n size of the internal register in words
91  */
92  BigInt(Sign sign, size_t n);
93 
94  /**
95  * Move constructor
96  */
97  BigInt(BigInt&& other)
98  {
99  this->swap(other);
100  }
101 
102  /**
103  * Move assignment
104  */
106  {
107  if(this != &other)
108  this->swap(other);
109 
110  return (*this);
111  }
112 
113  /**
114  * Copy assignment
115  */
116  BigInt& operator=(const BigInt&) = default;
117 
118  /**
119  * Swap this value with another
120  * @param other BigInt to swap values with
121  */
122  void swap(BigInt& other)
123  {
124  m_reg.swap(other.m_reg);
125  std::swap(m_signedness, other.m_signedness);
126  }
127 
129  {
130  m_reg.swap(reg);
131  }
132 
133  /**
134  * += operator
135  * @param y the BigInt to add to this
136  */
137  BigInt& operator+=(const BigInt& y);
138 
139  /**
140  * -= operator
141  * @param y the BigInt to subtract from this
142  */
143  BigInt& operator-=(const BigInt& y);
144 
145  /**
146  * *= operator
147  * @param y the BigInt to multiply with this
148  */
149  BigInt& operator*=(const BigInt& y);
150 
151  /**
152  * /= operator
153  * @param y the BigInt to divide this by
154  */
155  BigInt& operator/=(const BigInt& y);
156 
157  /**
158  * Modulo operator
159  * @param y the modulus to reduce this by
160  */
161  BigInt& operator%=(const BigInt& y);
162 
163  /**
164  * Modulo operator
165  * @param y the modulus (word) to reduce this by
166  */
167  word operator%=(word y);
168 
169  /**
170  * Left shift operator
171  * @param shift the number of bits to shift this left by
172  */
173  BigInt& operator<<=(size_t shift);
174 
175  /**
176  * Right shift operator
177  * @param shift the number of bits to shift this right by
178  */
179  BigInt& operator>>=(size_t shift);
180 
181  /**
182  * Increment operator
183  */
184  BigInt& operator++() { return (*this += 1); }
185 
186  /**
187  * Decrement operator
188  */
189  BigInt& operator--() { return (*this -= 1); }
190 
191  /**
192  * Postfix increment operator
193  */
194  BigInt operator++(int) { BigInt x = (*this); ++(*this); return x; }
195 
196  /**
197  * Postfix decrement operator
198  */
199  BigInt operator--(int) { BigInt x = (*this); --(*this); return x; }
200 
201  /**
202  * Unary negation operator
203  * @return negative this
204  */
205  BigInt operator-() const;
206 
207  /**
208  * ! operator
209  * @return true iff this is zero, otherwise false
210  */
211  bool operator !() const { return (!is_nonzero()); }
212 
213  /**
214  * Zeroize the BigInt. The size of the underlying register is not
215  * modified.
216  */
217  void clear() { zeroise(m_reg); }
218 
219  /**
220  * Compare this to another BigInt
221  * @param n the BigInt value to compare with
222  * @param check_signs include sign in comparison?
223  * @result if (this<n) return -1, if (this>n) return 1, if both
224  * values are identical return 0 [like Perl's <=> operator]
225  */
226  int32_t cmp(const BigInt& n, bool check_signs = true) const;
227 
228  /**
229  * Test if the integer has an even value
230  * @result true if the integer is even, false otherwise
231  */
232  bool is_even() const { return (get_bit(0) == 0); }
233 
234  /**
235  * Test if the integer has an odd value
236  * @result true if the integer is odd, false otherwise
237  */
238  bool is_odd() const { return (get_bit(0) == 1); }
239 
240  /**
241  * Test if the integer is not zero
242  * @result true if the integer is non-zero, false otherwise
243  */
244  bool is_nonzero() const { return (!is_zero()); }
245 
246  /**
247  * Test if the integer is zero
248  * @result true if the integer is zero, false otherwise
249  */
250  bool is_zero() const
251  {
252  const size_t sw = sig_words();
253 
254  for(size_t i = 0; i != sw; ++i)
255  if(m_reg[i])
256  return false;
257  return true;
258  }
259 
260  /**
261  * Set bit at specified position
262  * @param n bit position to set
263  */
264  void set_bit(size_t n);
265 
266  /**
267  * Clear bit at specified position
268  * @param n bit position to clear
269  */
270  void clear_bit(size_t n);
271 
272  /**
273  * Clear all but the lowest n bits
274  * @param n amount of bits to keep
275  */
276  void mask_bits(size_t n)
277  {
278  if(n == 0) { clear(); return; }
279 
280  const size_t top_word = n / BOTAN_MP_WORD_BITS;
281  const word mask = (static_cast<word>(1) << (n % BOTAN_MP_WORD_BITS)) - 1;
282 
283  if(top_word < size())
284  {
285  const size_t len = size() - (top_word + 1);
286  if (len > 0)
287  {
288  clear_mem(&m_reg[top_word+1], len);
289  }
290  m_reg[top_word] &= mask;
291  }
292  }
293 
294  /**
295  * Return bit value at specified position
296  * @param n the bit offset to test
297  * @result true, if the bit at position n is set, false otherwise
298  */
299  bool get_bit(size_t n) const
300  {
301  return ((word_at(n / BOTAN_MP_WORD_BITS) >> (n % BOTAN_MP_WORD_BITS)) & 1);
302  }
303 
304  /**
305  * Return (a maximum of) 32 bits of the complete value
306  * @param offset the offset to start extracting
307  * @param length amount of bits to extract (starting at offset)
308  * @result the integer extracted from the register starting at
309  * offset with specified length
310  */
311  uint32_t get_substring(size_t offset, size_t length) const;
312 
313  /**
314  * Convert this value into a uint32_t, if it is in the range
315  * [0 ... 2**32-1], or otherwise throw an exception.
316  * @result the value as a uint32_t if conversion is possible
317  */
318  uint32_t to_u32bit() const;
319 
320  /**
321  * @param n the offset to get a byte from
322  * @result byte at offset n
323  */
324  uint8_t byte_at(size_t n) const
325  {
326  return get_byte(sizeof(word) - (n % sizeof(word)) - 1,
327  word_at(n / sizeof(word)));
328  }
329 
330  /**
331  * Return the word at a specified position of the internal register
332  * @param n position in the register
333  * @return value at position n
334  */
335  word word_at(size_t n) const
336  { return ((n < size()) ? m_reg[n] : 0); }
337 
338  void set_word_at(size_t i, word w)
339  {
340  grow_to(i + 1);
341  m_reg[i] = w;
342  }
343 
344  /**
345  * Tests if the sign of the integer is negative
346  * @result true, iff the integer has a negative sign
347  */
348  bool is_negative() const { return (sign() == Negative); }
349 
350  /**
351  * Tests if the sign of the integer is positive
352  * @result true, iff the integer has a positive sign
353  */
354  bool is_positive() const { return (sign() == Positive); }
355 
356  /**
357  * Return the sign of the integer
358  * @result the sign of the integer
359  */
360  Sign sign() const { return (m_signedness); }
361 
362  /**
363  * @result the opposite sign of the represented integer value
364  */
365  Sign reverse_sign() const;
366 
367  /**
368  * Flip the sign of this BigInt
369  */
370  void flip_sign();
371 
372  /**
373  * Set sign of the integer
374  * @param sign new Sign to set
375  */
376  void set_sign(Sign sign);
377 
378  /**
379  * @result absolute (positive) value of this
380  */
381  BigInt abs() const;
382 
383  /**
384  * Give size of internal register
385  * @result size of internal register in words
386  */
387  size_t size() const { return m_reg.size(); }
388 
389  /**
390  * Return how many words we need to hold this value
391  * @result significant words of the represented integer value
392  */
393  size_t sig_words() const
394  {
395  const word* x = m_reg.data();
396  size_t sig = m_reg.size();
397 
398  while(sig && (x[sig-1] == 0))
399  sig--;
400  return sig;
401  }
402 
403  /**
404  * Give byte length of the integer
405  * @result byte length of the represented integer value
406  */
407  size_t bytes() const;
408 
409  /**
410  * Get the bit length of the integer
411  * @result bit length of the represented integer value
412  */
413  size_t bits() const;
414 
415  /**
416  * Return a mutable pointer to the register
417  * @result a pointer to the start of the internal register
418  */
419  word* mutable_data() { return m_reg.data(); }
420 
421  /**
422  * Return a const pointer to the register
423  * @result a pointer to the start of the internal register
424  */
425  const word* data() const { return m_reg.data(); }
426 
428  const secure_vector<word>& get_word_vector() const { return m_reg; }
429 
430  /**
431  * Increase internal register buffer to at least n words
432  * @param n new size of register
433  */
434  void grow_to(size_t n);
435 
436  /**
437  * Fill BigInt with a random number with size of bitsize
438  *
439  * If \p set_high_bit is true, the highest bit will be set, which causes
440  * the entropy to be \a bits-1. Otherwise the highest bit is randomly chosen
441  * by the rng, causing the entropy to be \a bits.
442  *
443  * @param rng the random number generator to use
444  * @param bitsize number of bits the created random value should have
445  * @param set_high_bit if true, the highest bit is always set
446  */
447  void randomize(RandomNumberGenerator& rng, size_t bitsize, bool set_high_bit = true);
448 
449  /**
450  * Store BigInt-value in a given byte array
451  * @param buf destination byte array for the integer value
452  */
453  void binary_encode(uint8_t buf[]) const;
454 
455  /**
456  * Read integer value from a byte array with given size
457  * @param buf byte array buffer containing the integer
458  * @param length size of buf
459  */
460  void binary_decode(const uint8_t buf[], size_t length);
461 
462  /**
463  * Read integer value from a byte array (secure_vector<uint8_t>)
464  * @param buf the array to load from
465  */
467  {
468  binary_decode(buf.data(), buf.size());
469  }
470 
471  /**
472  * @param base the base to measure the size for
473  * @return size of this integer in base base
474  */
475  size_t encoded_size(Base base = Binary) const;
476 
477  /**
478  * @param rng a random number generator
479  * @param min the minimum value
480  * @param max the maximum value
481  * @return random integer in [min,max)
482  */
483  static BigInt random_integer(RandomNumberGenerator& rng,
484  const BigInt& min,
485  const BigInt& max);
486 
487  /**
488  * Create a power of two
489  * @param n the power of two to create
490  * @return bigint representing 2^n
491  */
492  static BigInt power_of_2(size_t n)
493  {
494  BigInt b;
495  b.set_bit(n);
496  return b;
497  }
498 
499  /**
500  * Encode the integer value from a BigInt to a std::vector of bytes
501  * @param n the BigInt to use as integer source
502  * @param base number-base of resulting byte array representation
503  * @result secure_vector of bytes containing the integer with given base
504  */
505  static std::vector<uint8_t> encode(const BigInt& n, Base base = Binary);
506 
507  /**
508  * Encode the integer value from a BigInt to a secure_vector of bytes
509  * @param n the BigInt to use as integer source
510  * @param base number-base of resulting byte array representation
511  * @result secure_vector of bytes containing the integer with given base
512  */
513  static secure_vector<uint8_t> encode_locked(const BigInt& n,
514  Base base = Binary);
515 
516  /**
517  * Encode the integer value from a BigInt to a byte array
518  * @param buf destination byte array for the encoded integer
519  * value with given base
520  * @param n the BigInt to use as integer source
521  * @param base number-base of resulting byte array representation
522  */
523  static void encode(uint8_t buf[], const BigInt& n, Base base = Binary);
524 
525  /**
526  * Create a BigInt from an integer in a byte array
527  * @param buf the binary value to load
528  * @param length size of buf
529  * @param base number-base of the integer in buf
530  * @result BigInt representing the integer in the byte array
531  */
532  static BigInt decode(const uint8_t buf[], size_t length,
533  Base base = Binary);
534 
535  /**
536  * Create a BigInt from an integer in a byte array
537  * @param buf the binary value to load
538  * @param base number-base of the integer in buf
539  * @result BigInt representing the integer in the byte array
540  */
542  Base base = Binary)
543  {
544  return BigInt::decode(buf.data(), buf.size(), base);
545  }
546 
547  /**
548  * Create a BigInt from an integer in a byte array
549  * @param buf the binary value to load
550  * @param base number-base of the integer in buf
551  * @result BigInt representing the integer in the byte array
552  */
553  static BigInt decode(const std::vector<uint8_t>& buf,
554  Base base = Binary)
555  {
556  return BigInt::decode(buf.data(), buf.size(), base);
557  }
558 
559  /**
560  * Encode a BigInt to a byte array according to IEEE 1363
561  * @param n the BigInt to encode
562  * @param bytes the length of the resulting secure_vector<uint8_t>
563  * @result a secure_vector<uint8_t> containing the encoded BigInt
564  */
565  static secure_vector<uint8_t> encode_1363(const BigInt& n, size_t bytes);
566 
567  static void encode_1363(uint8_t out[], size_t bytes, const BigInt& n);
568 
569  /**
570  * Encode two BigInt to a byte array according to IEEE 1363
571  * @param n1 the first BigInt to encode
572  * @param n2 the second BigInt to encode
573  * @param bytes the length of the encoding of each single BigInt
574  * @result a secure_vector<uint8_t> containing the concatenation of the two encoded BigInt
575  */
576  static secure_vector<uint8_t> encode_fixed_length_int_pair(const BigInt& n1, const BigInt& n2, size_t bytes);
577 
578  private:
579  secure_vector<word> m_reg;
580  Sign m_signedness = Positive;
581  };
582 
583 /*
584 * Arithmetic Operators
585 */
586 BigInt BOTAN_DLL operator+(const BigInt& x, const BigInt& y);
587 BigInt BOTAN_DLL operator-(const BigInt& x, const BigInt& y);
588 BigInt BOTAN_DLL operator*(const BigInt& x, const BigInt& y);
589 BigInt BOTAN_DLL operator/(const BigInt& x, const BigInt& d);
590 BigInt BOTAN_DLL operator%(const BigInt& x, const BigInt& m);
591 word BOTAN_DLL operator%(const BigInt& x, word m);
592 BigInt BOTAN_DLL operator<<(const BigInt& x, size_t n);
593 BigInt BOTAN_DLL operator>>(const BigInt& x, size_t n);
594 
595 /*
596 * Comparison Operators
597 */
598 inline bool operator==(const BigInt& a, const BigInt& b)
599  { return (a.cmp(b) == 0); }
600 inline bool operator!=(const BigInt& a, const BigInt& b)
601  { return (a.cmp(b) != 0); }
602 inline bool operator<=(const BigInt& a, const BigInt& b)
603  { return (a.cmp(b) <= 0); }
604 inline bool operator>=(const BigInt& a, const BigInt& b)
605  { return (a.cmp(b) >= 0); }
606 inline bool operator<(const BigInt& a, const BigInt& b)
607  { return (a.cmp(b) < 0); }
608 inline bool operator>(const BigInt& a, const BigInt& b)
609  { return (a.cmp(b) > 0); }
610 
611 /*
612 * I/O Operators
613 */
614 BOTAN_DLL std::ostream& operator<<(std::ostream&, const BigInt&);
615 BOTAN_DLL std::istream& operator>>(std::istream&, BigInt&);
616 
617 }
618 
619 namespace std {
620 
621 template<>
622 inline void swap<Botan::BigInt>(Botan::BigInt& x, Botan::BigInt& y)
623  {
624  x.swap(y);
625  }
626 
627 }
628 
629 #endif
uint32_t to_u32bit(const std::string &str)
Definition: parsing.cpp:18
word word_at(size_t n) const
Definition: bigint.h:335
size_t sig_words() const
Definition: bigint.h:393
bool operator>=(const X509_Time &t1, const X509_Time &t2)
Definition: asn1_time.cpp:268
bool is_odd() const
Definition: bigint.h:238
bool is_even() const
Definition: bigint.h:232
BigInt(BigInt &&other)
Definition: bigint.h:97
BigInt operator--(int)
Definition: bigint.h:199
secure_vector< uint8_t > decode(DataSource &source, std::string &label)
Definition: pem.cpp:68
bool operator>(const X509_Time &t1, const X509_Time &t2)
Definition: asn1_time.cpp:273
BigInt & operator--()
Definition: bigint.h:189
std::istream & operator>>(std::istream &in, X509_DN &dn)
Definition: x509_dn.cpp:325
bool operator!=(const AlgorithmIdentifier &a1, const AlgorithmIdentifier &a2)
Definition: alg_id.cpp:82
std::string encode(const uint8_t der[], size_t length, const std::string &label, size_t width)
Definition: pem.cpp:43
void clear_mem(T *ptr, size_t n)
Definition: mem_ops.h:57
void set_bit(size_t n)
Definition: bigint.cpp:157
std::ostream & operator<<(std::ostream &out, const X509_DN &dn)
Definition: x509_dn.cpp:299
secure_vector< word > & get_word_vector()
Definition: bigint.h:427
bool operator==(const AlgorithmIdentifier &a1, const AlgorithmIdentifier &a2)
Definition: alg_id.cpp:67
Definition: bigint.h:619
static BigInt decode(const std::vector< uint8_t > &buf, Base base=Binary)
Definition: bigint.h:553
word * mutable_data()
Definition: bigint.h:419
void swap_reg(secure_vector< word > &reg)
Definition: bigint.h:128
bool is_negative() const
Definition: bigint.h:348
static BigInt decode(const secure_vector< uint8_t > &buf, Base base=Binary)
Definition: bigint.h:541
size_t size() const
Definition: bigint.h:387
void swap(BigInt &other)
Definition: bigint.h:122
void mask_bits(size_t n)
Definition: bigint.h:276
bool operator<(const OID &a, const OID &b)
Definition: asn1_oid.cpp:105
OID operator+(const OID &oid, uint32_t component)
Definition: asn1_oid.cpp:87
bool is_nonzero() const
Definition: bigint.h:244
BigInt & operator++()
Definition: bigint.h:184
BigInt operator%(const BigInt &n, const BigInt &mod)
Definition: big_ops3.cpp:118
int32_t cmp(const BigInt &n, bool check_signs=true) const
Definition: bigint.cpp:98
BigInt abs(const BigInt &n)
Definition: numthry.h:55
std::vector< T, secure_allocator< T >> secure_vector
Definition: secmem.h:121
void binary_decode(const secure_vector< uint8_t > &buf)
Definition: bigint.h:466
BigInt operator++(int)
Definition: bigint.h:194
const secure_vector< word > & get_word_vector() const
Definition: bigint.h:428
std::vector< T, Alloc > & operator+=(std::vector< T, Alloc > &out, const std::vector< T, Alloc2 > &in)
Definition: secmem.h:161
const word * data() const
Definition: bigint.h:425
BigInt operator*(const BigInt &x, const BigInt &y)
Definition: big_ops3.cpp:84
static BigInt power_of_2(size_t n)
Definition: bigint.h:492
Definition: alg_id.cpp:13
T max(T a, T b)
Definition: ct_utils.h:173
void clear()
Definition: bigint.h:217
T is_zero(T x)
Definition: ct_utils.h:110
bool is_positive() const
Definition: bigint.h:354
void set_word_at(size_t i, word w)
Definition: bigint.h:338
T min(T a, T b)
Definition: ct_utils.h:180
uint8_t get_byte(size_t byte_num, T input)
Definition: loadstor.h:47
BigInt & operator=(BigInt &&other)
Definition: bigint.h:105
bool operator<=(const X509_Time &t1, const X509_Time &t2)
Definition: asn1_time.cpp:266
bool get_bit(size_t n) const
Definition: bigint.h:299
bool is_zero() const
Definition: bigint.h:250
BigInt operator-(const BigInt &x, const BigInt &y)
Definition: big_ops3.cpp:49
static BigInt decode(const uint8_t buf[], size_t length, Base base=Binary)
Definition: big_code.cpp:114
uint8_t byte_at(size_t n) const
Definition: bigint.h:324
BigInt operator/(const BigInt &x, const BigInt &y)
Definition: big_ops3.cpp:108
void zeroise(std::vector< T, Alloc > &vec)
Definition: secmem.h:211
Sign sign() const
Definition: bigint.h:360