EIC code displayed by LXR |
|
|
|
|||
File indexing completed on 2025-01-18 09:55:04
0001 // integer.h - originally written and placed in the public domain by Wei Dai 0002 0003 /// \file integer.h 0004 /// \brief Multiple precision integer with arithmetic operations 0005 /// \details The Integer class can represent positive and negative integers 0006 /// with absolute value less than (256**sizeof(word))<sup>(256**sizeof(int))</sup>. 0007 /// \details Internally, the library uses a sign magnitude representation, and the class 0008 /// has two data members. The first is a IntegerSecBlock (a SecBlock<word>) and it is 0009 /// used to hold the representation. The second is a Sign (an enumeration), and it is 0010 /// used to track the sign of the Integer. 0011 /// \details For details on how the Integer class initializes its function pointers using 0012 /// InitializeInteger and how it creates Integer::Zero(), Integer::One(), and 0013 /// Integer::Two(), then see the comments at the top of <tt>integer.cpp</tt>. 0014 /// \since Crypto++ 1.0 0015 0016 #ifndef CRYPTOPP_INTEGER_H 0017 #define CRYPTOPP_INTEGER_H 0018 0019 #include "cryptlib.h" 0020 #include "secblock.h" 0021 #include "stdcpp.h" 0022 0023 #include <iosfwd> 0024 0025 NAMESPACE_BEGIN(CryptoPP) 0026 0027 /// \struct InitializeInteger 0028 /// \brief Performs static initialization of the Integer class 0029 struct InitializeInteger 0030 { 0031 InitializeInteger(); 0032 }; 0033 0034 // Always align, http://github.com/weidai11/cryptopp/issues/256 0035 typedef SecBlock<word, AllocatorWithCleanup<word, true> > IntegerSecBlock; 0036 0037 /// \brief Multiple precision integer with arithmetic operations 0038 /// \details The Integer class can represent positive and negative integers 0039 /// with absolute value less than (256**sizeof(word))<sup>(256**sizeof(int))</sup>. 0040 /// \details Internally, the library uses a sign magnitude representation, and the class 0041 /// has two data members. The first is a IntegerSecBlock (a SecBlock<word>) and it is 0042 /// used to hold the representation. The second is a Sign (an enumeration), and it is 0043 /// used to track the sign of the Integer. 0044 /// \details For details on how the Integer class initializes its function pointers using 0045 /// InitializeInteger and how it creates Integer::Zero(), Integer::One(), and 0046 /// Integer::Two(), then see the comments at the top of <tt>integer.cpp</tt>. 0047 /// \since Crypto++ 1.0 0048 /// \nosubgrouping 0049 class CRYPTOPP_DLL Integer : private InitializeInteger, public ASN1Object 0050 { 0051 public: 0052 /// \name ENUMS, EXCEPTIONS, and TYPEDEFS 0053 //@{ 0054 /// \brief Exception thrown when division by 0 is encountered 0055 class DivideByZero : public Exception 0056 { 0057 public: 0058 DivideByZero() : Exception(OTHER_ERROR, "Integer: division by zero") {} 0059 }; 0060 0061 /// \brief Exception thrown when a random number cannot be found that 0062 /// satisfies the condition 0063 class RandomNumberNotFound : public Exception 0064 { 0065 public: 0066 RandomNumberNotFound() : Exception(OTHER_ERROR, "Integer: no integer satisfies the given parameters") {} 0067 }; 0068 0069 /// \enum Sign 0070 /// \brief Used internally to represent the integer 0071 /// \details Sign is used internally to represent the integer. It is also used in a few API functions. 0072 /// \sa SetPositive(), SetNegative(), Signedness 0073 enum Sign { 0074 /// \brief the value is positive or 0 0075 POSITIVE=0, 0076 /// \brief the value is negative 0077 NEGATIVE=1}; 0078 0079 /// \enum Signedness 0080 /// \brief Used when importing and exporting integers 0081 /// \details Signedness is usually used in API functions. 0082 /// \sa Sign 0083 enum Signedness { 0084 /// \brief an unsigned value 0085 UNSIGNED, 0086 /// \brief a signed value 0087 SIGNED}; 0088 0089 /// \enum RandomNumberType 0090 /// \brief Properties of a random integer 0091 enum RandomNumberType { 0092 /// \brief a number with no special properties 0093 ANY, 0094 /// \brief a number which is probabilistically prime 0095 PRIME}; 0096 //@} 0097 0098 /// \name CREATORS 0099 //@{ 0100 /// \brief Creates the zero integer 0101 Integer(); 0102 0103 /// copy constructor 0104 Integer(const Integer& t); 0105 0106 /// \brief Convert from signed long 0107 Integer(signed long value); 0108 0109 /// \brief Convert from lword 0110 /// \param sign enumeration indicating Sign 0111 /// \param value the long word 0112 Integer(Sign sign, lword value); 0113 0114 /// \brief Convert from two words 0115 /// \param sign enumeration indicating Sign 0116 /// \param highWord the high word 0117 /// \param lowWord the low word 0118 Integer(Sign sign, word highWord, word lowWord); 0119 0120 /// \brief Convert from a C-string 0121 /// \param str C-string value 0122 /// \param order the ByteOrder of the string to be processed 0123 /// \details \p str can be in base 8, 10, or 16. Base is determined 0124 /// by a case insensitive suffix of 'o' (8), '.' (10), or 'h' (16). 0125 /// No suffix means base 10. 0126 /// \details Byte order was added at Crypto++ 5.7 to allow use of little-endian 0127 /// integers with curve25519, Poly1305 and Microsoft CAPI. 0128 explicit Integer(const char *str, ByteOrder order = BIG_ENDIAN_ORDER); 0129 0130 /// \brief Convert from a wide C-string 0131 /// \param str wide C-string value 0132 /// \param order the ByteOrder of the string to be processed 0133 /// \details \p str can be in base 8, 10, or 16. Base is determined 0134 /// by a case insensitive suffix of 'o' (8), '.' (10), or 'h' (16). 0135 /// No suffix means base 10. 0136 /// \details Byte order was added at Crypto++ 5.7 to allow use of little-endian 0137 /// integers with curve25519, Poly1305 and Microsoft CAPI. 0138 explicit Integer(const wchar_t *str, ByteOrder order = BIG_ENDIAN_ORDER); 0139 0140 /// \brief Convert from a big-endian byte array 0141 /// \param encodedInteger big-endian byte array 0142 /// \param byteCount length of the byte array 0143 /// \param sign enumeration indicating Signedness 0144 /// \param order the ByteOrder of the array to be processed 0145 /// \details Byte order was added at Crypto++ 5.7 to allow use of little-endian 0146 /// integers with curve25519, Poly1305 and Microsoft CAPI. 0147 Integer(const byte *encodedInteger, size_t byteCount, Signedness sign=UNSIGNED, ByteOrder order = BIG_ENDIAN_ORDER); 0148 0149 /// \brief Convert from a big-endian array 0150 /// \param bt BufferedTransformation object with big-endian byte array 0151 /// \param byteCount length of the byte array 0152 /// \param sign enumeration indicating Signedness 0153 /// \param order the ByteOrder of the data to be processed 0154 /// \details Byte order was added at Crypto++ 5.7 to allow use of little-endian 0155 /// integers with curve25519, Poly1305 and Microsoft CAPI. 0156 Integer(BufferedTransformation &bt, size_t byteCount, Signedness sign=UNSIGNED, ByteOrder order = BIG_ENDIAN_ORDER); 0157 0158 /// \brief Convert from a BER encoded byte array 0159 /// \param bt BufferedTransformation object with BER encoded byte array 0160 explicit Integer(BufferedTransformation &bt); 0161 0162 /// \brief Create a random integer 0163 /// \param rng RandomNumberGenerator used to generate material 0164 /// \param bitCount the number of bits in the resulting integer 0165 /// \details The random integer created is uniformly distributed over <tt>[0, 2<sup>bitCount</sup>]</tt>. 0166 Integer(RandomNumberGenerator &rng, size_t bitCount); 0167 0168 /// \brief Integer representing 0 0169 /// \return an Integer representing 0 0170 /// \details Zero() avoids calling constructors for frequently used integers 0171 static const Integer & CRYPTOPP_API Zero(); 0172 /// \brief Integer representing 1 0173 /// \return an Integer representing 1 0174 /// \details One() avoids calling constructors for frequently used integers 0175 static const Integer & CRYPTOPP_API One(); 0176 /// \brief Integer representing 2 0177 /// \return an Integer representing 2 0178 /// \details Two() avoids calling constructors for frequently used integers 0179 static const Integer & CRYPTOPP_API Two(); 0180 0181 /// \brief Create a random integer of special form 0182 /// \param rng RandomNumberGenerator used to generate material 0183 /// \param min the minimum value 0184 /// \param max the maximum value 0185 /// \param rnType RandomNumberType to specify the type 0186 /// \param equiv the equivalence class based on the parameter \p mod 0187 /// \param mod the modulus used to reduce the equivalence class 0188 /// \throw RandomNumberNotFound if the set is empty. 0189 /// \details Ideally, the random integer created should be uniformly distributed 0190 /// over <tt>{x | min \<= x \<= max</tt> and \p x is of rnType and <tt>x \% mod == equiv}</tt>. 0191 /// However the actual distribution may not be uniform because sequential 0192 /// search is used to find an appropriate number from a random starting 0193 /// point. 0194 /// \details May return (with very small probability) a pseudoprime when a prime 0195 /// is requested and <tt>max \> lastSmallPrime*lastSmallPrime</tt>. \p lastSmallPrime 0196 /// is declared in nbtheory.h. 0197 Integer(RandomNumberGenerator &rng, const Integer &min, const Integer &max, RandomNumberType rnType=ANY, const Integer &equiv=Zero(), const Integer &mod=One()); 0198 0199 /// \brief Exponentiates to a power of 2 0200 /// \return the Integer 2<sup>e</sup> 0201 /// \sa a_times_b_mod_c() and a_exp_b_mod_c() 0202 static Integer CRYPTOPP_API Power2(size_t e); 0203 //@} 0204 0205 /// \name ENCODE/DECODE 0206 //@{ 0207 /// \brief Minimum number of bytes to encode this integer 0208 /// \param sign enumeration indicating Signedness 0209 /// \note The MinEncodedSize() of 0 is 1. 0210 size_t MinEncodedSize(Signedness sign=UNSIGNED) const; 0211 0212 /// \brief Encode in big-endian format 0213 /// \param output big-endian byte array 0214 /// \param outputLen length of the byte array 0215 /// \param sign enumeration indicating Signedness 0216 /// \details Unsigned means encode absolute value, signed means encode two's complement if negative. 0217 /// \details outputLen can be used to ensure an Integer is encoded to an exact size (rather than a 0218 /// minimum size). An exact size is useful, for example, when encoding to a field element size. 0219 void Encode(byte *output, size_t outputLen, Signedness sign=UNSIGNED) const; 0220 0221 /// \brief Encode in big-endian format 0222 /// \param bt BufferedTransformation object 0223 /// \param outputLen length of the encoding 0224 /// \param sign enumeration indicating Signedness 0225 /// \details Unsigned means encode absolute value, signed means encode two's complement if negative. 0226 /// \details outputLen can be used to ensure an Integer is encoded to an exact size (rather than a 0227 /// minimum size). An exact size is useful, for example, when encoding to a field element size. 0228 void Encode(BufferedTransformation &bt, size_t outputLen, Signedness sign=UNSIGNED) const; 0229 0230 /// \brief Encode in DER format 0231 /// \param bt BufferedTransformation object 0232 /// \details Encodes the Integer using Distinguished Encoding Rules 0233 /// The result is placed into a BufferedTransformation object 0234 void DEREncode(BufferedTransformation &bt) const; 0235 0236 /// \brief Encode absolute value as big-endian octet string 0237 /// \param bt BufferedTransformation object 0238 /// \param length the number of mytes to decode 0239 void DEREncodeAsOctetString(BufferedTransformation &bt, size_t length) const; 0240 0241 /// \brief Encode absolute value in OpenPGP format 0242 /// \param output big-endian byte array 0243 /// \param bufferSize length of the byte array 0244 /// \return length of the output 0245 /// \details OpenPGPEncode places result into the buffer and returns the 0246 /// number of bytes used for the encoding 0247 size_t OpenPGPEncode(byte *output, size_t bufferSize) const; 0248 0249 /// \brief Encode absolute value in OpenPGP format 0250 /// \param bt BufferedTransformation object 0251 /// \return length of the output 0252 /// \details OpenPGPEncode places result into a BufferedTransformation object and returns the 0253 /// number of bytes used for the encoding 0254 size_t OpenPGPEncode(BufferedTransformation &bt) const; 0255 0256 /// \brief Decode from big-endian byte array 0257 /// \param input big-endian byte array 0258 /// \param inputLen length of the byte array 0259 /// \param sign enumeration indicating Signedness 0260 void Decode(const byte *input, size_t inputLen, Signedness sign=UNSIGNED); 0261 0262 /// \brief Decode nonnegative value from big-endian byte array 0263 /// \param bt BufferedTransformation object 0264 /// \param inputLen length of the byte array 0265 /// \param sign enumeration indicating Signedness 0266 /// \note <tt>bt.MaxRetrievable() \>= inputLen</tt>. 0267 void Decode(BufferedTransformation &bt, size_t inputLen, Signedness sign=UNSIGNED); 0268 0269 /// \brief Decode from BER format 0270 /// \param input big-endian byte array 0271 /// \param inputLen length of the byte array 0272 void BERDecode(const byte *input, size_t inputLen); 0273 0274 /// \brief Decode from BER format 0275 /// \param bt BufferedTransformation object 0276 void BERDecode(BufferedTransformation &bt); 0277 0278 /// \brief Decode nonnegative value from big-endian octet string 0279 /// \param bt BufferedTransformation object 0280 /// \param length length of the byte array 0281 void BERDecodeAsOctetString(BufferedTransformation &bt, size_t length); 0282 0283 /// \brief Exception thrown when an error is encountered decoding an OpenPGP integer 0284 class OpenPGPDecodeErr : public Exception 0285 { 0286 public: 0287 OpenPGPDecodeErr() : Exception(INVALID_DATA_FORMAT, "OpenPGP decode error") {} 0288 }; 0289 0290 /// \brief Decode from OpenPGP format 0291 /// \param input big-endian byte array 0292 /// \param inputLen length of the byte array 0293 void OpenPGPDecode(const byte *input, size_t inputLen); 0294 /// \brief Decode from OpenPGP format 0295 /// \param bt BufferedTransformation object 0296 void OpenPGPDecode(BufferedTransformation &bt); 0297 //@} 0298 0299 /// \name ACCESSORS 0300 //@{ 0301 /// \brief Determines if the Integer is convertable to Long 0302 /// \return true if <tt>*this</tt> can be represented as a signed long 0303 /// \sa ConvertToLong() 0304 bool IsConvertableToLong() const; 0305 /// \brief Convert the Integer to Long 0306 /// \return equivalent signed long if possible, otherwise undefined 0307 /// \sa IsConvertableToLong() 0308 signed long ConvertToLong() const; 0309 0310 /// \brief Determines the number of bits required to represent the Integer 0311 /// \return number of significant bits 0312 /// \details BitCount is calculated as <tt>floor(log2(abs(*this))) + 1</tt>. 0313 unsigned int BitCount() const; 0314 /// \brief Determines the number of bytes required to represent the Integer 0315 /// \return number of significant bytes 0316 /// \details ByteCount is calculated as <tt>ceiling(BitCount()/8)</tt>. 0317 unsigned int ByteCount() const; 0318 /// \brief Determines the number of words required to represent the Integer 0319 /// \return number of significant words 0320 /// \details WordCount is calculated as <tt>ceiling(ByteCount()/sizeof(word))</tt>. 0321 unsigned int WordCount() const; 0322 0323 /// \brief Provides the i-th bit of the Integer 0324 /// \return the i-th bit, i=0 being the least significant bit 0325 bool GetBit(size_t i) const; 0326 /// \brief Provides the i-th byte of the Integer 0327 /// \return the i-th byte 0328 byte GetByte(size_t i) const; 0329 /// \brief Provides the low order bits of the Integer 0330 /// \return n lowest bits of <tt>*this >> i</tt> 0331 lword GetBits(size_t i, size_t n) const; 0332 0333 /// \brief Determines if the Integer is 0 0334 /// \return true if the Integer is 0, false otherwise 0335 bool IsZero() const {return !*this;} 0336 /// \brief Determines if the Integer is non-0 0337 /// \return true if the Integer is non-0, false otherwise 0338 bool NotZero() const {return !IsZero();} 0339 /// \brief Determines if the Integer is negative 0340 /// \return true if the Integer is negative, false otherwise 0341 bool IsNegative() const {return sign == NEGATIVE;} 0342 /// \brief Determines if the Integer is non-negative 0343 /// \return true if the Integer is non-negative, false otherwise 0344 bool NotNegative() const {return !IsNegative();} 0345 /// \brief Determines if the Integer is positive 0346 /// \return true if the Integer is positive, false otherwise 0347 bool IsPositive() const {return NotNegative() && NotZero();} 0348 /// \brief Determines if the Integer is non-positive 0349 /// \return true if the Integer is non-positive, false otherwise 0350 bool NotPositive() const {return !IsPositive();} 0351 /// \brief Determines if the Integer is even parity 0352 /// \return true if the Integer is even, false otherwise 0353 bool IsEven() const {return GetBit(0) == 0;} 0354 /// \brief Determines if the Integer is odd parity 0355 /// \return true if the Integer is odd, false otherwise 0356 bool IsOdd() const {return GetBit(0) == 1;} 0357 //@} 0358 0359 /// \name MANIPULATORS 0360 //@{ 0361 /// \brief Assignment 0362 /// \param t the other Integer 0363 /// \return the result of assignment 0364 Integer& operator=(const Integer& t); 0365 /// \brief Addition Assignment 0366 /// \param t the other Integer 0367 /// \return the result of <tt>*this + t</tt> 0368 Integer& operator+=(const Integer& t); 0369 /// \brief Subtraction Assignment 0370 /// \param t the other Integer 0371 /// \return the result of <tt>*this - t</tt> 0372 Integer& operator-=(const Integer& t); 0373 /// \brief Multiplication Assignment 0374 /// \param t the other Integer 0375 /// \return the result of <tt>*this * t</tt> 0376 /// \sa a_times_b_mod_c() and a_exp_b_mod_c() 0377 Integer& operator*=(const Integer& t) {return *this = Times(t);} 0378 /// \brief Division Assignment 0379 /// \param t the other Integer 0380 /// \return the result of <tt>*this / t</tt> 0381 Integer& operator/=(const Integer& t) {return *this = DividedBy(t);} 0382 /// \brief Remainder Assignment 0383 /// \param t the other Integer 0384 /// \return the result of <tt>*this % t</tt> 0385 /// \sa a_times_b_mod_c() and a_exp_b_mod_c() 0386 Integer& operator%=(const Integer& t) {return *this = Modulo(t);} 0387 /// \brief Division Assignment 0388 /// \param t the other word 0389 /// \return the result of <tt>*this / t</tt> 0390 Integer& operator/=(word t) {return *this = DividedBy(t);} 0391 /// \brief Remainder Assignment 0392 /// \param t the other word 0393 /// \return the result of <tt>*this % t</tt> 0394 /// \sa a_times_b_mod_c() and a_exp_b_mod_c() 0395 Integer& operator%=(word t) {return *this = Integer(POSITIVE, 0, Modulo(t));} 0396 0397 /// \brief Left-shift Assignment 0398 /// \param n number of bits to shift 0399 /// \return reference to this Integer 0400 Integer& operator<<=(size_t n); 0401 /// \brief Right-shift Assignment 0402 /// \param n number of bits to shift 0403 /// \return reference to this Integer 0404 Integer& operator>>=(size_t n); 0405 0406 /// \brief Bitwise AND Assignment 0407 /// \param t the other Integer 0408 /// \return the result of <tt>*this & t</tt> 0409 /// \details operator&=() performs a bitwise AND on <tt>*this</tt>. Missing bits are truncated 0410 /// at the most significant bit positions, so the result is as small as the 0411 /// smaller of the operands. 0412 /// \details Internally, Crypto++ uses a sign-magnitude representation. The library 0413 /// does not attempt to interpret bits, and the result is always POSITIVE. If needed, 0414 /// the integer should be converted to a 2's compliment representation before performing 0415 /// the operation. 0416 /// \since Crypto++ 6.0 0417 Integer& operator&=(const Integer& t); 0418 /// \brief Bitwise OR Assignment 0419 /// \param t the second Integer 0420 /// \return the result of <tt>*this | t</tt> 0421 /// \details operator|=() performs a bitwise OR on <tt>*this</tt>. Missing bits are shifted in 0422 /// at the most significant bit positions, so the result is as large as the 0423 /// larger of the operands. 0424 /// \details Internally, Crypto++ uses a sign-magnitude representation. The library 0425 /// does not attempt to interpret bits, and the result is always POSITIVE. If needed, 0426 /// the integer should be converted to a 2's compliment representation before performing 0427 /// the operation. 0428 /// \since Crypto++ 6.0 0429 Integer& operator|=(const Integer& t); 0430 /// \brief Bitwise XOR Assignment 0431 /// \param t the other Integer 0432 /// \return the result of <tt>*this ^ t</tt> 0433 /// \details operator^=() performs a bitwise XOR on <tt>*this</tt>. Missing bits are shifted 0434 /// in at the most significant bit positions, so the result is as large as the 0435 /// larger of the operands. 0436 /// \details Internally, Crypto++ uses a sign-magnitude representation. The library 0437 /// does not attempt to interpret bits, and the result is always POSITIVE. If needed, 0438 /// the integer should be converted to a 2's compliment representation before performing 0439 /// the operation. 0440 /// \since Crypto++ 6.0 0441 Integer& operator^=(const Integer& t); 0442 0443 /// \brief Set this Integer to random integer 0444 /// \param rng RandomNumberGenerator used to generate material 0445 /// \param bitCount the number of bits in the resulting integer 0446 /// \details The random integer created is uniformly distributed over <tt>[0, 2<sup>bitCount</sup>]</tt>. 0447 /// \note If \p bitCount is 0, then this Integer is set to 0 (and not 0 or 1). 0448 void Randomize(RandomNumberGenerator &rng, size_t bitCount); 0449 0450 /// \brief Set this Integer to random integer 0451 /// \param rng RandomNumberGenerator used to generate material 0452 /// \param min the minimum value 0453 /// \param max the maximum value 0454 /// \details The random integer created is uniformly distributed over <tt>[min, max]</tt>. 0455 void Randomize(RandomNumberGenerator &rng, const Integer &min, const Integer &max); 0456 0457 /// \brief Set this Integer to random integer of special form 0458 /// \param rng RandomNumberGenerator used to generate material 0459 /// \param min the minimum value 0460 /// \param max the maximum value 0461 /// \param rnType RandomNumberType to specify the type 0462 /// \param equiv the equivalence class based on the parameter \p mod 0463 /// \param mod the modulus used to reduce the equivalence class 0464 /// \throw RandomNumberNotFound if the set is empty. 0465 /// \details Ideally, the random integer created should be uniformly distributed 0466 /// over <tt>{x | min \<= x \<= max</tt> and \p x is of rnType and <tt>x \% mod == equiv}</tt>. 0467 /// However the actual distribution may not be uniform because sequential 0468 /// search is used to find an appropriate number from a random starting 0469 /// point. 0470 /// \details May return (with very small probability) a pseudoprime when a prime 0471 /// is requested and <tt>max \> lastSmallPrime*lastSmallPrime</tt>. \p lastSmallPrime 0472 /// is declared in nbtheory.h. 0473 bool Randomize(RandomNumberGenerator &rng, const Integer &min, const Integer &max, RandomNumberType rnType, const Integer &equiv=Zero(), const Integer &mod=One()); 0474 0475 /// \brief Generate a random number 0476 /// \param rng RandomNumberGenerator used to generate material 0477 /// \param params additional parameters that cannot be passed directly to the function 0478 /// \return true if a random number was generated, false otherwise 0479 /// \details GenerateRandomNoThrow attempts to generate a random number according to the 0480 /// parameters specified in params. The function does not throw RandomNumberNotFound. 0481 /// \details The example below generates a prime number using NameValuePairs that Integer 0482 /// class recognizes. The names are not provided in argnames.h. 0483 /// <pre> 0484 /// AutoSeededRandomPool prng; 0485 /// AlgorithmParameters params = MakeParameters("BitLength", 2048) 0486 /// ("RandomNumberType", Integer::PRIME); 0487 /// Integer x; 0488 /// if (x.GenerateRandomNoThrow(prng, params) == false) 0489 /// throw std::runtime_error("Failed to generate prime number"); 0490 /// </pre> 0491 bool GenerateRandomNoThrow(RandomNumberGenerator &rng, const NameValuePairs ¶ms = g_nullNameValuePairs); 0492 0493 /// \brief Generate a random number 0494 /// \param rng RandomNumberGenerator used to generate material 0495 /// \param params additional parameters that cannot be passed directly to the function 0496 /// \throw RandomNumberNotFound if a random number is not found 0497 /// \details GenerateRandom attempts to generate a random number according to the 0498 /// parameters specified in params. 0499 /// \details The example below generates a prime number using NameValuePairs that Integer 0500 /// class recognizes. The names are not provided in argnames.h. 0501 /// <pre> 0502 /// AutoSeededRandomPool prng; 0503 /// AlgorithmParameters params = MakeParameters("BitLength", 2048) 0504 /// ("RandomNumberType", Integer::PRIME); 0505 /// Integer x; 0506 /// try { x.GenerateRandom(prng, params); } 0507 /// catch (RandomNumberNotFound&) { x = -1; } 0508 /// </pre> 0509 void GenerateRandom(RandomNumberGenerator &rng, const NameValuePairs ¶ms = g_nullNameValuePairs) 0510 { 0511 if (!GenerateRandomNoThrow(rng, params)) 0512 throw RandomNumberNotFound(); 0513 } 0514 0515 /// \brief Set the n-th bit to value 0516 /// \details 0-based numbering. 0517 void SetBit(size_t n, bool value=1); 0518 0519 /// \brief Set the n-th byte to value 0520 /// \details 0-based numbering. 0521 void SetByte(size_t n, byte value); 0522 0523 /// \brief Reverse the Sign of the Integer 0524 void Negate(); 0525 0526 /// \brief Sets the Integer to positive 0527 void SetPositive() {sign = POSITIVE;} 0528 0529 /// \brief Sets the Integer to negative 0530 void SetNegative() {if (!!(*this)) sign = NEGATIVE;} 0531 0532 /// \brief Swaps this Integer with another Integer 0533 void swap(Integer &a); 0534 //@} 0535 0536 /// \name UNARY OPERATORS 0537 //@{ 0538 /// \brief Negation 0539 bool operator!() const; 0540 /// \brief Addition 0541 Integer operator+() const {return *this;} 0542 /// \brief Subtraction 0543 Integer operator-() const; 0544 /// \brief Pre-increment 0545 Integer& operator++(); 0546 /// \brief Pre-decrement 0547 Integer& operator--(); 0548 /// \brief Post-increment 0549 Integer operator++(int) {Integer temp = *this; ++*this; return temp;} 0550 /// \brief Post-decrement 0551 Integer operator--(int) {Integer temp = *this; --*this; return temp;} 0552 //@} 0553 0554 /// \name BINARY OPERATORS 0555 //@{ 0556 /// \brief Perform signed comparison 0557 /// \param a the Integer to compare 0558 /// \retval -1 if <tt>*this < a</tt> 0559 /// \retval 0 if <tt>*this = a</tt> 0560 /// \retval 1 if <tt>*this > a</tt> 0561 int Compare(const Integer& a) const; 0562 0563 /// \brief Addition 0564 Integer Plus(const Integer &b) const; 0565 /// \brief Subtraction 0566 Integer Minus(const Integer &b) const; 0567 /// \brief Multiplication 0568 /// \sa a_times_b_mod_c() and a_exp_b_mod_c() 0569 Integer Times(const Integer &b) const; 0570 /// \brief Division 0571 Integer DividedBy(const Integer &b) const; 0572 /// \brief Remainder 0573 /// \sa a_times_b_mod_c() and a_exp_b_mod_c() 0574 Integer Modulo(const Integer &b) const; 0575 /// \brief Division 0576 Integer DividedBy(word b) const; 0577 /// \brief Remainder 0578 /// \sa a_times_b_mod_c() and a_exp_b_mod_c() 0579 word Modulo(word b) const; 0580 0581 /// \brief Bitwise AND 0582 /// \param t the other Integer 0583 /// \return the result of <tt>*this & t</tt> 0584 /// \details And() performs a bitwise AND on the operands. Missing bits are truncated 0585 /// at the most significant bit positions, so the result is as small as the 0586 /// smaller of the operands. 0587 /// \details Internally, Crypto++ uses a sign-magnitude representation. The library 0588 /// does not attempt to interpret bits, and the result is always POSITIVE. If needed, 0589 /// the integer should be converted to a 2's compliment representation before performing 0590 /// the operation. 0591 /// \since Crypto++ 6.0 0592 Integer And(const Integer& t) const; 0593 0594 /// \brief Bitwise OR 0595 /// \param t the other Integer 0596 /// \return the result of <tt>*this | t</tt> 0597 /// \details Or() performs a bitwise OR on the operands. Missing bits are shifted in 0598 /// at the most significant bit positions, so the result is as large as the 0599 /// larger of the operands. 0600 /// \details Internally, Crypto++ uses a sign-magnitude representation. The library 0601 /// does not attempt to interpret bits, and the result is always POSITIVE. If needed, 0602 /// the integer should be converted to a 2's compliment representation before performing 0603 /// the operation. 0604 /// \since Crypto++ 6.0 0605 Integer Or(const Integer& t) const; 0606 0607 /// \brief Bitwise XOR 0608 /// \param t the other Integer 0609 /// \return the result of <tt>*this ^ t</tt> 0610 /// \details Xor() performs a bitwise XOR on the operands. Missing bits are shifted in 0611 /// at the most significant bit positions, so the result is as large as the 0612 /// larger of the operands. 0613 /// \details Internally, Crypto++ uses a sign-magnitude representation. The library 0614 /// does not attempt to interpret bits, and the result is always POSITIVE. If needed, 0615 /// the integer should be converted to a 2's compliment representation before performing 0616 /// the operation. 0617 /// \since Crypto++ 6.0 0618 Integer Xor(const Integer& t) const; 0619 0620 /// \brief Right-shift 0621 Integer operator>>(size_t n) const {return Integer(*this)>>=n;} 0622 /// \brief Left-shift 0623 Integer operator<<(size_t n) const {return Integer(*this)<<=n;} 0624 //@} 0625 0626 /// \name OTHER ARITHMETIC FUNCTIONS 0627 //@{ 0628 /// \brief Retrieve the absolute value of this integer 0629 Integer AbsoluteValue() const; 0630 /// \brief Add this integer to itself 0631 Integer Doubled() const {return Plus(*this);} 0632 /// \brief Multiply this integer by itself 0633 /// \sa a_times_b_mod_c() and a_exp_b_mod_c() 0634 Integer Squared() const {return Times(*this);} 0635 /// \brief Extract square root 0636 /// \details if negative return 0, else return floor of square root 0637 Integer SquareRoot() const; 0638 /// \brief Determine whether this integer is a perfect square 0639 bool IsSquare() const; 0640 0641 /// \brief Determine if 1 or -1 0642 /// \return true if this integer is 1 or -1, false otherwise 0643 bool IsUnit() const; 0644 /// \brief Calculate multiplicative inverse 0645 /// \return MultiplicativeInverse inverse if 1 or -1, otherwise return 0. 0646 Integer MultiplicativeInverse() const; 0647 0648 /// \brief Extended Division 0649 /// \param r a reference for the remainder 0650 /// \param q a reference for the quotient 0651 /// \param a reference to the dividend 0652 /// \param d reference to the divisor 0653 /// \details Divide calculates r and q such that (a == d*q + r) && (0 <= r < abs(d)). 0654 static void CRYPTOPP_API Divide(Integer &r, Integer &q, const Integer &a, const Integer &d); 0655 0656 /// \brief Extended Division 0657 /// \param r a reference for the remainder 0658 /// \param q a reference for the quotient 0659 /// \param a reference to the dividend 0660 /// \param d reference to the divisor 0661 /// \details Divide calculates r and q such that (a == d*q + r) && (0 <= r < abs(d)). 0662 /// This overload uses a faster division algorithm because the divisor is short. 0663 static void CRYPTOPP_API Divide(word &r, Integer &q, const Integer &a, word d); 0664 0665 /// \brief Extended Division 0666 /// \param r a reference for the remainder 0667 /// \param q a reference for the quotient 0668 /// \param a reference to the dividend 0669 /// \param n reference to the divisor 0670 /// \details DivideByPowerOf2 calculates r and q such that (a == d*q + r) && (0 <= r < abs(d)). 0671 /// It returns same result as Divide(r, q, a, Power2(n)), but faster. 0672 /// This overload uses a faster division algorithm because the divisor is a power of 2. 0673 static void CRYPTOPP_API DivideByPowerOf2(Integer &r, Integer &q, const Integer &a, unsigned int n); 0674 0675 /// \brief Calculate greatest common divisor 0676 /// \param a reference to the first number 0677 /// \param n reference to the secind number 0678 /// \return the greatest common divisor <tt>a</tt> and <tt>n</tt>. 0679 static Integer CRYPTOPP_API Gcd(const Integer &a, const Integer &n); 0680 0681 /// \brief Calculate multiplicative inverse 0682 /// \param n reference to the modulus 0683 /// \return an Integer <tt>*this % n</tt>. 0684 /// \details InverseMod returns the multiplicative inverse of the Integer <tt>*this</tt> 0685 /// modulo the Integer <tt>n</tt>. If no Integer exists then Integer 0 is returned. 0686 /// \sa a_times_b_mod_c() and a_exp_b_mod_c() 0687 Integer InverseMod(const Integer &n) const; 0688 0689 /// \brief Calculate multiplicative inverse 0690 /// \param n the modulus 0691 /// \return a word <tt>*this % n</tt>. 0692 /// \details InverseMod returns the multiplicative inverse of the Integer <tt>*this</tt> 0693 /// modulo the word <tt>n</tt>. If no Integer exists then word 0 is returned. 0694 /// \sa a_times_b_mod_c() and a_exp_b_mod_c() 0695 word InverseMod(word n) const; 0696 //@} 0697 0698 /// \name INPUT/OUTPUT 0699 //@{ 0700 /// \brief Extraction operator 0701 /// \param in reference to a std::istream 0702 /// \param a reference to an Integer 0703 /// \return reference to a std::istream reference 0704 friend CRYPTOPP_DLL std::istream& CRYPTOPP_API operator>>(std::istream& in, Integer &a); 0705 0706 /// \brief Insertion operator 0707 /// \param out reference to a std::ostream 0708 /// \param a a constant reference to an Integer 0709 /// \return reference to a std::ostream reference 0710 /// \details The output integer responds to hex, std::oct, std::hex, std::upper and 0711 /// std::lower. The output includes the suffix \a h (for hex), \a . (\a dot, for dec) 0712 /// and \a o (for octal). There is currently no way to suppress the suffix. 0713 /// \details If you want to print an Integer without the suffix or using an arbitrary base, then 0714 /// use IntToString<Integer>(). 0715 /// \sa IntToString<Integer> 0716 friend CRYPTOPP_DLL std::ostream& CRYPTOPP_API operator<<(std::ostream& out, const Integer &a); 0717 //@} 0718 0719 /// \brief Modular multiplication 0720 /// \param x reference to the first term 0721 /// \param y reference to the second term 0722 /// \param m reference to the modulus 0723 /// \return an Integer <tt>(a * b) % m</tt>. 0724 CRYPTOPP_DLL friend Integer CRYPTOPP_API a_times_b_mod_c(const Integer &x, const Integer& y, const Integer& m); 0725 /// \brief Modular exponentiation 0726 /// \param x reference to the base 0727 /// \param e reference to the exponent 0728 /// \param m reference to the modulus 0729 /// \return an Integer <tt>(a ^ b) % m</tt>. 0730 CRYPTOPP_DLL friend Integer CRYPTOPP_API a_exp_b_mod_c(const Integer &x, const Integer& e, const Integer& m); 0731 0732 protected: 0733 0734 // http://github.com/weidai11/cryptopp/issues/602 0735 Integer InverseModNext(const Integer &n) const; 0736 0737 private: 0738 0739 Integer(word value, size_t length); 0740 int PositiveCompare(const Integer &t) const; 0741 0742 IntegerSecBlock reg; 0743 Sign sign; 0744 0745 #ifndef CRYPTOPP_DOXYGEN_PROCESSING 0746 friend class ModularArithmetic; 0747 friend class MontgomeryRepresentation; 0748 friend class HalfMontgomeryRepresentation; 0749 0750 friend void PositiveAdd(Integer &sum, const Integer &a, const Integer &b); 0751 friend void PositiveSubtract(Integer &diff, const Integer &a, const Integer &b); 0752 friend void PositiveMultiply(Integer &product, const Integer &a, const Integer &b); 0753 friend void PositiveDivide(Integer &remainder, Integer "ient, const Integer ÷nd, const Integer &divisor); 0754 #endif 0755 }; 0756 0757 /// \brief Comparison 0758 inline bool operator==(const CryptoPP::Integer& a, const CryptoPP::Integer& b) {return a.Compare(b)==0;} 0759 /// \brief Comparison 0760 inline bool operator!=(const CryptoPP::Integer& a, const CryptoPP::Integer& b) {return a.Compare(b)!=0;} 0761 /// \brief Comparison 0762 inline bool operator> (const CryptoPP::Integer& a, const CryptoPP::Integer& b) {return a.Compare(b)> 0;} 0763 /// \brief Comparison 0764 inline bool operator>=(const CryptoPP::Integer& a, const CryptoPP::Integer& b) {return a.Compare(b)>=0;} 0765 /// \brief Comparison 0766 inline bool operator< (const CryptoPP::Integer& a, const CryptoPP::Integer& b) {return a.Compare(b)< 0;} 0767 /// \brief Comparison 0768 inline bool operator<=(const CryptoPP::Integer& a, const CryptoPP::Integer& b) {return a.Compare(b)<=0;} 0769 /// \brief Addition 0770 inline CryptoPP::Integer operator+(const CryptoPP::Integer &a, const CryptoPP::Integer &b) {return a.Plus(b);} 0771 /// \brief Subtraction 0772 inline CryptoPP::Integer operator-(const CryptoPP::Integer &a, const CryptoPP::Integer &b) {return a.Minus(b);} 0773 /// \brief Multiplication 0774 /// \sa a_times_b_mod_c() and a_exp_b_mod_c() 0775 inline CryptoPP::Integer operator*(const CryptoPP::Integer &a, const CryptoPP::Integer &b) {return a.Times(b);} 0776 /// \brief Division 0777 inline CryptoPP::Integer operator/(const CryptoPP::Integer &a, const CryptoPP::Integer &b) {return a.DividedBy(b);} 0778 /// \brief Remainder 0779 /// \sa a_times_b_mod_c() and a_exp_b_mod_c() 0780 inline CryptoPP::Integer operator%(const CryptoPP::Integer &a, const CryptoPP::Integer &b) {return a.Modulo(b);} 0781 /// \brief Division 0782 inline CryptoPP::Integer operator/(const CryptoPP::Integer &a, CryptoPP::word b) {return a.DividedBy(b);} 0783 /// \brief Remainder 0784 /// \sa a_times_b_mod_c() and a_exp_b_mod_c() 0785 inline CryptoPP::word operator%(const CryptoPP::Integer &a, CryptoPP::word b) {return a.Modulo(b);} 0786 0787 /// \brief Bitwise AND 0788 /// \param a the first Integer 0789 /// \param b the second Integer 0790 /// \return the result of a & b 0791 /// \details operator&() performs a bitwise AND on the operands. Missing bits are truncated 0792 /// at the most significant bit positions, so the result is as small as the 0793 /// smaller of the operands. 0794 /// \details Internally, Crypto++ uses a sign-magnitude representation. The library 0795 /// does not attempt to interpret bits, and the result is always POSITIVE. If needed, 0796 /// the integer should be converted to a 2's compliment representation before performing 0797 /// the operation. 0798 /// \since Crypto++ 6.0 0799 inline CryptoPP::Integer operator&(const CryptoPP::Integer &a, const CryptoPP::Integer &b) {return a.And(b);} 0800 0801 /// \brief Bitwise OR 0802 /// \param a the first Integer 0803 /// \param b the second Integer 0804 /// \return the result of a | b 0805 /// \details operator|() performs a bitwise OR on the operands. Missing bits are shifted in 0806 /// at the most significant bit positions, so the result is as large as the 0807 /// larger of the operands. 0808 /// \details Internally, Crypto++ uses a sign-magnitude representation. The library 0809 /// does not attempt to interpret bits, and the result is always POSITIVE. If needed, 0810 /// the integer should be converted to a 2's compliment representation before performing 0811 /// the operation. 0812 /// \since Crypto++ 6.0 0813 inline CryptoPP::Integer operator|(const CryptoPP::Integer &a, const CryptoPP::Integer &b) {return a.Or(b);} 0814 0815 /// \brief Bitwise XOR 0816 /// \param a the first Integer 0817 /// \param b the second Integer 0818 /// \return the result of a ^ b 0819 /// \details operator^() performs a bitwise XOR on the operands. Missing bits are shifted 0820 /// in at the most significant bit positions, so the result is as large as the 0821 /// larger of the operands. 0822 /// \details Internally, Crypto++ uses a sign-magnitude representation. The library 0823 /// does not attempt to interpret bits, and the result is always POSITIVE. If needed, 0824 /// the integer should be converted to a 2's compliment representation before performing 0825 /// the operation. 0826 /// \since Crypto++ 6.0 0827 inline CryptoPP::Integer operator^(const CryptoPP::Integer &a, const CryptoPP::Integer &b) {return a.Xor(b);} 0828 0829 NAMESPACE_END 0830 0831 #ifndef __BORLANDC__ 0832 NAMESPACE_BEGIN(std) 0833 inline void swap(CryptoPP::Integer &a, CryptoPP::Integer &b) 0834 { 0835 a.swap(b); 0836 } 0837 NAMESPACE_END 0838 #endif 0839 0840 #endif
| [ Source navigation ] | [ Diff markup ] | [ Identifier search ] | [ general search ] |
|
This page was automatically generated by the 2.3.7 LXR engine. The LXR team |
|