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