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