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