00001 #ifndef CRYPTOPP_INTEGER_H
00002 #define CRYPTOPP_INTEGER_H
00003
00004
00005
00006 #include "cryptlib.h"
00007 #include "secblock.h"
00008
00009 #include <iosfwd>
00010 #include <algorithm>
00011
00012 #ifdef CRYPTOPP_X86ASM_AVAILABLE
00013
00014 #ifdef _M_IX86
00015 #if (defined(__INTEL_COMPILER) && (__INTEL_COMPILER >= 500)) || (defined(__ICL) && (__ICL >= 500))
00016 #define SSE2_INTRINSICS_AVAILABLE
00017 #define CRYPTOPP_MM_MALLOC_AVAILABLE
00018 #elif defined(_MSC_VER)
00019
00020 #include <malloc.h>
00021 #if defined(_mm_free)
00022 #define SSE2_INTRINSICS_AVAILABLE
00023 #define CRYPTOPP_MM_MALLOC_AVAILABLE
00024 #endif
00025 #endif
00026 #endif
00027
00028
00029 #if defined(__SSE2__) && (__GNUC_MAJOR__ > 3 || __GNUC_MINOR__ > 2)
00030 #define SSE2_INTRINSICS_AVAILABLE
00031 #endif
00032
00033 #endif
00034
00035 NAMESPACE_BEGIN(CryptoPP)
00036
00037 #if defined(SSE2_INTRINSICS_AVAILABLE)
00038 template <class T>
00039 class AlignedAllocator : public AllocatorBase<T>
00040 {
00041 public:
00042 CRYPTOPP_INHERIT_ALLOCATOR_TYPES
00043
00044 pointer allocate(size_type n, const void *);
00045 void deallocate(void *p, size_type n);
00046 pointer reallocate(T *p, size_type oldSize, size_type newSize, bool preserve)
00047 {
00048 return StandardReallocate(*this, p, oldSize, newSize, preserve);
00049 }
00050
00051 #if !(defined(CRYPTOPP_MALLOC_ALIGNMENT_IS_16) || defined(CRYPTOPP_MEMALIGN_AVAILABLE) || defined(CRYPTOPP_MM_MALLOC_AVAILABLE))
00052 #define CRYPTOPP_NO_ALIGNED_ALLOC
00053 AlignedAllocator() : m_pBlock(NULL) {}
00054 protected:
00055 void *m_pBlock;
00056 #endif
00057 };
00058
00059 template class CRYPTOPP_DLL AlignedAllocator<word>;
00060 typedef SecBlock<word, AlignedAllocator<word> > SecAlignedWordBlock;
00061 #else
00062 typedef SecWordBlock SecAlignedWordBlock;
00063 #endif
00064
00065 void CRYPTOPP_DLL CRYPTOPP_API DisableSSE2();
00066
00067
00068
00069
00070
00071
00072 class CRYPTOPP_DLL Integer : public ASN1Object
00073 {
00074 public:
00075
00076
00077
00078 class DivideByZero : public Exception
00079 {
00080 public:
00081 DivideByZero() : Exception(OTHER_ERROR, "Integer: division by zero") {}
00082 };
00083
00084
00085 class RandomNumberNotFound : public Exception
00086 {
00087 public:
00088 RandomNumberNotFound() : Exception(OTHER_ERROR, "Integer: no integer satisfies the given parameters") {}
00089 };
00090
00091
00092 enum Sign {POSITIVE=0, NEGATIVE=1};
00093
00094
00095 enum Signedness {
00096
00097 UNSIGNED,
00098
00099 SIGNED};
00100
00101
00102 enum RandomNumberType {
00103
00104 ANY,
00105
00106 PRIME};
00107
00108
00109
00110
00111
00112 Integer();
00113
00114
00115 Integer(const Integer& t);
00116
00117
00118 Integer(signed long value);
00119
00120
00121 Integer(Sign s, lword value);
00122
00123
00124 Integer(Sign s, word highWord, word lowWord);
00125
00126
00127
00128
00129
00130 explicit Integer(const char *str);
00131 explicit Integer(const wchar_t *str);
00132
00133
00134 Integer(const byte *encodedInteger, size_t byteCount, Signedness s=UNSIGNED);
00135
00136
00137 Integer(BufferedTransformation &bt, size_t byteCount, Signedness s=UNSIGNED);
00138
00139
00140 explicit Integer(BufferedTransformation &bt);
00141
00142
00143
00144 Integer(RandomNumberGenerator &rng, size_t bitcount);
00145
00146
00147 static const Integer & CRYPTOPP_API Zero();
00148
00149 static const Integer & CRYPTOPP_API One();
00150
00151 static const Integer & CRYPTOPP_API Two();
00152
00153
00154
00155
00156
00157
00158
00159
00160
00161
00162
00163
00164 Integer(RandomNumberGenerator &rng, const Integer &min, const Integer &max, RandomNumberType rnType=ANY, const Integer &equiv=Zero(), const Integer &mod=One());
00165
00166
00167 static Integer CRYPTOPP_API Power2(size_t e);
00168
00169
00170
00171
00172
00173
00174 size_t MinEncodedSize(Signedness=UNSIGNED) const;
00175
00176
00177
00178
00179
00180 void Encode(byte *output, size_t outputLen, Signedness=UNSIGNED) const;
00181
00182 void Encode(BufferedTransformation &bt, size_t outputLen, Signedness=UNSIGNED) const;
00183
00184
00185 void DEREncode(BufferedTransformation &bt) const;
00186
00187
00188 void DEREncodeAsOctetString(BufferedTransformation &bt, size_t length) const;
00189
00190
00191 size_t OpenPGPEncode(byte *output, size_t bufferSize) const;
00192
00193 size_t OpenPGPEncode(BufferedTransformation &bt) const;
00194
00195
00196 void Decode(const byte *input, size_t inputLen, Signedness=UNSIGNED);
00197
00198
00199 void Decode(BufferedTransformation &bt, size_t inputLen, Signedness=UNSIGNED);
00200
00201
00202 void BERDecode(const byte *input, size_t inputLen);
00203
00204 void BERDecode(BufferedTransformation &bt);
00205
00206
00207 void BERDecodeAsOctetString(BufferedTransformation &bt, size_t length);
00208
00209 class OpenPGPDecodeErr : public Exception
00210 {
00211 public:
00212 OpenPGPDecodeErr() : Exception(INVALID_DATA_FORMAT, "OpenPGP decode error") {}
00213 };
00214
00215
00216 void OpenPGPDecode(const byte *input, size_t inputLen);
00217
00218 void OpenPGPDecode(BufferedTransformation &bt);
00219
00220
00221
00222
00223
00224 bool IsConvertableToLong() const;
00225
00226 signed long ConvertToLong() const;
00227
00228
00229 unsigned int BitCount() const;
00230
00231 unsigned int ByteCount() const;
00232
00233 unsigned int WordCount() const;
00234
00235
00236 bool GetBit(size_t i) const;
00237
00238 byte GetByte(size_t i) const;
00239
00240 lword GetBits(size_t i, size_t n) const;
00241
00242
00243 bool IsZero() const {return !*this;}
00244
00245 bool NotZero() const {return !IsZero();}
00246
00247 bool IsNegative() const {return sign == NEGATIVE;}
00248
00249 bool NotNegative() const {return !IsNegative();}
00250
00251 bool IsPositive() const {return NotNegative() && NotZero();}
00252
00253 bool NotPositive() const {return !IsPositive();}
00254
00255 bool IsEven() const {return GetBit(0) == 0;}
00256
00257 bool IsOdd() const {return GetBit(0) == 1;}
00258
00259
00260
00261
00262
00263 Integer& operator=(const Integer& t);
00264
00265
00266 Integer& operator+=(const Integer& t);
00267
00268 Integer& operator-=(const Integer& t);
00269
00270 Integer& operator*=(const Integer& t) {return *this = Times(t);}
00271
00272 Integer& operator/=(const Integer& t) {return *this = DividedBy(t);}
00273
00274 Integer& operator%=(const Integer& t) {return *this = Modulo(t);}
00275
00276 Integer& operator/=(word t) {return *this = DividedBy(t);}
00277
00278 Integer& operator%=(word t) {return *this = Modulo(t);}
00279
00280
00281 Integer& operator<<=(size_t);
00282
00283 Integer& operator>>=(size_t);
00284
00285
00286 void Randomize(RandomNumberGenerator &rng, size_t bitcount);
00287
00288 void Randomize(RandomNumberGenerator &rng, const Integer &min, const Integer &max);
00289
00290
00291 bool Randomize(RandomNumberGenerator &rng, const Integer &min, const Integer &max, RandomNumberType rnType, const Integer &equiv=Zero(), const Integer &mod=One());
00292
00293 bool GenerateRandomNoThrow(RandomNumberGenerator &rng, const NameValuePairs ¶ms = g_nullNameValuePairs);
00294 void GenerateRandom(RandomNumberGenerator &rng, const NameValuePairs ¶ms = g_nullNameValuePairs)
00295 {
00296 if (!GenerateRandomNoThrow(rng, params))
00297 throw RandomNumberNotFound();
00298 }
00299
00300
00301 void SetBit(size_t n, bool value=1);
00302
00303 void SetByte(size_t n, byte value);
00304
00305
00306 void Negate();
00307
00308 void SetPositive() {sign = POSITIVE;}
00309
00310 void SetNegative() {if (!!(*this)) sign = NEGATIVE;}
00311
00312
00313 void swap(Integer &a);
00314
00315
00316
00317
00318
00319 bool operator!() const;
00320
00321 Integer operator+() const {return *this;}
00322
00323 Integer operator-() const;
00324
00325 Integer& operator++();
00326
00327 Integer& operator--();
00328
00329 Integer operator++(int) {Integer temp = *this; ++*this; return temp;}
00330
00331 Integer operator--(int) {Integer temp = *this; --*this; return temp;}
00332
00333
00334
00335
00336
00337
00338
00339
00340
00341 int Compare(const Integer& a) const;
00342
00343
00344 Integer Plus(const Integer &b) const;
00345
00346 Integer Minus(const Integer &b) const;
00347
00348 Integer Times(const Integer &b) const;
00349
00350 Integer DividedBy(const Integer &b) const;
00351
00352 Integer Modulo(const Integer &b) const;
00353
00354 Integer DividedBy(word b) const;
00355
00356 word Modulo(word b) const;
00357
00358
00359 Integer operator>>(size_t n) const {return Integer(*this)>>=n;}
00360
00361 Integer operator<<(size_t n) const {return Integer(*this)<<=n;}
00362
00363
00364
00365
00366
00367 Integer AbsoluteValue() const;
00368
00369 Integer Doubled() const {return Plus(*this);}
00370
00371 Integer Squared() const {return Times(*this);}
00372
00373 Integer SquareRoot() const;
00374
00375 bool IsSquare() const;
00376
00377
00378 bool IsUnit() const;
00379
00380 Integer MultiplicativeInverse() const;
00381
00382
00383 CRYPTOPP_DLL friend Integer CRYPTOPP_API a_times_b_mod_c(const Integer &x, const Integer& y, const Integer& m);
00384
00385 CRYPTOPP_DLL friend Integer CRYPTOPP_API a_exp_b_mod_c(const Integer &x, const Integer& e, const Integer& m);
00386
00387
00388 static void CRYPTOPP_API Divide(Integer &r, Integer &q, const Integer &a, const Integer &d);
00389
00390 static void CRYPTOPP_API Divide(word &r, Integer &q, const Integer &a, word d);
00391
00392
00393 static void CRYPTOPP_API DivideByPowerOf2(Integer &r, Integer &q, const Integer &a, unsigned int n);
00394
00395
00396 static Integer CRYPTOPP_API Gcd(const Integer &a, const Integer &n);
00397
00398 Integer InverseMod(const Integer &n) const;
00399
00400 word InverseMod(word n) const;
00401
00402
00403
00404
00405
00406 friend CRYPTOPP_DLL std::istream& CRYPTOPP_API operator>>(std::istream& in, Integer &a);
00407
00408 friend CRYPTOPP_DLL std::ostream& CRYPTOPP_API operator<<(std::ostream& out, const Integer &a);
00409
00410
00411 private:
00412 friend class ModularArithmetic;
00413 friend class MontgomeryRepresentation;
00414 friend class HalfMontgomeryRepresentation;
00415
00416 Integer(word value, size_t length);
00417
00418 int PositiveCompare(const Integer &t) const;
00419 friend void PositiveAdd(Integer &sum, const Integer &a, const Integer &b);
00420 friend void PositiveSubtract(Integer &diff, const Integer &a, const Integer &b);
00421 friend void PositiveMultiply(Integer &product, const Integer &a, const Integer &b);
00422 friend void PositiveDivide(Integer &remainder, Integer "ient, const Integer ÷nd, const Integer &divisor);
00423
00424 SecAlignedWordBlock reg;
00425 Sign sign;
00426 };
00427
00428
00429 inline bool operator==(const CryptoPP::Integer& a, const CryptoPP::Integer& b) {return a.Compare(b)==0;}
00430
00431 inline bool operator!=(const CryptoPP::Integer& a, const CryptoPP::Integer& b) {return a.Compare(b)!=0;}
00432
00433 inline bool operator> (const CryptoPP::Integer& a, const CryptoPP::Integer& b) {return a.Compare(b)> 0;}
00434
00435 inline bool operator>=(const CryptoPP::Integer& a, const CryptoPP::Integer& b) {return a.Compare(b)>=0;}
00436
00437 inline bool operator< (const CryptoPP::Integer& a, const CryptoPP::Integer& b) {return a.Compare(b)< 0;}
00438
00439 inline bool operator<=(const CryptoPP::Integer& a, const CryptoPP::Integer& b) {return a.Compare(b)<=0;}
00440
00441 inline CryptoPP::Integer operator+(const CryptoPP::Integer &a, const CryptoPP::Integer &b) {return a.Plus(b);}
00442
00443 inline CryptoPP::Integer operator-(const CryptoPP::Integer &a, const CryptoPP::Integer &b) {return a.Minus(b);}
00444
00445 inline CryptoPP::Integer operator*(const CryptoPP::Integer &a, const CryptoPP::Integer &b) {return a.Times(b);}
00446
00447 inline CryptoPP::Integer operator/(const CryptoPP::Integer &a, const CryptoPP::Integer &b) {return a.DividedBy(b);}
00448
00449 inline CryptoPP::Integer operator%(const CryptoPP::Integer &a, const CryptoPP::Integer &b) {return a.Modulo(b);}
00450
00451 inline CryptoPP::Integer operator/(const CryptoPP::Integer &a, CryptoPP::word b) {return a.DividedBy(b);}
00452
00453 inline CryptoPP::word operator%(const CryptoPP::Integer &a, CryptoPP::word b) {return a.Modulo(b);}
00454
00455 NAMESPACE_END
00456
00457 NAMESPACE_BEGIN(std)
00458 template<> inline void swap(CryptoPP::Integer &a, CryptoPP::Integer &b)
00459 {
00460 a.swap(b);
00461 }
00462 NAMESPACE_END
00463
00464 #endif