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 ¶ms = 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 ¶ms = 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 "ient, const Integer ÷nd, 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 |