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
29 struct InitializeInteger
30 {
31 InitializeInteger();
32 };
33
34 // Always align, http://github.com/weidai11/cryptopp/issues/256
35 typedef SecBlock<word, AllocatorWithCleanup<word, true> > IntegerSecBlock;
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:
DivideByZero()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
63 class RandomNumberNotFound : public Exception
64 {
65 public:
RandomNumberNotFound()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
85 UNSIGNED,
86 /// \brief a signed value
87 SIGNED};
88
89 /// \enum RandomNumberType
90 /// \brief Properties of a random integer
91 enum RandomNumberType {
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 /// \return 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 /// \return 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 /// \return 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 /// \return 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 /// \return 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 /// \return 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
274 void BERDecode(BufferedTransformation &bt);
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
282 class OpenPGPDecodeErr : public Exception
283 {
284 public:
OpenPGPDecodeErr()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 /// \return 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 /// \return 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 /// \return 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 /// \return 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 /// \return 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 /// \return the i-th byte
326 byte GetByte(size_t i) const;
327 /// \brief Provides the low order bits of the Integer
328 /// \return 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 /// \return true if the Integer is 0, false otherwise
IsZero()333 bool IsZero() const {return !*this;}
334 /// \brief Determines if the Integer is non-0
335 /// \return true if the Integer is non-0, false otherwise
NotZero()336 bool NotZero() const {return !IsZero();}
337 /// \brief Determines if the Integer is negative
338 /// \return true if the Integer is negative, false otherwise
IsNegative()339 bool IsNegative() const {return sign == NEGATIVE;}
340 /// \brief Determines if the Integer is non-negative
341 /// \return true if the Integer is non-negative, false otherwise
NotNegative()342 bool NotNegative() const {return !IsNegative();}
343 /// \brief Determines if the Integer is positive
344 /// \return true if the Integer is positive, false otherwise
IsPositive()345 bool IsPositive() const {return NotNegative() && NotZero();}
346 /// \brief Determines if the Integer is non-positive
347 /// \return true if the Integer is non-positive, false otherwise
NotPositive()348 bool NotPositive() const {return !IsPositive();}
349 /// \brief Determines if the Integer is even parity
350 /// \return true if the Integer is even, false otherwise
IsEven()351 bool IsEven() const {return GetBit(0) == 0;}
352 /// \brief Determines if the Integer is odd parity
353 /// \return true if the Integer is odd, false otherwise
IsOdd()354 bool IsOdd() const {return GetBit(0) == 1;}
355 //@}
356
357 /// \name MANIPULATORS
358 //@{
359 /// \brief Assignment
360 /// \param t the other Integer
361 /// \return the result of assignment
362 Integer& operator=(const Integer& t);
363 /// \brief Addition Assignment
364 /// \param t the other Integer
365 /// \return the result of <tt>*this + t</tt>
366 Integer& operator+=(const Integer& t);
367 /// \brief Subtraction Assignment
368 /// \param t the other Integer
369 /// \return the result of <tt>*this - t</tt>
370 Integer& operator-=(const Integer& t);
371 /// \brief Multiplication Assignment
372 /// \param t the other Integer
373 /// \return 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 /// \return 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 /// \return 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 /// \return 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 /// \return 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 /// \return reference to this Integer
398 Integer& operator<<=(size_t n);
399 /// \brief Right-shift Assignment
400 /// \param n number of bits to shift
401 /// \return reference to this Integer
402 Integer& operator>>=(size_t n);
403
404 /// \brief Bitwise AND Assignment
405 /// \param t the other Integer
406 /// \return 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 /// \return 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 /// \return 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 /// \return 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 ¶ms = 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>
506 void GenerateRandom(RandomNumberGenerator &rng, const NameValuePairs ¶ms = g_nullNameValuePairs)
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
SetPositive()524 void SetPositive() {sign = POSITIVE;}
525
526 /// \brief Sets the Integer to negative
SetNegative()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 /// \return 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 /// \return 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 /// \return 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
Doubled()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()
Squared()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 /// \return true if this integer is 1 or -1, false otherwise
640 bool IsUnit() const;
641 /// \brief Calculate multiplicative inverse
642 /// \return 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 /// \return 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 /// \return 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 /// \return 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 /// \return 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 /// \return 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 h (for hex), \a . (\a dot, for dec)
709 /// and \a 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 /// \return 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 /// \return 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 "ient, const Integer ÷nd, 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 /// \return 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 /// \return 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 /// \return 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__
NAMESPACE_BEGIN(std)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
838