Coverage Report

Created: 2024-11-21 07:03

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