Crypto++  8.2
Free C++ class library of cryptographic schemes
integer.h
Go to the documentation of this file.
1 // integer.h - originally written and placed in the public domain by Wei Dai
2 
3 /// \file integer.h
4 /// \brief Multiple precision integer with arithmetic operations
5 /// \details The Integer class can represent positive and negative integers
6 /// with absolute value less than (256**sizeof(word))<sup>(256**sizeof(int))</sup>.
7 /// \details Internally, the library uses a sign magnitude representation, and the class
8 /// has two data members. The first is a IntegerSecBlock (a SecBlock<word>) and it is
9 /// used to hold the representation. The second is a Sign (an enumeration), and it is
10 /// used to track the sign of the Integer.
11 /// \details For details on how the Integer class initializes its function pointers using
12 /// InitializeInteger and how it creates Integer::Zero(), Integer::One(), and
13 /// Integer::Two(), then see the comments at the top of <tt>integer.cpp</tt>.
14 /// \since Crypto++ 1.0
15 
16 #ifndef CRYPTOPP_INTEGER_H
17 #define CRYPTOPP_INTEGER_H
18 
19 #include "cryptlib.h"
20 #include "secblock.h"
21 #include "stdcpp.h"
22 
23 #include <iosfwd>
24 
25 NAMESPACE_BEGIN(CryptoPP)
26 
27 /// \struct InitializeInteger
28 /// \brief Performs static initialization of the Integer class
30 {
32 };
33 
34 // Always align, http://github.com/weidai11/cryptopp/issues/256
36 
37 /// \brief Multiple precision integer with arithmetic operations
38 /// \details The Integer class can represent positive and negative integers
39 /// with absolute value less than (256**sizeof(word))<sup>(256**sizeof(int))</sup>.
40 /// \details Internally, the library uses a sign magnitude representation, and the class
41 /// has two data members. The first is a IntegerSecBlock (a SecBlock<word>) and it is
42 /// used to hold the representation. The second is a Sign (an enumeration), and it is
43 /// used to track the sign of the Integer.
44 /// \details For details on how the Integer class initializes its function pointers using
45 /// InitializeInteger and how it creates Integer::Zero(), Integer::One(), and
46 /// Integer::Two(), then see the comments at the top of <tt>integer.cpp</tt>.
47 /// \since Crypto++ 1.0
48 /// \nosubgrouping
49 class CRYPTOPP_DLL Integer : private InitializeInteger, public ASN1Object
50 {
51 public:
52  /// \name ENUMS, EXCEPTIONS, and TYPEDEFS
53  //@{
54  /// \brief Exception thrown when division by 0 is encountered
55  class DivideByZero : public Exception
56  {
57  public:
58  DivideByZero() : Exception(OTHER_ERROR, "Integer: division by zero") {}
59  };
60 
61  /// \brief Exception thrown when a random number cannot be found that
62  /// satisfies the condition
64  {
65  public:
66  RandomNumberNotFound() : Exception(OTHER_ERROR, "Integer: no integer satisfies the given parameters") {}
67  };
68 
69  /// \enum Sign
70  /// \brief Used internally to represent the integer
71  /// \details Sign is used internally to represent the integer. It is also used in a few API functions.
72  /// \sa SetPositive(), SetNegative(), Signedness
73  enum Sign {
74  /// \brief the value is positive or 0
75  POSITIVE=0,
76  /// \brief the value is negative
77  NEGATIVE=1};
78 
79  /// \enum Signedness
80  /// \brief Used when importing and exporting integers
81  /// \details Signedness is usually used in API functions.
82  /// \sa Sign
83  enum Signedness {
84  /// \brief an unsigned value
86  /// \brief a signed value
87  SIGNED};
88 
89  /// \enum RandomNumberType
90  /// \brief Properties of a random integer
92  /// \brief a number with no special properties
93  ANY,
94  /// \brief a number which is probabilistically prime
95  PRIME};
96  //@}
97 
98  /// \name CREATORS
99  //@{
100  /// \brief Creates the zero integer
101  Integer();
102 
103  /// copy constructor
104  Integer(const Integer& t);
105 
106  /// \brief Convert from signed long
107  Integer(signed long value);
108 
109  /// \brief Convert from lword
110  /// \param sign enumeration indicating Sign
111  /// \param value the long word
112  Integer(Sign sign, lword value);
113 
114  /// \brief Convert from two words
115  /// \param sign enumeration indicating Sign
116  /// \param highWord the high word
117  /// \param lowWord the low word
118  Integer(Sign sign, word highWord, word lowWord);
119 
120  /// \brief Convert from a C-string
121  /// \param str C-string value
122  /// \param order the ByteOrder of the string to be processed
123  /// \details \p str can be in base 2, 8, 10, or 16. Base is determined by a case
124  /// insensitive suffix of 'h', 'o', or 'b'. No suffix means base 10.
125  /// \details Byte order was added at Crypto++ 5.7 to allow use of little-endian
126  /// integers with curve25519, Poly1305 and Microsoft CAPI.
127  explicit Integer(const char *str, ByteOrder order = BIG_ENDIAN_ORDER);
128 
129  /// \brief Convert from a wide C-string
130  /// \param str wide C-string value
131  /// \param order the ByteOrder of the string to be processed
132  /// \details \p str can be in base 2, 8, 10, or 16. Base is determined by a case
133  /// insensitive suffix of 'h', 'o', or 'b'. No suffix means base 10.
134  /// \details Byte order was added at Crypto++ 5.7 to allow use of little-endian
135  /// integers with curve25519, Poly1305 and Microsoft CAPI.
136  explicit Integer(const wchar_t *str, ByteOrder order = BIG_ENDIAN_ORDER);
137 
138  /// \brief Convert from a big-endian byte array
139  /// \param encodedInteger big-endian byte array
140  /// \param byteCount length of the byte array
141  /// \param sign enumeration indicating Signedness
142  /// \param order the ByteOrder of the array to be processed
143  /// \details Byte order was added at Crypto++ 5.7 to allow use of little-endian
144  /// integers with curve25519, Poly1305 and Microsoft CAPI.
145  Integer(const byte *encodedInteger, size_t byteCount, Signedness sign=UNSIGNED, ByteOrder order = BIG_ENDIAN_ORDER);
146 
147  /// \brief Convert from a big-endian array
148  /// \param bt BufferedTransformation object with big-endian byte array
149  /// \param byteCount length of the byte array
150  /// \param sign enumeration indicating Signedness
151  /// \param order the ByteOrder of the data to be processed
152  /// \details Byte order was added at Crypto++ 5.7 to allow use of little-endian
153  /// integers with curve25519, Poly1305 and Microsoft CAPI.
154  Integer(BufferedTransformation &bt, size_t byteCount, Signedness sign=UNSIGNED, ByteOrder order = BIG_ENDIAN_ORDER);
155 
156  /// \brief Convert from a BER encoded byte array
157  /// \param bt BufferedTransformation object with BER encoded byte array
158  explicit Integer(BufferedTransformation &bt);
159 
160  /// \brief Create a random integer
161  /// \param rng RandomNumberGenerator used to generate material
162  /// \param bitCount the number of bits in the resulting integer
163  /// \details The random integer created is uniformly distributed over <tt>[0, 2<sup>bitCount</sup>]</tt>.
164  Integer(RandomNumberGenerator &rng, size_t bitCount);
165 
166  /// \brief Integer representing 0
167  /// \returns an Integer representing 0
168  /// \details Zero() avoids calling constructors for frequently used integers
169  static const Integer & CRYPTOPP_API Zero();
170  /// \brief Integer representing 1
171  /// \returns an Integer representing 1
172  /// \details One() avoids calling constructors for frequently used integers
173  static const Integer & CRYPTOPP_API One();
174  /// \brief Integer representing 2
175  /// \returns an Integer representing 2
176  /// \details Two() avoids calling constructors for frequently used integers
177  static const Integer & CRYPTOPP_API Two();
178 
179  /// \brief Create a random integer of special form
180  /// \param rng RandomNumberGenerator used to generate material
181  /// \param min the minimum value
182  /// \param max the maximum value
183  /// \param rnType RandomNumberType to specify the type
184  /// \param equiv the equivalence class based on the parameter \p mod
185  /// \param mod the modulus used to reduce the equivalence class
186  /// \throw RandomNumberNotFound if the set is empty.
187  /// \details Ideally, the random integer created should be uniformly distributed
188  /// over <tt>{x | min <= x <= max</tt> and \p x is of rnType and <tt>x \% mod == equiv}</tt>.
189  /// However the actual distribution may not be uniform because sequential
190  /// search is used to find an appropriate number from a random starting
191  /// point.
192  /// \details May return (with very small probability) a pseudoprime when a prime
193  /// is requested and <tt>max > lastSmallPrime*lastSmallPrime</tt>. \p lastSmallPrime
194  /// is declared in nbtheory.h.
195  Integer(RandomNumberGenerator &rng, const Integer &min, const Integer &max, RandomNumberType rnType=ANY, const Integer &equiv=Zero(), const Integer &mod=One());
196 
197  /// \brief Exponentiates to a power of 2
198  /// \returns the Integer 2<sup>e</sup>
199  /// \sa a_times_b_mod_c() and a_exp_b_mod_c()
200  static Integer CRYPTOPP_API Power2(size_t e);
201  //@}
202 
203  /// \name ENCODE/DECODE
204  //@{
205  /// \brief Minimum number of bytes to encode this integer
206  /// \param sign enumeration indicating Signedness
207  /// \note The MinEncodedSize() of 0 is 1.
208  size_t MinEncodedSize(Signedness sign=UNSIGNED) const;
209 
210  /// \brief Encode in big-endian format
211  /// \param output big-endian byte array
212  /// \param outputLen length of the byte array
213  /// \param sign enumeration indicating Signedness
214  /// \details Unsigned means encode absolute value, signed means encode two's complement if negative.
215  /// \details outputLen can be used to ensure an Integer is encoded to an exact size (rather than a
216  /// minimum size). An exact size is useful, for example, when encoding to a field element size.
217  void Encode(byte *output, size_t outputLen, Signedness sign=UNSIGNED) const;
218 
219  /// \brief Encode in big-endian format
220  /// \param bt BufferedTransformation object
221  /// \param outputLen length of the encoding
222  /// \param sign enumeration indicating Signedness
223  /// \details Unsigned means encode absolute value, signed means encode two's complement if negative.
224  /// \details outputLen can be used to ensure an Integer is encoded to an exact size (rather than a
225  /// minimum size). An exact size is useful, for example, when encoding to a field element size.
226  void Encode(BufferedTransformation &bt, size_t outputLen, Signedness sign=UNSIGNED) const;
227 
228  /// \brief Encode in DER format
229  /// \param bt BufferedTransformation object
230  /// \details Encodes the Integer using Distinguished Encoding Rules
231  /// The result is placed into a BufferedTransformation object
232  void DEREncode(BufferedTransformation &bt) const;
233 
234  /// \brief Encode absolute value as big-endian octet string
235  /// \param bt BufferedTransformation object
236  /// \param length the number of mytes to decode
237  void DEREncodeAsOctetString(BufferedTransformation &bt, size_t length) const;
238 
239  /// \brief Encode absolute value in OpenPGP format
240  /// \param output big-endian byte array
241  /// \param bufferSize length of the byte array
242  /// \returns length of the output
243  /// \details OpenPGPEncode places result into the buffer and returns the
244  /// number of bytes used for the encoding
245  size_t OpenPGPEncode(byte *output, size_t bufferSize) const;
246 
247  /// \brief Encode absolute value in OpenPGP format
248  /// \param bt BufferedTransformation object
249  /// \returns length of the output
250  /// \details OpenPGPEncode places result into a BufferedTransformation object and returns the
251  /// number of bytes used for the encoding
252  size_t OpenPGPEncode(BufferedTransformation &bt) const;
253 
254  /// \brief Decode from big-endian byte array
255  /// \param input big-endian byte array
256  /// \param inputLen length of the byte array
257  /// \param sign enumeration indicating Signedness
258  void Decode(const byte *input, size_t inputLen, Signedness sign=UNSIGNED);
259 
260  /// \brief Decode nonnegative value from big-endian byte array
261  /// \param bt BufferedTransformation object
262  /// \param inputLen length of the byte array
263  /// \param sign enumeration indicating Signedness
264  /// \note <tt>bt.MaxRetrievable() >= inputLen</tt>.
265  void Decode(BufferedTransformation &bt, size_t inputLen, Signedness sign=UNSIGNED);
266 
267  /// \brief Decode from BER format
268  /// \param input big-endian byte array
269  /// \param inputLen length of the byte array
270  void BERDecode(const byte *input, size_t inputLen);
271 
272  /// \brief Decode from BER format
273  /// \param bt BufferedTransformation object
275 
276  /// \brief Decode nonnegative value from big-endian octet string
277  /// \param bt BufferedTransformation object
278  /// \param length length of the byte array
279  void BERDecodeAsOctetString(BufferedTransformation &bt, size_t length);
280 
281  /// \brief Exception thrown when an error is encountered decoding an OpenPGP integer
283  {
284  public:
285  OpenPGPDecodeErr() : Exception(INVALID_DATA_FORMAT, "OpenPGP decode error") {}
286  };
287 
288  /// \brief Decode from OpenPGP format
289  /// \param input big-endian byte array
290  /// \param inputLen length of the byte array
291  void OpenPGPDecode(const byte *input, size_t inputLen);
292  /// \brief Decode from OpenPGP format
293  /// \param bt BufferedTransformation object
294  void OpenPGPDecode(BufferedTransformation &bt);
295  //@}
296 
297  /// \name ACCESSORS
298  //@{
299  /// \brief Determines if the Integer is convertable to Long
300  /// \returns true if *this can be represented as a signed long
301  /// \sa ConvertToLong()
302  bool IsConvertableToLong() const;
303  /// \brief Convert the Integer to Long
304  /// \return equivalent signed long if possible, otherwise undefined
305  /// \sa IsConvertableToLong()
306  signed long ConvertToLong() const;
307 
308  /// \brief Determines the number of bits required to represent the Integer
309  /// \returns number of significant bits
310  /// \details BitCount is calculated as <tt>floor(log2(abs(*this))) + 1</tt>.
311  unsigned int BitCount() const;
312  /// \brief Determines the number of bytes required to represent the Integer
313  /// \returns number of significant bytes
314  /// \details ByteCount is calculated as <tt>ceiling(BitCount()/8)</tt>.
315  unsigned int ByteCount() const;
316  /// \brief Determines the number of words required to represent the Integer
317  /// \returns number of significant words
318  /// \details WordCount is calculated as <tt>ceiling(ByteCount()/sizeof(word))</tt>.
319  unsigned int WordCount() const;
320 
321  /// \brief Provides the i-th bit of the Integer
322  /// \returns the i-th bit, i=0 being the least significant bit
323  bool GetBit(size_t i) const;
324  /// \brief Provides the i-th byte of the Integer
325  /// \returns the i-th byte
326  byte GetByte(size_t i) const;
327  /// \brief Provides the low order bits of the Integer
328  /// \returns n lowest bits of *this >> i
329  lword GetBits(size_t i, size_t n) const;
330 
331  /// \brief Determines if the Integer is 0
332  /// \returns true if the Integer is 0, false otherwise
333  bool IsZero() const {return !*this;}
334  /// \brief Determines if the Integer is non-0
335  /// \returns true if the Integer is non-0, false otherwise
336  bool NotZero() const {return !IsZero();}
337  /// \brief Determines if the Integer is negative
338  /// \returns true if the Integer is negative, false otherwise
339  bool IsNegative() const {return sign == NEGATIVE;}
340  /// \brief Determines if the Integer is non-negative
341  /// \returns true if the Integer is non-negative, false otherwise
342  bool NotNegative() const {return !IsNegative();}
343  /// \brief Determines if the Integer is positive
344  /// \returns true if the Integer is positive, false otherwise
345  bool IsPositive() const {return NotNegative() && NotZero();}
346  /// \brief Determines if the Integer is non-positive
347  /// \returns true if the Integer is non-positive, false otherwise
348  bool NotPositive() const {return !IsPositive();}
349  /// \brief Determines if the Integer is even parity
350  /// \returns true if the Integer is even, false otherwise
351  bool IsEven() const {return GetBit(0) == 0;}
352  /// \brief Determines if the Integer is odd parity
353  /// \returns true if the Integer is odd, false otherwise
354  bool IsOdd() const {return GetBit(0) == 1;}
355  //@}
356 
357  /// \name MANIPULATORS
358  //@{
359  /// \brief Assignment
360  /// \param t the other Integer
361  /// \returns the result of assignment
362  Integer& operator=(const Integer& t);
363  /// \brief Addition Assignment
364  /// \param t the other Integer
365  /// \returns the result of <tt>*this + t</tt>
366  Integer& operator+=(const Integer& t);
367  /// \brief Subtraction Assignment
368  /// \param t the other Integer
369  /// \returns the result of <tt>*this - t</tt>
370  Integer& operator-=(const Integer& t);
371  /// \brief Multiplication Assignment
372  /// \param t the other Integer
373  /// \returns the result of <tt>*this * t</tt>
374  /// \sa a_times_b_mod_c() and a_exp_b_mod_c()
375  Integer& operator*=(const Integer& t) {return *this = Times(t);}
376  /// \brief Division Assignment
377  /// \param t the other Integer
378  /// \returns the result of <tt>*this / t</tt>
379  Integer& operator/=(const Integer& t) {return *this = DividedBy(t);}
380  /// \brief Remainder Assignment
381  /// \param t the other Integer
382  /// \returns the result of <tt>*this % t</tt>
383  /// \sa a_times_b_mod_c() and a_exp_b_mod_c()
384  Integer& operator%=(const Integer& t) {return *this = Modulo(t);}
385  /// \brief Division Assignment
386  /// \param t the other word
387  /// \returns the result of <tt>*this / t</tt>
388  Integer& operator/=(word t) {return *this = DividedBy(t);}
389  /// \brief Remainder Assignment
390  /// \param t the other word
391  /// \returns the result of <tt>*this % t</tt>
392  /// \sa a_times_b_mod_c() and a_exp_b_mod_c()
393  Integer& operator%=(word t) {return *this = Integer(POSITIVE, 0, Modulo(t));}
394 
395  /// \brief Left-shift Assignment
396  /// \param n number of bits to shift
397  /// \returns reference to this Integer
398  Integer& operator<<=(size_t n);
399  /// \brief Right-shift Assignment
400  /// \param n number of bits to shift
401  /// \returns reference to this Integer
402  Integer& operator>>=(size_t n);
403 
404  /// \brief Bitwise AND Assignment
405  /// \param t the other Integer
406  /// \returns the result of *this & t
407  /// \details operator&=() performs a bitwise AND on *this. Missing bits are truncated
408  /// at the most significant bit positions, so the result is as small as the
409  /// smaller of the operands.
410  /// \details Internally, Crypto++ uses a sign-magnitude representation. The library
411  /// does not attempt to interpret bits, and the result is always POSITIVE. If needed,
412  /// the integer should be converted to a 2's compliment representation before performing
413  /// the operation.
414  /// \since Crypto++ 6.0
415  Integer& operator&=(const Integer& t);
416  /// \brief Bitwise OR Assignment
417  /// \param t the second Integer
418  /// \returns the result of *this | t
419  /// \details operator|=() performs a bitwise OR on *this. Missing bits are shifted in
420  /// at the most significant bit positions, so the result is as large as the
421  /// larger of the operands.
422  /// \details Internally, Crypto++ uses a sign-magnitude representation. The library
423  /// does not attempt to interpret bits, and the result is always POSITIVE. If needed,
424  /// the integer should be converted to a 2's compliment representation before performing
425  /// the operation.
426  /// \since Crypto++ 6.0
427  Integer& operator|=(const Integer& t);
428  /// \brief Bitwise XOR Assignment
429  /// \param t the other Integer
430  /// \returns the result of *this ^ t
431  /// \details operator^=() performs a bitwise XOR on *this. Missing bits are shifted
432  /// in at the most significant bit positions, so the result is as large as the
433  /// larger of the operands.
434  /// \details Internally, Crypto++ uses a sign-magnitude representation. The library
435  /// does not attempt to interpret bits, and the result is always POSITIVE. If needed,
436  /// the integer should be converted to a 2's compliment representation before performing
437  /// the operation.
438  /// \since Crypto++ 6.0
439  Integer& operator^=(const Integer& t);
440 
441  /// \brief Set this Integer to random integer
442  /// \param rng RandomNumberGenerator used to generate material
443  /// \param bitCount the number of bits in the resulting integer
444  /// \details The random integer created is uniformly distributed over <tt>[0, 2<sup>bitCount</sup>]</tt>.
445  void Randomize(RandomNumberGenerator &rng, size_t bitCount);
446 
447  /// \brief Set this Integer to random integer
448  /// \param rng RandomNumberGenerator used to generate material
449  /// \param min the minimum value
450  /// \param max the maximum value
451  /// \details The random integer created is uniformly distributed over <tt>[min, max]</tt>.
452  void Randomize(RandomNumberGenerator &rng, const Integer &min, const Integer &max);
453 
454  /// \brief Set this Integer to random integer of special form
455  /// \param rng RandomNumberGenerator used to generate material
456  /// \param min the minimum value
457  /// \param max the maximum value
458  /// \param rnType RandomNumberType to specify the type
459  /// \param equiv the equivalence class based on the parameter \p mod
460  /// \param mod the modulus used to reduce the equivalence class
461  /// \throw RandomNumberNotFound if the set is empty.
462  /// \details Ideally, the random integer created should be uniformly distributed
463  /// over <tt>{x | min <= x <= max</tt> and \p x is of rnType and <tt>x \% mod == equiv}</tt>.
464  /// However the actual distribution may not be uniform because sequential
465  /// search is used to find an appropriate number from a random starting
466  /// point.
467  /// \details May return (with very small probability) a pseudoprime when a prime
468  /// is requested and <tt>max > lastSmallPrime*lastSmallPrime</tt>. \p lastSmallPrime
469  /// is declared in nbtheory.h.
470  bool Randomize(RandomNumberGenerator &rng, const Integer &min, const Integer &max, RandomNumberType rnType, const Integer &equiv=Zero(), const Integer &mod=One());
471 
472  /// \brief Generate a random number
473  /// \param rng RandomNumberGenerator used to generate material
474  /// \param params additional parameters that cannot be passed directly to the function
475  /// \returns true if a random number was generated, false otherwise
476  /// \details GenerateRandomNoThrow attempts to generate a random number according to the
477  /// parameters specified in params. The function does not throw RandomNumberNotFound.
478  /// \details The example below generates a prime number using NameValuePairs that Integer
479  /// class recognizes. The names are not provided in argnames.h.
480  /// <pre>
481  /// AutoSeededRandomPool prng;
482  /// AlgorithmParameters params = MakeParameters("BitLength", 2048)
483  /// ("RandomNumberType", Integer::PRIME);
484  /// Integer x;
485  /// if (x.GenerateRandomNoThrow(prng, params) == false)
486  /// throw std::runtime_error("Failed to generate prime number");
487  /// </pre>
488  bool GenerateRandomNoThrow(RandomNumberGenerator &rng, const NameValuePairs &params = g_nullNameValuePairs);
489 
490  /// \brief Generate a random number
491  /// \param rng RandomNumberGenerator used to generate material
492  /// \param params additional parameters that cannot be passed directly to the function
493  /// \throw RandomNumberNotFound if a random number is not found
494  /// \details GenerateRandom attempts to generate a random number according to the
495  /// parameters specified in params.
496  /// \details The example below generates a prime number using NameValuePairs that Integer
497  /// class recognizes. The names are not provided in argnames.h.
498  /// <pre>
499  /// AutoSeededRandomPool prng;
500  /// AlgorithmParameters params = MakeParameters("BitLength", 2048)
501  /// ("RandomNumberType", Integer::PRIME);
502  /// Integer x;
503  /// try { x.GenerateRandom(prng, params); }
504  /// catch (RandomNumberNotFound&) { x = -1; }
505  /// </pre>
507  {
508  if (!GenerateRandomNoThrow(rng, params))
509  throw RandomNumberNotFound();
510  }
511 
512  /// \brief Set the n-th bit to value
513  /// \details 0-based numbering.
514  void SetBit(size_t n, bool value=1);
515 
516  /// \brief Set the n-th byte to value
517  /// \details 0-based numbering.
518  void SetByte(size_t n, byte value);
519 
520  /// \brief Reverse the Sign of the Integer
521  void Negate();
522 
523  /// \brief Sets the Integer to positive
524  void SetPositive() {sign = POSITIVE;}
525 
526  /// \brief Sets the Integer to negative
527  void SetNegative() {if (!!(*this)) sign = NEGATIVE;}
528 
529  /// \brief Swaps this Integer with another Integer
530  void swap(Integer &a);
531  //@}
532 
533  /// \name UNARY OPERATORS
534  //@{
535  /// \brief Negation
536  bool operator!() const;
537  /// \brief Addition
538  Integer operator+() const {return *this;}
539  /// \brief Subtraction
540  Integer operator-() const;
541  /// \brief Pre-increment
542  Integer& operator++();
543  /// \brief Pre-decrement
544  Integer& operator--();
545  /// \brief Post-increment
546  Integer operator++(int) {Integer temp = *this; ++*this; return temp;}
547  /// \brief Post-decrement
548  Integer operator--(int) {Integer temp = *this; --*this; return temp;}
549  //@}
550 
551  /// \name BINARY OPERATORS
552  //@{
553  /// \brief Perform signed comparison
554  /// \param a the Integer to comapre
555  /// \retval -1 if <tt>*this < a</tt>
556  /// \retval 0 if <tt>*this = a</tt>
557  /// \retval 1 if <tt>*this > a</tt>
558  int Compare(const Integer& a) const;
559 
560  /// \brief Addition
561  Integer Plus(const Integer &b) const;
562  /// \brief Subtraction
563  Integer Minus(const Integer &b) const;
564  /// \brief Multiplication
565  /// \sa a_times_b_mod_c() and a_exp_b_mod_c()
566  Integer Times(const Integer &b) const;
567  /// \brief Division
568  Integer DividedBy(const Integer &b) const;
569  /// \brief Remainder
570  /// \sa a_times_b_mod_c() and a_exp_b_mod_c()
571  Integer Modulo(const Integer &b) const;
572  /// \brief Division
573  Integer DividedBy(word b) const;
574  /// \brief Remainder
575  /// \sa a_times_b_mod_c() and a_exp_b_mod_c()
576  word Modulo(word b) const;
577 
578  /// \brief Bitwise AND
579  /// \param t the other Integer
580  /// \returns the result of <tt>*this & t</tt>
581  /// \details And() performs a bitwise AND on the operands. Missing bits are truncated
582  /// at the most significant bit positions, so the result is as small as the
583  /// smaller of the operands.
584  /// \details Internally, Crypto++ uses a sign-magnitude representation. The library
585  /// does not attempt to interpret bits, and the result is always POSITIVE. If needed,
586  /// the integer should be converted to a 2's compliment representation before performing
587  /// the operation.
588  /// \since Crypto++ 6.0
589  Integer And(const Integer& t) const;
590 
591  /// \brief Bitwise OR
592  /// \param t the other Integer
593  /// \returns the result of <tt>*this | t</tt>
594  /// \details Or() performs a bitwise OR on the operands. Missing bits are shifted in
595  /// at the most significant bit positions, so the result is as large as the
596  /// larger of the operands.
597  /// \details Internally, Crypto++ uses a sign-magnitude representation. The library
598  /// does not attempt to interpret bits, and the result is always POSITIVE. If needed,
599  /// the integer should be converted to a 2's compliment representation before performing
600  /// the operation.
601  /// \since Crypto++ 6.0
602  Integer Or(const Integer& t) const;
603 
604  /// \brief Bitwise XOR
605  /// \param t the other Integer
606  /// \returns the result of <tt>*this ^ t</tt>
607  /// \details Xor() performs a bitwise XOR on the operands. Missing bits are shifted in
608  /// at the most significant bit positions, so the result is as large as the
609  /// larger of the operands.
610  /// \details Internally, Crypto++ uses a sign-magnitude representation. The library
611  /// does not attempt to interpret bits, and the result is always POSITIVE. If needed,
612  /// the integer should be converted to a 2's compliment representation before performing
613  /// the operation.
614  /// \since Crypto++ 6.0
615  Integer Xor(const Integer& t) const;
616 
617  /// \brief Right-shift
618  Integer operator>>(size_t n) const {return Integer(*this)>>=n;}
619  /// \brief Left-shift
620  Integer operator<<(size_t n) const {return Integer(*this)<<=n;}
621  //@}
622 
623  /// \name OTHER ARITHMETIC FUNCTIONS
624  //@{
625  /// \brief Retrieve the absolute value of this integer
626  Integer AbsoluteValue() const;
627  /// \brief Add this integer to itself
628  Integer Doubled() const {return Plus(*this);}
629  /// \brief Multiply this integer by itself
630  /// \sa a_times_b_mod_c() and a_exp_b_mod_c()
631  Integer Squared() const {return Times(*this);}
632  /// \brief Extract square root
633  /// \details if negative return 0, else return floor of square root
634  Integer SquareRoot() const;
635  /// \brief Determine whether this integer is a perfect square
636  bool IsSquare() const;
637 
638  /// \brief Determine if 1 or -1
639  /// \returns true if this integer is 1 or -1, false otherwise
640  bool IsUnit() const;
641  /// \brief Calculate multiplicative inverse
642  /// \returns MultiplicativeInverse inverse if 1 or -1, otherwise return 0.
643  Integer MultiplicativeInverse() const;
644 
645  /// \brief Extended Division
646  /// \param r a reference for the remainder
647  /// \param q a reference for the quotient
648  /// \param a a reference to the dividend
649  /// \param d a reference to the divisor
650  /// \details Divide calculates r and q such that (a == d*q + r) && (0 <= r < abs(d)).
651  static void CRYPTOPP_API Divide(Integer &r, Integer &q, const Integer &a, const Integer &d);
652 
653  /// \brief Extended Division
654  /// \param r a reference for the remainder
655  /// \param q a reference for the quotient
656  /// \param a a reference to the dividend
657  /// \param d a reference to the divisor
658  /// \details Divide calculates r and q such that (a == d*q + r) && (0 <= r < abs(d)).
659  /// This overload uses a faster division algorithm because the divisor is short.
660  static void CRYPTOPP_API Divide(word &r, Integer &q, const Integer &a, word d);
661 
662  /// \brief Extended Division
663  /// \param r a reference for the remainder
664  /// \param q a reference for the quotient
665  /// \param a a reference to the dividend
666  /// \param n a reference to the divisor
667  /// \details DivideByPowerOf2 calculates r and q such that (a == d*q + r) && (0 <= r < abs(d)).
668  /// It returns same result as Divide(r, q, a, Power2(n)), but faster.
669  /// This overload uses a faster division algorithm because the divisor is a power of 2.
670  static void CRYPTOPP_API DivideByPowerOf2(Integer &r, Integer &q, const Integer &a, unsigned int n);
671 
672  /// \brief Calculate greatest common divisor
673  /// \param a a reference to the first number
674  /// \param n a reference to the secind number
675  /// \returns the greatest common divisor <tt>a</tt> and <tt>n</tt>.
676  static Integer CRYPTOPP_API Gcd(const Integer &a, const Integer &n);
677 
678  /// \brief Calculate multiplicative inverse
679  /// \param n a reference to the modulus
680  /// \returns an Integer <tt>*this % n</tt>.
681  /// \details InverseMod returns the multiplicative inverse of the Integer <tt>*this</tt>
682  /// modulo the Integer <tt>n</tt>. If no Integer exists then Integer 0 is returned.
683  /// \sa a_times_b_mod_c() and a_exp_b_mod_c()
684  Integer InverseMod(const Integer &n) const;
685 
686  /// \brief Calculate multiplicative inverse
687  /// \param n the modulus
688  /// \returns a word <tt>*this % n</tt>.
689  /// \details InverseMod returns the multiplicative inverse of the Integer <tt>*this</tt>
690  /// modulo the word <tt>n</tt>. If no Integer exists then word 0 is returned.
691  /// \sa a_times_b_mod_c() and a_exp_b_mod_c()
692  word InverseMod(word n) const;
693  //@}
694 
695  /// \name INPUT/OUTPUT
696  //@{
697  /// \brief Extraction operator
698  /// \param in a reference to a std::istream
699  /// \param a a reference to an Integer
700  /// \returns a reference to a std::istream reference
701  friend CRYPTOPP_DLL std::istream& CRYPTOPP_API operator>>(std::istream& in, Integer &a);
702 
703  /// \brief Insertion operator
704  /// \param out a reference to a std::ostream
705  /// \param a a constant reference to an Integer
706  /// \returns a reference to a std::ostream reference
707  /// \details The output integer responds to std::hex, std::oct, std::hex, std::upper and
708  /// std::lower. The output includes the suffix \a \b h (for hex), \a \b . (\a \b dot, for dec)
709  /// and \a \b o (for octal). There is currently no way to suppress the suffix.
710  /// \details If you want to print an Integer without the suffix or using an arbitrary base, then
711  /// use IntToString<Integer>().
712  /// \sa IntToString<Integer>
713  friend CRYPTOPP_DLL std::ostream& CRYPTOPP_API operator<<(std::ostream& out, const Integer &a);
714  //@}
715 
716  /// \brief Modular multiplication
717  /// \param x a reference to the first term
718  /// \param y a reference to the second term
719  /// \param m a reference to the modulus
720  /// \returns an Integer <tt>(a * b) % m</tt>.
721  CRYPTOPP_DLL friend Integer CRYPTOPP_API a_times_b_mod_c(const Integer &x, const Integer& y, const Integer& m);
722  /// \brief Modular exponentiation
723  /// \param x a reference to the base
724  /// \param e a reference to the exponent
725  /// \param m a reference to the modulus
726  /// \returns an Integer <tt>(a ^ b) % m</tt>.
727  CRYPTOPP_DLL friend Integer CRYPTOPP_API a_exp_b_mod_c(const Integer &x, const Integer& e, const Integer& m);
728 
729 protected:
730 
731  // http://github.com/weidai11/cryptopp/issues/602
732  Integer InverseModNext(const Integer &n) const;
733 
734 private:
735 
736  Integer(word value, size_t length);
737  int PositiveCompare(const Integer &t) const;
738 
739  IntegerSecBlock reg;
740  Sign sign;
741 
742 #ifndef CRYPTOPP_DOXYGEN_PROCESSING
743  friend class ModularArithmetic;
744  friend class MontgomeryRepresentation;
745  friend class HalfMontgomeryRepresentation;
746 
747  friend void PositiveAdd(Integer &sum, const Integer &a, const Integer &b);
748  friend void PositiveSubtract(Integer &diff, const Integer &a, const Integer &b);
749  friend void PositiveMultiply(Integer &product, const Integer &a, const Integer &b);
750  friend void PositiveDivide(Integer &remainder, Integer &quotient, const Integer &dividend, const Integer &divisor);
751 #endif
752 };
753 
754 /// \brief Comparison
755 inline bool operator==(const CryptoPP::Integer& a, const CryptoPP::Integer& b) {return a.Compare(b)==0;}
756 /// \brief Comparison
757 inline bool operator!=(const CryptoPP::Integer& a, const CryptoPP::Integer& b) {return a.Compare(b)!=0;}
758 /// \brief Comparison
759 inline bool operator> (const CryptoPP::Integer& a, const CryptoPP::Integer& b) {return a.Compare(b)> 0;}
760 /// \brief Comparison
761 inline bool operator>=(const CryptoPP::Integer& a, const CryptoPP::Integer& b) {return a.Compare(b)>=0;}
762 /// \brief Comparison
763 inline bool operator< (const CryptoPP::Integer& a, const CryptoPP::Integer& b) {return a.Compare(b)< 0;}
764 /// \brief Comparison
765 inline bool operator<=(const CryptoPP::Integer& a, const CryptoPP::Integer& b) {return a.Compare(b)<=0;}
766 /// \brief Addition
767 inline CryptoPP::Integer operator+(const CryptoPP::Integer &a, const CryptoPP::Integer &b) {return a.Plus(b);}
768 /// \brief Subtraction
769 inline CryptoPP::Integer operator-(const CryptoPP::Integer &a, const CryptoPP::Integer &b) {return a.Minus(b);}
770 /// \brief Multiplication
771 /// \sa a_times_b_mod_c() and a_exp_b_mod_c()
772 inline CryptoPP::Integer operator*(const CryptoPP::Integer &a, const CryptoPP::Integer &b) {return a.Times(b);}
773 /// \brief Division
774 inline CryptoPP::Integer operator/(const CryptoPP::Integer &a, const CryptoPP::Integer &b) {return a.DividedBy(b);}
775 /// \brief Remainder
776 /// \sa a_times_b_mod_c() and a_exp_b_mod_c()
777 inline CryptoPP::Integer operator%(const CryptoPP::Integer &a, const CryptoPP::Integer &b) {return a.Modulo(b);}
778 /// \brief Division
779 inline CryptoPP::Integer operator/(const CryptoPP::Integer &a, CryptoPP::word b) {return a.DividedBy(b);}
780 /// \brief Remainder
781 /// \sa a_times_b_mod_c() and a_exp_b_mod_c()
782 inline CryptoPP::word operator%(const CryptoPP::Integer &a, CryptoPP::word b) {return a.Modulo(b);}
783 
784 /// \brief Bitwise AND
785 /// \param a the first Integer
786 /// \param b the second Integer
787 /// \returns the result of a & b
788 /// \details operator&() performs a bitwise AND on the operands. Missing bits are truncated
789 /// at the most significant bit positions, so the result is as small as the
790 /// smaller of the operands.
791 /// \details Internally, Crypto++ uses a sign-magnitude representation. The library
792 /// does not attempt to interpret bits, and the result is always POSITIVE. If needed,
793 /// the integer should be converted to a 2's compliment representation before performing
794 /// the operation.
795 /// \since Crypto++ 6.0
796 inline CryptoPP::Integer operator&(const CryptoPP::Integer &a, const CryptoPP::Integer &b) {return a.And(b);}
797 
798 /// \brief Bitwise OR
799 /// \param a the first Integer
800 /// \param b the second Integer
801 /// \returns the result of a | b
802 /// \details operator|() performs a bitwise OR on the operands. Missing bits are shifted in
803 /// at the most significant bit positions, so the result is as large as the
804 /// larger of the operands.
805 /// \details Internally, Crypto++ uses a sign-magnitude representation. The library
806 /// does not attempt to interpret bits, and the result is always POSITIVE. If needed,
807 /// the integer should be converted to a 2's compliment representation before performing
808 /// the operation.
809 /// \since Crypto++ 6.0
810 inline CryptoPP::Integer operator|(const CryptoPP::Integer &a, const CryptoPP::Integer &b) {return a.Or(b);}
811 
812 /// \brief Bitwise XOR
813 /// \param a the first Integer
814 /// \param b the second Integer
815 /// \returns the result of a ^ b
816 /// \details operator^() performs a bitwise XOR on the operands. Missing bits are shifted
817 /// in at the most significant bit positions, so the result is as large as the
818 /// larger of the operands.
819 /// \details Internally, Crypto++ uses a sign-magnitude representation. The library
820 /// does not attempt to interpret bits, and the result is always POSITIVE. If needed,
821 /// the integer should be converted to a 2's compliment representation before performing
822 /// the operation.
823 /// \since Crypto++ 6.0
824 inline CryptoPP::Integer operator^(const CryptoPP::Integer &a, const CryptoPP::Integer &b) {return a.Xor(b);}
825 
826 NAMESPACE_END
827 
828 #ifndef __BORLANDC__
829 NAMESPACE_BEGIN(std)
830 inline void swap(CryptoPP::Integer &a, CryptoPP::Integer &b)
831 {
832  a.swap(b);
833 }
834 NAMESPACE_END
835 #endif
836 
837 #endif
Base class for all exceptions thrown by the library.
Definition: cryptlib.h:158
virtual void DEREncode(BufferedTransformation &bt) const =0
Encode this object into a BufferedTransformation.
void SetNegative()
Sets the Integer to negative.
Definition: integer.h:527
bool NotZero() const
Determines if the Integer is non-0.
Definition: integer.h:336
inline ::Integer operator*(const ::Integer &a, const ::Integer &b)
Multiplication.
Definition: integer.h:772
Integer & operator/=(word t)
Division Assignment.
Definition: integer.h:388
Integer operator--(int)
Post-decrement.
Definition: integer.h:548
ByteOrder
Provides the byte ordering.
Definition: cryptlib.h:143
an unsigned value
Definition: integer.h:85
void SetPositive()
Sets the Integer to positive.
Definition: integer.h:524
inline ::Integer operator&(const ::Integer &a, const ::Integer &b)
Bitwise AND.
Definition: integer.h:796
inline ::Integer operator%(const ::Integer &a, const ::Integer &b)
Remainder.
Definition: integer.h:777
Secure memory block with allocator and cleanup.
Definition: secblock.h:688
Abstract base classes that provide a uniform interface to this library.
Signedness
Used when importing and exporting integers.
Definition: integer.h:83
bool IsNegative() const
Determines if the Integer is negative.
Definition: integer.h:339
Ring of congruence classes modulo n.
Definition: modarith.h:43
Interface for random number generators.
Definition: cryptlib.h:1412
Common C++ header files.
void GenerateRandom(RandomNumberGenerator &rng, const NameValuePairs &params=g_nullNameValuePairs)
Generate a random number.
Definition: integer.h:506
Interface for buffered transformations.
Definition: cryptlib.h:1627
bool IsPositive() const
Determines if the Integer is positive.
Definition: integer.h:345
bool NotNegative() const
Determines if the Integer is non-negative.
Definition: integer.h:342
bool operator==(const ::Integer &a, const ::Integer &b)
Comparison.
Definition: integer.h:755
inline ::Integer operator+(const ::Integer &a, const ::Integer &b)
Addition.
Definition: integer.h:767
Sign
Used internally to represent the integer.
Definition: integer.h:73
Classes and functions for secure memory allocations.
Integer & operator/=(const Integer &t)
Division Assignment.
Definition: integer.h:379
inline ::Integer operator-(const ::Integer &a, const ::Integer &b)
Subtraction.
Definition: integer.h:769
a number with no special properties
Definition: integer.h:93
bool operator!=(const ::Integer &a, const ::Integer &b)
Comparison.
Definition: integer.h:757
bool operator<=(const ::Integer &a, const ::Integer &b)
Comparison.
Definition: integer.h:765
virtual void BERDecode(BufferedTransformation &bt)=0
Decode this object from a BufferedTransformation.
bool IsZero() const
Determines if the Integer is 0.
Definition: integer.h:333
Exception thrown when an error is encountered decoding an OpenPGP integer.
Definition: integer.h:282
Interface for encoding and decoding ASN1 objects.
Definition: cryptlib.h:3239
Performs static initialization of the Integer class.
Definition: integer.h:29
Multiple precision integer with arithmetic operations.
Definition: integer.h:49
const NameValuePairs & g_nullNameValuePairs
An empty set of name-value pairs.
Definition: cryptlib.h:529
RandomNumberType
Properties of a random integer.
Definition: integer.h:91
bool IsEven() const
Determines if the Integer is even parity.
Definition: integer.h:351
byte order is big-endian
Definition: cryptlib.h:147
Integer & operator*=(const Integer &t)
Multiplication Assignment.
Definition: integer.h:375
bool operator>(const ::Integer &a, const ::Integer &b)
Comparison.
Definition: integer.h:759
inline ::Integer operator^(const ::Integer &a, const ::Integer &b)
Bitwise XOR.
Definition: integer.h:824
Integer operator++(int)
Post-increment.
Definition: integer.h:546
Exception thrown when division by 0 is encountered.
Definition: integer.h:55
Integer Squared() const
Multiply this integer by itself.
Definition: integer.h:631
Exception thrown when a random number cannot be found that satisfies the condition.
Definition: integer.h:63
Performs modular arithmetic in Montgomery representation for increased speed.
Definition: modarith.h:295
Integer operator<<(size_t n) const
Left-shift.
Definition: integer.h:620
Integer Doubled() const
Add this integer to itself.
Definition: integer.h:628
Integer operator>>(size_t n) const
Right-shift.
Definition: integer.h:618
bool NotPositive() const
Determines if the Integer is non-positive.
Definition: integer.h:348
Integer operator+() const
Addition.
Definition: integer.h:538
Crypto++ library namespace.
Integer & operator%=(word t)
Remainder Assignment.
Definition: integer.h:393
unsigned int GetByte(ByteOrder order, T value, unsigned int index)
Gets a byte from a value.
Definition: misc.h:2019
bool operator<(const ::Integer &a, const ::Integer &b)
Comparison.
Definition: integer.h:763
Integer & operator%=(const Integer &t)
Remainder Assignment.
Definition: integer.h:384
inline ::Integer operator|(const ::Integer &a, const ::Integer &b)
Bitwise OR.
Definition: integer.h:810
bool IsOdd() const
Determines if the Integer is odd parity.
Definition: integer.h:354
bool operator>=(const ::Integer &a, const ::Integer &b)
Comparison.
Definition: integer.h:761
inline ::Integer operator/(const ::Integer &a, const ::Integer &b)
Division.
Definition: integer.h:774
Interface for retrieving values given their names.
Definition: cryptlib.h:321