Botan  1.10.9
bigint.h
Go to the documentation of this file.
1 /*
2 * BigInt
3 * (C) 1999-2008 Jack Lloyd
4 * 2007 FlexSecure
5 *
6 * Distributed under the terms of the Botan license
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 <iosfwd>
16 
17 namespace Botan {
18 
19 /**
20 * Arbitrary precision integer
21 */
22 class BOTAN_DLL BigInt
23  {
24  public:
25  /**
26  * Base enumerator for encoding and decoding
27  */
28  enum Base { Octal = 8, Decimal = 10, Hexadecimal = 16, Binary = 256 };
29 
30  /**
31  * Sign symbol definitions for positive and negative numbers
32  */
33  enum Sign { Negative = 0, Positive = 1 };
34 
35  /**
36  * Number types (currently only power-of-2 supported)
37  */
38  enum NumberType { Power2 };
39 
40  /**
41  * DivideByZero Exception
42  */
43  struct BOTAN_DLL DivideByZero : public Exception
44  { DivideByZero() : Exception("BigInt divide by zero") {} };
45 
46  /**
47  * += operator
48  * @param y the BigInt to add to this
49  */
50  BigInt& operator+=(const BigInt& y);
51 
52  /**
53  * -= operator
54  * @param y the BigInt to subtract from this
55  */
56  BigInt& operator-=(const BigInt& y);
57 
58  /**
59  * *= operator
60  * @param y the BigInt to multiply with this
61  */
62  BigInt& operator*=(const BigInt& y);
63 
64  /**
65  * /= operator
66  * @param y the BigInt to divide this by
67  */
68  BigInt& operator/=(const BigInt& y);
69 
70  /**
71  * Modulo operator
72  * @param y the modulus to reduce this by
73  */
74  BigInt& operator%=(const BigInt& y);
75 
76  /**
77  * Modulo operator
78  * @param y the modulus (word) to reduce this by
79  */
80  word operator%=(word y);
81 
82  /**
83  * Left shift operator
84  * @param shift the number of bits to shift this left by
85  */
86  BigInt& operator<<=(size_t shift);
87 
88  /**
89  * Right shift operator
90  * @param shift the number of bits to shift this right by
91  */
92  BigInt& operator>>=(size_t shift);
93 
94  /**
95  * Increment operator
96  */
97  BigInt& operator++() { return (*this += 1); }
98 
99  /**
100  * Decrement operator
101  */
102  BigInt& operator--() { return (*this -= 1); }
103 
104  /**
105  * Postfix increment operator
106  */
107  BigInt operator++(int) { BigInt x = (*this); ++(*this); return x; }
108 
109  /**
110  * Postfix decrement operator
111  */
112  BigInt operator--(int) { BigInt x = (*this); --(*this); return x; }
113 
114  /**
115  * Unary negation operator
116  * @return negative this
117  */
118  BigInt operator-() const;
119 
120  /**
121  * ! operator
122  * @return true iff this is zero, otherwise false
123  */
124  bool operator !() const { return (!is_nonzero()); }
125 
126  /**
127  * [] operator (array access)
128  * @param i a word index
129  * @return the word at index i
130  */
131  word& operator[](size_t i) { return reg[i]; }
132 
133  /**
134  * [] operator (array access)
135  * @param i a word index
136  * @return the word at index i
137  */
138  const word& operator[](size_t i) const { return reg[i]; }
139 
140  /**
141  * Zeroize the BigInt
142  */
143  void clear() { zeroise(reg); }
144 
145  /**
146  * Compare this to another BigInt
147  * @param n the BigInt value to compare with
148  * @param check_signs include sign in comparison?
149  * @result if (this<n) return -1, if (this>n) return 1, if both
150  * values are identical return 0 [like Perl's <=> operator]
151  */
152  s32bit cmp(const BigInt& n, bool check_signs = true) const;
153 
154  /**
155  * Test if the integer has an even value
156  * @result true if the integer is even, false otherwise
157  */
158  bool is_even() const { return (get_bit(0) == 0); }
159 
160  /**
161  * Test if the integer has an odd value
162  * @result true if the integer is odd, false otherwise
163  */
164  bool is_odd() const { return (get_bit(0) == 1); }
165 
166  /**
167  * Test if the integer is not zero
168  * @result true if the integer is non-zero, false otherwise
169  */
170  bool is_nonzero() const { return (!is_zero()); }
171 
172  /**
173  * Test if the integer is zero
174  * @result true if the integer is zero, false otherwise
175  */
176  bool is_zero() const
177  {
178  const size_t sw = sig_words();
179 
180  for(size_t i = 0; i != sw; ++i)
181  if(reg[i])
182  return false;
183  return true;
184  }
185 
186  /**
187  * Set bit at specified position
188  * @param n bit position to set
189  */
190  void set_bit(size_t n);
191 
192  /**
193  * Clear bit at specified position
194  * @param n bit position to clear
195  */
196  void clear_bit(size_t n);
197 
198  /**
199  * Clear all but the lowest n bits
200  * @param n amount of bits to keep
201  */
202  void mask_bits(size_t n);
203 
204  /**
205  * Return bit value at specified position
206  * @param n the bit offset to test
207  * @result true, if the bit at position n is set, false otherwise
208  */
209  bool get_bit(size_t n) const;
210 
211  /**
212  * Return (a maximum of) 32 bits of the complete value
213  * @param offset the offset to start extracting
214  * @param length amount of bits to extract (starting at offset)
215  * @result the integer extracted from the register starting at
216  * offset with specified length
217  */
218  u32bit get_substring(size_t offset, size_t length) const;
219 
220  /**
221  * Convert this value into a u32bit, if it is in the range
222  * [0 ... 2**32-1], or otherwise throw an exception.
223  * @result the value as a u32bit if conversion is possible
224  */
225  u32bit to_u32bit() const;
226 
227  /**
228  * @param n the offset to get a byte from
229  * @result byte at offset n
230  */
231  byte byte_at(size_t n) const;
232 
233  /**
234  * Return the word at a specified position of the internal register
235  * @param n position in the register
236  * @return value at position n
237  */
238  word word_at(size_t n) const
239  { return ((n < size()) ? reg[n] : 0); }
240 
241  /**
242  * Tests if the sign of the integer is negative
243  * @result true, iff the integer has a negative sign
244  */
245  bool is_negative() const { return (sign() == Negative); }
246 
247  /**
248  * Tests if the sign of the integer is positive
249  * @result true, iff the integer has a positive sign
250  */
251  bool is_positive() const { return (sign() == Positive); }
252 
253  /**
254  * Return the sign of the integer
255  * @result the sign of the integer
256  */
257  Sign sign() const { return (signedness); }
258 
259  /**
260  * @result the opposite sign of the represented integer value
261  */
262  Sign reverse_sign() const;
263 
264  /**
265  * Flip the sign of this BigInt
266  */
267  void flip_sign();
268 
269  /**
270  * Set sign of the integer
271  * @param sign new Sign to set
272  */
273  void set_sign(Sign sign);
274 
275  /**
276  * @result absolute (positive) value of this
277  */
278  BigInt abs() const;
279 
280  /**
281  * Give size of internal register
282  * @result size of internal register in words
283  */
284  size_t size() const { return get_reg().size(); }
285 
286  /**
287  * Return how many words we need to hold this value
288  * @result significant words of the represented integer value
289  */
290  size_t sig_words() const
291  {
292  const word* x = &reg[0];
293  size_t sig = reg.size();
294 
295  while(sig && (x[sig-1] == 0))
296  sig--;
297  return sig;
298  }
299 
300  /**
301  * Give byte length of the integer
302  * @result byte length of the represented integer value
303  */
304  size_t bytes() const;
305 
306  /**
307  * Get the bit length of the integer
308  * @result bit length of the represented integer value
309  */
310  size_t bits() const;
311 
312  /**
313  * Return a pointer to the big integer word register
314  * @result a pointer to the start of the internal register of
315  * the integer value
316  */
317  const word* data() const { return &reg[0]; }
318 
319  /**
320  * return a reference to the internal register containing the value
321  * @result a reference to the word-array (SecureVector<word>)
322  * with the internal register value (containing the integer
323  * value)
324  */
325  SecureVector<word>& get_reg() { return reg; }
326 
327  /**
328  * return a const reference to the internal register containing the value
329  * @result a const reference to the word-array (SecureVector<word>)
330  * with the internal register value (containing the integer value)
331  */
332  const SecureVector<word>& get_reg() const { return reg; }
333 
334  /**
335  * Assign using a plain word array
336  */
337  void assign(const word x[], size_t length)
338  {
339  reg.resize(length);
340  copy_mem(&reg[0], x, length);
341  }
342 
343  /**
344  * Increase internal register buffer by n words
345  * @param n increase by n words
346  */
347  void grow_reg(size_t n);
348 
349  void grow_to(size_t n);
350 
351  /**
352  * Fill BigInt with a random number with size of bitsize
353  * @param rng the random number generator to use
354  * @param bitsize number of bits the created random value should have
355  */
356  void randomize(RandomNumberGenerator& rng, size_t bitsize = 0);
357 
358  /**
359  * Store BigInt-value in a given byte array
360  * @param buf destination byte array for the integer value
361  */
362  void binary_encode(byte buf[]) const;
363 
364  /**
365  * Read integer value from a byte array with given size
366  * @param buf byte array buffer containing the integer
367  * @param length size of buf
368  */
369  void binary_decode(const byte buf[], size_t length);
370 
371  /**
372  * Read integer value from a byte array (MemoryRegion<byte>)
373  * @param buf the array to load from
374  */
375  void binary_decode(const MemoryRegion<byte>& buf);
376 
377  /**
378  * @param base the base to measure the size for
379  * @return size of this integer in base base
380  */
381  size_t encoded_size(Base base = Binary) const;
382 
383  /**
384  * @param rng a random number generator
385  * @param min the minimum value
386  * @param max the maximum value
387  * @return random integer between min and max
388  */
389  static BigInt random_integer(RandomNumberGenerator& rng,
390  const BigInt& min,
391  const BigInt& max);
392 
393  /**
394  * Encode the integer value from a BigInt to a SecureVector of bytes
395  * @param n the BigInt to use as integer source
396  * @param base number-base of resulting byte array representation
397  * @result SecureVector of bytes containing the integer with given base
398  */
399  static SecureVector<byte> encode(const BigInt& n, Base base = Binary);
400 
401  /**
402  * Encode the integer value from a BigInt to a byte array
403  * @param buf destination byte array for the encoded integer
404  * value with given base
405  * @param n the BigInt to use as integer source
406  * @param base number-base of resulting byte array representation
407  */
408  static void encode(byte buf[], const BigInt& n, Base base = Binary);
409 
410  /**
411  * Create a BigInt from an integer in a byte array
412  * @param buf the binary value to load
413  * @param length size of buf
414  * @param base number-base of the integer in buf
415  * @result BigInt representing the integer in the byte array
416  */
417  static BigInt decode(const byte buf[], size_t length,
418  Base base = Binary);
419 
420  /**
421  * Create a BigInt from an integer in a byte array
422  * @param buf the binary value to load
423  * @param base number-base of the integer in buf
424  * @result BigInt representing the integer in the byte array
425  */
426  static BigInt decode(const MemoryRegion<byte>& buf,
427  Base base = Binary);
428 
429  /**
430  * Encode a BigInt to a byte array according to IEEE 1363
431  * @param n the BigInt to encode
432  * @param bytes the length of the resulting SecureVector<byte>
433  * @result a SecureVector<byte> containing the encoded BigInt
434  */
435  static SecureVector<byte> encode_1363(const BigInt& n, size_t bytes);
436 
437  /**
438  * Swap this value with another
439  * @param other BigInt to swap values with
440  */
441  void swap(BigInt& other);
442 
443  /**
444  * Create empty BigInt
445  */
446  BigInt() { signedness = Positive; }
447 
448  /**
449  * Create BigInt from 64 bit integer
450  * @param n initial value of this BigInt
451  */
452  BigInt(u64bit n);
453 
454  /**
455  * Copy Constructor
456  * @param other the BigInt to copy
457  */
458  BigInt(const BigInt& other);
459 
460  /**
461  * Create BigInt from a string. If the string starts with 0x the
462  * rest of the string will be interpreted as hexadecimal digits.
463  * If the string starts with 0 and the second character is NOT an
464  * 'x' the string will be interpreted as octal digits. If the
465  * string starts with non-zero digit, it will be interpreted as a
466  * decimal number.
467  *
468  * @param str the string to parse for an integer value
469  */
470  BigInt(const std::string& str);
471 
472  /**
473  * Create a BigInt from an integer in a byte array
474  * @param buf the byte array holding the value
475  * @param length size of buf
476  * @param base is the number base of the integer in buf
477  */
478  BigInt(const byte buf[], size_t length, Base base = Binary);
479 
480  /**
481  * Create a random BigInt of the specified size
482  * @param rng random number generator
483  * @param bits size in bits
484  */
485  BigInt(RandomNumberGenerator& rng, size_t bits);
486 
487  /**
488  * Create BigInt of specified size, all zeros
489  * @param sign the sign
490  * @param n size of the internal register in words
491  */
492  BigInt(Sign sign, size_t n);
493 
494  /**
495  * Create a number of the specified type and size
496  * @param type the type of number to create. For Power2,
497  * will create the integer 2^n
498  * @param n a size/length parameter, interpretation depends upon
499  * the value of type
500  */
501  BigInt(NumberType type, size_t n);
502 
503  private:
504  SecureVector<word> reg;
505  Sign signedness;
506  };
507 
508 /*
509 * Arithmetic Operators
510 */
511 BigInt BOTAN_DLL operator+(const BigInt& x, const BigInt& y);
512 BigInt BOTAN_DLL operator-(const BigInt& x, const BigInt& y);
513 BigInt BOTAN_DLL operator*(const BigInt& x, const BigInt& y);
514 BigInt BOTAN_DLL operator/(const BigInt& x, const BigInt& d);
515 BigInt BOTAN_DLL operator%(const BigInt& x, const BigInt& m);
516 word BOTAN_DLL operator%(const BigInt& x, word m);
517 BigInt BOTAN_DLL operator<<(const BigInt& x, size_t n);
518 BigInt BOTAN_DLL operator>>(const BigInt& x, size_t n);
519 
520 /*
521 * Comparison Operators
522 */
523 inline bool operator==(const BigInt& a, const BigInt& b)
524  { return (a.cmp(b) == 0); }
525 inline bool operator!=(const BigInt& a, const BigInt& b)
526  { return (a.cmp(b) != 0); }
527 inline bool operator<=(const BigInt& a, const BigInt& b)
528  { return (a.cmp(b) <= 0); }
529 inline bool operator>=(const BigInt& a, const BigInt& b)
530  { return (a.cmp(b) >= 0); }
531 inline bool operator<(const BigInt& a, const BigInt& b)
532  { return (a.cmp(b) < 0); }
533 inline bool operator>(const BigInt& a, const BigInt& b)
534  { return (a.cmp(b) > 0); }
535 
536 /*
537 * I/O Operators
538 */
539 BOTAN_DLL std::ostream& operator<<(std::ostream&, const BigInt&);
540 BOTAN_DLL std::istream& operator>>(std::istream&, BigInt&);
541 
542 }
543 
544 namespace std {
545 
546 template<>
547 inline void swap(Botan::BigInt& x, Botan::BigInt& y)
548  {
549  x.swap(y);
550  }
551 
552 }
553 
554 #endif
word word_at(size_t n) const
Definition: bigint.h:238
size_t sig_words() const
Definition: bigint.h:290
const word & operator[](size_t i) const
Definition: bigint.h:138
bool is_odd() const
Definition: bigint.h:164
bool is_even() const
Definition: bigint.h:158
BigInt operator--(int)
Definition: bigint.h:112
bool operator!=(const OctetString &s1, const OctetString &s2)
Definition: symkey.cpp:106
void assign(const word x[], size_t length)
Definition: bigint.h:337
BigInt n
Definition: numthry.cpp:26
bool BOTAN_DLL operator>=(const X509_Time &, const X509_Time &)
Definition: asn1_tm.cpp:283
s32bit cmp(const BigInt &n, bool check_signs=true) const
Definition: bigint.cpp:132
BigInt & operator--()
Definition: bigint.h:102
SecureVector< word > & get_reg()
Definition: bigint.h:325
bool operator==(const OctetString &s1, const OctetString &s2)
Definition: symkey.cpp:98
Definition: secmem.h:422
bool is_negative() const
Definition: bigint.h:245
size_t size() const
Definition: bigint.h:284
void swap(BigInt &other)
Definition: bigint.cpp:106
int operator>>(int fd, Pipe &pipe)
Definition: fd_unix.cpp:39
bool is_nonzero() const
Definition: bigint.h:170
signed int s32bit
Definition: types.h:37
unsigned char byte
Definition: types.h:22
BigInt & operator++()
Definition: bigint.h:97
SecureVector< byte > decode(DataSource &source, std::string &label)
Definition: pem.cpp:56
BigInt operator%(const BigInt &n, const BigInt &mod)
Definition: big_ops3.cpp:119
unsigned long long u64bit
Definition: types.h:49
int operator<<(int fd, Pipe &pipe)
Definition: fd_unix.cpp:17
RandomNumberGenerator * rng
Definition: global_rng.cpp:165
BigInt abs(const BigInt &n)
Definition: numthry.h:44
OctetString operator+(const OctetString &k1, const OctetString &k2)
Definition: symkey.cpp:114
BigInt operator++(int)
Definition: bigint.h:107
bool BOTAN_DLL operator>(const X509_Time &, const X509_Time &)
Definition: asn1_tm.cpp:288
word & operator[](size_t i)
Definition: bigint.h:131
const word * data() const
Definition: bigint.h:317
const SecureVector< word > & get_reg() const
Definition: bigint.h:332
BigInt operator*(const BigInt &x, const BigInt &y)
Definition: big_ops3.cpp:83
std::runtime_error Exception
Definition: exceptn.h:19
void copy_mem(T *out, const T *in, size_t n)
Definition: mem_ops.h:22
MemoryRegion< T > & operator+=(MemoryRegion< T > &out, const MemoryRegion< T > &in)
Definition: secmem.h:373
void clear()
Definition: bigint.h:143
std::string encode(const byte der[], size_t length, const std::string &label, size_t width)
Definition: pem.cpp:19
bool BOTAN_DLL operator<(const X509_Time &, const X509_Time &)
Definition: asn1_tm.cpp:286
bool is_positive() const
Definition: bigint.h:251
void swap(Botan::MemoryRegion< T > &x, Botan::MemoryRegion< T > &y)
Definition: secmem.h:425
bool is_zero() const
Definition: bigint.h:176
void swap(Botan::BigInt &x, Botan::BigInt &y)
Definition: bigint.h:547
BigInt operator-(const BigInt &x, const BigInt &y)
Definition: big_ops3.cpp:48
bool BOTAN_DLL operator<=(const X509_Time &, const X509_Time &)
Definition: asn1_tm.cpp:281
u32bit to_u32bit(const std::string &number)
Definition: parsing.cpp:18
void zeroise(MemoryRegion< T > &vec)
Definition: secmem.h:415
BigInt operator/(const BigInt &x, const BigInt &y)
Definition: big_ops3.cpp:109
unsigned int u32bit
Definition: types.h:32
GMP_MPZ base
Definition: gmp_powm.cpp:29
Sign sign() const
Definition: bigint.h:257