bigint.h

Go to the documentation of this file.

/*
* BigInt
* (C) 1999-2008 Jack Lloyd
*     2007 FlexSecure
*
* Distributed under the terms of the Botan license
*/
 
#ifndef BOTAN_BIGINT_H__
#define BOTAN_BIGINT_H__
 
#include <botan/rng.h>
#include <botan/secmem.h>
#include <botan/mp_types.h>
#include <iosfwd>
 
namespace Botan {
 
/**
* Arbitrary precision integer
*/
class BOTAN_DLL BigInt
   {
   public:
     /**
     * Base enumerator for encoding and decoding
     */
     enum Base { Octal = 8, Decimal = 10, Hexadecimal = 16, Binary = 256 };
 
     /**
     * Sign symbol definitions for positive and negative numbers
     */
     enum Sign { Negative = 0, Positive = 1 };
 
     /**
     * Number types (currently only power-of-2 supported)
     */
     enum NumberType { Power2 };
 
     /**
     * DivideByZero Exception
     */
     struct BOTAN_DLL DivideByZero : public Exception
        { DivideByZero() : Exception("BigInt divide by zero") {} };
 
     /**
     * += operator
     * @param y the BigInt to add to this
     */
     BigInt& operator+=(const BigInt& y);
 
     /**
     * -= operator
     * @param y the BigInt to subtract from this
     */
     BigInt& operator-=(const BigInt& y);
 
     /**
     * *= operator
     * @param y the BigInt to multiply with this
     */
     BigInt& operator*=(const BigInt& y);
 
     /**
     * /= operator
     * @param y the BigInt to divide this by
     */
     BigInt& operator/=(const BigInt& y);
 
     /**
     * Modulo operator
     * @param y the modulus to reduce this by
     */
     BigInt& operator%=(const BigInt& y);
 
     /**
     * Modulo operator
     * @param y the modulus (word) to reduce this by
     */
     word    operator%=(word y);
 
     /**
     * Left shift operator
     * @param shift the number of bits to shift this left by
     */
     BigInt& operator<<=(size_t shift);
 
     /**
     * Right shift operator
     * @param shift the number of bits to shift this right by
     */
     BigInt& operator>>=(size_t shift);
 
     /**
     * Increment operator
     */
     BigInt& operator++() { return (*this += 1); }
 
     /**
     * Decrement operator
     */
     BigInt& operator--() { return (*this -= 1); }
 
     /**
     * Postfix increment operator
     */
     BigInt  operator++(int) { BigInt x = (*this); ++(*this); return x; }
 
     /**
     * Postfix decrement operator
     */
     BigInt  operator--(int) { BigInt x = (*this); --(*this); return x; }
 
     /**
     * Unary negation operator
     * @return negative this
     */
     BigInt operator-() const;
 
     /**
     * ! operator
     * @return true iff this is zero, otherwise false
     */
     bool operator !() const { return (!is_nonzero()); }
 
     /**
     * [] operator (array access)
     * @param i a word index
     * @return the word at index i
     */
     word& operator[](size_t i) { return reg[i]; }
 
     /**
     * [] operator (array access)
     * @param i a word index
     * @return the word at index i
     */
     const word& operator[](size_t i) const { return reg[i]; }
 
     /**
     * Zeroize the BigInt
     */
     void clear() { zeroise(reg); }
 
     /**
     * Compare this to another BigInt
     * @param n the BigInt value to compare with
     * @param check_signs include sign in comparison?
     * @result if (this<n) return -1, if (this>n) return 1, if both
     * values are identical return 0 [like Perl's <=> operator]
     */
     s32bit cmp(const BigInt& n, bool check_signs = true) const;
 
     /**
     * Test if the integer has an even value
     * @result true if the integer is even, false otherwise
     */
     bool is_even() const { return (get_bit(0) == 0); }
 
     /**
     * Test if the integer has an odd value
     * @result true if the integer is odd, false otherwise
     */
     bool is_odd()  const { return (get_bit(0) == 1); }
 
     /**
     * Test if the integer is not zero
     * @result true if the integer is non-zero, false otherwise
     */
     bool is_nonzero() const { return (!is_zero()); }
 
     /**
     * Test if the integer is zero
     * @result true if the integer is zero, false otherwise
     */
     bool is_zero() const
        {
        const size_t sw = sig_words();
 
        for(size_t i = 0; i != sw; ++i)
           if(reg[i])
              return false;
        return true;
        }
 
     /**
     * Set bit at specified position
     * @param n bit position to set
     */
     void set_bit(size_t n);
 
     /**
     * Clear bit at specified position
     * @param n bit position to clear
     */
     void clear_bit(size_t n);
 
     /**
     * Clear all but the lowest n bits
     * @param n amount of bits to keep
     */
     void mask_bits(size_t n);
 
     /**
     * Return bit value at specified position
     * @param n the bit offset to test
     * @result true, if the bit at position n is set, false otherwise
     */
     bool get_bit(size_t n) const;
 
     /**
     * Return (a maximum of) 32 bits of the complete value
     * @param offset the offset to start extracting
     * @param length amount of bits to extract (starting at offset)
     * @result the integer extracted from the register starting at
     * offset with specified length
     */
     u32bit get_substring(size_t offset, size_t length) const;
 
     /**
     * Convert this value into a u32bit, if it is in the range
     * [0 ... 2**32-1], or otherwise throw an exception.
     * @result the value as a u32bit if conversion is possible
     */
     u32bit to_u32bit() const;
 
     /**
     * @param n the offset to get a byte from
     * @result byte at offset n
     */
     byte byte_at(size_t n) const;
 
     /**
     * Return the word at a specified position of the internal register
     * @param n position in the register
     * @return value at position n
     */
     word word_at(size_t n) const
        { return ((n < size()) ? reg[n] : 0); }
 
     /**
     * Tests if the sign of the integer is negative
     * @result true, iff the integer has a negative sign
     */
     bool is_negative() const { return (sign() == Negative); }
 
     /**
     * Tests if the sign of the integer is positive
     * @result true, iff the integer has a positive sign
     */
     bool is_positive() const { return (sign() == Positive); }
 
     /**
     * Return the sign of the integer
     * @result the sign of the integer
     */
     Sign sign() const { return (signedness); }
 
     /**
     * @result the opposite sign of the represented integer value
     */
     Sign reverse_sign() const;
 
     /**
     * Flip the sign of this BigInt
     */
     void flip_sign();
 
     /**
     * Set sign of the integer
     * @param sign new Sign to set
     */
     void set_sign(Sign sign);
 
     /**
     * @result absolute (positive) value of this
     */
     BigInt abs() const;
 
     /**
     * Give size of internal register
     * @result size of internal register in words
     */
     size_t size() const { return get_reg().size(); }
 
     /**
     * Return how many words we need to hold this value
     * @result significant words of the represented integer value
     */
     size_t sig_words() const
        {
        const word* x = &reg[0];
        size_t sig = reg.size();
 
        while(sig && (x[sig-1] == 0))
           sig--;
        return sig;
        }
 
     /**
     * Give byte length of the integer
     * @result byte length of the represented integer value
     */
     size_t bytes() const;
 
     /**
     * Get the bit length of the integer
     * @result bit length of the represented integer value
     */
     size_t bits() const;
 
     /**
     * Return a pointer to the big integer word register
     * @result a pointer to the start of the internal register of
     * the integer value
     */
     const word* data() const { return &reg[0]; }
 
     /**
     * return a reference to the internal register containing the value
     * @result a reference to the word-array (SecureVector<word>)
     * with the internal register value (containing the integer
     * value)
     */
     SecureVector<word>& get_reg() { return reg; }
 
     /**
     * return a const reference to the internal register containing the value
     * @result a const reference to the word-array (SecureVector<word>)
     * with the internal register value (containing the integer value)
     */
     const SecureVector<word>& get_reg() const { return reg; }
 
     /**
     * Assign using a plain word array
     */
     void assign(const word x[], size_t length)
        {
        reg.resize(length);
        copy_mem(&reg[0], x, length);
        }
 
     /**
     * Increase internal register buffer by n words
     * @param n increase by n words
     */
     void grow_reg(size_t n);
 
     void grow_to(size_t n);
 
     /**
     * Fill BigInt with a random number with size of bitsize
     * @param rng the random number generator to use
     * @param bitsize number of bits the created random value should have
     */
     void randomize(RandomNumberGenerator& rng, size_t bitsize = 0);
 
     /**
     * Store BigInt-value in a given byte array
     * @param buf destination byte array for the integer value
     */
     void binary_encode(byte buf[]) const;
 
     /**
     * Read integer value from a byte array with given size
     * @param buf byte array buffer containing the integer
     * @param length size of buf
     */
     void binary_decode(const byte buf[], size_t length);
 
     /**
     * Read integer value from a byte array (MemoryRegion<byte>)
     * @param buf the array to load from
     */
     void binary_decode(const MemoryRegion<byte>& buf);
 
     /**
     * @param base the base to measure the size for
     * @return size of this integer in base base
     */
     size_t encoded_size(Base base = Binary) const;
 
     /**
     * @param rng a random number generator
     * @param min the minimum value
     * @param max the maximum value
     * @return random integer between min and max
     */
     static BigInt random_integer(RandomNumberGenerator& rng,
                                  const BigInt& min,
                                  const BigInt& max);
 
     /**
     * Encode the integer value from a BigInt to a SecureVector of bytes
     * @param n the BigInt to use as integer source
     * @param base number-base of resulting byte array representation
     * @result SecureVector of bytes containing the integer with given base
     */
     static SecureVector<byte> encode(const BigInt& n, Base base = Binary);
 
     /**
     * Encode the integer value from a BigInt to a byte array
     * @param buf destination byte array for the encoded integer
     * value with given base
     * @param n the BigInt to use as integer source
     * @param base number-base of resulting byte array representation
     */
     static void encode(byte buf[], const BigInt& n, Base base = Binary);
 
     /**
     * Create a BigInt from an integer in a byte array
     * @param buf the binary value to load
     * @param length size of buf
     * @param base number-base of the integer in buf
     * @result BigInt representing the integer in the byte array
     */
     static BigInt decode(const byte buf[], size_t length,
                          Base base = Binary);
 
     /**
     * Create a BigInt from an integer in a byte array
     * @param buf the binary value to load
     * @param base number-base of the integer in buf
     * @result BigInt representing the integer in the byte array
     */
     static BigInt decode(const MemoryRegion<byte>& buf,
                          Base base = Binary);
 
     /**
     * Encode a BigInt to a byte array according to IEEE 1363
     * @param n the BigInt to encode
     * @param bytes the length of the resulting SecureVector<byte>
     * @result a SecureVector<byte> containing the encoded BigInt
     */
     static SecureVector<byte> encode_1363(const BigInt& n, size_t bytes);
 
     /**
     * Swap this value with another
     * @param other BigInt to swap values with
     */
     void swap(BigInt& other);
 
     /**
     * Create empty BigInt
     */
     BigInt() { signedness = Positive; }
 
     /**
     * Create BigInt from 64 bit integer
     * @param n initial value of this BigInt
     */
     BigInt(u64bit n);
 
     /**
     * Copy Constructor
     * @param other the BigInt to copy
     */
     BigInt(const BigInt& other);
 
     /**
     * Create BigInt from a string. If the string starts with 0x the
     * rest of the string will be interpreted as hexadecimal digits.
     * If the string starts with 0 and the second character is NOT an
     * 'x' the string will be interpreted as octal digits. If the
     * string starts with non-zero digit, it will be interpreted as a
     * decimal number.
     *
     * @param str the string to parse for an integer value
     */
     BigInt(const std::string& str);
 
     /**
     * Create a BigInt from an integer in a byte array
     * @param buf the byte array holding the value
     * @param length size of buf
     * @param base is the number base of the integer in buf
     */
     BigInt(const byte buf[], size_t length, Base base = Binary);
 
     /**
     * Create a random BigInt of the specified size
     * @param rng random number generator
     * @param bits size in bits
     */
     BigInt(RandomNumberGenerator& rng, size_t bits);
 
     /**
     * Create BigInt of specified size, all zeros
     * @param sign the sign
     * @param n size of the internal register in words
     */
     BigInt(Sign sign, size_t n);
 
     /**
     * Create a number of the specified type and size
     * @param type the type of number to create. For Power2,
     * will create the integer 2^n
     * @param n a size/length parameter, interpretation depends upon
     * the value of type
     */
     BigInt(NumberType type, size_t n);
 
     void shrink_to_fit();
 
     static void const_time_lookup(SecureVector<word>& output,
                                   const std::vector<BigInt>& vec,
                                   size_t idx);
 
   private:
      SecureVector<word> reg;
      Sign signedness;
   };
 
/*
* Arithmetic Operators
*/
BigInt BOTAN_DLL operator+(const BigInt& x, const BigInt& y);
BigInt BOTAN_DLL operator-(const BigInt& x, const BigInt& y);
BigInt BOTAN_DLL operator*(const BigInt& x, const BigInt& y);
BigInt BOTAN_DLL operator/(const BigInt& x, const BigInt& d);
BigInt BOTAN_DLL operator%(const BigInt& x, const BigInt& m);
word   BOTAN_DLL operator%(const BigInt& x, word m);
BigInt BOTAN_DLL operator<<(const BigInt& x, size_t n);
BigInt BOTAN_DLL operator>>(const BigInt& x, size_t n);
 
/*
* Comparison Operators
*/
inline bool operator==(const BigInt& a, const BigInt& b)
   { return (a.cmp(b) == 0); }
inline bool operator!=(const BigInt& a, const BigInt& b)
   { return (a.cmp(b) != 0); }
inline bool operator<=(const BigInt& a, const BigInt& b)
   { return (a.cmp(b) <= 0); }
inline bool operator>=(const BigInt& a, const BigInt& b)
   { return (a.cmp(b) >= 0); }
inline bool operator<(const BigInt& a, const BigInt& b)
   { return (a.cmp(b) < 0); }
inline bool operator>(const BigInt& a, const BigInt& b)
   { return (a.cmp(b) > 0); }
 
/*
* I/O Operators
*/
BOTAN_DLL std::ostream& operator<<(std::ostream&, const BigInt&);
BOTAN_DLL std::istream& operator>>(std::istream&, BigInt&);
 
}
 
namespace std {
 
template<>
inline void swap(Botan::BigInt& x, Botan::BigInt& y)
   {
   x.swap(y);
   }
 
}
 
#endif