Crypto++

- 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 #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