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