Botan  1.11.15
src/lib/math/bigint/bigint.h
Go to the documentation of this file.
00001 /*
00002 * BigInt
00003 * (C) 1999-2008,2012 Jack Lloyd
00004 *     2007 FlexSecure
00005 *
00006 * Botan is released under the Simplified BSD License (see license.txt)
00007 */
00008 
00009 #ifndef BOTAN_BIGINT_H__
00010 #define BOTAN_BIGINT_H__
00011 
00012 #include <botan/rng.h>
00013 #include <botan/secmem.h>
00014 #include <botan/mp_types.h>
00015 #include <botan/get_byte.h>
00016 #include <iosfwd>
00017 
00018 namespace Botan {
00019 
00020 /**
00021 * Arbitrary precision integer
00022 */
00023 class BOTAN_DLL BigInt
00024    {
00025    public:
00026      /**
00027      * Base enumerator for encoding and decoding
00028      */
00029      enum Base { Decimal = 10, Hexadecimal = 16, Binary = 256 };
00030 
00031      /**
00032      * Sign symbol definitions for positive and negative numbers
00033      */
00034      enum Sign { Negative = 0, Positive = 1 };
00035 
00036      /**
00037      * DivideByZero Exception
00038      */
00039      struct BOTAN_DLL DivideByZero : public Exception
00040         { DivideByZero() : Exception("BigInt divide by zero") {} };
00041 
00042      /**
00043      * Create empty BigInt
00044      */
00045      BigInt() { m_signedness = Positive; }
00046 
00047      /**
00048      * Create BigInt from 64 bit integer
00049      * @param n initial value of this BigInt
00050      */
00051      BigInt(u64bit n);
00052 
00053      /**
00054      * Copy Constructor
00055      * @param other the BigInt to copy
00056      */
00057      BigInt(const BigInt& other);
00058 
00059      /**
00060      * Create BigInt from a string. If the string starts with 0x the
00061      * rest of the string will be interpreted as hexadecimal digits.
00062      * Otherwise, it will be interpreted as a decimal number.
00063      *
00064      * @param str the string to parse for an integer value
00065      */
00066      BigInt(const std::string& str);
00067 
00068      /**
00069      * Create a BigInt from an integer in a byte array
00070      * @param buf the byte array holding the value
00071      * @param length size of buf
00072      * @param base is the number base of the integer in buf
00073      */
00074      BigInt(const byte buf[], size_t length, Base base = Binary);
00075 
00076      /**
00077      * Create a random BigInt of the specified size
00078      * @param rng random number generator
00079      * @param bits size in bits
00080      */
00081      BigInt(RandomNumberGenerator& rng, size_t bits);
00082 
00083      /**
00084      * Create BigInt of specified size, all zeros
00085      * @param sign the sign
00086      * @param n size of the internal register in words
00087      */
00088      BigInt(Sign sign, size_t n);
00089 
00090      /**
00091      * Move constructor
00092      */
00093      BigInt(BigInt&& other)
00094         {
00095         this->swap(other);
00096         }
00097 
00098      /**
00099      * Move assignment
00100      */
00101      BigInt& operator=(BigInt&& other)
00102         {
00103         if(this != &other)
00104            this->swap(other);
00105 
00106         return (*this);
00107         }
00108 
00109      /**
00110      * Copy assignment
00111      */
00112      BigInt& operator=(const BigInt&) = default;
00113 
00114      /**
00115      * Swap this value with another
00116      * @param other BigInt to swap values with
00117      */
00118      void swap(BigInt& other)
00119         {
00120         m_reg.swap(other.m_reg);
00121         std::swap(m_signedness, other.m_signedness);
00122         }
00123 
00124      void swap_reg(secure_vector<word>& reg)
00125         {
00126         m_reg.swap(reg);
00127         }
00128 
00129      /**
00130      * += operator
00131      * @param y the BigInt to add to this
00132      */
00133      BigInt& operator+=(const BigInt& y);
00134 
00135      /**
00136      * -= operator
00137      * @param y the BigInt to subtract from this
00138      */
00139      BigInt& operator-=(const BigInt& y);
00140 
00141      /**
00142      * *= operator
00143      * @param y the BigInt to multiply with this
00144      */
00145      BigInt& operator*=(const BigInt& y);
00146 
00147      /**
00148      * /= operator
00149      * @param y the BigInt to divide this by
00150      */
00151      BigInt& operator/=(const BigInt& y);
00152 
00153      /**
00154      * Modulo operator
00155      * @param y the modulus to reduce this by
00156      */
00157      BigInt& operator%=(const BigInt& y);
00158 
00159      /**
00160      * Modulo operator
00161      * @param y the modulus (word) to reduce this by
00162      */
00163      word    operator%=(word y);
00164 
00165      /**
00166      * Left shift operator
00167      * @param shift the number of bits to shift this left by
00168      */
00169      BigInt& operator<<=(size_t shift);
00170 
00171      /**
00172      * Right shift operator
00173      * @param shift the number of bits to shift this right by
00174      */
00175      BigInt& operator>>=(size_t shift);
00176 
00177      /**
00178      * Increment operator
00179      */
00180      BigInt& operator++() { return (*this += 1); }
00181 
00182      /**
00183      * Decrement operator
00184      */
00185      BigInt& operator--() { return (*this -= 1); }
00186 
00187      /**
00188      * Postfix increment operator
00189      */
00190      BigInt  operator++(int) { BigInt x = (*this); ++(*this); return x; }
00191 
00192      /**
00193      * Postfix decrement operator
00194      */
00195      BigInt  operator--(int) { BigInt x = (*this); --(*this); return x; }
00196 
00197      /**
00198      * Unary negation operator
00199      * @return negative this
00200      */
00201      BigInt operator-() const;
00202 
00203      /**
00204      * ! operator
00205      * @return true iff this is zero, otherwise false
00206      */
00207      bool operator !() const { return (!is_nonzero()); }
00208 
00209      /**
00210      * Zeroize the BigInt. The size of the underlying register is not
00211      * modified.
00212      */
00213      void clear() { zeroise(m_reg); }
00214 
00215      /**
00216      * Compare this to another BigInt
00217      * @param n the BigInt value to compare with
00218      * @param check_signs include sign in comparison?
00219      * @result if (this<n) return -1, if (this>n) return 1, if both
00220      * values are identical return 0 [like Perl's <=> operator]
00221      */
00222      s32bit cmp(const BigInt& n, bool check_signs = true) const;
00223 
00224      /**
00225      * Test if the integer has an even value
00226      * @result true if the integer is even, false otherwise
00227      */
00228      bool is_even() const { return (get_bit(0) == 0); }
00229 
00230      /**
00231      * Test if the integer has an odd value
00232      * @result true if the integer is odd, false otherwise
00233      */
00234      bool is_odd()  const { return (get_bit(0) == 1); }
00235 
00236      /**
00237      * Test if the integer is not zero
00238      * @result true if the integer is non-zero, false otherwise
00239      */
00240      bool is_nonzero() const { return (!is_zero()); }
00241 
00242      /**
00243      * Test if the integer is zero
00244      * @result true if the integer is zero, false otherwise
00245      */
00246      bool is_zero() const
00247         {
00248         const size_t sw = sig_words();
00249 
00250         for(size_t i = 0; i != sw; ++i)
00251            if(m_reg[i])
00252               return false;
00253         return true;
00254         }
00255 
00256      /**
00257      * Set bit at specified position
00258      * @param n bit position to set
00259      */
00260      void set_bit(size_t n);
00261 
00262      /**
00263      * Clear bit at specified position
00264      * @param n bit position to clear
00265      */
00266      void clear_bit(size_t n);
00267 
00268      /**
00269      * Clear all but the lowest n bits
00270      * @param n amount of bits to keep
00271      */
00272      void mask_bits(size_t n)
00273         {
00274         if(n == 0) { clear(); return; }
00275 
00276         const size_t top_word = n / BOTAN_MP_WORD_BITS;
00277         const word mask = (static_cast<word>(1) << (n % BOTAN_MP_WORD_BITS)) - 1;
00278 
00279         if(top_word < size())
00280            {
00281            clear_mem(&m_reg[top_word+1], size() - (top_word + 1));
00282            m_reg[top_word] &= mask;
00283            }
00284         }
00285 
00286      /**
00287      * Return bit value at specified position
00288      * @param n the bit offset to test
00289      * @result true, if the bit at position n is set, false otherwise
00290      */
00291      bool get_bit(size_t n) const
00292         {
00293         return ((word_at(n / BOTAN_MP_WORD_BITS) >> (n % BOTAN_MP_WORD_BITS)) & 1);
00294         }
00295 
00296      /**
00297      * Return (a maximum of) 32 bits of the complete value
00298      * @param offset the offset to start extracting
00299      * @param length amount of bits to extract (starting at offset)
00300      * @result the integer extracted from the register starting at
00301      * offset with specified length
00302      */
00303      u32bit get_substring(size_t offset, size_t length) const;
00304 
00305      /**
00306      * Convert this value into a u32bit, if it is in the range
00307      * [0 ... 2**32-1], or otherwise throw an exception.
00308      * @result the value as a u32bit if conversion is possible
00309      */
00310      u32bit to_u32bit() const;
00311 
00312      /**
00313      * @param n the offset to get a byte from
00314      * @result byte at offset n
00315      */
00316      byte byte_at(size_t n) const
00317         {
00318         return get_byte(sizeof(word) - (n % sizeof(word)) - 1,
00319                         word_at(n / sizeof(word)));
00320         }
00321 
00322      /**
00323      * Return the word at a specified position of the internal register
00324      * @param n position in the register
00325      * @return value at position n
00326      */
00327      word word_at(size_t n) const
00328         { return ((n < size()) ? m_reg[n] : 0); }
00329 
00330      void set_word_at(size_t i, word w)
00331         {
00332         grow_to(i + 1);
00333         m_reg[i] = w;
00334         }
00335 
00336      /**
00337      * Tests if the sign of the integer is negative
00338      * @result true, iff the integer has a negative sign
00339      */
00340      bool is_negative() const { return (sign() == Negative); }
00341 
00342      /**
00343      * Tests if the sign of the integer is positive
00344      * @result true, iff the integer has a positive sign
00345      */
00346      bool is_positive() const { return (sign() == Positive); }
00347 
00348      /**
00349      * Return the sign of the integer
00350      * @result the sign of the integer
00351      */
00352      Sign sign() const { return (m_signedness); }
00353 
00354      /**
00355      * @result the opposite sign of the represented integer value
00356      */
00357      Sign reverse_sign() const;
00358 
00359      /**
00360      * Flip the sign of this BigInt
00361      */
00362      void flip_sign();
00363 
00364      /**
00365      * Set sign of the integer
00366      * @param sign new Sign to set
00367      */
00368      void set_sign(Sign sign);
00369 
00370      /**
00371      * @result absolute (positive) value of this
00372      */
00373      BigInt abs() const;
00374 
00375      /**
00376      * Give size of internal register
00377      * @result size of internal register in words
00378      */
00379      size_t size() const { return m_reg.size(); }
00380 
00381      /**
00382      * Return how many words we need to hold this value
00383      * @result significant words of the represented integer value
00384      */
00385      size_t sig_words() const
00386         {
00387         const word* x = &m_reg[0];
00388         size_t sig = m_reg.size();
00389 
00390         while(sig && (x[sig-1] == 0))
00391            sig--;
00392         return sig;
00393         }
00394 
00395      /**
00396      * Give byte length of the integer
00397      * @result byte length of the represented integer value
00398      */
00399      size_t bytes() const { return (bits() + 7) / 8; }
00400 
00401      /**
00402      * Get the bit length of the integer
00403      * @result bit length of the represented integer value
00404      */
00405      size_t bits() const;
00406 
00407      /**
00408      * Return a mutable pointer to the register
00409      * @result a pointer to the start of the internal register
00410      */
00411      word* mutable_data() { return &m_reg[0]; }
00412 
00413      /**
00414      * Return a const pointer to the register
00415      * @result a pointer to the start of the internal register
00416      */
00417      const word* data() const { return &m_reg[0]; }
00418 
00419      secure_vector<word>& get_word_vector() { return m_reg; }
00420      const secure_vector<word>& get_word_vector() const { return m_reg; }
00421 
00422      /**
00423      * Increase internal register buffer to at least n words
00424      * @param n new size of register
00425      */
00426      void grow_to(size_t n)
00427         {
00428         if(n > size())
00429            m_reg.resize(n + (8 - n % 8));
00430         }
00431 
00432      /**
00433      * Fill BigInt with a random number with size of bitsize
00434      * @param rng the random number generator to use
00435      * @param bitsize number of bits the created random value should have
00436      */
00437      void randomize(RandomNumberGenerator& rng, size_t bitsize = 0);
00438 
00439      /**
00440      * Store BigInt-value in a given byte array
00441      * @param buf destination byte array for the integer value
00442      */
00443      void binary_encode(byte buf[]) const;
00444 
00445      /**
00446      * Read integer value from a byte array with given size
00447      * @param buf byte array buffer containing the integer
00448      * @param length size of buf
00449      */
00450      void binary_decode(const byte buf[], size_t length);
00451 
00452      /**
00453      * Read integer value from a byte array (secure_vector<byte>)
00454      * @param buf the array to load from
00455      */
00456      void binary_decode(const secure_vector<byte>& buf)
00457         {
00458         binary_decode(&buf[0], buf.size());
00459         }
00460 
00461      /**
00462      * @param base the base to measure the size for
00463      * @return size of this integer in base base
00464      */
00465      size_t encoded_size(Base base = Binary) const;
00466 
00467      /**
00468      * @param rng a random number generator
00469      * @param min the minimum value
00470      * @param max the maximum value
00471      * @return random integer in [min,max)
00472      */
00473      static BigInt random_integer(RandomNumberGenerator& rng,
00474                                   const BigInt& min,
00475                                   const BigInt& max);
00476 
00477      /**
00478      * Create a power of two
00479      * @param n the power of two to create
00480      * @return bigint representing 2^n
00481      */
00482      static BigInt power_of_2(size_t n)
00483         {
00484         BigInt b;
00485         b.set_bit(n);
00486         return b;
00487         }
00488 
00489      /**
00490      * Encode the integer value from a BigInt to a std::vector of bytes
00491      * @param n the BigInt to use as integer source
00492      * @param base number-base of resulting byte array representation
00493      * @result secure_vector of bytes containing the integer with given base
00494      */
00495      static std::vector<byte> encode(const BigInt& n, Base base = Binary);
00496 
00497      /**
00498      * Encode the integer value from a BigInt to a secure_vector of bytes
00499      * @param n the BigInt to use as integer source
00500      * @param base number-base of resulting byte array representation
00501      * @result secure_vector of bytes containing the integer with given base
00502      */
00503      static secure_vector<byte> encode_locked(const BigInt& n,
00504                                               Base base = Binary);
00505 
00506      /**
00507      * Encode the integer value from a BigInt to a byte array
00508      * @param buf destination byte array for the encoded integer
00509      * value with given base
00510      * @param n the BigInt to use as integer source
00511      * @param base number-base of resulting byte array representation
00512      */
00513      static void encode(byte buf[], const BigInt& n, Base base = Binary);
00514 
00515      /**
00516      * Create a BigInt from an integer in a byte array
00517      * @param buf the binary value to load
00518      * @param length size of buf
00519      * @param base number-base of the integer in buf
00520      * @result BigInt representing the integer in the byte array
00521      */
00522      static BigInt decode(const byte buf[], size_t length,
00523                           Base base = Binary);
00524 
00525      /**
00526      * Create a BigInt from an integer in a byte array
00527      * @param buf the binary value to load
00528      * @param base number-base of the integer in buf
00529      * @result BigInt representing the integer in the byte array
00530      */
00531      static BigInt decode(const secure_vector<byte>& buf,
00532                           Base base = Binary)
00533         {
00534         return BigInt::decode(&buf[0], buf.size(), base);
00535         }
00536 
00537      /**
00538      * Create a BigInt from an integer in a byte array
00539      * @param buf the binary value to load
00540      * @param base number-base of the integer in buf
00541      * @result BigInt representing the integer in the byte array
00542      */
00543      static BigInt decode(const std::vector<byte>& buf,
00544                           Base base = Binary)
00545         {
00546         return BigInt::decode(&buf[0], buf.size(), base);
00547         }
00548 
00549      /**
00550      * Encode a BigInt to a byte array according to IEEE 1363
00551      * @param n the BigInt to encode
00552      * @param bytes the length of the resulting secure_vector<byte>
00553      * @result a secure_vector<byte> containing the encoded BigInt
00554      */
00555      static secure_vector<byte> encode_1363(const BigInt& n, size_t bytes);
00556 
00557    private:
00558       secure_vector<word> m_reg;
00559       Sign m_signedness = Positive;
00560    };
00561 
00562 /*
00563 * Arithmetic Operators
00564 */
00565 BigInt BOTAN_DLL operator+(const BigInt& x, const BigInt& y);
00566 BigInt BOTAN_DLL operator-(const BigInt& x, const BigInt& y);
00567 BigInt BOTAN_DLL operator*(const BigInt& x, const BigInt& y);
00568 BigInt BOTAN_DLL operator/(const BigInt& x, const BigInt& d);
00569 BigInt BOTAN_DLL operator%(const BigInt& x, const BigInt& m);
00570 word   BOTAN_DLL operator%(const BigInt& x, word m);
00571 BigInt BOTAN_DLL operator<<(const BigInt& x, size_t n);
00572 BigInt BOTAN_DLL operator>>(const BigInt& x, size_t n);
00573 
00574 /*
00575 * Comparison Operators
00576 */
00577 inline bool operator==(const BigInt& a, const BigInt& b)
00578    { return (a.cmp(b) == 0); }
00579 inline bool operator!=(const BigInt& a, const BigInt& b)
00580    { return (a.cmp(b) != 0); }
00581 inline bool operator<=(const BigInt& a, const BigInt& b)
00582    { return (a.cmp(b) <= 0); }
00583 inline bool operator>=(const BigInt& a, const BigInt& b)
00584    { return (a.cmp(b) >= 0); }
00585 inline bool operator<(const BigInt& a, const BigInt& b)
00586    { return (a.cmp(b) < 0); }
00587 inline bool operator>(const BigInt& a, const BigInt& b)
00588    { return (a.cmp(b) > 0); }
00589 
00590 /*
00591 * I/O Operators
00592 */
00593 BOTAN_DLL std::ostream& operator<<(std::ostream&, const BigInt&);
00594 BOTAN_DLL std::istream& operator>>(std::istream&, BigInt&);
00595 
00596 }
00597 
00598 namespace std {
00599 
00600 template<>
00601 inline void swap<Botan::BigInt>(Botan::BigInt& x, Botan::BigInt& y)
00602    {
00603    x.swap(y);
00604    }
00605 
00606 }
00607 
00608 #endif