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