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 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 Aug 27 15:51:08 2004 for Crypto++ by doxygen 1.3.8