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 Fri Aug 13 09:56:54 2004 for Crypto++ by doxygen 1.3.7