/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 | | * Create empty (zero) BigInt |
39 | | */ |
40 | 43.5M | BigInt() = default; |
41 | | |
42 | | /** |
43 | | * Create a 0-value BigInt |
44 | | */ |
45 | 2.35M | static BigInt zero() { return BigInt(); } |
46 | | |
47 | | /** |
48 | | * Create a 1-value BigInt |
49 | | */ |
50 | 24.7k | static BigInt one() { return BigInt::from_word(1); } |
51 | | |
52 | | /** |
53 | | * Create BigInt from an unsigned 64 bit integer |
54 | | * @param n initial value of this BigInt |
55 | | */ |
56 | | static BigInt from_u64(uint64_t n); |
57 | | |
58 | | /** |
59 | | * Create BigInt from a word (limb) |
60 | | * @param n initial value of this BigInt |
61 | | */ |
62 | | static BigInt from_word(word n); |
63 | | |
64 | | /** |
65 | | * Create BigInt from a signed 32 bit integer |
66 | | * @param n initial value of this BigInt |
67 | | */ |
68 | | static BigInt from_s32(int32_t n); |
69 | | |
70 | | /** |
71 | | * Create BigInt from an unsigned 64 bit integer |
72 | | * @param n initial value of this BigInt |
73 | | */ |
74 | | BigInt(uint64_t n); |
75 | | |
76 | | /** |
77 | | * Copy Constructor |
78 | | * @param other the BigInt to copy |
79 | | */ |
80 | 12.5M | BigInt(const BigInt& other) = default; |
81 | | |
82 | | /** |
83 | | * Create BigInt from a string. If the string starts with 0x the |
84 | | * rest of the string will be interpreted as hexadecimal digits. |
85 | | * Otherwise, it will be interpreted as a decimal number. |
86 | | * |
87 | | * @param str the string to parse for an integer value |
88 | | */ |
89 | | explicit BigInt(const std::string& str); |
90 | | |
91 | | /** |
92 | | * Create a BigInt from an integer in a byte array |
93 | | * @param buf the byte array holding the value |
94 | | * @param length size of buf |
95 | | */ |
96 | | BigInt(const uint8_t buf[], size_t length); |
97 | | |
98 | | /** |
99 | | * Create a BigInt from an integer in a byte array |
100 | | * @param vec the byte vector holding the value |
101 | | */ |
102 | | template<typename Alloc> |
103 | 0 | explicit BigInt(const std::vector<uint8_t, Alloc>& vec) : BigInt(vec.data(), vec.size()) {} Unexecuted instantiation: Botan::BigInt::BigInt<std::__1::allocator<unsigned char> >(std::__1::vector<unsigned char, std::__1::allocator<unsigned char> > const&) Unexecuted instantiation: Botan::BigInt::BigInt<Botan::secure_allocator<unsigned char> >(std::__1::vector<unsigned char, Botan::secure_allocator<unsigned char> > const&) |
104 | | |
105 | | /** |
106 | | * Create a BigInt from an integer in a byte array |
107 | | * @param buf the byte array holding the value |
108 | | * @param length size of buf |
109 | | * @param base is the number base of the integer in buf |
110 | | */ |
111 | | BigInt(const uint8_t buf[], size_t length, Base base); |
112 | | |
113 | | /** |
114 | | * Create a BigInt from an integer in a byte array |
115 | | * @param buf the byte array holding the value |
116 | | * @param length size of buf |
117 | | * @param max_bits if the resulting integer is more than max_bits, |
118 | | * it will be shifted so it is at most max_bits in length. |
119 | | */ |
120 | | static BigInt from_bytes_with_max_bits(const uint8_t buf[], size_t length, |
121 | | size_t max_bits); |
122 | | |
123 | | /** |
124 | | * \brief Create a random BigInt of the specified size |
125 | | * |
126 | | * @param rng random number generator |
127 | | * @param bits size in bits |
128 | | * @param set_high_bit if true, the highest bit is always set |
129 | | * |
130 | | * @see randomize |
131 | | */ |
132 | | BigInt(RandomNumberGenerator& rng, size_t bits, bool set_high_bit = true); |
133 | | |
134 | | /** |
135 | | * Create BigInt of specified size, all zeros |
136 | | * @param n size of the internal register in words |
137 | | */ |
138 | | static BigInt with_capacity(size_t n); |
139 | | |
140 | | /** |
141 | | * Move constructor |
142 | | */ |
143 | | BigInt(BigInt&& other) |
144 | 6.32M | { |
145 | 6.32M | this->swap(other); |
146 | 6.32M | } |
147 | | |
148 | 62.8M | ~BigInt() { const_time_unpoison(); } |
149 | | |
150 | | /** |
151 | | * Move assignment |
152 | | */ |
153 | | BigInt& operator=(BigInt&& other) |
154 | 14.5M | { |
155 | 14.5M | if(this != &other) |
156 | 14.5M | this->swap(other); |
157 | | |
158 | 14.5M | return (*this); |
159 | 14.5M | } |
160 | | |
161 | | /** |
162 | | * Copy assignment |
163 | | */ |
164 | 24.9M | BigInt& operator=(const BigInt&) = default; |
165 | | |
166 | | /** |
167 | | * Swap this value with another |
168 | | * @param other BigInt to swap values with |
169 | | */ |
170 | | void swap(BigInt& other) |
171 | 130M | { |
172 | 130M | m_data.swap(other.m_data); |
173 | 130M | std::swap(m_signedness, other.m_signedness); |
174 | 130M | } |
175 | | |
176 | | void swap_reg(secure_vector<word>& reg) |
177 | 99.3M | { |
178 | 99.3M | m_data.swap(reg); |
179 | | // sign left unchanged |
180 | 99.3M | } |
181 | | |
182 | | /** |
183 | | * += operator |
184 | | * @param y the BigInt to add to this |
185 | | */ |
186 | | BigInt& operator+=(const BigInt& y) |
187 | 3.29M | { |
188 | 3.29M | return add(y.data(), y.sig_words(), y.sign()); |
189 | 3.29M | } |
190 | | |
191 | | /** |
192 | | * += operator |
193 | | * @param y the word to add to this |
194 | | */ |
195 | | BigInt& operator+=(word y) |
196 | 3.93k | { |
197 | 3.93k | return add(&y, 1, Positive); |
198 | 3.93k | } |
199 | | |
200 | | /** |
201 | | * -= operator |
202 | | * @param y the BigInt to subtract from this |
203 | | */ |
204 | | BigInt& operator-=(const BigInt& y) |
205 | 4.50M | { |
206 | 4.50M | return sub(y.data(), y.sig_words(), y.sign()); |
207 | 4.50M | } |
208 | | |
209 | | /** |
210 | | * -= operator |
211 | | * @param y the word to subtract from this |
212 | | */ |
213 | | BigInt& operator-=(word y) |
214 | 2.58k | { |
215 | 2.58k | return sub(&y, 1, Positive); |
216 | 2.58k | } |
217 | | |
218 | | /** |
219 | | * *= operator |
220 | | * @param y the BigInt to multiply with this |
221 | | */ |
222 | | BigInt& operator*=(const BigInt& y); |
223 | | |
224 | | /** |
225 | | * *= operator |
226 | | * @param y the word to multiply with this |
227 | | */ |
228 | | BigInt& operator*=(word y); |
229 | | |
230 | | /** |
231 | | * /= operator |
232 | | * @param y the BigInt to divide this by |
233 | | */ |
234 | | BigInt& operator/=(const BigInt& y); |
235 | | |
236 | | /** |
237 | | * Modulo operator |
238 | | * @param y the modulus to reduce this by |
239 | | */ |
240 | | BigInt& operator%=(const BigInt& y); |
241 | | |
242 | | /** |
243 | | * Modulo operator |
244 | | * @param y the modulus (word) to reduce this by |
245 | | */ |
246 | | word operator%=(word y); |
247 | | |
248 | | /** |
249 | | * Left shift operator |
250 | | * @param shift the number of bits to shift this left by |
251 | | */ |
252 | | BigInt& operator<<=(size_t shift); |
253 | | |
254 | | /** |
255 | | * Right shift operator |
256 | | * @param shift the number of bits to shift this right by |
257 | | */ |
258 | | BigInt& operator>>=(size_t shift); |
259 | | |
260 | | /** |
261 | | * Increment operator |
262 | | */ |
263 | 0 | BigInt& operator++() { return (*this += 1); } |
264 | | |
265 | | /** |
266 | | * Decrement operator |
267 | | */ |
268 | 0 | BigInt& operator--() { return (*this -= 1); } |
269 | | |
270 | | /** |
271 | | * Postfix increment operator |
272 | | */ |
273 | 0 | BigInt operator++(int) { BigInt x = (*this); ++(*this); return x; } |
274 | | |
275 | | /** |
276 | | * Postfix decrement operator |
277 | | */ |
278 | 0 | BigInt operator--(int) { BigInt x = (*this); --(*this); return x; } |
279 | | |
280 | | /** |
281 | | * Unary negation operator |
282 | | * @return negative this |
283 | | */ |
284 | | BigInt operator-() const; |
285 | | |
286 | | /** |
287 | | * ! operator |
288 | | * @return true iff this is zero, otherwise false |
289 | | */ |
290 | 0 | bool operator !() const { return (!is_nonzero()); } |
291 | | |
292 | | static BigInt add2(const BigInt& x, const word y[], size_t y_words, Sign y_sign); |
293 | | |
294 | | BigInt& add(const word y[], size_t y_words, Sign sign); |
295 | | |
296 | | BigInt& sub(const word y[], size_t y_words, Sign sign) |
297 | 4.50M | { |
298 | 4.08M | return add(y, y_words, sign == Positive ? Negative : Positive); |
299 | 4.50M | } |
300 | | |
301 | | /** |
302 | | * Multiply this with y |
303 | | * @param y the BigInt to multiply with this |
304 | | * @param ws a temp workspace |
305 | | */ |
306 | | BigInt& mul(const BigInt& y, secure_vector<word>& ws); |
307 | | |
308 | | /** |
309 | | * Square value of *this |
310 | | * @param ws a temp workspace |
311 | | */ |
312 | | BigInt& square(secure_vector<word>& ws); |
313 | | |
314 | | /** |
315 | | * Set *this to y - *this |
316 | | * @param y the BigInt to subtract from as a sequence of words |
317 | | * @param y_words length of y in words |
318 | | * @param ws a temp workspace |
319 | | */ |
320 | | BigInt& rev_sub(const word y[], size_t y_words, 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 add - assumed y >= 0 and y < mod |
326 | | * @param mod the positive modulus |
327 | | * @param ws a temp workspace |
328 | | */ |
329 | | BigInt& mod_add(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 | | * @param y the BigInt to subtract - assumed y >= 0 and y < mod |
335 | | * @param mod the positive modulus |
336 | | * @param ws a temp workspace |
337 | | */ |
338 | | BigInt& mod_sub(const BigInt& y, const BigInt& mod, secure_vector<word>& ws); |
339 | | |
340 | | /** |
341 | | * Set *this to (*this * y) % mod |
342 | | * This function assumes *this is >= 0 && < mod |
343 | | * y should be small, less than 16 |
344 | | * @param y the small integer to multiply by |
345 | | * @param mod the positive modulus |
346 | | * @param ws a temp workspace |
347 | | */ |
348 | | BigInt& mod_mul(uint8_t y, 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 |
354 | | * mod and performs repeated subtractions. It should not be used if |
355 | | * *this is much larger than mod, instead use modulo operator. |
356 | | */ |
357 | | size_t reduce_below(const BigInt& mod, secure_vector<word> &ws); |
358 | | |
359 | | /** |
360 | | * Return *this % mod |
361 | | * |
362 | | * Assumes that *this is (if anything) only slightly larger than mod and |
363 | | * performs repeated subtractions. It should not be used if *this is much |
364 | | * larger than mod, instead use modulo operator. |
365 | | * |
366 | | * Performs exactly bound subtractions, so if *this is >= bound*mod then the |
367 | | * result will not be fully reduced. If bound is zero, nothing happens. |
368 | | */ |
369 | | void ct_reduce_below(const BigInt& mod, secure_vector<word> &ws, size_t bound); |
370 | | |
371 | | /** |
372 | | * Zeroize the BigInt. The size of the underlying register is not |
373 | | * modified. |
374 | | */ |
375 | 1.46M | void clear() { m_data.set_to_zero(); m_signedness = Positive; } |
376 | | |
377 | | /** |
378 | | * Compare this to another BigInt |
379 | | * @param n the BigInt value to compare with |
380 | | * @param check_signs include sign in comparison? |
381 | | * @result if (this<n) return -1, if (this>n) return 1, if both |
382 | | * values are identical return 0 [like Perl's <=> operator] |
383 | | */ |
384 | | int32_t cmp(const BigInt& n, bool check_signs = true) const; |
385 | | |
386 | | /** |
387 | | * Compare this to another BigInt |
388 | | * @param n the BigInt value to compare with |
389 | | * @result true if this == n or false otherwise |
390 | | */ |
391 | | bool is_equal(const BigInt& n) const; |
392 | | |
393 | | /** |
394 | | * Compare this to another BigInt |
395 | | * @param n the BigInt value to compare with |
396 | | * @result true if this < n or false otherwise |
397 | | */ |
398 | | bool is_less_than(const BigInt& n) const; |
399 | | |
400 | | /** |
401 | | * Compare this to an integer |
402 | | * @param n the value to compare with |
403 | | * @result if (this<n) return -1, if (this>n) return 1, if both |
404 | | * values are identical return 0 [like Perl's <=> operator] |
405 | | */ |
406 | | int32_t cmp_word(word n) const; |
407 | | |
408 | | /** |
409 | | * Test if the integer has an even value |
410 | | * @result true if the integer is even, false otherwise |
411 | | */ |
412 | 186k | bool is_even() const { return (get_bit(0) == 0); } |
413 | | |
414 | | /** |
415 | | * Test if the integer has an odd value |
416 | | * @result true if the integer is odd, false otherwise |
417 | | */ |
418 | 3.86M | bool is_odd() const { return (get_bit(0) == 1); } |
419 | | |
420 | | /** |
421 | | * Test if the integer is not zero |
422 | | * @result true if the integer is non-zero, false otherwise |
423 | | */ |
424 | 6.05M | bool is_nonzero() const { return (!is_zero()); } |
425 | | |
426 | | /** |
427 | | * Test if the integer is zero |
428 | | * @result true if the integer is zero, false otherwise |
429 | | */ |
430 | | bool is_zero() const |
431 | 67.6M | { |
432 | 67.6M | return (sig_words() == 0); |
433 | 67.6M | } |
434 | | |
435 | | /** |
436 | | * Set bit at specified position |
437 | | * @param n bit position to set |
438 | | */ |
439 | | void set_bit(size_t n) |
440 | 388k | { |
441 | 388k | conditionally_set_bit(n, true); |
442 | 388k | } |
443 | | |
444 | | /** |
445 | | * Conditionally set bit at specified position. Note if set_it is |
446 | | * false, nothing happens, and if the bit is already set, it |
447 | | * remains set. |
448 | | * |
449 | | * @param n bit position to set |
450 | | * @param set_it if the bit should be set |
451 | | */ |
452 | | void conditionally_set_bit(size_t n, bool set_it); |
453 | | |
454 | | /** |
455 | | * Clear bit at specified position |
456 | | * @param n bit position to clear |
457 | | */ |
458 | | void clear_bit(size_t n); |
459 | | |
460 | | /** |
461 | | * Clear all but the lowest n bits |
462 | | * @param n amount of bits to keep |
463 | | */ |
464 | | void mask_bits(size_t n) |
465 | 224M | { |
466 | 224M | m_data.mask_bits(n); |
467 | 224M | } |
468 | | |
469 | | /** |
470 | | * Return bit value at specified position |
471 | | * @param n the bit offset to test |
472 | | * @result true, if the bit at position n is set, false otherwise |
473 | | */ |
474 | | bool get_bit(size_t n) const |
475 | 53.2M | { |
476 | 53.2M | return ((word_at(n / BOTAN_MP_WORD_BITS) >> (n % BOTAN_MP_WORD_BITS)) & 1); |
477 | 53.2M | } |
478 | | |
479 | | /** |
480 | | * Return (a maximum of) 32 bits of the complete value |
481 | | * @param offset the offset to start extracting |
482 | | * @param length amount of bits to extract (starting at offset) |
483 | | * @result the integer extracted from the register starting at |
484 | | * offset with specified length |
485 | | */ |
486 | | uint32_t get_substring(size_t offset, size_t length) const; |
487 | | |
488 | | /** |
489 | | * Convert this value into a uint32_t, if it is in the range |
490 | | * [0 ... 2**32-1], or otherwise throw an exception. |
491 | | * @result the value as a uint32_t if conversion is possible |
492 | | */ |
493 | | uint32_t to_u32bit() const; |
494 | | |
495 | | /** |
496 | | * Convert this value to a decimal string. |
497 | | * Warning: decimal conversions are relatively slow |
498 | | */ |
499 | | std::string to_dec_string() const; |
500 | | |
501 | | /** |
502 | | * Convert this value to a hexadecimal string. |
503 | | */ |
504 | | std::string to_hex_string() const; |
505 | | |
506 | | /** |
507 | | * @param n the offset to get a byte from |
508 | | * @result byte at offset n |
509 | | */ |
510 | | uint8_t byte_at(size_t n) const; |
511 | | |
512 | | /** |
513 | | * Return the word at a specified position of the internal register |
514 | | * @param n position in the register |
515 | | * @return value at position n |
516 | | */ |
517 | | word word_at(size_t n) const |
518 | 1.41G | { |
519 | 1.41G | return m_data.get_word_at(n); |
520 | 1.41G | } |
521 | | |
522 | | void set_word_at(size_t i, word w) |
523 | 123M | { |
524 | 123M | m_data.set_word_at(i, w); |
525 | 123M | } |
526 | | |
527 | | void set_words(const word w[], size_t len) |
528 | 12.4M | { |
529 | 12.4M | m_data.set_words(w, len); |
530 | 12.4M | } |
531 | | |
532 | | /** |
533 | | * Tests if the sign of the integer is negative |
534 | | * @result true, iff the integer has a negative sign |
535 | | */ |
536 | 663M | bool is_negative() const { return (sign() == Negative); } |
537 | | |
538 | | /** |
539 | | * Tests if the sign of the integer is positive |
540 | | * @result true, iff the integer has a positive sign |
541 | | */ |
542 | 12.2M | bool is_positive() const { return (sign() == Positive); } |
543 | | |
544 | | /** |
545 | | * Return the sign of the integer |
546 | | * @result the sign of the integer |
547 | | */ |
548 | 779M | Sign sign() const { return (m_signedness); } |
549 | | |
550 | | /** |
551 | | * @result the opposite sign of the represented integer value |
552 | | */ |
553 | | Sign reverse_sign() const |
554 | 1.96M | { |
555 | 1.96M | if(sign() == Positive) |
556 | 1.96M | return Negative; |
557 | 998 | return Positive; |
558 | 998 | } |
559 | | |
560 | | /** |
561 | | * Flip the sign of this BigInt |
562 | | */ |
563 | | void flip_sign() |
564 | 18.6k | { |
565 | 18.6k | set_sign(reverse_sign()); |
566 | 18.6k | } |
567 | | |
568 | | /** |
569 | | * Set sign of the integer |
570 | | * @param sign new Sign to set |
571 | | */ |
572 | | void set_sign(Sign sign) |
573 | 54.0M | { |
574 | 54.0M | if(sign == Negative && is_zero()) |
575 | 1.18k | sign = Positive; |
576 | | |
577 | 54.0M | m_signedness = sign; |
578 | 54.0M | } |
579 | | |
580 | | /** |
581 | | * @result absolute (positive) value of this |
582 | | */ |
583 | | BigInt abs() const; |
584 | | |
585 | | /** |
586 | | * Give size of internal register |
587 | | * @result size of internal register in words |
588 | | */ |
589 | 2.01G | size_t size() const { return m_data.size(); } |
590 | | |
591 | | /** |
592 | | * Return how many words we need to hold this value |
593 | | * @result significant words of the represented integer value |
594 | | */ |
595 | | size_t sig_words() const |
596 | 395M | { |
597 | 395M | return m_data.sig_words(); |
598 | 395M | } |
599 | | |
600 | | /** |
601 | | * Give byte length of the integer |
602 | | * @result byte length of the represented integer value |
603 | | */ |
604 | | size_t bytes() const; |
605 | | |
606 | | /** |
607 | | * Get the bit length of the integer |
608 | | * @result bit length of the represented integer value |
609 | | */ |
610 | | size_t bits() const; |
611 | | |
612 | | /** |
613 | | * Get the number of high bits unset in the top (allocated) word |
614 | | * of this integer. Returns BOTAN_MP_WORD_BITS only iff *this is |
615 | | * zero. Ignores sign. |
616 | | */ |
617 | | size_t top_bits_free() const; |
618 | | |
619 | | /** |
620 | | * Return a mutable pointer to the register |
621 | | * @result a pointer to the start of the internal register |
622 | | */ |
623 | 1.34G | word* mutable_data() { return m_data.mutable_data(); } |
624 | | |
625 | | /** |
626 | | * Return a const pointer to the register |
627 | | * @result a pointer to the start of the internal register |
628 | | */ |
629 | 1.62G | const word* data() const { return m_data.const_data(); } |
630 | | |
631 | | /** |
632 | | * Don't use this function in application code |
633 | | */ |
634 | 58.4M | secure_vector<word>& get_word_vector() { return m_data.mutable_vector(); } |
635 | | |
636 | | /** |
637 | | * Don't use this function in application code |
638 | | */ |
639 | 2.08M | const secure_vector<word>& get_word_vector() const { return m_data.const_vector(); } |
640 | | |
641 | | /** |
642 | | * Increase internal register buffer to at least n words |
643 | | * @param n new size of register |
644 | | */ |
645 | 657M | void grow_to(size_t n) const { m_data.grow_to(n); } |
646 | | |
647 | 435k | 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 | 430k | { |
694 | 430k | binary_decode(buf.data(), buf.size()); |
695 | 430k | } |
696 | | |
697 | | /** |
698 | | * Place the value into out, zero-padding up to size words |
699 | | * Throw if *this cannot be represented in size words |
700 | | */ |
701 | | void encode_words(word out[], size_t size) const; |
702 | | |
703 | | /** |
704 | | * If predicate is true assign other to *this |
705 | | * Uses a masked operation to avoid side channels |
706 | | */ |
707 | | void ct_cond_assign(bool predicate, const BigInt& other); |
708 | | |
709 | | /** |
710 | | * If predicate is true swap *this and other |
711 | | * Uses a masked operation to avoid side channels |
712 | | */ |
713 | | void ct_cond_swap(bool predicate, BigInt& other); |
714 | | |
715 | | /** |
716 | | * If predicate is true add value to *this |
717 | | */ |
718 | | void ct_cond_add(bool predicate, const BigInt& value); |
719 | | |
720 | | /** |
721 | | * If predicate is true flip the sign of *this |
722 | | */ |
723 | | void cond_flip_sign(bool predicate); |
724 | | |
725 | | #if defined(BOTAN_HAS_VALGRIND) |
726 | | void const_time_poison() const; |
727 | | void const_time_unpoison() const; |
728 | | #else |
729 | 30.8k | void const_time_poison() const {} |
730 | 62.9M | void const_time_unpoison() const {} |
731 | | #endif |
732 | | |
733 | | /** |
734 | | * @param rng a random number generator |
735 | | * @param min the minimum value (must be non-negative) |
736 | | * @param max the maximum value (must be non-negative and > min) |
737 | | * @return random integer in [min,max) |
738 | | */ |
739 | | static BigInt random_integer(RandomNumberGenerator& rng, |
740 | | const BigInt& min, |
741 | | const BigInt& max); |
742 | | |
743 | | /** |
744 | | * Create a power of two |
745 | | * @param n the power of two to create |
746 | | * @return bigint representing 2^n |
747 | | */ |
748 | | static BigInt power_of_2(size_t n) |
749 | 72.4k | { |
750 | 72.4k | BigInt b; |
751 | 72.4k | b.set_bit(n); |
752 | 72.4k | return b; |
753 | 72.4k | } |
754 | | |
755 | | /** |
756 | | * Encode the integer value from a BigInt to a std::vector of bytes |
757 | | * @param n the BigInt to use as integer source |
758 | | * @result secure_vector of bytes containing the bytes of the integer |
759 | | */ |
760 | | static std::vector<uint8_t> encode(const BigInt& n) |
761 | 26.9k | { |
762 | 26.9k | std::vector<uint8_t> output(n.bytes()); |
763 | 26.9k | n.binary_encode(output.data()); |
764 | 26.9k | return output; |
765 | 26.9k | } |
766 | | |
767 | | /** |
768 | | * Encode the integer value from a BigInt to a secure_vector of bytes |
769 | | * @param n the BigInt to use as integer source |
770 | | * @result secure_vector of bytes containing the bytes of the integer |
771 | | */ |
772 | | static secure_vector<uint8_t> encode_locked(const BigInt& n) |
773 | 6.34k | { |
774 | 6.34k | secure_vector<uint8_t> output(n.bytes()); |
775 | 6.34k | n.binary_encode(output.data()); |
776 | 6.34k | return output; |
777 | 6.34k | } |
778 | | |
779 | | /** |
780 | | * Create a BigInt from an integer in a byte array |
781 | | * @param buf the binary value to load |
782 | | * @param length size of buf |
783 | | * @result BigInt representing the integer in the byte array |
784 | | */ |
785 | | static BigInt decode(const uint8_t buf[], size_t length) |
786 | 42.7k | { |
787 | 42.7k | return BigInt(buf, length); |
788 | 42.7k | } |
789 | | |
790 | | /** |
791 | | * Create a BigInt from an integer in a byte array |
792 | | * @param buf the binary value to load |
793 | | * @result BigInt representing the integer in the byte array |
794 | | */ |
795 | | template<typename Alloc> |
796 | | static BigInt decode(const std::vector<uint8_t, Alloc>& buf) |
797 | 0 | { |
798 | 0 | return BigInt(buf); |
799 | 0 | } Unexecuted instantiation: Botan::BigInt Botan::BigInt::decode<std::__1::allocator<unsigned char> >(std::__1::vector<unsigned char, std::__1::allocator<unsigned char> > const&) Unexecuted instantiation: Botan::BigInt Botan::BigInt::decode<Botan::secure_allocator<unsigned char> >(std::__1::vector<unsigned char, Botan::secure_allocator<unsigned char> > const&) |
800 | | |
801 | | /** |
802 | | * Create a BigInt from an integer in a byte array |
803 | | * @param buf the binary value to load |
804 | | * @param length size of buf |
805 | | * @param base number-base of the integer in buf |
806 | | * @result BigInt representing the integer in the byte array |
807 | | */ |
808 | | static BigInt decode(const uint8_t buf[], size_t length, |
809 | | Base base); |
810 | | |
811 | | /** |
812 | | * Create a BigInt from an integer in a byte array |
813 | | * @param buf the binary value to load |
814 | | * @param base number-base of the integer in buf |
815 | | * @result BigInt representing the integer in the byte array |
816 | | */ |
817 | | template<typename Alloc> |
818 | | static BigInt decode(const std::vector<uint8_t, Alloc>& buf, Base base) |
819 | | { |
820 | | if(base == Binary) |
821 | | return BigInt(buf); |
822 | | return BigInt::decode(buf.data(), buf.size(), base); |
823 | | } |
824 | | |
825 | | /** |
826 | | * Encode a BigInt to a byte array according to IEEE 1363 |
827 | | * @param n the BigInt to encode |
828 | | * @param bytes the length of the resulting secure_vector<uint8_t> |
829 | | * @result a secure_vector<uint8_t> containing the encoded BigInt |
830 | | */ |
831 | | static secure_vector<uint8_t> encode_1363(const BigInt& n, size_t bytes); |
832 | | |
833 | | static void encode_1363(uint8_t out[], size_t bytes, const BigInt& n); |
834 | | |
835 | | /** |
836 | | * Encode two BigInt to a byte array according to IEEE 1363 |
837 | | * @param n1 the first BigInt to encode |
838 | | * @param n2 the second BigInt to encode |
839 | | * @param bytes the length of the encoding of each single BigInt |
840 | | * @result a secure_vector<uint8_t> containing the concatenation of the two encoded BigInt |
841 | | */ |
842 | | static secure_vector<uint8_t> encode_fixed_length_int_pair(const BigInt& n1, const BigInt& n2, size_t bytes); |
843 | | |
844 | | private: |
845 | | |
846 | | class Data |
847 | | { |
848 | | public: |
849 | | word* mutable_data() |
850 | 1.37G | { |
851 | 1.37G | invalidate_sig_words(); |
852 | 1.37G | return m_reg.data(); |
853 | 1.37G | } |
854 | | |
855 | | const word* const_data() const |
856 | 1.62G | { |
857 | 1.62G | return m_reg.data(); |
858 | 1.62G | } |
859 | | |
860 | | secure_vector<word>& mutable_vector() |
861 | 58.4M | { |
862 | 58.4M | invalidate_sig_words(); |
863 | 58.4M | return m_reg; |
864 | 58.4M | } |
865 | | |
866 | | const secure_vector<word>& const_vector() const |
867 | 2.08M | { |
868 | 2.08M | return m_reg; |
869 | 2.08M | } |
870 | | |
871 | | word get_word_at(size_t n) const |
872 | 1.41G | { |
873 | 1.41G | if(n < m_reg.size()) |
874 | 1.40G | return m_reg[n]; |
875 | 2.73M | return 0; |
876 | 2.73M | } |
877 | | |
878 | | void set_word_at(size_t i, word w) |
879 | 217M | { |
880 | 217M | invalidate_sig_words(); |
881 | 217M | if(i >= m_reg.size()) |
882 | 99.8M | { |
883 | 99.8M | if(w == 0) |
884 | 99.1M | return; |
885 | 671k | grow_to(i + 1); |
886 | 671k | } |
887 | 118M | m_reg[i] = w; |
888 | 118M | } |
889 | | |
890 | | void set_words(const word w[], size_t len) |
891 | 12.4M | { |
892 | 12.4M | invalidate_sig_words(); |
893 | 12.4M | m_reg.assign(w, w + len); |
894 | 12.4M | } |
895 | | |
896 | | void set_to_zero() |
897 | 1.46M | { |
898 | 1.46M | m_reg.resize(m_reg.capacity()); |
899 | 1.46M | clear_mem(m_reg.data(), m_reg.size()); |
900 | 1.46M | m_sig_words = 0; |
901 | 1.46M | } |
902 | | |
903 | | void set_size(size_t s) |
904 | 0 | { |
905 | 0 | invalidate_sig_words(); |
906 | 0 | clear_mem(m_reg.data(), m_reg.size()); |
907 | 0 | m_reg.resize(s + (8 - (s % 8))); |
908 | 0 | } |
909 | | |
910 | | void mask_bits(size_t n) |
911 | 224M | { |
912 | 224M | if(n == 0) { return set_to_zero(); } |
913 | | |
914 | 224M | const size_t top_word = n / BOTAN_MP_WORD_BITS; |
915 | | |
916 | | // if(top_word < sig_words()) ? |
917 | 224M | if(top_word < size()) |
918 | 224M | { |
919 | 224M | const word mask = (static_cast<word>(1) << (n % BOTAN_MP_WORD_BITS)) - 1; |
920 | 224M | const size_t len = size() - (top_word + 1); |
921 | 224M | if(len > 0) |
922 | 224M | { |
923 | 224M | clear_mem(&m_reg[top_word+1], len); |
924 | 224M | } |
925 | 224M | m_reg[top_word] &= mask; |
926 | 224M | invalidate_sig_words(); |
927 | 224M | } |
928 | 224M | } |
929 | | |
930 | | void grow_to(size_t n) const |
931 | 662M | { |
932 | 662M | if(n > size()) |
933 | 44.0M | { |
934 | 44.0M | if(n <= m_reg.capacity()) |
935 | 17.0M | m_reg.resize(n); |
936 | 27.0M | else |
937 | 27.0M | m_reg.resize(n + (8 - (n % 8))); |
938 | 44.0M | } |
939 | 662M | } |
940 | | |
941 | 3.15G | size_t size() const { return m_reg.size(); } |
942 | | |
943 | | void shrink_to_fit(size_t min_size = 0) |
944 | 0 | { |
945 | 0 | const size_t words = std::max(min_size, sig_words()); |
946 | 0 | m_reg.resize(words); |
947 | 0 | } |
948 | | |
949 | | void resize(size_t s) |
950 | 435k | { |
951 | 435k | m_reg.resize(s); |
952 | 435k | } |
953 | | |
954 | | void swap(Data& other) |
955 | 130M | { |
956 | 130M | m_reg.swap(other.m_reg); |
957 | 130M | std::swap(m_sig_words, other.m_sig_words); |
958 | 130M | } |
959 | | |
960 | | void swap(secure_vector<word>& reg) |
961 | 99.8M | { |
962 | 99.8M | m_reg.swap(reg); |
963 | 99.8M | invalidate_sig_words(); |
964 | 99.8M | } |
965 | | |
966 | | void invalidate_sig_words() const |
967 | 1.98G | { |
968 | 1.98G | m_sig_words = sig_words_npos; |
969 | 1.98G | } |
970 | | |
971 | | size_t sig_words() const |
972 | 395M | { |
973 | 395M | if(m_sig_words == sig_words_npos) |
974 | 126M | { |
975 | 126M | m_sig_words = calc_sig_words(); |
976 | 126M | } |
977 | 269M | else |
978 | 269M | { |
979 | 269M | BOTAN_DEBUG_ASSERT(m_sig_words == calc_sig_words()); |
980 | 269M | } |
981 | 395M | return m_sig_words; |
982 | 395M | } |
983 | | private: |
984 | | static const size_t sig_words_npos = static_cast<size_t>(-1); |
985 | | |
986 | | size_t calc_sig_words() const; |
987 | | |
988 | | mutable secure_vector<word> m_reg; |
989 | | mutable size_t m_sig_words = sig_words_npos; |
990 | | }; |
991 | | |
992 | | Data m_data; |
993 | | Sign m_signedness = Positive; |
994 | | }; |
995 | | |
996 | | /* |
997 | | * Arithmetic Operators |
998 | | */ |
999 | | inline BigInt operator+(const BigInt& x, const BigInt& y) |
1000 | 646k | { |
1001 | 646k | return BigInt::add2(x, y.data(), y.sig_words(), y.sign()); |
1002 | 646k | } |
1003 | | |
1004 | | inline BigInt operator+(const BigInt& x, word y) |
1005 | 15.8k | { |
1006 | 15.8k | return BigInt::add2(x, &y, 1, BigInt::Positive); |
1007 | 15.8k | } |
1008 | | |
1009 | | inline BigInt operator+(word x, const BigInt& y) |
1010 | 0 | { |
1011 | 0 | return y + x; |
1012 | 0 | } |
1013 | | |
1014 | | inline BigInt operator-(const BigInt& x, const BigInt& y) |
1015 | 1.94M | { |
1016 | 1.94M | return BigInt::add2(x, y.data(), y.sig_words(), y.reverse_sign()); |
1017 | 1.94M | } |
1018 | | |
1019 | | inline BigInt operator-(const BigInt& x, word y) |
1020 | 3.70k | { |
1021 | 3.70k | return BigInt::add2(x, &y, 1, BigInt::Negative); |
1022 | 3.70k | } |
1023 | | |
1024 | | BigInt BOTAN_PUBLIC_API(2,0) operator*(const BigInt& x, const BigInt& y); |
1025 | | BigInt BOTAN_PUBLIC_API(2,8) operator*(const BigInt& x, word y); |
1026 | 5.30M | inline BigInt operator*(word x, const BigInt& y) { return y*x; } |
1027 | | |
1028 | | BigInt BOTAN_PUBLIC_API(2,0) operator/(const BigInt& x, const BigInt& d); |
1029 | | BigInt BOTAN_PUBLIC_API(2,0) operator/(const BigInt& x, word m); |
1030 | | BigInt BOTAN_PUBLIC_API(2,0) operator%(const BigInt& x, const BigInt& m); |
1031 | | word BOTAN_PUBLIC_API(2,0) operator%(const BigInt& x, word m); |
1032 | | BigInt BOTAN_PUBLIC_API(2,0) operator<<(const BigInt& x, size_t n); |
1033 | | BigInt BOTAN_PUBLIC_API(2,0) operator>>(const BigInt& x, size_t n); |
1034 | | |
1035 | | /* |
1036 | | * Comparison Operators |
1037 | | */ |
1038 | | inline bool operator==(const BigInt& a, const BigInt& b) |
1039 | 172k | { return a.is_equal(b); } |
1040 | | inline bool operator!=(const BigInt& a, const BigInt& b) |
1041 | 59.9k | { return !a.is_equal(b); } |
1042 | | inline bool operator<=(const BigInt& a, const BigInt& b) |
1043 | 78.6k | { return (a.cmp(b) <= 0); } |
1044 | | inline bool operator>=(const BigInt& a, const BigInt& b) |
1045 | 584k | { return (a.cmp(b) >= 0); } |
1046 | | inline bool operator<(const BigInt& a, const BigInt& b) |
1047 | 3.15M | { return a.is_less_than(b); } |
1048 | | inline bool operator>(const BigInt& a, const BigInt& b) |
1049 | 2.73M | { return b.is_less_than(a); } |
1050 | | |
1051 | | inline bool operator==(const BigInt& a, word b) |
1052 | 245k | { return (a.cmp_word(b) == 0); } |
1053 | | inline bool operator!=(const BigInt& a, word b) |
1054 | 2.68M | { return (a.cmp_word(b) != 0); } |
1055 | | inline bool operator<=(const BigInt& a, word b) |
1056 | 26.4k | { return (a.cmp_word(b) <= 0); } |
1057 | | inline bool operator>=(const BigInt& a, word b) |
1058 | 383 | { return (a.cmp_word(b) >= 0); } |
1059 | | inline bool operator<(const BigInt& a, word b) |
1060 | 174k | { return (a.cmp_word(b) < 0); } |
1061 | | inline bool operator>(const BigInt& a, word b) |
1062 | 3.40M | { return (a.cmp_word(b) > 0); } |
1063 | | |
1064 | | /* |
1065 | | * I/O Operators |
1066 | | */ |
1067 | | BOTAN_PUBLIC_API(2,0) std::ostream& operator<<(std::ostream&, const BigInt&); |
1068 | | BOTAN_PUBLIC_API(2,0) std::istream& operator>>(std::istream&, BigInt&); |
1069 | | |
1070 | | } |
1071 | | |
1072 | | namespace std { |
1073 | | |
1074 | | template<> |
1075 | | inline void swap<Botan::BigInt>(Botan::BigInt& x, Botan::BigInt& y) |
1076 | 2.73M | { |
1077 | 2.73M | x.swap(y); |
1078 | 2.73M | } |
1079 | | |
1080 | | } |
1081 | | |
1082 | | #endif |