1#ifndef CRYPTOPP_INTEGER_H 2#define CRYPTOPP_INTEGER_H 3 4/** \file */ 5 6#include "cryptlib.h" 7#include "secblock.h" 8 9#include <iosfwd> 10#include <algorithm> 11 12NAMESPACE_BEGIN(CryptoPP) 13 14struct InitializeInteger // used to initialize static variables 15{ 16 InitializeInteger(); 17}; 18 19typedef SecBlock<word, AllocatorWithCleanup<word, CRYPTOPP_BOOL_X86> > IntegerSecBlock; 20 21//! multiple precision integer and basic arithmetics 22/*! This class can represent positive and negative integers 23 with absolute value less than (256**sizeof(word)) ** (256**sizeof(int)). 24 \nosubgrouping 25*/ 26class CRYPTOPP_DLL Integer : private InitializeInteger, public ASN1Object 27{ 28public: 29 //! \name ENUMS, EXCEPTIONS, and TYPEDEFS 30 //@{ 31 //! division by zero exception 32 class DivideByZero : public Exception 33 { 34 public: 35 DivideByZero() : Exception(OTHER_ERROR, "Integer: division by zero") {} 36 }; 37 38 //! 39 class RandomNumberNotFound : public Exception 40 { 41 public: 42 RandomNumberNotFound() : Exception(OTHER_ERROR, "Integer: no integer satisfies the given parameters") {} 43 }; 44 45 //! 46 enum Sign {POSITIVE=0, NEGATIVE=1}; 47 48 //! 49 enum Signedness { 50 //! 51 UNSIGNED, 52 //! 53 SIGNED}; 54 55 //! 56 enum RandomNumberType { 57 //! 58 ANY, 59 //! 60 PRIME}; 61 //@} 62 63 //! \name CREATORS 64 //@{ 65 //! creates the zero integer 66 Integer(); 67 68 //! copy constructor 69 Integer(const Integer& t); 70 71 //! convert from signed long 72 Integer(signed long value); 73 74 //! convert from lword 75 Integer(Sign s, lword value); 76 77 //! convert from two words 78 Integer(Sign s, word highWord, word lowWord); 79 80 //! convert from string 81 /*! str can be in base 2, 8, 10, or 16. Base is determined by a 82 case insensitive suffix of 'h', 'o', or 'b'. No suffix means base 10. 83 */ 84 explicit Integer(const char *str); 85 explicit Integer(const wchar_t *str); 86 87 //! convert from big-endian byte array 88 Integer(const byte *encodedInteger, size_t byteCount, Signedness s=UNSIGNED); 89 90 //! convert from big-endian form stored in a BufferedTransformation 91 Integer(BufferedTransformation &bt, size_t byteCount, Signedness s=UNSIGNED); 92 93 //! convert from BER encoded byte array stored in a BufferedTransformation object 94 explicit Integer(BufferedTransformation &bt); 95 96 //! create a random integer 97 /*! The random integer created is uniformly distributed over [0, 2**bitcount). */ 98 Integer(RandomNumberGenerator &rng, size_t bitcount); 99 100 //! avoid calling constructors for these frequently used integers 101 static const Integer & CRYPTOPP_API Zero(); 102 //! avoid calling constructors for these frequently used integers 103 static const Integer & CRYPTOPP_API One(); 104 //! avoid calling constructors for these frequently used integers 105 static const Integer & CRYPTOPP_API Two(); 106 107 //! create a random integer of special type 108 /*! Ideally, the random integer created should be uniformly distributed 109 over {x | min <= x <= max and x is of rnType and x % mod == equiv}. 110 However the actual distribution may not be uniform because sequential 111 search is used to find an appropriate number from a random starting 112 point. 113 May return (with very small probability) a pseudoprime when a prime 114 is requested and max > lastSmallPrime*lastSmallPrime (lastSmallPrime 115 is declared in nbtheory.h). 116 \throw RandomNumberNotFound if the set is empty. 117 */ 118 Integer(RandomNumberGenerator &rng, const Integer &min, const Integer &max, RandomNumberType rnType=ANY, const Integer &equiv=Zero(), const Integer &mod=One()); 119 120 //! return the integer 2**e 121 static Integer CRYPTOPP_API Power2(size_t e); 122 //@} 123 124 //! \name ENCODE/DECODE 125 //@{ 126 //! minimum number of bytes to encode this integer 127 /*! MinEncodedSize of 0 is 1 */ 128 size_t MinEncodedSize(Signedness=UNSIGNED) const; 129 //! encode in big-endian format 130 /*! unsigned means encode absolute value, signed means encode two's complement if negative. 131 if outputLen < MinEncodedSize, the most significant bytes will be dropped 132 if outputLen > MinEncodedSize, the most significant bytes will be padded 133 */ 134 void Encode(byte *output, size_t outputLen, Signedness=UNSIGNED) const; 135 //! 136 void Encode(BufferedTransformation &bt, size_t outputLen, Signedness=UNSIGNED) const; 137 138 //! encode using Distinguished Encoding Rules, put result into a BufferedTransformation object 139 void DEREncode(BufferedTransformation &bt) const; 140 141 //! encode absolute value as big-endian octet string 142 void DEREncodeAsOctetString(BufferedTransformation &bt, size_t length) const; 143 144 //! encode absolute value in OpenPGP format, return length of output 145 size_t OpenPGPEncode(byte *output, size_t bufferSize) const; 146 //! encode absolute value in OpenPGP format, put result into a BufferedTransformation object 147 size_t OpenPGPEncode(BufferedTransformation &bt) const; 148 149 //! 150 void Decode(const byte *input, size_t inputLen, Signedness=UNSIGNED); 151 //! 152 //* Precondition: bt.MaxRetrievable() >= inputLen 153 void Decode(BufferedTransformation &bt, size_t inputLen, Signedness=UNSIGNED); 154 155 //! 156 void BERDecode(const byte *input, size_t inputLen); 157 //! 158 void BERDecode(BufferedTransformation &bt); 159 160 //! decode nonnegative value as big-endian octet string 161 void BERDecodeAsOctetString(BufferedTransformation &bt, size_t length); 162 163 class OpenPGPDecodeErr : public Exception 164 { 165 public: 166 OpenPGPDecodeErr() : Exception(INVALID_DATA_FORMAT, "OpenPGP decode error") {} 167 }; 168 169 //! 170 void OpenPGPDecode(const byte *input, size_t inputLen); 171 //! 172 void OpenPGPDecode(BufferedTransformation &bt); 173 //@} 174 175 //! \name ACCESSORS 176 //@{ 177 //! return true if *this can be represented as a signed long 178 bool IsConvertableToLong() const; 179 //! return equivalent signed long if possible, otherwise undefined 180 signed long ConvertToLong() const; 181 182 //! number of significant bits = floor(log2(abs(*this))) + 1 183 unsigned int BitCount() const; 184 //! number of significant bytes = ceiling(BitCount()/8) 185 unsigned int ByteCount() const; 186 //! number of significant words = ceiling(ByteCount()/sizeof(word)) 187 unsigned int WordCount() const; 188 189 //! return the i-th bit, i=0 being the least significant bit 190 bool GetBit(size_t i) const; 191 //! return the i-th byte 192 byte GetByte(size_t i) const; 193 //! return n lowest bits of *this >> i 194 lword GetBits(size_t i, size_t n) const; 195 196 //! 197 bool IsZero() const {return !*this;} 198 //! 199 bool NotZero() const {return !IsZero();} 200 //! 201 bool IsNegative() const {return sign == NEGATIVE;} 202 //! 203 bool NotNegative() const {return !IsNegative();} 204 //! 205 bool IsPositive() const {return NotNegative() && NotZero();} 206 //! 207 bool NotPositive() const {return !IsPositive();} 208 //! 209 bool IsEven() const {return GetBit(0) == 0;} 210 //! 211 bool IsOdd() const {return GetBit(0) == 1;} 212 //@} 213 214 //! \name MANIPULATORS 215 //@{ 216 //! 217 Integer& operator=(const Integer& t); 218 219 //! 220 Integer& operator+=(const Integer& t); 221 //! 222 Integer& operator-=(const Integer& t); 223 //! 224 Integer& operator*=(const Integer& t) {return *this = Times(t);} 225 //! 226 Integer& operator/=(const Integer& t) {return *this = DividedBy(t);} 227 //! 228 Integer& operator%=(const Integer& t) {return *this = Modulo(t);} 229 //! 230 Integer& operator/=(word t) {return *this = DividedBy(t);} 231 //! 232 Integer& operator%=(word t) {return *this = Integer(POSITIVE, 0, Modulo(t));} 233 234 //! 235 Integer& operator<<=(size_t); 236 //! 237 Integer& operator>>=(size_t); 238 239 //! 240 void Randomize(RandomNumberGenerator &rng, size_t bitcount); 241 //! 242 void Randomize(RandomNumberGenerator &rng, const Integer &min, const Integer &max); 243 //! set this Integer to a random element of {x | min <= x <= max and x is of rnType and x % mod == equiv} 244 /*! returns false if the set is empty */ 245 bool Randomize(RandomNumberGenerator &rng, const Integer &min, const Integer &max, RandomNumberType rnType, const Integer &equiv=Zero(), const Integer &mod=One()); 246 247 bool GenerateRandomNoThrow(RandomNumberGenerator &rng, const NameValuePairs ¶ms = g_nullNameValuePairs); 248 void GenerateRandom(RandomNumberGenerator &rng, const NameValuePairs ¶ms = g_nullNameValuePairs) 249 { 250 if (!GenerateRandomNoThrow(rng, params)) 251 throw RandomNumberNotFound(); 252 } 253 254 //! set the n-th bit to value 255 void SetBit(size_t n, bool value=1); 256 //! set the n-th byte to value 257 void SetByte(size_t n, byte value); 258 259 //! 260 void Negate(); 261 //! 262 void SetPositive() {sign = POSITIVE;} 263 //! 264 void SetNegative() {if (!!(*this)) sign = NEGATIVE;} 265 266 //! 267 void swap(Integer &a); 268 //@} 269 270 //! \name UNARY OPERATORS 271 //@{ 272 //! 273 bool operator!() const; 274 //! 275 Integer operator+() const {return *this;} 276 //! 277 Integer operator-() const; 278 //! 279 Integer& operator++(); 280 //! 281 Integer& operator--(); 282 //! 283 Integer operator++(int) {Integer temp = *this; ++*this; return temp;} 284 //! 285 Integer operator--(int) {Integer temp = *this; --*this; return temp;} 286 //@} 287 288 //! \name BINARY OPERATORS 289 //@{ 290 //! signed comparison 291 /*! \retval -1 if *this < a 292 \retval 0 if *this = a 293 \retval 1 if *this > a 294 */ 295 int Compare(const Integer& a) const; 296 297 //! 298 Integer Plus(const Integer &b) const; 299 //! 300 Integer Minus(const Integer &b) const; 301 //! 302 Integer Times(const Integer &b) const; 303 //! 304 Integer DividedBy(const Integer &b) const; 305 //! 306 Integer Modulo(const Integer &b) const; 307 //! 308 Integer DividedBy(word b) const; 309 //! 310 word Modulo(word b) const; 311 312 //! 313 Integer operator>>(size_t n) const {return Integer(*this)>>=n;} 314 //! 315 Integer operator<<(size_t n) const {return Integer(*this)<<=n;} 316 //@} 317 318 //! \name OTHER ARITHMETIC FUNCTIONS 319 //@{ 320 //! 321 Integer AbsoluteValue() const; 322 //! 323 Integer Doubled() const {return Plus(*this);} 324 //! 325 Integer Squared() const {return Times(*this);} 326 //! extract square root, if negative return 0, else return floor of square root 327 Integer SquareRoot() const; 328 //! return whether this integer is a perfect square 329 bool IsSquare() const; 330 331 //! is 1 or -1 332 bool IsUnit() const; 333 //! return inverse if 1 or -1, otherwise return 0 334 Integer MultiplicativeInverse() const; 335 336 //! modular multiplication 337 CRYPTOPP_DLL friend Integer CRYPTOPP_API a_times_b_mod_c(const Integer &x, const Integer& y, const Integer& m); 338 //! modular exponentiation 339 CRYPTOPP_DLL friend Integer CRYPTOPP_API a_exp_b_mod_c(const Integer &x, const Integer& e, const Integer& m); 340 341 //! calculate r and q such that (a == d*q + r) && (0 <= r < abs(d)) 342 static void CRYPTOPP_API Divide(Integer &r, Integer &q, const Integer &a, const Integer &d); 343 //! use a faster division algorithm when divisor is short 344 static void CRYPTOPP_API Divide(word &r, Integer &q, const Integer &a, word d); 345 346 //! returns same result as Divide(r, q, a, Power2(n)), but faster 347 static void CRYPTOPP_API DivideByPowerOf2(Integer &r, Integer &q, const Integer &a, unsigned int n); 348 349 //! greatest common divisor 350 static Integer CRYPTOPP_API Gcd(const Integer &a, const Integer &n); 351 //! calculate multiplicative inverse of *this mod n 352 Integer InverseMod(const Integer &n) const; 353 //! 354 word InverseMod(word n) const; 355 //@} 356 357 //! \name INPUT/OUTPUT 358 //@{ 359 //! 360 friend CRYPTOPP_DLL std::istream& CRYPTOPP_API operator>>(std::istream& in, Integer &a); 361 //! 362 friend CRYPTOPP_DLL std::ostream& CRYPTOPP_API operator<<(std::ostream& out, const Integer &a); 363 //@} 364 365private: 366 friend class ModularArithmetic; 367 friend class MontgomeryRepresentation; 368 friend class HalfMontgomeryRepresentation; 369 370 Integer(word value, size_t length); 371 372 int PositiveCompare(const Integer &t) const; 373 friend void PositiveAdd(Integer &sum, const Integer &a, const Integer &b); 374 friend void PositiveSubtract(Integer &diff, const Integer &a, const Integer &b); 375 friend void PositiveMultiply(Integer &product, const Integer &a, const Integer &b); 376 friend void PositiveDivide(Integer &remainder, Integer "ient, const Integer ÷nd, const Integer &divisor); 377 378 IntegerSecBlock reg; 379 Sign sign; 380}; 381 382//! 383inline bool operator==(const CryptoPP::Integer& a, const CryptoPP::Integer& b) {return a.Compare(b)==0;} 384//! 385inline bool operator!=(const CryptoPP::Integer& a, const CryptoPP::Integer& b) {return a.Compare(b)!=0;} 386//! 387inline bool operator> (const CryptoPP::Integer& a, const CryptoPP::Integer& b) {return a.Compare(b)> 0;} 388//! 389inline bool operator>=(const CryptoPP::Integer& a, const CryptoPP::Integer& b) {return a.Compare(b)>=0;} 390//! 391inline bool operator< (const CryptoPP::Integer& a, const CryptoPP::Integer& b) {return a.Compare(b)< 0;} 392//! 393inline bool operator<=(const CryptoPP::Integer& a, const CryptoPP::Integer& b) {return a.Compare(b)<=0;} 394//! 395inline CryptoPP::Integer operator+(const CryptoPP::Integer &a, const CryptoPP::Integer &b) {return a.Plus(b);} 396//! 397inline CryptoPP::Integer operator-(const CryptoPP::Integer &a, const CryptoPP::Integer &b) {return a.Minus(b);} 398//! 399inline CryptoPP::Integer operator*(const CryptoPP::Integer &a, const CryptoPP::Integer &b) {return a.Times(b);} 400//! 401inline CryptoPP::Integer operator/(const CryptoPP::Integer &a, const CryptoPP::Integer &b) {return a.DividedBy(b);} 402//! 403inline CryptoPP::Integer operator%(const CryptoPP::Integer &a, const CryptoPP::Integer &b) {return a.Modulo(b);} 404//! 405inline CryptoPP::Integer operator/(const CryptoPP::Integer &a, CryptoPP::word b) {return a.DividedBy(b);} 406//! 407inline CryptoPP::word operator%(const CryptoPP::Integer &a, CryptoPP::word b) {return a.Modulo(b);} 408 409NAMESPACE_END 410 411#ifndef __BORLANDC__ 412NAMESPACE_BEGIN(std) 413inline void swap(CryptoPP::Integer &a, CryptoPP::Integer &b) 414{ 415 a.swap(b); 416} 417NAMESPACE_END 418#endif 419 420#endif 421