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