integer.h

Go to the documentation of this file.

#ifndef CRYPTOPP_INTEGER_H
#define CRYPTOPP_INTEGER_H

/** \file */

#include "cryptlib.h"
#include "secblock.h"

#include <iosfwd>
#include <algorithm>

#ifdef CRYPTOPP_X86ASM_AVAILABLE

#ifdef _M_IX86
        #if (defined(__INTEL_COMPILER) && (__INTEL_COMPILER >= 500)) || (defined(__ICL) && (__ICL >= 500))
                #define SSE2_INTRINSICS_AVAILABLE
                #define CRYPTOPP_MM_MALLOC_AVAILABLE
        #elif defined(_MSC_VER)
                // _mm_free seems to be the only way to tell if the Processor Pack is installed or not
                #include <malloc.h>
                #if defined(_mm_free)
                        #define SSE2_INTRINSICS_AVAILABLE
                        #define CRYPTOPP_MM_MALLOC_AVAILABLE
                #endif
        #endif
#endif

// SSE2 intrinsics work in GCC 3.3 or later
#if defined(__SSE2__) && (__GNUC__ > 3 || __GNUC_MINOR__ > 2)
        #define SSE2_INTRINSICS_AVAILABLE
#endif

#endif

NAMESPACE_BEGIN(CryptoPP)

#if defined(SSE2_INTRINSICS_AVAILABLE)
        template <class T>
        class AlignedAllocator : public AllocatorBase<T>
        {
        public:
                CRYPTOPP_INHERIT_ALLOCATOR_TYPES

                pointer allocate(size_type n, const void *);
                void deallocate(void *p, size_type n);
                pointer reallocate(T *p, size_type oldSize, size_type newSize, bool preserve)
                {
                        return StandardReallocate(*this, p, oldSize, newSize, preserve);
                }

        #if !(defined(CRYPTOPP_MALLOC_ALIGNMENT_IS_16) || defined(CRYPTOPP_MEMALIGN_AVAILABLE) || defined(CRYPTOPP_MM_MALLOC_AVAILABLE))
        #define CRYPTOPP_NO_ALIGNED_ALLOC
                AlignedAllocator() : m_pBlock(NULL) {}
        protected:
                void *m_pBlock;
        #endif
        };

        #ifdef CRYPTOPP_IMPORTS
                CRYPTOPP_DLL_TEMPLATE_CLASS AlignedAllocator<word>;
        #endif

        typedef SecBlock<word, AlignedAllocator<word> > SecAlignedWordBlock;
#else
        typedef SecWordBlock SecAlignedWordBlock;
#endif

void CRYPTOPP_DLL CRYPTOPP_API DisableSSE2();

struct InitializeInteger        // used to initialize static variables
{
        InitializeInteger();
};

//! multiple precision integer and basic arithmetics
/*! This class can represent positive and negative integers
        with absolute value less than (256**sizeof(word)) ** (256**sizeof(int)).
        \nosubgrouping
*/
class CRYPTOPP_DLL Integer : private InitializeInteger, public ASN1Object
{
public:
        //! \name ENUMS, EXCEPTIONS, and TYPEDEFS
        //@{
                //! division by zero exception
                class DivideByZero : public Exception
                {
                public:
                        DivideByZero() : Exception(OTHER_ERROR, "Integer: division by zero") {}
                };

                //!
                class RandomNumberNotFound : public Exception
                {
                public:
                        RandomNumberNotFound() : Exception(OTHER_ERROR, "Integer: no integer satisfies the given parameters") {}
                };

                //!
                enum Sign {POSITIVE=0, NEGATIVE=1};

                //!
                enum Signedness {
                //!
                        UNSIGNED,
                //!
                        SIGNED};

                //!
                enum RandomNumberType {
                //!
                        ANY,
                //!
                        PRIME};
        //@}

        //! \name CREATORS
        //@{
                //! creates the zero integer
                Integer();

                //! copy constructor
                Integer(const Integer& t);

                //! convert from signed long
                Integer(signed long value);

                //! convert from lword
                Integer(Sign s, lword value);

                //! convert from two words
                Integer(Sign s, word highWord, word lowWord);

                //! convert from string
                /*! str can be in base 2, 8, 10, or 16.  Base is determined by a
                        case insensitive suffix of 'h', 'o', or 'b'.  No suffix means base 10.
                */
                explicit Integer(const char *str);
                explicit Integer(const wchar_t *str);

                //! convert from big-endian byte array
                Integer(const byte *encodedInteger, size_t byteCount, Signedness s=UNSIGNED);

                //! convert from big-endian form stored in a BufferedTransformation
                Integer(BufferedTransformation &bt, size_t byteCount, Signedness s=UNSIGNED);

                //! convert from BER encoded byte array stored in a BufferedTransformation object
                explicit Integer(BufferedTransformation &bt);

                //! create a random integer
                /*! The random integer created is uniformly distributed over [0, 2**bitcount). */
                Integer(RandomNumberGenerator &rng, size_t bitcount);

                //! avoid calling constructors for these frequently used integers
                static const Integer & CRYPTOPP_API Zero();
                //! avoid calling constructors for these frequently used integers
                static const Integer & CRYPTOPP_API One();
                //! avoid calling constructors for these frequently used integers
                static const Integer & CRYPTOPP_API Two();

                //! create a random integer of special type
                /*! Ideally, the random integer created should be uniformly distributed
                        over {x | min <= x <= max and x is of rnType and x % mod == equiv}.
                        However the actual distribution may not be uniform because sequential
                        search is used to find an appropriate number from a random starting
                        point.
                        May return (with very small probability) a pseudoprime when a prime
                        is requested and max > lastSmallPrime*lastSmallPrime (lastSmallPrime
                        is declared in nbtheory.h).
                        \throw RandomNumberNotFound if the set is empty.
                */
                Integer(RandomNumberGenerator &rng, const Integer &min, const Integer &max, RandomNumberType rnType=ANY, const Integer &equiv=Zero(), const Integer &mod=One());

                //! return the integer 2**e
                static Integer CRYPTOPP_API Power2(size_t e);
        //@}

        //! \name ENCODE/DECODE
        //@{
                //! minimum number of bytes to encode this integer
                /*! MinEncodedSize of 0 is 1 */
                size_t MinEncodedSize(Signedness=UNSIGNED) const;
                //! encode in big-endian format
                /*! unsigned means encode absolute value, signed means encode two's complement if negative.
                        if outputLen < MinEncodedSize, the most significant bytes will be dropped
                        if outputLen > MinEncodedSize, the most significant bytes will be padded
                */
                void Encode(byte *output, size_t outputLen, Signedness=UNSIGNED) const;
                //!
                void Encode(BufferedTransformation &bt, size_t outputLen, Signedness=UNSIGNED) const;

                //! encode using Distinguished Encoding Rules, put result into a BufferedTransformation object
                void DEREncode(BufferedTransformation &bt) const;

                //! encode absolute value as big-endian octet string
                void DEREncodeAsOctetString(BufferedTransformation &bt, size_t length) const;

                //! encode absolute value in OpenPGP format, return length of output
                size_t OpenPGPEncode(byte *output, size_t bufferSize) const;
                //! encode absolute value in OpenPGP format, put result into a BufferedTransformation object
                size_t OpenPGPEncode(BufferedTransformation &bt) const;

                //!
                void Decode(const byte *input, size_t inputLen, Signedness=UNSIGNED);
                //! 
                //* Precondition: bt.MaxRetrievable() >= inputLen
                void Decode(BufferedTransformation &bt, size_t inputLen, Signedness=UNSIGNED);

                //!
                void BERDecode(const byte *input, size_t inputLen);
                //!
                void BERDecode(BufferedTransformation &bt);

                //! decode nonnegative value as big-endian octet string
                void BERDecodeAsOctetString(BufferedTransformation &bt, size_t length);

                class OpenPGPDecodeErr : public Exception
                {
                public: 
                        OpenPGPDecodeErr() : Exception(INVALID_DATA_FORMAT, "OpenPGP decode error") {}
                };

                //!
                void OpenPGPDecode(const byte *input, size_t inputLen);
                //!
                void OpenPGPDecode(BufferedTransformation &bt);
        //@}

        //! \name ACCESSORS
        //@{
                //! return true if *this can be represented as a signed long
                bool IsConvertableToLong() const;
                //! return equivalent signed long if possible, otherwise undefined
                signed long ConvertToLong() const;

                //! number of significant bits = floor(log2(abs(*this))) + 1
                unsigned int BitCount() const;
                //! number of significant bytes = ceiling(BitCount()/8)
                unsigned int ByteCount() const;
                //! number of significant words = ceiling(ByteCount()/sizeof(word))
                unsigned int WordCount() const;

                //! return the i-th bit, i=0 being the least significant bit
                bool GetBit(size_t i) const;
                //! return the i-th byte
                byte GetByte(size_t i) const;
                //! return n lowest bits of *this >> i
                lword GetBits(size_t i, size_t n) const;

                //!
                bool IsZero() const {return !*this;}
                //!
                bool NotZero() const {return !IsZero();}
                //!
                bool IsNegative() const {return sign == NEGATIVE;}
                //!
                bool NotNegative() const {return !IsNegative();}
                //!
                bool IsPositive() const {return NotNegative() && NotZero();}
                //!
                bool NotPositive() const {return !IsPositive();}
                //!
                bool IsEven() const {return GetBit(0) == 0;}
                //!
                bool IsOdd() const      {return GetBit(0) == 1;}
        //@}

        //! \name MANIPULATORS
        //@{
                //!
                Integer&  operator=(const Integer& t);

                //!
                Integer&  operator+=(const Integer& t);
                //!
                Integer&  operator-=(const Integer& t);
                //!
                Integer&  operator*=(const Integer& t)  {return *this = Times(t);}
                //!
                Integer&  operator/=(const Integer& t)  {return *this = DividedBy(t);}
                //!
                Integer&  operator%=(const Integer& t)  {return *this = Modulo(t);}
                //!
                Integer&  operator/=(word t)  {return *this = DividedBy(t);}
                //!
                Integer&  operator%=(word t)  {return *this = Integer(POSITIVE, 0, Modulo(t));}

                //!
                Integer&  operator<<=(size_t);
                //!
                Integer&  operator>>=(size_t);

                //!
                void Randomize(RandomNumberGenerator &rng, size_t bitcount);
                //!
                void Randomize(RandomNumberGenerator &rng, const Integer &min, const Integer &max);
                //! set this Integer to a random element of {x | min <= x <= max and x is of rnType and x % mod == equiv}
                /*! returns false if the set is empty */
                bool Randomize(RandomNumberGenerator &rng, const Integer &min, const Integer &max, RandomNumberType rnType, const Integer &equiv=Zero(), const Integer &mod=One());

                bool GenerateRandomNoThrow(RandomNumberGenerator &rng, const NameValuePairs &params = g_nullNameValuePairs);
                void GenerateRandom(RandomNumberGenerator &rng, const NameValuePairs &params = g_nullNameValuePairs)
                {
                        if (!GenerateRandomNoThrow(rng, params))
                                throw RandomNumberNotFound();
                }

                //! set the n-th bit to value
                void SetBit(size_t n, bool value=1);
                //! set the n-th byte to value
                void SetByte(size_t n, byte value);

                //!
                void Negate();
                //!
                void SetPositive() {sign = POSITIVE;}
                //!
                void SetNegative() {if (!!(*this)) sign = NEGATIVE;}

                //!
                void swap(Integer &a);
        //@}

        //! \name UNARY OPERATORS
        //@{
                //!
                bool            operator!() const;
                //!
                Integer         operator+() const {return *this;}
                //!
                Integer         operator-() const;
                //!
                Integer&        operator++();
                //!
                Integer&        operator--();
                //!
                Integer         operator++(int) {Integer temp = *this; ++*this; return temp;}
                //!
                Integer         operator--(int) {Integer temp = *this; --*this; return temp;}
        //@}

        //! \name BINARY OPERATORS
        //@{
                //! signed comparison
                /*! \retval -1 if *this < a
                        \retval  0 if *this = a
                        \retval  1 if *this > a
                */
                int Compare(const Integer& a) const;

                //!
                Integer Plus(const Integer &b) const;
                //!
                Integer Minus(const Integer &b) const;
                //!
                Integer Times(const Integer &b) const;
                //!
                Integer DividedBy(const Integer &b) const;
                //!
                Integer Modulo(const Integer &b) const;
                //!
                Integer DividedBy(word b) const;
                //!
                word Modulo(word b) const;

                //!
                Integer operator>>(size_t n) const      {return Integer(*this)>>=n;}
                //!
                Integer operator<<(size_t n) const      {return Integer(*this)<<=n;}
        //@}

        //! \name OTHER ARITHMETIC FUNCTIONS
        //@{
                //!
                Integer AbsoluteValue() const;
                //!
                Integer Doubled() const {return Plus(*this);}
                //!
                Integer Squared() const {return Times(*this);}
                //! extract square root, if negative return 0, else return floor of square root
                Integer SquareRoot() const;
                //! return whether this integer is a perfect square
                bool IsSquare() const;

                //! is 1 or -1
                bool IsUnit() const;
                //! return inverse if 1 or -1, otherwise return 0
                Integer MultiplicativeInverse() const;

                //! modular multiplication
                CRYPTOPP_DLL friend Integer CRYPTOPP_API a_times_b_mod_c(const Integer &x, const Integer& y, const Integer& m);
                //! modular exponentiation
                CRYPTOPP_DLL friend Integer CRYPTOPP_API a_exp_b_mod_c(const Integer &x, const Integer& e, const Integer& m);

                //! calculate r and q such that (a == d*q + r) && (0 <= r < abs(d))
                static void CRYPTOPP_API Divide(Integer &r, Integer &q, const Integer &a, const Integer &d);
                //! use a faster division algorithm when divisor is short
                static void CRYPTOPP_API Divide(word &r, Integer &q, const Integer &a, word d);

                //! returns same result as Divide(r, q, a, Power2(n)), but faster
                static void CRYPTOPP_API DivideByPowerOf2(Integer &r, Integer &q, const Integer &a, unsigned int n);

                //! greatest common divisor
                static Integer CRYPTOPP_API Gcd(const Integer &a, const Integer &n);
                //! calculate multiplicative inverse of *this mod n
                Integer InverseMod(const Integer &n) const;
                //!
                word InverseMod(word n) const;
        //@}

        //! \name INPUT/OUTPUT
        //@{
                //!
                friend CRYPTOPP_DLL std::istream& CRYPTOPP_API operator>>(std::istream& in, Integer &a);
                //!
                friend CRYPTOPP_DLL std::ostream& CRYPTOPP_API operator<<(std::ostream& out, const Integer &a);
        //@}

private:
        friend class ModularArithmetic;
        friend class MontgomeryRepresentation;
        friend class HalfMontgomeryRepresentation;

        Integer(word value, size_t length);

        int PositiveCompare(const Integer &t) const;
        friend void PositiveAdd(Integer &sum, const Integer &a, const Integer &b);
        friend void PositiveSubtract(Integer &diff, const Integer &a, const Integer &b);
        friend void PositiveMultiply(Integer &product, const Integer &a, const Integer &b);
        friend void PositiveDivide(Integer &remainder, Integer &quotient, const Integer &dividend, const Integer &divisor);

        SecAlignedWordBlock reg;
        Sign sign;
};

//!
inline bool operator==(const CryptoPP::Integer& a, const CryptoPP::Integer& b) {return a.Compare(b)==0;}
//!
inline bool operator!=(const CryptoPP::Integer& a, const CryptoPP::Integer& b) {return a.Compare(b)!=0;}
//!
inline bool operator> (const CryptoPP::Integer& a, const CryptoPP::Integer& b) {return a.Compare(b)> 0;}
//!
inline bool operator>=(const CryptoPP::Integer& a, const CryptoPP::Integer& b) {return a.Compare(b)>=0;}
//!
inline bool operator< (const CryptoPP::Integer& a, const CryptoPP::Integer& b) {return a.Compare(b)< 0;}
//!
inline bool operator<=(const CryptoPP::Integer& a, const CryptoPP::Integer& b) {return a.Compare(b)<=0;}
//!
inline CryptoPP::Integer operator+(const CryptoPP::Integer &a, const CryptoPP::Integer &b) {return a.Plus(b);}
//!
inline CryptoPP::Integer operator-(const CryptoPP::Integer &a, const CryptoPP::Integer &b) {return a.Minus(b);}
//!
inline CryptoPP::Integer operator*(const CryptoPP::Integer &a, const CryptoPP::Integer &b) {return a.Times(b);}
//!
inline CryptoPP::Integer operator/(const CryptoPP::Integer &a, const CryptoPP::Integer &b) {return a.DividedBy(b);}
//!
inline CryptoPP::Integer operator%(const CryptoPP::Integer &a, const CryptoPP::Integer &b) {return a.Modulo(b);}
//!
inline CryptoPP::Integer operator/(const CryptoPP::Integer &a, CryptoPP::word b) {return a.DividedBy(b);}
//!
inline CryptoPP::word    operator%(const CryptoPP::Integer &a, CryptoPP::word b) {return a.Modulo(b);}

NAMESPACE_END

NAMESPACE_BEGIN(std)
template<> inline void swap(CryptoPP::Integer &a, CryptoPP::Integer &b)
{
        a.swap(b);
}
NAMESPACE_END

#endif

---