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 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,
unsigned int byteCount, Signedness s=UNSIGNED);
00135
00136
00137 Integer(
BufferedTransformation &bt,
unsigned int byteCount, Signedness s=UNSIGNED);
00138
00139
00140
explicit Integer(
BufferedTransformation &bt);
00141
00142
00143
00144 Integer(
RandomNumberGenerator &rng,
unsigned int bitcount);
00145
00146
00147
static const Integer &Zero();
00148
00149
static const Integer &One();
00150
00151
static const Integer &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 Power2(
unsigned int e);
00168
00169
00170
00171
00172
00173
00174
unsigned int MinEncodedSize(Signedness=UNSIGNED)
const;
00175
00176
00177
00178
00179
00180
unsigned int Encode(byte *output,
unsigned int outputLen, Signedness=UNSIGNED)
const;
00181
00182
unsigned int Encode(
BufferedTransformation &bt,
unsigned int outputLen, Signedness=UNSIGNED)
const;
00183
00184
00185
void DEREncode(
BufferedTransformation &bt)
const;
00186
00187
00188
void DEREncodeAsOctetString(
BufferedTransformation &bt,
unsigned int length)
const;
00189
00190
00191
unsigned int OpenPGPEncode(byte *output,
unsigned int bufferSize)
const;
00192
00193
unsigned int OpenPGPEncode(
BufferedTransformation &bt)
const;
00194
00195
00196
void Decode(
const byte *input,
unsigned int inputLen, Signedness=UNSIGNED);
00197
00198
00199
void Decode(
BufferedTransformation &bt,
unsigned int inputLen, Signedness=UNSIGNED);
00200
00201
00202
void BERDecode(
const byte *input,
unsigned int inputLen);
00203
00204
void BERDecode(
BufferedTransformation &bt);
00205
00206
00207
void BERDecodeAsOctetString(
BufferedTransformation &bt,
unsigned int 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,
unsigned int 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(
unsigned int i) const;
00237
00238 byte GetByte(
unsigned int i) const;
00239
00240
unsigned long GetBits(
unsigned int i,
unsigned int 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<<=(
unsigned int);
00282
00283 Integer& operator>>=(
unsigned int);
00284
00285
00286
void Randomize(
RandomNumberGenerator &rng,
unsigned int 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(
unsigned int n,
bool value=1);
00302
00303
void SetByte(
unsigned int 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>>(
unsigned int n)
const {
return Integer(*
this)>>=n;}
00360
00361 Integer operator<<(
unsigned int 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 a_times_b_mod_c(const Integer &x, const Integer& y, const Integer& m);
00384
00385 CRYPTOPP_DLL friend Integer a_exp_b_mod_c(const Integer &x, const Integer& e, const Integer& m);
00386
00387
00388 static
void Divide(Integer &r, Integer &q, const Integer &a, const Integer &d);
00389
00390 static
void Divide(word &r, Integer &q, const Integer &a, word d);
00391
00392
00393 static
void DivideByPowerOf2(Integer &r, Integer &q, const Integer &a,
unsigned int n);
00394
00395
00396 static Integer 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& operator>>(std::istream& in, Integer &a);
00407
00408 friend CRYPTOPP_DLL std::ostream& 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,
unsigned int 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