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