/src/botan/build/include/botan/bigint.h
Line | Count | Source (jump to first uncovered line) |
1 | | /* |
2 | | * BigInt |
3 | | * (C) 1999-2008,2012,2018 Jack Lloyd |
4 | | * 2007 FlexSecure |
5 | | * |
6 | | * Botan is released under the Simplified BSD License (see license.txt) |
7 | | */ |
8 | | |
9 | | #ifndef BOTAN_BIGINT_H_ |
10 | | #define BOTAN_BIGINT_H_ |
11 | | |
12 | | #include <botan/types.h> |
13 | | #include <botan/secmem.h> |
14 | | #include <botan/exceptn.h> |
15 | | #include <iosfwd> |
16 | | |
17 | | namespace Botan { |
18 | | |
19 | | class RandomNumberGenerator; |
20 | | |
21 | | /** |
22 | | * Arbitrary precision integer |
23 | | */ |
24 | | class BOTAN_PUBLIC_API(2,0) BigInt final |
25 | | { |
26 | | public: |
27 | | /** |
28 | | * Base enumerator for encoding and decoding |
29 | | */ |
30 | | enum Base { Decimal = 10, Hexadecimal = 16, Binary = 256 }; |
31 | | |
32 | | /** |
33 | | * Sign symbol definitions for positive and negative numbers |
34 | | */ |
35 | | enum Sign { Negative = 0, Positive = 1 }; |
36 | | |
37 | | /** |
38 | | * DivideByZero Exception |
39 | | * |
40 | | * In a future release this exception will be removed and its usage |
41 | | * replaced by Invalid_Argument |
42 | | */ |
43 | | class BOTAN_PUBLIC_API(2,0) DivideByZero final : public Invalid_Argument |
44 | | { |
45 | | public: |
46 | 0 | DivideByZero() : Invalid_Argument("BigInt divide by zero") {} |
47 | | }; |
48 | | |
49 | | /** |
50 | | * Create empty BigInt |
51 | | */ |
52 | 23.8M | BigInt() = default; |
53 | | |
54 | | /** |
55 | | * Create BigInt from 64 bit integer |
56 | | * @param n initial value of this BigInt |
57 | | */ |
58 | | BigInt(uint64_t n); |
59 | | |
60 | | /** |
61 | | * Copy Constructor |
62 | | * @param other the BigInt to copy |
63 | | */ |
64 | 11.7M | BigInt(const BigInt& other) = default; |
65 | | |
66 | | /** |
67 | | * Create BigInt from a string. If the string starts with 0x the |
68 | | * rest of the string will be interpreted as hexadecimal digits. |
69 | | * Otherwise, it will be interpreted as a decimal number. |
70 | | * |
71 | | * @param str the string to parse for an integer value |
72 | | */ |
73 | | explicit BigInt(const std::string& str); |
74 | | |
75 | | /** |
76 | | * Create a BigInt from an integer in a byte array |
77 | | * @param buf the byte array holding the value |
78 | | * @param length size of buf |
79 | | */ |
80 | | BigInt(const uint8_t buf[], size_t length); |
81 | | |
82 | | /** |
83 | | * Create a BigInt from an integer in a byte array |
84 | | * @param vec the byte vector holding the value |
85 | | */ |
86 | | template<typename Alloc> |
87 | 471 | explicit BigInt(const std::vector<uint8_t, Alloc>& vec) : BigInt(vec.data(), vec.size()) {} Botan::BigInt::BigInt<std::__1::allocator<unsigned char> >(std::__1::vector<unsigned char, std::__1::allocator<unsigned char> > const&) Line | Count | Source | 87 | 471 | explicit BigInt(const std::vector<uint8_t, Alloc>& vec) : BigInt(vec.data(), vec.size()) {} |
Unexecuted instantiation: Botan::BigInt::BigInt<Botan::secure_allocator<unsigned char> >(std::__1::vector<unsigned char, Botan::secure_allocator<unsigned char> > const&) |
88 | | |
89 | | /** |
90 | | * Create a BigInt from an integer in a byte array |
91 | | * @param buf the byte array holding the value |
92 | | * @param length size of buf |
93 | | * @param base is the number base of the integer in buf |
94 | | */ |
95 | | BigInt(const uint8_t buf[], size_t length, Base base); |
96 | | |
97 | | /** |
98 | | * Create a BigInt from an integer in a byte array |
99 | | * @param buf the byte array holding the value |
100 | | * @param length size of buf |
101 | | * @param max_bits if the resulting integer is more than max_bits, |
102 | | * it will be shifted so it is at most max_bits in length. |
103 | | */ |
104 | | BigInt(const uint8_t buf[], size_t length, size_t max_bits); |
105 | | |
106 | | /** |
107 | | * Create a BigInt from an array of words |
108 | | * @param words the words |
109 | | * @param length number of words |
110 | | */ |
111 | | BigInt(const word words[], size_t length); |
112 | | |
113 | | /** |
114 | | * \brief Create a random BigInt of the specified size |
115 | | * |
116 | | * @param rng random number generator |
117 | | * @param bits size in bits |
118 | | * @param set_high_bit if true, the highest bit is always set |
119 | | * |
120 | | * @see randomize |
121 | | */ |
122 | | BigInt(RandomNumberGenerator& rng, size_t bits, bool set_high_bit = true); |
123 | | |
124 | | /** |
125 | | * Create BigInt of specified size, all zeros |
126 | | * @param sign the sign |
127 | | * @param n size of the internal register in words |
128 | | */ |
129 | | BigInt(Sign sign, size_t n); |
130 | | |
131 | | /** |
132 | | * Move constructor |
133 | | */ |
134 | | BigInt(BigInt&& other) |
135 | 3.63M | { |
136 | 3.63M | this->swap(other); |
137 | 3.63M | } |
138 | | |
139 | 59.5M | ~BigInt() { const_time_unpoison(); } |
140 | | |
141 | | /** |
142 | | * Move assignment |
143 | | */ |
144 | | BigInt& operator=(BigInt&& other) |
145 | 13.0M | { |
146 | 13.0M | if(this != &other) |
147 | 13.0M | this->swap(other); |
148 | 13.0M | |
149 | 13.0M | return (*this); |
150 | 13.0M | } |
151 | | |
152 | | /** |
153 | | * Copy assignment |
154 | | */ |
155 | 26.1M | BigInt& operator=(const BigInt&) = default; |
156 | | |
157 | | /** |
158 | | * Swap this value with another |
159 | | * @param other BigInt to swap values with |
160 | | */ |
161 | | void swap(BigInt& other) |
162 | 110M | { |
163 | 110M | m_data.swap(other.m_data); |
164 | 110M | std::swap(m_signedness, other.m_signedness); |
165 | 110M | } |
166 | | |
167 | | void swap_reg(secure_vector<word>& reg) |
168 | 95.6M | { |
169 | 95.6M | m_data.swap(reg); |
170 | 95.6M | // sign left unchanged |
171 | 95.6M | } |
172 | | |
173 | | /** |
174 | | * += operator |
175 | | * @param y the BigInt to add to this |
176 | | */ |
177 | | BigInt& operator+=(const BigInt& y) |
178 | 3.19M | { |
179 | 3.19M | return add(y.data(), y.sig_words(), y.sign()); |
180 | 3.19M | } |
181 | | |
182 | | /** |
183 | | * += operator |
184 | | * @param y the word to add to this |
185 | | */ |
186 | | BigInt& operator+=(word y) |
187 | 11.0k | { |
188 | 11.0k | return add(&y, 1, Positive); |
189 | 11.0k | } |
190 | | |
191 | | /** |
192 | | * -= operator |
193 | | * @param y the BigInt to subtract from this |
194 | | */ |
195 | | BigInt& operator-=(const BigInt& y) |
196 | 4.24M | { |
197 | 4.24M | return sub(y.data(), y.sig_words(), y.sign()); |
198 | 4.24M | } |
199 | | |
200 | | /** |
201 | | * -= operator |
202 | | * @param y the word to subtract from this |
203 | | */ |
204 | | BigInt& operator-=(word y) |
205 | 2.23k | { |
206 | 2.23k | return sub(&y, 1, Positive); |
207 | 2.23k | } |
208 | | |
209 | | /** |
210 | | * *= operator |
211 | | * @param y the BigInt to multiply with this |
212 | | */ |
213 | | BigInt& operator*=(const BigInt& y); |
214 | | |
215 | | /** |
216 | | * *= operator |
217 | | * @param y the word to multiply with this |
218 | | */ |
219 | | BigInt& operator*=(word y); |
220 | | |
221 | | /** |
222 | | * /= operator |
223 | | * @param y the BigInt to divide this by |
224 | | */ |
225 | | BigInt& operator/=(const BigInt& y); |
226 | | |
227 | | /** |
228 | | * Modulo operator |
229 | | * @param y the modulus to reduce this by |
230 | | */ |
231 | | BigInt& operator%=(const BigInt& y); |
232 | | |
233 | | /** |
234 | | * Modulo operator |
235 | | * @param y the modulus (word) to reduce this by |
236 | | */ |
237 | | word operator%=(word y); |
238 | | |
239 | | /** |
240 | | * Left shift operator |
241 | | * @param shift the number of bits to shift this left by |
242 | | */ |
243 | | BigInt& operator<<=(size_t shift); |
244 | | |
245 | | /** |
246 | | * Right shift operator |
247 | | * @param shift the number of bits to shift this right by |
248 | | */ |
249 | | BigInt& operator>>=(size_t shift); |
250 | | |
251 | | /** |
252 | | * Increment operator |
253 | | */ |
254 | 8.34k | BigInt& operator++() { return (*this += 1); } |
255 | | |
256 | | /** |
257 | | * Decrement operator |
258 | | */ |
259 | 0 | BigInt& operator--() { return (*this -= 1); } |
260 | | |
261 | | /** |
262 | | * Postfix increment operator |
263 | | */ |
264 | 0 | BigInt operator++(int) { BigInt x = (*this); ++(*this); return x; } |
265 | | |
266 | | /** |
267 | | * Postfix decrement operator |
268 | | */ |
269 | 0 | BigInt operator--(int) { BigInt x = (*this); --(*this); return x; } |
270 | | |
271 | | /** |
272 | | * Unary negation operator |
273 | | * @return negative this |
274 | | */ |
275 | | BigInt operator-() const; |
276 | | |
277 | | /** |
278 | | * ! operator |
279 | | * @return true iff this is zero, otherwise false |
280 | | */ |
281 | 0 | bool operator !() const { return (!is_nonzero()); } |
282 | | |
283 | | static BigInt add2(const BigInt& x, const word y[], size_t y_words, Sign y_sign); |
284 | | |
285 | | BigInt& add(const word y[], size_t y_words, Sign sign); |
286 | | |
287 | | BigInt& sub(const word y[], size_t y_words, Sign sign) |
288 | 4.24M | { |
289 | 4.24M | return add(y, y_words, sign == Positive ? Negative : Positive); |
290 | 4.24M | } |
291 | | |
292 | | /** |
293 | | * Multiply this with y |
294 | | * @param y the BigInt to multiply with this |
295 | | * @param ws a temp workspace |
296 | | */ |
297 | | BigInt& mul(const BigInt& y, secure_vector<word>& ws); |
298 | | |
299 | | /** |
300 | | * Square value of *this |
301 | | * @param ws a temp workspace |
302 | | */ |
303 | | BigInt& square(secure_vector<word>& ws); |
304 | | |
305 | | /** |
306 | | * Set *this to y - *this |
307 | | * @param y the BigInt to subtract from as a sequence of words |
308 | | * @param y_words length of y in words |
309 | | * @param ws a temp workspace |
310 | | */ |
311 | | BigInt& rev_sub(const word y[], size_t y_words, secure_vector<word>& ws); |
312 | | |
313 | | /** |
314 | | * Set *this to (*this + y) % mod |
315 | | * This function assumes *this is >= 0 && < mod |
316 | | * @param y the BigInt to add - assumed y >= 0 and y < mod |
317 | | * @param mod the positive modulus |
318 | | * @param ws a temp workspace |
319 | | */ |
320 | | BigInt& mod_add(const BigInt& y, const BigInt& mod, secure_vector<word>& ws); |
321 | | |
322 | | /** |
323 | | * Set *this to (*this - y) % mod |
324 | | * This function assumes *this is >= 0 && < mod |
325 | | * @param y the BigInt to subtract - assumed y >= 0 and y < mod |
326 | | * @param mod the positive modulus |
327 | | * @param ws a temp workspace |
328 | | */ |
329 | | BigInt& mod_sub(const BigInt& y, const BigInt& mod, secure_vector<word>& ws); |
330 | | |
331 | | /** |
332 | | * Set *this to (*this * y) % mod |
333 | | * This function assumes *this is >= 0 && < mod |
334 | | * y should be small, less than 16 |
335 | | * @param y the small integer to multiply by |
336 | | * @param mod the positive modulus |
337 | | * @param ws a temp workspace |
338 | | */ |
339 | | BigInt& mod_mul(uint8_t y, const BigInt& mod, secure_vector<word>& ws); |
340 | | |
341 | | /** |
342 | | * Return *this % mod |
343 | | * |
344 | | * Assumes that *this is (if anything) only slightly larger than |
345 | | * mod and performs repeated subtractions. It should not be used if |
346 | | * *this is much larger than mod, instead use modulo operator. |
347 | | */ |
348 | | size_t reduce_below(const BigInt& mod, secure_vector<word> &ws); |
349 | | |
350 | | /** |
351 | | * Return *this % mod |
352 | | * |
353 | | * Assumes that *this is (if anything) only slightly larger than mod and |
354 | | * performs repeated subtractions. It should not be used if *this is much |
355 | | * larger than mod, instead use modulo operator. |
356 | | * |
357 | | * Performs exactly bound subtractions, so if *this is >= bound*mod then the |
358 | | * result will not be fully reduced. If bound is zero, nothing happens. |
359 | | */ |
360 | | void ct_reduce_below(const BigInt& mod, secure_vector<word> &ws, size_t bound); |
361 | | |
362 | | /** |
363 | | * Zeroize the BigInt. The size of the underlying register is not |
364 | | * modified. |
365 | | */ |
366 | 1.68M | void clear() { m_data.set_to_zero(); m_signedness = Positive; } |
367 | | |
368 | | /** |
369 | | * Compare this to another BigInt |
370 | | * @param n the BigInt value to compare with |
371 | | * @param check_signs include sign in comparison? |
372 | | * @result if (this<n) return -1, if (this>n) return 1, if both |
373 | | * values are identical return 0 [like Perl's <=> operator] |
374 | | */ |
375 | | int32_t cmp(const BigInt& n, bool check_signs = true) const; |
376 | | |
377 | | /** |
378 | | * Compare this to another BigInt |
379 | | * @param n the BigInt value to compare with |
380 | | * @result true if this == n or false otherwise |
381 | | */ |
382 | | bool is_equal(const BigInt& n) const; |
383 | | |
384 | | /** |
385 | | * Compare this to another BigInt |
386 | | * @param n the BigInt value to compare with |
387 | | * @result true if this < n or false otherwise |
388 | | */ |
389 | | bool is_less_than(const BigInt& n) const; |
390 | | |
391 | | /** |
392 | | * Compare this to an integer |
393 | | * @param n the value to compare with |
394 | | * @result if (this<n) return -1, if (this>n) return 1, if both |
395 | | * values are identical return 0 [like Perl's <=> operator] |
396 | | */ |
397 | | int32_t cmp_word(word n) const; |
398 | | |
399 | | /** |
400 | | * Test if the integer has an even value |
401 | | * @result true if the integer is even, false otherwise |
402 | | */ |
403 | 203k | bool is_even() const { return (get_bit(0) == 0); } |
404 | | |
405 | | /** |
406 | | * Test if the integer has an odd value |
407 | | * @result true if the integer is odd, false otherwise |
408 | | */ |
409 | 2.90M | bool is_odd() const { return (get_bit(0) == 1); } |
410 | | |
411 | | /** |
412 | | * Test if the integer is not zero |
413 | | * @result true if the integer is non-zero, false otherwise |
414 | | */ |
415 | 6.19M | bool is_nonzero() const { return (!is_zero()); } |
416 | | |
417 | | /** |
418 | | * Test if the integer is zero |
419 | | * @result true if the integer is zero, false otherwise |
420 | | */ |
421 | | bool is_zero() const |
422 | 61.0M | { |
423 | 61.0M | return (sig_words() == 0); |
424 | 61.0M | } |
425 | | |
426 | | /** |
427 | | * Set bit at specified position |
428 | | * @param n bit position to set |
429 | | */ |
430 | | void set_bit(size_t n) |
431 | 505k | { |
432 | 505k | conditionally_set_bit(n, true); |
433 | 505k | } |
434 | | |
435 | | /** |
436 | | * Conditionally set bit at specified position. Note if set_it is |
437 | | * false, nothing happens, and if the bit is already set, it |
438 | | * remains set. |
439 | | * |
440 | | * @param n bit position to set |
441 | | * @param set_it if the bit should be set |
442 | | */ |
443 | | void conditionally_set_bit(size_t n, bool set_it); |
444 | | |
445 | | /** |
446 | | * Clear bit at specified position |
447 | | * @param n bit position to clear |
448 | | */ |
449 | | void clear_bit(size_t n); |
450 | | |
451 | | /** |
452 | | * Clear all but the lowest n bits |
453 | | * @param n amount of bits to keep |
454 | | */ |
455 | | void mask_bits(size_t n) |
456 | 224M | { |
457 | 224M | m_data.mask_bits(n); |
458 | 224M | } |
459 | | |
460 | | /** |
461 | | * Return bit value at specified position |
462 | | * @param n the bit offset to test |
463 | | * @result true, if the bit at position n is set, false otherwise |
464 | | */ |
465 | | bool get_bit(size_t n) const |
466 | 149M | { |
467 | 149M | return ((word_at(n / BOTAN_MP_WORD_BITS) >> (n % BOTAN_MP_WORD_BITS)) & 1); |
468 | 149M | } |
469 | | |
470 | | /** |
471 | | * Return (a maximum of) 32 bits of the complete value |
472 | | * @param offset the offset to start extracting |
473 | | * @param length amount of bits to extract (starting at offset) |
474 | | * @result the integer extracted from the register starting at |
475 | | * offset with specified length |
476 | | */ |
477 | | uint32_t get_substring(size_t offset, size_t length) const; |
478 | | |
479 | | /** |
480 | | * Convert this value into a uint32_t, if it is in the range |
481 | | * [0 ... 2**32-1], or otherwise throw an exception. |
482 | | * @result the value as a uint32_t if conversion is possible |
483 | | */ |
484 | | uint32_t to_u32bit() const; |
485 | | |
486 | | /** |
487 | | * Convert this value to a decimal string. |
488 | | * Warning: decimal conversions are relatively slow |
489 | | */ |
490 | | std::string to_dec_string() const; |
491 | | |
492 | | /** |
493 | | * Convert this value to a hexadecimal string. |
494 | | */ |
495 | | std::string to_hex_string() const; |
496 | | |
497 | | /** |
498 | | * @param n the offset to get a byte from |
499 | | * @result byte at offset n |
500 | | */ |
501 | | uint8_t byte_at(size_t n) const; |
502 | | |
503 | | /** |
504 | | * Return the word at a specified position of the internal register |
505 | | * @param n position in the register |
506 | | * @return value at position n |
507 | | */ |
508 | | word word_at(size_t n) const |
509 | 1.75G | { |
510 | 1.75G | return m_data.get_word_at(n); |
511 | 1.75G | } |
512 | | |
513 | | void set_word_at(size_t i, word w) |
514 | 223M | { |
515 | 223M | m_data.set_word_at(i, w); |
516 | 223M | } |
517 | | |
518 | | void set_words(const word w[], size_t len) |
519 | 12.0M | { |
520 | 12.0M | m_data.set_words(w, len); |
521 | 12.0M | } |
522 | | |
523 | | /** |
524 | | * Tests if the sign of the integer is negative |
525 | | * @result true, iff the integer has a negative sign |
526 | | */ |
527 | 611M | bool is_negative() const { return (sign() == Negative); } |
528 | | |
529 | | /** |
530 | | * Tests if the sign of the integer is positive |
531 | | * @result true, iff the integer has a positive sign |
532 | | */ |
533 | 10.1M | bool is_positive() const { return (sign() == Positive); } |
534 | | |
535 | | /** |
536 | | * Return the sign of the integer |
537 | | * @result the sign of the integer |
538 | | */ |
539 | 724M | Sign sign() const { return (m_signedness); } |
540 | | |
541 | | /** |
542 | | * @result the opposite sign of the represented integer value |
543 | | */ |
544 | | Sign reverse_sign() const |
545 | 1.68M | { |
546 | 1.68M | if(sign() == Positive) |
547 | 1.68M | return Negative; |
548 | 694 | return Positive; |
549 | 694 | } |
550 | | |
551 | | /** |
552 | | * Flip the sign of this BigInt |
553 | | */ |
554 | | void flip_sign() |
555 | 11.9k | { |
556 | 11.9k | set_sign(reverse_sign()); |
557 | 11.9k | } |
558 | | |
559 | | /** |
560 | | * Set sign of the integer |
561 | | * @param sign new Sign to set |
562 | | */ |
563 | | void set_sign(Sign sign) |
564 | 47.3M | { |
565 | 47.3M | if(sign == Negative && is_zero()) |
566 | 993 | sign = Positive; |
567 | 47.3M | |
568 | 47.3M | m_signedness = sign; |
569 | 47.3M | } |
570 | | |
571 | | /** |
572 | | * @result absolute (positive) value of this |
573 | | */ |
574 | | BigInt abs() const; |
575 | | |
576 | | /** |
577 | | * Give size of internal register |
578 | | * @result size of internal register in words |
579 | | */ |
580 | 2.32G | size_t size() const { return m_data.size(); } |
581 | | |
582 | | /** |
583 | | * Return how many words we need to hold this value |
584 | | * @result significant words of the represented integer value |
585 | | */ |
586 | | size_t sig_words() const |
587 | 373M | { |
588 | 373M | return m_data.sig_words(); |
589 | 373M | } |
590 | | |
591 | | /** |
592 | | * Give byte length of the integer |
593 | | * @result byte length of the represented integer value |
594 | | */ |
595 | | size_t bytes() const; |
596 | | |
597 | | /** |
598 | | * Get the bit length of the integer |
599 | | * @result bit length of the represented integer value |
600 | | */ |
601 | | size_t bits() const; |
602 | | |
603 | | /** |
604 | | * Get the number of high bits unset in the top (allocated) word |
605 | | * of this integer. Returns BOTAN_MP_WORD_BITS only iff *this is |
606 | | * zero. Ignores sign. |
607 | | */ |
608 | | size_t top_bits_free() const; |
609 | | |
610 | | /** |
611 | | * Return a mutable pointer to the register |
612 | | * @result a pointer to the start of the internal register |
613 | | */ |
614 | 1.63G | word* mutable_data() { return m_data.mutable_data(); } |
615 | | |
616 | | /** |
617 | | * Return a const pointer to the register |
618 | | * @result a pointer to the start of the internal register |
619 | | */ |
620 | 1.69G | const word* data() const { return m_data.const_data(); } |
621 | | |
622 | | /** |
623 | | * Don't use this function in application code |
624 | | */ |
625 | 53.3M | secure_vector<word>& get_word_vector() { return m_data.mutable_vector(); } |
626 | | |
627 | | /** |
628 | | * Don't use this function in application code |
629 | | */ |
630 | 41.7M | const secure_vector<word>& get_word_vector() const { return m_data.const_vector(); } |
631 | | |
632 | | /** |
633 | | * Increase internal register buffer to at least n words |
634 | | * @param n new size of register |
635 | | */ |
636 | 807M | void grow_to(size_t n) const { m_data.grow_to(n); } |
637 | | |
638 | | /** |
639 | | * Resize the vector to the minimum word size to hold the integer, or |
640 | | * min_size words, whichever is larger |
641 | | */ |
642 | | void BOTAN_DEPRECATED("Use resize if required") shrink_to_fit(size_t min_size = 0) |
643 | 0 | { |
644 | 0 | m_data.shrink_to_fit(min_size); |
645 | 0 | } |
646 | | |
647 | 0 | void resize(size_t s) { m_data.resize(s); } |
648 | | |
649 | | /** |
650 | | * Fill BigInt with a random number with size of bitsize |
651 | | * |
652 | | * If \p set_high_bit is true, the highest bit will be set, which causes |
653 | | * the entropy to be \a bits-1. Otherwise the highest bit is randomly chosen |
654 | | * by the rng, causing the entropy to be \a bits. |
655 | | * |
656 | | * @param rng the random number generator to use |
657 | | * @param bitsize number of bits the created random value should have |
658 | | * @param set_high_bit if true, the highest bit is always set |
659 | | */ |
660 | | void randomize(RandomNumberGenerator& rng, size_t bitsize, bool set_high_bit = true); |
661 | | |
662 | | /** |
663 | | * Store BigInt-value in a given byte array |
664 | | * @param buf destination byte array for the integer value |
665 | | */ |
666 | | void binary_encode(uint8_t buf[]) const; |
667 | | |
668 | | /** |
669 | | * Store BigInt-value in a given byte array. If len is less than |
670 | | * the size of the value, then it will be truncated. If len is |
671 | | * greater than the size of the value, it will be zero-padded. |
672 | | * If len exactly equals this->bytes(), this function behaves identically |
673 | | * to binary_encode. |
674 | | * |
675 | | * @param buf destination byte array for the integer value |
676 | | * @param len how many bytes to write |
677 | | */ |
678 | | void binary_encode(uint8_t buf[], size_t len) const; |
679 | | |
680 | | /** |
681 | | * Read integer value from a byte array with given size |
682 | | * @param buf byte array buffer containing the integer |
683 | | * @param length size of buf |
684 | | */ |
685 | | void binary_decode(const uint8_t buf[], size_t length); |
686 | | |
687 | | /** |
688 | | * Read integer value from a byte vector |
689 | | * @param buf the vector to load from |
690 | | */ |
691 | | template<typename Alloc> |
692 | | void binary_decode(const std::vector<uint8_t, Alloc>& buf) |
693 | 421k | { |
694 | 421k | binary_decode(buf.data(), buf.size()); |
695 | 421k | } |
696 | | |
697 | | /** |
698 | | * @param base the base to measure the size for |
699 | | * @return size of this integer in base base |
700 | | * |
701 | | * Deprecated. This is only needed when using the `encode` and |
702 | | * `encode_locked` functions, which are also deprecated. |
703 | | */ |
704 | | BOTAN_DEPRECATED("See comments on declaration") |
705 | | size_t encoded_size(Base base = Binary) const; |
706 | | |
707 | | /** |
708 | | * Place the value into out, zero-padding up to size words |
709 | | * Throw if *this cannot be represented in size words |
710 | | */ |
711 | | void encode_words(word out[], size_t size) const; |
712 | | |
713 | | /** |
714 | | * If predicate is true assign other to *this |
715 | | * Uses a masked operation to avoid side channels |
716 | | */ |
717 | | void ct_cond_assign(bool predicate, const BigInt& other); |
718 | | |
719 | | /** |
720 | | * If predicate is true swap *this and other |
721 | | * Uses a masked operation to avoid side channels |
722 | | */ |
723 | | void ct_cond_swap(bool predicate, BigInt& other); |
724 | | |
725 | | /** |
726 | | * If predicate is true add value to *this |
727 | | */ |
728 | | void ct_cond_add(bool predicate, const BigInt& value); |
729 | | |
730 | | /** |
731 | | * If predicate is true flip the sign of *this |
732 | | */ |
733 | | void cond_flip_sign(bool predicate); |
734 | | |
735 | | #if defined(BOTAN_HAS_VALGRIND) |
736 | | void const_time_poison() const; |
737 | | void const_time_unpoison() const; |
738 | | #else |
739 | 1.21M | void const_time_poison() const {} |
740 | 59.6M | void const_time_unpoison() const {} |
741 | | #endif |
742 | | |
743 | | /** |
744 | | * @param rng a random number generator |
745 | | * @param min the minimum value (must be non-negative) |
746 | | * @param max the maximum value (must be non-negative and > min) |
747 | | * @return random integer in [min,max) |
748 | | */ |
749 | | static BigInt random_integer(RandomNumberGenerator& rng, |
750 | | const BigInt& min, |
751 | | const BigInt& max); |
752 | | |
753 | | /** |
754 | | * Create a power of two |
755 | | * @param n the power of two to create |
756 | | * @return bigint representing 2^n |
757 | | */ |
758 | | static BigInt power_of_2(size_t n) |
759 | 123k | { |
760 | 123k | BigInt b; |
761 | 123k | b.set_bit(n); |
762 | 123k | return b; |
763 | 123k | } |
764 | | |
765 | | /** |
766 | | * Encode the integer value from a BigInt to a std::vector of bytes |
767 | | * @param n the BigInt to use as integer source |
768 | | * @result secure_vector of bytes containing the bytes of the integer |
769 | | */ |
770 | | static std::vector<uint8_t> encode(const BigInt& n) |
771 | 38.0k | { |
772 | 38.0k | std::vector<uint8_t> output(n.bytes()); |
773 | 38.0k | n.binary_encode(output.data()); |
774 | 38.0k | return output; |
775 | 38.0k | } |
776 | | |
777 | | /** |
778 | | * Encode the integer value from a BigInt to a secure_vector of bytes |
779 | | * @param n the BigInt to use as integer source |
780 | | * @result secure_vector of bytes containing the bytes of the integer |
781 | | */ |
782 | | static secure_vector<uint8_t> encode_locked(const BigInt& n) |
783 | 5.64k | { |
784 | 5.64k | secure_vector<uint8_t> output(n.bytes()); |
785 | 5.64k | n.binary_encode(output.data()); |
786 | 5.64k | return output; |
787 | 5.64k | } |
788 | | |
789 | | /** |
790 | | * Encode the integer value from a BigInt to a byte array |
791 | | * @param buf destination byte array for the encoded integer |
792 | | * @param n the BigInt to use as integer source |
793 | | */ |
794 | | static BOTAN_DEPRECATED("Use n.binary_encode") void encode(uint8_t buf[], const BigInt& n) |
795 | 0 | { |
796 | 0 | n.binary_encode(buf); |
797 | 0 | } |
798 | | |
799 | | /** |
800 | | * Create a BigInt from an integer in a byte array |
801 | | * @param buf the binary value to load |
802 | | * @param length size of buf |
803 | | * @result BigInt representing the integer in the byte array |
804 | | */ |
805 | | static BigInt decode(const uint8_t buf[], size_t length) |
806 | 37.6k | { |
807 | 37.6k | return BigInt(buf, length); |
808 | 37.6k | } |
809 | | |
810 | | /** |
811 | | * Create a BigInt from an integer in a byte array |
812 | | * @param buf the binary value to load |
813 | | * @result BigInt representing the integer in the byte array |
814 | | */ |
815 | | template<typename Alloc> |
816 | | static BigInt decode(const std::vector<uint8_t, Alloc>& buf) |
817 | 471 | { |
818 | 471 | return BigInt(buf); |
819 | 471 | } Botan::BigInt Botan::BigInt::decode<std::__1::allocator<unsigned char> >(std::__1::vector<unsigned char, std::__1::allocator<unsigned char> > const&) Line | Count | Source | 817 | 471 | { | 818 | 471 | return BigInt(buf); | 819 | 471 | } |
Unexecuted instantiation: Botan::BigInt Botan::BigInt::decode<Botan::secure_allocator<unsigned char> >(std::__1::vector<unsigned char, Botan::secure_allocator<unsigned char> > const&) |
820 | | |
821 | | /** |
822 | | * Encode the integer value from a BigInt to a std::vector of bytes |
823 | | * @param n the BigInt to use as integer source |
824 | | * @param base number-base of resulting byte array representation |
825 | | * @result secure_vector of bytes containing the integer with given base |
826 | | * |
827 | | * Deprecated. If you need Binary, call the version of encode that doesn't |
828 | | * take a Base. If you need Hex or Decimal output, use to_hex_string or |
829 | | * to_dec_string resp. |
830 | | */ |
831 | | BOTAN_DEPRECATED("See comments on declaration") |
832 | | static std::vector<uint8_t> encode(const BigInt& n, Base base); |
833 | | |
834 | | /** |
835 | | * Encode the integer value from a BigInt to a secure_vector of bytes |
836 | | * @param n the BigInt to use as integer source |
837 | | * @param base number-base of resulting byte array representation |
838 | | * @result secure_vector of bytes containing the integer with given base |
839 | | * |
840 | | * Deprecated. If you need Binary, call the version of encode_locked that |
841 | | * doesn't take a Base. If you need Hex or Decimal output, use to_hex_string |
842 | | * or to_dec_string resp. |
843 | | */ |
844 | | BOTAN_DEPRECATED("See comments on declaration") |
845 | | static secure_vector<uint8_t> encode_locked(const BigInt& n, |
846 | | Base base); |
847 | | |
848 | | /** |
849 | | * Encode the integer value from a BigInt to a byte array |
850 | | * @param buf destination byte array for the encoded integer |
851 | | * value with given base |
852 | | * @param n the BigInt to use as integer source |
853 | | * @param base number-base of resulting byte array representation |
854 | | * |
855 | | * Deprecated. If you need Binary, call binary_encode. If you need |
856 | | * Hex or Decimal output, use to_hex_string or to_dec_string resp. |
857 | | */ |
858 | | BOTAN_DEPRECATED("See comments on declaration") |
859 | | static void encode(uint8_t buf[], const BigInt& n, Base base); |
860 | | |
861 | | /** |
862 | | * Create a BigInt from an integer in a byte array |
863 | | * @param buf the binary value to load |
864 | | * @param length size of buf |
865 | | * @param base number-base of the integer in buf |
866 | | * @result BigInt representing the integer in the byte array |
867 | | */ |
868 | | static BigInt decode(const uint8_t buf[], size_t length, |
869 | | Base base); |
870 | | |
871 | | /** |
872 | | * Create a BigInt from an integer in a byte array |
873 | | * @param buf the binary value to load |
874 | | * @param base number-base of the integer in buf |
875 | | * @result BigInt representing the integer in the byte array |
876 | | */ |
877 | | template<typename Alloc> |
878 | | static BigInt decode(const std::vector<uint8_t, Alloc>& buf, Base base) |
879 | | { |
880 | | if(base == Binary) |
881 | | return BigInt(buf); |
882 | | return BigInt::decode(buf.data(), buf.size(), base); |
883 | | } |
884 | | |
885 | | /** |
886 | | * Encode a BigInt to a byte array according to IEEE 1363 |
887 | | * @param n the BigInt to encode |
888 | | * @param bytes the length of the resulting secure_vector<uint8_t> |
889 | | * @result a secure_vector<uint8_t> containing the encoded BigInt |
890 | | */ |
891 | | static secure_vector<uint8_t> encode_1363(const BigInt& n, size_t bytes); |
892 | | |
893 | | static void encode_1363(uint8_t out[], size_t bytes, const BigInt& n); |
894 | | |
895 | | /** |
896 | | * Encode two BigInt to a byte array according to IEEE 1363 |
897 | | * @param n1 the first BigInt to encode |
898 | | * @param n2 the second BigInt to encode |
899 | | * @param bytes the length of the encoding of each single BigInt |
900 | | * @result a secure_vector<uint8_t> containing the concatenation of the two encoded BigInt |
901 | | */ |
902 | | static secure_vector<uint8_t> encode_fixed_length_int_pair(const BigInt& n1, const BigInt& n2, size_t bytes); |
903 | | |
904 | | /** |
905 | | * Set output = vec[idx].m_reg in constant time |
906 | | * |
907 | | * All elements of vec must have the same size, and output must be |
908 | | * pre-allocated with the same size. |
909 | | */ |
910 | | static void BOTAN_DEPRECATED("No longer in use") const_time_lookup( |
911 | | secure_vector<word>& output, |
912 | | const std::vector<BigInt>& vec, |
913 | | size_t idx); |
914 | | |
915 | | private: |
916 | | |
917 | | class Data |
918 | | { |
919 | | public: |
920 | | word* mutable_data() |
921 | 1.65G | { |
922 | 1.65G | invalidate_sig_words(); |
923 | 1.65G | return m_reg.data(); |
924 | 1.65G | } |
925 | | |
926 | | const word* const_data() const |
927 | 1.69G | { |
928 | 1.69G | return m_reg.data(); |
929 | 1.69G | } |
930 | | |
931 | | secure_vector<word>& mutable_vector() |
932 | 53.3M | { |
933 | 53.3M | invalidate_sig_words(); |
934 | 53.3M | return m_reg; |
935 | 53.3M | } |
936 | | |
937 | | const secure_vector<word>& const_vector() const |
938 | 41.7M | { |
939 | 41.7M | return m_reg; |
940 | 41.7M | } |
941 | | |
942 | | word get_word_at(size_t n) const |
943 | 1.75G | { |
944 | 1.75G | if(n < m_reg.size()) |
945 | 1.74G | return m_reg[n]; |
946 | 3.79M | return 0; |
947 | 3.79M | } |
948 | | |
949 | | void set_word_at(size_t i, word w) |
950 | 512M | { |
951 | 512M | invalidate_sig_words(); |
952 | 512M | if(i >= m_reg.size()) |
953 | 196M | { |
954 | 196M | if(w == 0) |
955 | 193M | return; |
956 | 2.59M | grow_to(i + 1); |
957 | 2.59M | } |
958 | 512M | m_reg[i] = w; |
959 | 318M | } |
960 | | |
961 | | void set_words(const word w[], size_t len) |
962 | 12.0M | { |
963 | 12.0M | invalidate_sig_words(); |
964 | 12.0M | m_reg.assign(w, w + len); |
965 | 12.0M | } |
966 | | |
967 | | void set_to_zero() |
968 | 1.68M | { |
969 | 1.68M | m_reg.resize(m_reg.capacity()); |
970 | 1.68M | clear_mem(m_reg.data(), m_reg.size()); |
971 | 1.68M | m_sig_words = 0; |
972 | 1.68M | } |
973 | | |
974 | | void set_size(size_t s) |
975 | 15.2M | { |
976 | 15.2M | invalidate_sig_words(); |
977 | 15.2M | clear_mem(m_reg.data(), m_reg.size()); |
978 | 15.2M | m_reg.resize(s + (8 - (s % 8))); |
979 | 15.2M | } |
980 | | |
981 | | void mask_bits(size_t n) |
982 | 224M | { |
983 | 224M | if(n == 0) { return set_to_zero(); } |
984 | 224M | |
985 | 224M | const size_t top_word = n / BOTAN_MP_WORD_BITS; |
986 | 224M | |
987 | 224M | // if(top_word < sig_words()) ? |
988 | 224M | if(top_word < size()) |
989 | 224M | { |
990 | 224M | const word mask = (static_cast<word>(1) << (n % BOTAN_MP_WORD_BITS)) - 1; |
991 | 224M | const size_t len = size() - (top_word + 1); |
992 | 224M | if(len > 0) |
993 | 224M | { |
994 | 224M | clear_mem(&m_reg[top_word+1], len); |
995 | 224M | } |
996 | 224M | m_reg[top_word] &= mask; |
997 | 224M | invalidate_sig_words(); |
998 | 224M | } |
999 | 224M | } |
1000 | | |
1001 | | void grow_to(size_t n) const |
1002 | 814M | { |
1003 | 814M | if(n > size()) |
1004 | 30.3M | { |
1005 | 30.3M | if(n <= m_reg.capacity()) |
1006 | 17.6M | m_reg.resize(n); |
1007 | 12.6M | else |
1008 | 12.6M | m_reg.resize(n + (8 - (n % 8))); |
1009 | 30.3M | } |
1010 | 814M | } |
1011 | | |
1012 | 3.61G | size_t size() const { return m_reg.size(); } |
1013 | | |
1014 | | void shrink_to_fit(size_t min_size = 0) |
1015 | 0 | { |
1016 | 0 | const size_t words = std::max(min_size, sig_words()); |
1017 | 0 | m_reg.resize(words); |
1018 | 0 | } |
1019 | | |
1020 | | void resize(size_t s) |
1021 | 0 | { |
1022 | 0 | m_reg.resize(s); |
1023 | 0 | } |
1024 | | |
1025 | | void swap(Data& other) |
1026 | 110M | { |
1027 | 110M | m_reg.swap(other.m_reg); |
1028 | 110M | std::swap(m_sig_words, other.m_sig_words); |
1029 | 110M | } |
1030 | | |
1031 | | void swap(secure_vector<word>& reg) |
1032 | 96.1M | { |
1033 | 96.1M | m_reg.swap(reg); |
1034 | 96.1M | invalidate_sig_words(); |
1035 | 96.1M | } |
1036 | | |
1037 | | void invalidate_sig_words() const |
1038 | 2.57G | { |
1039 | 2.57G | m_sig_words = sig_words_npos; |
1040 | 2.57G | } |
1041 | | |
1042 | | size_t sig_words() const |
1043 | 373M | { |
1044 | 373M | if(m_sig_words == sig_words_npos) |
1045 | 119M | { |
1046 | 119M | m_sig_words = calc_sig_words(); |
1047 | 119M | } |
1048 | 253M | else |
1049 | 253M | { |
1050 | 253M | BOTAN_DEBUG_ASSERT(m_sig_words == calc_sig_words()); |
1051 | 253M | } |
1052 | 373M | return m_sig_words; |
1053 | 373M | } |
1054 | | private: |
1055 | | static const size_t sig_words_npos = static_cast<size_t>(-1); |
1056 | | |
1057 | | size_t calc_sig_words() const; |
1058 | | |
1059 | | mutable secure_vector<word> m_reg; |
1060 | | mutable size_t m_sig_words = sig_words_npos; |
1061 | | }; |
1062 | | |
1063 | | Data m_data; |
1064 | | Sign m_signedness = Positive; |
1065 | | }; |
1066 | | |
1067 | | /* |
1068 | | * Arithmetic Operators |
1069 | | */ |
1070 | | inline BigInt operator+(const BigInt& x, const BigInt& y) |
1071 | 825k | { |
1072 | 825k | return BigInt::add2(x, y.data(), y.sig_words(), y.sign()); |
1073 | 825k | } |
1074 | | |
1075 | | inline BigInt operator+(const BigInt& x, word y) |
1076 | 16.9k | { |
1077 | 16.9k | return BigInt::add2(x, &y, 1, BigInt::Positive); |
1078 | 16.9k | } |
1079 | | |
1080 | | inline BigInt operator+(word x, const BigInt& y) |
1081 | 0 | { |
1082 | 0 | return y + x; |
1083 | 0 | } |
1084 | | |
1085 | | inline BigInt operator-(const BigInt& x, const BigInt& y) |
1086 | 1.67M | { |
1087 | 1.67M | return BigInt::add2(x, y.data(), y.sig_words(), y.reverse_sign()); |
1088 | 1.67M | } |
1089 | | |
1090 | | inline BigInt operator-(const BigInt& x, word y) |
1091 | 11.9k | { |
1092 | 11.9k | return BigInt::add2(x, &y, 1, BigInt::Negative); |
1093 | 11.9k | } |
1094 | | |
1095 | | BigInt BOTAN_PUBLIC_API(2,0) operator*(const BigInt& x, const BigInt& y); |
1096 | | BigInt BOTAN_PUBLIC_API(2,8) operator*(const BigInt& x, word y); |
1097 | 5.30M | inline BigInt operator*(word x, const BigInt& y) { return y*x; } |
1098 | | |
1099 | | BigInt BOTAN_PUBLIC_API(2,0) operator/(const BigInt& x, const BigInt& d); |
1100 | | BigInt BOTAN_PUBLIC_API(2,0) operator%(const BigInt& x, const BigInt& m); |
1101 | | word BOTAN_PUBLIC_API(2,0) operator%(const BigInt& x, word m); |
1102 | | BigInt BOTAN_PUBLIC_API(2,0) operator<<(const BigInt& x, size_t n); |
1103 | | BigInt BOTAN_PUBLIC_API(2,0) operator>>(const BigInt& x, size_t n); |
1104 | | |
1105 | | /* |
1106 | | * Comparison Operators |
1107 | | */ |
1108 | | inline bool operator==(const BigInt& a, const BigInt& b) |
1109 | 151k | { return a.is_equal(b); } |
1110 | | inline bool operator!=(const BigInt& a, const BigInt& b) |
1111 | 59.6k | { return !a.is_equal(b); } |
1112 | | inline bool operator<=(const BigInt& a, const BigInt& b) |
1113 | 69.9k | { return (a.cmp(b) <= 0); } |
1114 | | inline bool operator>=(const BigInt& a, const BigInt& b) |
1115 | 515k | { return (a.cmp(b) >= 0); } |
1116 | | inline bool operator<(const BigInt& a, const BigInt& b) |
1117 | 2.62M | { return a.is_less_than(b); } |
1118 | | inline bool operator>(const BigInt& a, const BigInt& b) |
1119 | 2.28M | { return b.is_less_than(a); } |
1120 | | |
1121 | | inline bool operator==(const BigInt& a, word b) |
1122 | 287k | { return (a.cmp_word(b) == 0); } |
1123 | | inline bool operator!=(const BigInt& a, word b) |
1124 | 2.39M | { return (a.cmp_word(b) != 0); } |
1125 | | inline bool operator<=(const BigInt& a, word b) |
1126 | 25.8k | { return (a.cmp_word(b) <= 0); } |
1127 | | inline bool operator>=(const BigInt& a, word b) |
1128 | 207 | { return (a.cmp_word(b) >= 0); } |
1129 | | inline bool operator<(const BigInt& a, word b) |
1130 | 274k | { return (a.cmp_word(b) < 0); } |
1131 | | inline bool operator>(const BigInt& a, word b) |
1132 | 2.89M | { return (a.cmp_word(b) > 0); } |
1133 | | |
1134 | | /* |
1135 | | * I/O Operators |
1136 | | */ |
1137 | | BOTAN_PUBLIC_API(2,0) std::ostream& operator<<(std::ostream&, const BigInt&); |
1138 | | BOTAN_PUBLIC_API(2,0) std::istream& operator>>(std::istream&, BigInt&); |
1139 | | |
1140 | | } |
1141 | | |
1142 | | namespace std { |
1143 | | |
1144 | | template<> |
1145 | | inline void swap<Botan::BigInt>(Botan::BigInt& x, Botan::BigInt& y) |
1146 | 2.28M | { |
1147 | 2.28M | x.swap(y); |
1148 | 2.28M | } |
1149 | | |
1150 | | } |
1151 | | |
1152 | | #endif |