Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | File List | Namespace Members | Class Members | File Members

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

Generated on Sun Mar 14 20:44:27 2004 for Crypto++ by doxygen 1.3.6-20040222