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

Generated on Tue Jul 8 23:34:19 2003 for Crypto++ by doxygen 1.3.2