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

Generated on Thu Jul 5 22:21:37 2007 for Crypto++ by  doxygen 1.5.2