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 NAMESPACE_BEGIN(CryptoPP)
00013
00014 struct InitializeInteger
00015 {
00016 InitializeInteger();
00017 };
00018
00019 typedef SecBlock<word, AllocatorWithCleanup<word, CRYPTOPP_BOOL_X86> > IntegerSecBlock;
00020
00021
00022
00023
00024
00025
00026 class CRYPTOPP_DLL Integer : private InitializeInteger, public ASN1Object
00027 {
00028 public:
00029
00030
00031
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
00064
00065
00066 Integer();
00067
00068
00069 Integer(const Integer& t);
00070
00071
00072 Integer(signed long value);
00073
00074
00075 Integer(Sign s, lword value);
00076
00077
00078 Integer(Sign s, word highWord, word lowWord);
00079
00080
00081
00082
00083
00084 explicit Integer(const char *str);
00085 explicit Integer(const wchar_t *str);
00086
00087
00088 Integer(const byte *encodedInteger, size_t byteCount, Signedness s=UNSIGNED);
00089
00090
00091 Integer(BufferedTransformation &bt, size_t byteCount, Signedness s=UNSIGNED);
00092
00093
00094 explicit Integer(BufferedTransformation &bt);
00095
00096
00097
00098 Integer(RandomNumberGenerator &rng, size_t bitcount);
00099
00100
00101 static const Integer & CRYPTOPP_API Zero();
00102
00103 static const Integer & CRYPTOPP_API One();
00104
00105 static const Integer & CRYPTOPP_API Two();
00106
00107
00108
00109
00110
00111
00112
00113
00114
00115
00116
00117
00118 Integer(RandomNumberGenerator &rng, const Integer &min, const Integer &max, RandomNumberType rnType=ANY, const Integer &equiv=Zero(), const Integer &mod=One());
00119
00120
00121 static Integer CRYPTOPP_API Power2(size_t e);
00122
00123
00124
00125
00126
00127
00128 size_t MinEncodedSize(Signedness=UNSIGNED) const;
00129
00130
00131
00132
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
00139 void DEREncode(BufferedTransformation &bt) const;
00140
00141
00142 void DEREncodeAsOctetString(BufferedTransformation &bt, size_t length) const;
00143
00144
00145 size_t OpenPGPEncode(byte *output, size_t bufferSize) const;
00146
00147 size_t OpenPGPEncode(BufferedTransformation &bt) const;
00148
00149
00150 void Decode(const byte *input, size_t inputLen, Signedness=UNSIGNED);
00151
00152
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
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
00176
00177
00178 bool IsConvertableToLong() const;
00179
00180 signed long ConvertToLong() const;
00181
00182
00183 unsigned int BitCount() const;
00184
00185 unsigned int ByteCount() const;
00186
00187 unsigned int WordCount() const;
00188
00189
00190 bool GetBit(size_t i) const;
00191
00192 byte GetByte(size_t i) const;
00193
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
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
00244
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 ¶ms = g_nullNameValuePairs);
00248 void GenerateRandom(RandomNumberGenerator &rng, const NameValuePairs ¶ms = g_nullNameValuePairs)
00249 {
00250 if (!GenerateRandomNoThrow(rng, params))
00251 throw RandomNumberNotFound();
00252 }
00253
00254
00255 void SetBit(size_t n, bool value=1);
00256
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
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
00289
00290
00291
00292
00293
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
00319
00320
00321 Integer AbsoluteValue() const;
00322
00323 Integer Doubled() const {return Plus(*this);}
00324
00325 Integer Squared() const {return Times(*this);}
00326
00327 Integer SquareRoot() const;
00328
00329 bool IsSquare() const;
00330
00331
00332 bool IsUnit() const;
00333
00334 Integer MultiplicativeInverse() const;
00335
00336
00337 CRYPTOPP_DLL friend Integer CRYPTOPP_API a_times_b_mod_c(const Integer &x, const Integer& y, const Integer& m);
00338
00339 CRYPTOPP_DLL friend Integer CRYPTOPP_API a_exp_b_mod_c(const Integer &x, const Integer& e, const Integer& m);
00340
00341
00342 static void CRYPTOPP_API Divide(Integer &r, Integer &q, const Integer &a, const Integer &d);
00343
00344 static void CRYPTOPP_API Divide(word &r, Integer &q, const Integer &a, word d);
00345
00346
00347 static void CRYPTOPP_API DivideByPowerOf2(Integer &r, Integer &q, const Integer &a, unsigned int n);
00348
00349
00350 static Integer CRYPTOPP_API Gcd(const Integer &a, const Integer &n);
00351
00352 Integer InverseMod(const Integer &n) const;
00353
00354 word InverseMod(word n) const;
00355
00356
00357
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 "ient, const Integer ÷nd, 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