integer.h

Go to the documentation of this file.
00001 #ifndef CRYPTOPP_INTEGER_H
00002 #define CRYPTOPP_INTEGER_H
00003 
00004 /** \file */
00005 
00006 #include "cryptlib.h"
00007 #include "secblock.h"
00008 
00009 #include <iosfwd>
00010 #include <algorithm>
00011 
00012 #ifdef CRYPTOPP_X86ASM_AVAILABLE
00013 
00014 #ifdef _M_IX86
00015         #if (defined(__INTEL_COMPILER) && (__INTEL_COMPILER >= 500)) || (defined(__ICL) && (__ICL >= 500))
00016                 #define SSE2_INTRINSICS_AVAILABLE
00017                 #define CRYPTOPP_MM_MALLOC_AVAILABLE
00018         #elif defined(_MSC_VER)
00019                 // _mm_free seems to be the only way to tell if the Processor Pack is installed or not
00020                 #include <malloc.h>
00021                 #if defined(_mm_free)
00022                         #define SSE2_INTRINSICS_AVAILABLE
00023                         #define CRYPTOPP_MM_MALLOC_AVAILABLE
00024                 #endif
00025         #endif
00026 #endif
00027 
00028 // SSE2 intrinsics work in GCC 3.3 or later
00029 #if defined(__SSE2__) && (__GNUC_MAJOR__ > 3 || __GNUC_MINOR__ > 2)
00030         #define SSE2_INTRINSICS_AVAILABLE
00031 #endif
00032 
00033 #endif
00034 
00035 NAMESPACE_BEGIN(CryptoPP)
00036 
00037 #if defined(SSE2_INTRINSICS_AVAILABLE)
00038         template <class T>
00039         class AlignedAllocator : public AllocatorBase<T>
00040         {
00041         public:
00042                 CRYPTOPP_INHERIT_ALLOCATOR_TYPES
00043 
00044                 pointer allocate(size_type n, const void *);
00045                 void deallocate(void *p, size_type n);
00046                 pointer reallocate(T *p, size_type oldSize, size_type newSize, bool preserve)
00047                 {
00048                         return StandardReallocate(*this, p, oldSize, newSize, preserve);
00049                 }
00050 
00051         #if !(defined(CRYPTOPP_MALLOC_ALIGNMENT_IS_16) || defined(CRYPTOPP_MEMALIGN_AVAILABLE) || defined(CRYPTOPP_MM_MALLOC_AVAILABLE))
00052         #define CRYPTOPP_NO_ALIGNED_ALLOC
00053                 AlignedAllocator() : m_pBlock(NULL) {}
00054         protected:
00055                 void *m_pBlock;
00056         #endif
00057         };
00058 
00059         template class CRYPTOPP_DLL AlignedAllocator<word>;
00060         typedef SecBlock<word, AlignedAllocator<word> > SecAlignedWordBlock;
00061 #else
00062         typedef SecWordBlock SecAlignedWordBlock;
00063 #endif
00064 
00065 void CRYPTOPP_DLL DisableSSE2();
00066 
00067 //! multiple precision integer and basic arithmetics
00068 /*! This class can represent positive and negative integers
00069         with absolute value less than (256**sizeof(word)) ** (256**sizeof(int)).
00070         \nosubgrouping
00071 */
00072 class CRYPTOPP_DLL Integer : public ASN1Object
00073 {
00074 public:
00075         //! \name ENUMS, EXCEPTIONS, and TYPEDEFS
00076         //@{
00077                 //! division by zero exception
00078                 class DivideByZero : public Exception
00079                 {
00080                 public:
00081                         DivideByZero() : Exception(OTHER_ERROR, "Integer: division by zero") {}
00082                 };
00083 
00084                 //!
00085                 class RandomNumberNotFound : public Exception
00086                 {
00087                 public:
00088                         RandomNumberNotFound() : Exception(OTHER_ERROR, "Integer: no integer satisfies the given parameters") {}
00089                 };
00090 
00091                 //!
00092                 enum Sign {POSITIVE=0, NEGATIVE=1};
00093 
00094                 //!
00095                 enum Signedness {
00096                 //!
00097                         UNSIGNED,
00098                 //!
00099                         SIGNED};
00100 
00101                 //!
00102                 enum RandomNumberType {
00103                 //!
00104                         ANY,
00105                 //!
00106                         PRIME};
00107         //@}
00108 
00109         //! \name CREATORS
00110         //@{
00111                 //! creates the zero integer
00112                 Integer();
00113 
00114                 //! copy constructor
00115                 Integer(const Integer& t);
00116 
00117                 //! convert from signed long
00118                 Integer(signed long value);
00119 
00120                 //! convert from lword
00121                 Integer(Sign s, lword value);
00122 
00123                 //! convert from two words
00124                 Integer(Sign s, word highWord, word lowWord);
00125 
00126                 //! convert from string
00127                 /*! str can be in base 2, 8, 10, or 16.  Base is determined by a
00128                         case insensitive suffix of 'h', 'o', or 'b'.  No suffix means base 10.
00129                 */
00130                 explicit Integer(const char *str);
00131                 explicit Integer(const wchar_t *str);
00132 
00133                 //! convert from big-endian byte array
00134                 Integer(const byte *encodedInteger, unsigned int byteCount, Signedness s=UNSIGNED);
00135 
00136                 //! convert from big-endian form stored in a BufferedTransformation
00137                 Integer(BufferedTransformation &bt, unsigned int byteCount, Signedness s=UNSIGNED);
00138 
00139                 //! convert from BER encoded byte array stored in a BufferedTransformation object
00140                 explicit Integer(BufferedTransformation &bt);
00141 
00142                 //! create a random integer
00143                 /*! The random integer created is uniformly distributed over [0, 2**bitcount). */
00144                 Integer(RandomNumberGenerator &rng, unsigned int bitcount);
00145 
00146                 //! avoid calling constructors for these frequently used integers
00147                 static const Integer &Zero();
00148                 //! avoid calling constructors for these frequently used integers
00149                 static const Integer &One();
00150                 //! avoid calling constructors for these frequently used integers
00151                 static const Integer &Two();
00152 
00153                 //! create a random integer of special type
00154                 /*! Ideally, the random integer created should be uniformly distributed
00155                         over {x | min <= x <= max and x is of rnType and x % mod == equiv}.
00156                         However the actual distribution may not be uniform because sequential
00157                         search is used to find an appropriate number from a random starting
00158                         point.
00159                         May return (with very small probability) a pseudoprime when a prime
00160                         is requested and max > lastSmallPrime*lastSmallPrime (lastSmallPrime
00161                         is declared in nbtheory.h).
00162                         \throw RandomNumberNotFound if the set is empty.
00163                 */
00164                 Integer(RandomNumberGenerator &rng, const Integer &min, const Integer &max, RandomNumberType rnType=ANY, const Integer &equiv=Zero(), const Integer &mod=One());
00165 
00166                 //! return the integer 2**e
00167                 static Integer Power2(unsigned int e);
00168         //@}
00169 
00170         //! \name ENCODE/DECODE
00171         //@{
00172                 //! minimum number of bytes to encode this integer
00173                 /*! MinEncodedSize of 0 is 1 */
00174                 unsigned int MinEncodedSize(Signedness=UNSIGNED) const;
00175                 //! encode in big-endian format
00176                 /*! unsigned means encode absolute value, signed means encode two's complement if negative.
00177                         if outputLen < MinEncodedSize, the most significant bytes will be dropped
00178                         if outputLen > MinEncodedSize, the most significant bytes will be padded
00179                 */
00180                 unsigned int Encode(byte *output, unsigned int outputLen, Signedness=UNSIGNED) const;
00181                 //!
00182                 unsigned int Encode(BufferedTransformation &bt, unsigned int outputLen, Signedness=UNSIGNED) const;
00183 
00184                 //! encode using Distinguished Encoding Rules, put result into a BufferedTransformation object
00185                 void DEREncode(BufferedTransformation &bt) const;
00186 
00187                 //! encode absolute value as big-endian octet string
00188                 void DEREncodeAsOctetString(BufferedTransformation &bt, unsigned int length) const;
00189 
00190                 //! encode absolute value in OpenPGP format, return length of output
00191                 unsigned int OpenPGPEncode(byte *output, unsigned int bufferSize) const;
00192                 //! encode absolute value in OpenPGP format, put result into a BufferedTransformation object
00193                 unsigned int OpenPGPEncode(BufferedTransformation &bt) const;
00194 
00195                 //!
00196                 void Decode(const byte *input, unsigned int inputLen, Signedness=UNSIGNED);
00197                 //! 
00198                 //* Precondition: bt.MaxRetrievable() >= inputLen
00199                 void Decode(BufferedTransformation &bt, unsigned int inputLen, Signedness=UNSIGNED);
00200 
00201                 //!
00202                 void BERDecode(const byte *input, unsigned int inputLen);
00203                 //!
00204                 void BERDecode(BufferedTransformation &bt);
00205 
00206                 //! decode nonnegative value as big-endian octet string
00207                 void BERDecodeAsOctetString(BufferedTransformation &bt, unsigned int length);
00208 
00209                 class OpenPGPDecodeErr : public Exception
00210                 {
00211                 public: 
00212                         OpenPGPDecodeErr() : Exception(INVALID_DATA_FORMAT, "OpenPGP decode error") {}
00213                 };
00214 
00215                 //!
00216                 void OpenPGPDecode(const byte *input, unsigned int inputLen);
00217                 //!
00218                 void OpenPGPDecode(BufferedTransformation &bt);
00219         //@}
00220 
00221         //! \name ACCESSORS
00222         //@{
00223                 //! return true if *this can be represented as a signed long
00224                 bool IsConvertableToLong() const;
00225                 //! return equivalent signed long if possible, otherwise undefined
00226                 signed long ConvertToLong() const;
00227 
00228                 //! number of significant bits = floor(log2(abs(*this))) + 1
00229                 unsigned int BitCount() const;
00230                 //! number of significant bytes = ceiling(BitCount()/8)
00231                 unsigned int ByteCount() const;
00232                 //! number of significant words = ceiling(ByteCount()/sizeof(word))
00233                 unsigned int WordCount() const;
00234 
00235                 //! return the i-th bit, i=0 being the least significant bit
00236                 bool GetBit(unsigned int i) const;
00237                 //! return the i-th byte
00238                 byte GetByte(unsigned int i) const;
00239                 //! return n lowest bits of *this >> i
00240                 unsigned long GetBits(unsigned int i, unsigned int n) const;
00241 
00242                 //!
00243                 bool IsZero() const {return !*this;}
00244                 //!
00245                 bool NotZero() const {return !IsZero();}
00246                 //!
00247                 bool IsNegative() const {return sign == NEGATIVE;}
00248                 //!
00249                 bool NotNegative() const {return !IsNegative();}
00250                 //!
00251                 bool IsPositive() const {return NotNegative() && NotZero();}
00252                 //!
00253                 bool NotPositive() const {return !IsPositive();}
00254                 //!
00255                 bool IsEven() const {return GetBit(0) == 0;}
00256                 //!
00257                 bool IsOdd() const      {return GetBit(0) == 1;}
00258         //@}
00259 
00260         //! \name MANIPULATORS
00261         //@{
00262                 //!
00263                 Integer&  operator=(const Integer& t);
00264 
00265                 //!
00266                 Integer&  operator+=(const Integer& t);
00267                 //!
00268                 Integer&  operator-=(const Integer& t);
00269                 //!
00270                 Integer&  operator*=(const Integer& t)  {return *this = Times(t);}
00271                 //!
00272                 Integer&  operator/=(const Integer& t)  {return *this = DividedBy(t);}
00273                 //!
00274                 Integer&  operator%=(const Integer& t)  {return *this = Modulo(t);}
00275                 //!
00276                 Integer&  operator/=(word t)  {return *this = DividedBy(t);}
00277                 //!
00278                 Integer&  operator%=(word t)  {return *this = Modulo(t);}
00279 
00280                 //!
00281                 Integer&  operator<<=(unsigned int);
00282                 //!
00283                 Integer&  operator>>=(unsigned int);
00284 
00285                 //!
00286                 void Randomize(RandomNumberGenerator &rng, unsigned int bitcount);
00287                 //!
00288                 void Randomize(RandomNumberGenerator &rng, const Integer &min, const Integer &max);
00289                 //! set this Integer to a random element of {x | min <= x <= max and x is of rnType and x % mod == equiv}
00290                 /*! returns false if the set is empty */
00291                 bool Randomize(RandomNumberGenerator &rng, const Integer &min, const Integer &max, RandomNumberType rnType, const Integer &equiv=Zero(), const Integer &mod=One());
00292 
00293                 bool GenerateRandomNoThrow(RandomNumberGenerator &rng, const NameValuePairs &params = g_nullNameValuePairs);
00294                 void GenerateRandom(RandomNumberGenerator &rng, const NameValuePairs &params = g_nullNameValuePairs)
00295                 {
00296                         if (!GenerateRandomNoThrow(rng, params))
00297                                 throw RandomNumberNotFound();
00298                 }
00299 
00300                 //! set the n-th bit to value
00301                 void SetBit(unsigned int n, bool value=1);
00302                 //! set the n-th byte to value
00303                 void SetByte(unsigned int n, byte value);
00304 
00305                 //!
00306                 void Negate();
00307                 //!
00308                 void SetPositive() {sign = POSITIVE;}
00309                 //!
00310                 void SetNegative() {if (!!(*this)) sign = NEGATIVE;}
00311 
00312                 //!
00313                 void swap(Integer &a);
00314         //@}
00315 
00316         //! \name UNARY OPERATORS
00317         //@{
00318                 //!
00319                 bool            operator!() const;
00320                 //!
00321                 Integer         operator+() const {return *this;}
00322                 //!
00323                 Integer         operator-() const;
00324                 //!
00325                 Integer&        operator++();
00326                 //!
00327                 Integer&        operator--();
00328                 //!
00329                 Integer         operator++(int) {Integer temp = *this; ++*this; return temp;}
00330                 //!
00331                 Integer         operator--(int) {Integer temp = *this; --*this; return temp;}
00332         //@}
00333 
00334         //! \name BINARY OPERATORS
00335         //@{
00336                 //! signed comparison
00337                 /*! \retval -1 if *this < a
00338                         \retval  0 if *this = a
00339                         \retval  1 if *this > a
00340                 */
00341                 int Compare(const Integer& a) const;
00342 
00343                 //!
00344                 Integer Plus(const Integer &b) const;
00345                 //!
00346                 Integer Minus(const Integer &b) const;
00347                 //!
00348                 Integer Times(const Integer &b) const;
00349                 //!
00350                 Integer DividedBy(const Integer &b) const;
00351                 //!
00352                 Integer Modulo(const Integer &b) const;
00353                 //!
00354                 Integer DividedBy(word b) const;
00355                 //!
00356                 word Modulo(word b) const;
00357 
00358                 //!
00359                 Integer operator>>(unsigned int n) const        {return Integer(*this)>>=n;}
00360                 //!
00361                 Integer operator<<(unsigned int n) const        {return Integer(*this)<<=n;}
00362         //@}
00363 
00364         //! \name OTHER ARITHMETIC FUNCTIONS
00365         //@{
00366                 //!
00367                 Integer AbsoluteValue() const;
00368                 //!
00369                 Integer Doubled() const {return Plus(*this);}
00370                 //!
00371                 Integer Squared() const {return Times(*this);}
00372                 //! extract square root, if negative return 0, else return floor of square root
00373                 Integer SquareRoot() const;
00374                 //! return whether this integer is a perfect square
00375                 bool IsSquare() const;
00376 
00377                 //! is 1 or -1
00378                 bool IsUnit() const;
00379                 //! return inverse if 1 or -1, otherwise return 0
00380                 Integer MultiplicativeInverse() const;
00381 
00382                 //! modular multiplication
00383                 CRYPTOPP_DLL friend Integer a_times_b_mod_c(const Integer &x, const Integer& y, const Integer& m);
00384                 //! modular exponentiation
00385                 CRYPTOPP_DLL friend Integer a_exp_b_mod_c(const Integer &x, const Integer& e, const Integer& m);
00386 
00387                 //! calculate r and q such that (a == d*q + r) && (0 <= r < abs(d))
00388                 static void Divide(Integer &r, Integer &q, const Integer &a, const Integer &d);
00389                 //! use a faster division algorithm when divisor is short
00390                 static void Divide(word &r, Integer &q, const Integer &a, word d);
00391 
00392                 //! returns same result as Divide(r, q, a, Power2(n)), but faster
00393                 static void DivideByPowerOf2(Integer &r, Integer &q, const Integer &a, unsigned int n);
00394 
00395                 //! greatest common divisor
00396                 static Integer Gcd(const Integer &a, const Integer &n);
00397                 //! calculate multiplicative inverse of *this mod n
00398                 Integer InverseMod(const Integer &n) const;
00399                 //!
00400                 word InverseMod(word n) const;
00401         //@}
00402 
00403         //! \name INPUT/OUTPUT
00404         //@{
00405                 //!
00406                 friend CRYPTOPP_DLL std::istream& operator>>(std::istream& in, Integer &a);
00407                 //!
00408                 friend CRYPTOPP_DLL std::ostream& operator<<(std::ostream& out, const Integer &a);
00409         //@}
00410 
00411 private:
00412         friend class ModularArithmetic;
00413         friend class MontgomeryRepresentation;
00414         friend class HalfMontgomeryRepresentation;
00415 
00416         Integer(word value, unsigned int length);
00417 
00418         int PositiveCompare(const Integer &t) const;
00419         friend void PositiveAdd(Integer &sum, const Integer &a, const Integer &b);
00420         friend void PositiveSubtract(Integer &diff, const Integer &a, const Integer &b);
00421         friend void PositiveMultiply(Integer &product, const Integer &a, const Integer &b);
00422         friend void PositiveDivide(Integer &remainder, Integer &quotient, const Integer &dividend, const Integer &divisor);
00423 
00424         SecAlignedWordBlock reg;
00425         Sign sign;
00426 };
00427 
00428 //!
00429 inline bool operator==(const CryptoPP::Integer& a, const CryptoPP::Integer& b) {return a.Compare(b)==0;}
00430 //!
00431 inline bool operator!=(const CryptoPP::Integer& a, const CryptoPP::Integer& b) {return a.Compare(b)!=0;}
00432 //!
00433 inline bool operator> (const CryptoPP::Integer& a, const CryptoPP::Integer& b) {return a.Compare(b)> 0;}
00434 //!
00435 inline bool operator>=(const CryptoPP::Integer& a, const CryptoPP::Integer& b) {return a.Compare(b)>=0;}
00436 //!
00437 inline bool operator< (const CryptoPP::Integer& a, const CryptoPP::Integer& b) {return a.Compare(b)< 0;}
00438 //!
00439 inline bool operator<=(const CryptoPP::Integer& a, const CryptoPP::Integer& b) {return a.Compare(b)<=0;}
00440 //!
00441 inline CryptoPP::Integer operator+(const CryptoPP::Integer &a, const CryptoPP::Integer &b) {return a.Plus(b);}
00442 //!
00443 inline CryptoPP::Integer operator-(const CryptoPP::Integer &a, const CryptoPP::Integer &b) {return a.Minus(b);}
00444 //!
00445 inline CryptoPP::Integer operator*(const CryptoPP::Integer &a, const CryptoPP::Integer &b) {return a.Times(b);}
00446 //!
00447 inline CryptoPP::Integer operator/(const CryptoPP::Integer &a, const CryptoPP::Integer &b) {return a.DividedBy(b);}
00448 //!
00449 inline CryptoPP::Integer operator%(const CryptoPP::Integer &a, const CryptoPP::Integer &b) {return a.Modulo(b);}
00450 //!
00451 inline CryptoPP::Integer operator/(const CryptoPP::Integer &a, CryptoPP::word b) {return a.DividedBy(b);}
00452 //!
00453 inline CryptoPP::word    operator%(const CryptoPP::Integer &a, CryptoPP::word b) {return a.Modulo(b);}
00454 
00455 NAMESPACE_END
00456 
00457 NAMESPACE_BEGIN(std)
00458 template<> inline void swap(CryptoPP::Integer &a, CryptoPP::Integer &b)
00459 {
00460         a.swap(b);
00461 }
00462 NAMESPACE_END
00463 
00464 #endif

Generated on Fri Dec 16 03:04:16 2005 for Crypto++ by  doxygen 1.4.5