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