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