- Main Page
- Namespaces
- Classes
- Files

- File List
- 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 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 &params = g_nullNameValuePairs);
    00248                 void GenerateRandom(RandomNumberGenerator &rng, const NameValuePairs &params = 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 &quotient, const Integer &dividend, 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 NAMESPACE_BEGIN(std)
    00412 template<> inline void swap(CryptoPP::Integer &a, CryptoPP::Integer &b)
    00413 {
    00414         a.swap(b);
    00415 }
    00416 NAMESPACE_END
    00417
    00418 #endif