diff options
Diffstat (limited to 'src/libs/3rdparty/botan/src/lib/math/bigint/bigint.h')
| -rw-r--r-- | src/libs/3rdparty/botan/src/lib/math/bigint/bigint.h | 901 |
1 files changed, 0 insertions, 901 deletions
diff --git a/src/libs/3rdparty/botan/src/lib/math/bigint/bigint.h b/src/libs/3rdparty/botan/src/lib/math/bigint/bigint.h deleted file mode 100644 index 8a434e6bb6..0000000000 --- a/src/libs/3rdparty/botan/src/lib/math/bigint/bigint.h +++ /dev/null @@ -1,901 +0,0 @@ -/* -* BigInt -* (C) 1999-2008,2012 Jack Lloyd -* 2007 FlexSecure -* -* Botan is released under the Simplified BSD License (see license.txt) -*/ - -#ifndef BOTAN_BIGINT_H_ -#define BOTAN_BIGINT_H_ - -#include <botan/types.h> -#include <botan/secmem.h> -#include <botan/exceptn.h> -#include <botan/loadstor.h> -#include <iosfwd> - -namespace Botan { - -class RandomNumberGenerator; - -/** -* Arbitrary precision integer -*/ -class BOTAN_PUBLIC_API(2,0) BigInt final - { - public: - /** - * Base enumerator for encoding and decoding - */ - enum Base { Decimal = 10, Hexadecimal = 16, Binary = 256 }; - - /** - * Sign symbol definitions for positive and negative numbers - */ - enum Sign { Negative = 0, Positive = 1 }; - - /** - * DivideByZero Exception - */ - class BOTAN_PUBLIC_API(2,0) DivideByZero final : public Exception - { - public: - DivideByZero() : Exception("BigInt divide by zero") {} - }; - - /** - * Create empty BigInt - */ - BigInt() = default; - - /** - * Create BigInt from 64 bit integer - * @param n initial value of this BigInt - */ - BigInt(uint64_t n); - - /** - * Copy Constructor - * @param other the BigInt to copy - */ - BigInt(const BigInt& other); - - /** - * Create BigInt from a string. If the string starts with 0x the - * rest of the string will be interpreted as hexadecimal digits. - * Otherwise, it will be interpreted as a decimal number. - * - * @param str the string to parse for an integer value - */ - explicit BigInt(const std::string& str); - - /** - * Create a BigInt from an integer in a byte array - * @param buf the byte array holding the value - * @param length size of buf - */ - BigInt(const uint8_t buf[], size_t length); - - /** - * Create a BigInt from an integer in a byte array - * @param vec the byte vector holding the value - */ - template<typename Alloc> - explicit BigInt(const std::vector<uint8_t, Alloc>& vec) : BigInt(vec.data(), vec.size()) {} - - /** - * Create a BigInt from an integer in a byte array - * @param buf the byte array holding the value - * @param length size of buf - * @param base is the number base of the integer in buf - */ - BigInt(const uint8_t buf[], size_t length, Base base); - - /** - * Create a BigInt from an integer in a byte array - * @param buf the byte array holding the value - * @param length size of buf - * @param max_bits if the resulting integer is more than max_bits, - * it will be shifted so it is at most max_bits in length. - */ - BigInt(const uint8_t buf[], size_t length, size_t max_bits); - - /** - * Create a BigInt from an array of words - * @param words the words - * @param length number of words - */ - BigInt(const word words[], size_t length); - - /** - * \brief Create a random BigInt of the specified size - * - * @param rng random number generator - * @param bits size in bits - * @param set_high_bit if true, the highest bit is always set - * - * @see randomize - */ - BigInt(RandomNumberGenerator& rng, size_t bits, bool set_high_bit = true); - - /** - * Create BigInt of specified size, all zeros - * @param sign the sign - * @param n size of the internal register in words - */ - BigInt(Sign sign, size_t n); - - /** - * Move constructor - */ - BigInt(BigInt&& other) - { - this->swap(other); - } - - /** - * Move assignment - */ - BigInt& operator=(BigInt&& other) - { - if(this != &other) - this->swap(other); - - return (*this); - } - - /** - * Copy assignment - */ - BigInt& operator=(const BigInt&) = default; - - /** - * Swap this value with another - * @param other BigInt to swap values with - */ - void swap(BigInt& other) - { - m_reg.swap(other.m_reg); - std::swap(m_signedness, other.m_signedness); - } - - void swap_reg(secure_vector<word>& reg) - { - m_reg.swap(reg); - } - - /** - * += operator - * @param y the BigInt to add to this - */ - BigInt& operator+=(const BigInt& y); - - /** - * += operator - * @param y the word to add to this - */ - BigInt& operator+=(word y); - - /** - * -= operator - * @param y the BigInt to subtract from this - */ - BigInt& operator-=(const BigInt& y); - - /** - * -= operator - * @param y the word to subtract from this - */ - BigInt& operator-=(word y); - - /** - * *= operator - * @param y the BigInt to multiply with this - */ - BigInt& operator*=(const BigInt& y); - - /** - * *= operator - * @param y the word to multiply with this - */ - BigInt& operator*=(word y); - - /** - * /= operator - * @param y the BigInt to divide this by - */ - BigInt& operator/=(const BigInt& y); - - /** - * Modulo operator - * @param y the modulus to reduce this by - */ - BigInt& operator%=(const BigInt& y); - - /** - * Modulo operator - * @param y the modulus (word) to reduce this by - */ - word operator%=(word y); - - /** - * Left shift operator - * @param shift the number of bits to shift this left by - */ - BigInt& operator<<=(size_t shift); - - /** - * Right shift operator - * @param shift the number of bits to shift this right by - */ - BigInt& operator>>=(size_t shift); - - /** - * Increment operator - */ - BigInt& operator++() { return (*this += 1); } - - /** - * Decrement operator - */ - BigInt& operator--() { return (*this -= 1); } - - /** - * Postfix increment operator - */ - BigInt operator++(int) { BigInt x = (*this); ++(*this); return x; } - - /** - * Postfix decrement operator - */ - BigInt operator--(int) { BigInt x = (*this); --(*this); return x; } - - /** - * Unary negation operator - * @return negative this - */ - BigInt operator-() const; - - /** - * ! operator - * @return true iff this is zero, otherwise false - */ - bool operator !() const { return (!is_nonzero()); } - - BigInt& add(const word y[], size_t y_words, Sign sign); - BigInt& sub(const word y[], size_t y_words, Sign sign); - - /** - * Multiply this with y - * @param y the BigInt to multiply with this - * @param ws a temp workspace - */ - BigInt& mul(const BigInt& y, secure_vector<word>& ws); - - /** - * Square value of *this - * @param ws a temp workspace - */ - BigInt& square(secure_vector<word>& ws); - - /** - * Set *this to y - *this - * @param y the BigInt to subtract from as a sequence of words - * @param y_size length of y in words - * @param ws a temp workspace - */ - BigInt& rev_sub(const word y[], size_t y_size, secure_vector<word>& ws); - - /** - * Set *this to (*this + y) % mod - * This function assumes *this is >= 0 && < mod - * @param y the BigInt to add - assumed y >= 0 and y < mod - * @param mod the positive modulus - * @param ws a temp workspace - */ - BigInt& mod_add(const BigInt& y, const BigInt& mod, secure_vector<word>& ws); - - /** - * Set *this to (*this - y) % mod - * This function assumes *this is >= 0 && < mod - * @param y the BigInt to subtract - assumed y >= 0 and y < mod - * @param mod the positive modulus - * @param ws a temp workspace - */ - BigInt& mod_sub(const BigInt& y, const BigInt& mod, secure_vector<word>& ws); - - /** - * Return *this below mod - * - * Assumes that *this is (if anything) only slightly larger than - * mod and performs repeated subtractions. It should not be used if - * *this is much larger than mod, instead of modulo operator. - */ - void reduce_below(const BigInt& mod, secure_vector<word> &ws); - - /** - * Zeroize the BigInt. The size of the underlying register is not - * modified. - */ - void clear() { zeroise(m_reg); } - - /** - * Compare this to another BigInt - * @param n the BigInt value to compare with - * @param check_signs include sign in comparison? - * @result if (this<n) return -1, if (this>n) return 1, if both - * values are identical return 0 [like Perl's <=> operator] - */ - int32_t cmp(const BigInt& n, bool check_signs = true) const; - - /** - * Compare this to an integer - * @param n the value to compare with - * @result if (this<n) return -1, if (this>n) return 1, if both - * values are identical return 0 [like Perl's <=> operator] - */ - int32_t cmp_word(word n) const; - - /** - * Test if the integer has an even value - * @result true if the integer is even, false otherwise - */ - bool is_even() const { return (get_bit(0) == 0); } - - /** - * Test if the integer has an odd value - * @result true if the integer is odd, false otherwise - */ - bool is_odd() const { return (get_bit(0) == 1); } - - /** - * Test if the integer is not zero - * @result true if the integer is non-zero, false otherwise - */ - bool is_nonzero() const { return (!is_zero()); } - - /** - * Test if the integer is zero - * @result true if the integer is zero, false otherwise - */ - bool is_zero() const - { - const size_t sw = sig_words(); - - for(size_t i = 0; i != sw; ++i) - if(m_reg[i]) - return false; - return true; - } - - /** - * Set bit at specified position - * @param n bit position to set - */ - void set_bit(size_t n); - - /** - * Clear bit at specified position - * @param n bit position to clear - */ - void clear_bit(size_t n); - - /** - * Clear all but the lowest n bits - * @param n amount of bits to keep - */ - void mask_bits(size_t n) - { - if(n == 0) { clear(); return; } - - const size_t top_word = n / BOTAN_MP_WORD_BITS; - const word mask = (static_cast<word>(1) << (n % BOTAN_MP_WORD_BITS)) - 1; - - if(top_word < size()) - { - const size_t len = size() - (top_word + 1); - if (len > 0) - { - clear_mem(&m_reg[top_word+1], len); - } - m_reg[top_word] &= mask; - } - } - - /** - * Return bit value at specified position - * @param n the bit offset to test - * @result true, if the bit at position n is set, false otherwise - */ - bool get_bit(size_t n) const - { - return ((word_at(n / BOTAN_MP_WORD_BITS) >> (n % BOTAN_MP_WORD_BITS)) & 1); - } - - /** - * Return (a maximum of) 32 bits of the complete value - * @param offset the offset to start extracting - * @param length amount of bits to extract (starting at offset) - * @result the integer extracted from the register starting at - * offset with specified length - */ - uint32_t get_substring(size_t offset, size_t length) const; - - /** - * Convert this value into a uint32_t, if it is in the range - * [0 ... 2**32-1], or otherwise throw an exception. - * @result the value as a uint32_t if conversion is possible - */ - uint32_t to_u32bit() const; - - /** - * Convert this value to a decimal string. - * Warning: decimal conversions are relatively slow - */ - std::string to_dec_string() const; - - /** - * Convert this value to a hexadecimal string. - */ - std::string to_hex_string() const; - - /** - * @param n the offset to get a byte from - * @result byte at offset n - */ - uint8_t byte_at(size_t n) const - { - return get_byte(sizeof(word) - (n % sizeof(word)) - 1, - word_at(n / sizeof(word))); - } - - /** - * Return the word at a specified position of the internal register - * @param n position in the register - * @return value at position n - */ - word word_at(size_t n) const - { return ((n < size()) ? m_reg[n] : 0); } - - void set_word_at(size_t i, word w) - { - if(i >= m_reg.size()) - grow_to(i + 1); - m_reg[i] = w; - } - - void set_words(const word w[], size_t len) - { - m_reg.resize(len); - copy_mem(mutable_data(), w, len); - } - - /** - * Tests if the sign of the integer is negative - * @result true, iff the integer has a negative sign - */ - bool is_negative() const { return (sign() == Negative); } - - /** - * Tests if the sign of the integer is positive - * @result true, iff the integer has a positive sign - */ - bool is_positive() const { return (sign() == Positive); } - - /** - * Return the sign of the integer - * @result the sign of the integer - */ - Sign sign() const { return (m_signedness); } - - /** - * @result the opposite sign of the represented integer value - */ - Sign reverse_sign() const - { - if(sign() == Positive) - return Negative; - return Positive; - } - - /** - * Flip the sign of this BigInt - */ - void flip_sign() - { - set_sign(reverse_sign()); - } - - /** - * Set sign of the integer - * @param sign new Sign to set - */ - void set_sign(Sign sign) - { - if(is_zero()) - m_signedness = Positive; - else - m_signedness = sign; - } - - /** - * @result absolute (positive) value of this - */ - BigInt abs() const; - - /** - * Give size of internal register - * @result size of internal register in words - */ - size_t size() const { return m_reg.size(); } - - /** - * Return how many words we need to hold this value - * @result significant words of the represented integer value - */ - size_t sig_words() const - { - const word* x = m_reg.data(); - size_t sig = m_reg.size(); - - while(sig && (x[sig-1] == 0)) - sig--; - return sig; - } - - /** - * Give byte length of the integer - * @result byte length of the represented integer value - */ - size_t bytes() const; - - /** - * Get the bit length of the integer - * @result bit length of the represented integer value - */ - size_t bits() const; - - /** - * Return a mutable pointer to the register - * @result a pointer to the start of the internal register - */ - word* mutable_data() { return m_reg.data(); } - - /** - * Return a const pointer to the register - * @result a pointer to the start of the internal register - */ - const word* data() const { return m_reg.data(); } - - secure_vector<word>& get_word_vector() { return m_reg; } - const secure_vector<word>& get_word_vector() const { return m_reg; } - - /** - * Increase internal register buffer to at least n words - * @param n new size of register - */ - void grow_to(size_t n); - - /** - * Resize the vector to the minimum word size to hold the integer, or - * min_size words, whichever is larger - */ - void shrink_to_fit(size_t min_size = 0) - { - const size_t words = std::max(min_size, sig_words()); - m_reg.resize(words); - } - - /** - * Fill BigInt with a random number with size of bitsize - * - * If \p set_high_bit is true, the highest bit will be set, which causes - * the entropy to be \a bits-1. Otherwise the highest bit is randomly chosen - * by the rng, causing the entropy to be \a bits. - * - * @param rng the random number generator to use - * @param bitsize number of bits the created random value should have - * @param set_high_bit if true, the highest bit is always set - */ - void randomize(RandomNumberGenerator& rng, size_t bitsize, bool set_high_bit = true); - - /** - * Store BigInt-value in a given byte array - * @param buf destination byte array for the integer value - */ - void binary_encode(uint8_t buf[]) const; - - /** - * Read integer value from a byte array with given size - * @param buf byte array buffer containing the integer - * @param length size of buf - */ - void binary_decode(const uint8_t buf[], size_t length); - - /** - * Read integer value from a byte array (secure_vector<uint8_t>) - * @param buf the array to load from - */ - void binary_decode(const secure_vector<uint8_t>& buf) - { - binary_decode(buf.data(), buf.size()); - } - - /** - * @param base the base to measure the size for - * @return size of this integer in base base - */ - size_t encoded_size(Base base = Binary) const; - - /** - * Place the value into out, zero-padding up to size words - * Throw if *this cannot be represented in size words - */ - void encode_words(word out[], size_t size) const; - - /** - * If predicate is true assign other to *this - * Uses a masked operation to avoid side channels - */ - void ct_cond_assign(bool predicate, BigInt& other); - -#if defined(BOTAN_HAS_VALGRIND) - void const_time_poison() const; - void const_time_unpoison() const; -#else - void const_time_poison() const {} - void const_time_unpoison() const {} -#endif - - /** - * @param rng a random number generator - * @param min the minimum value (must be non-negative) - * @param max the maximum value (must be non-negative and > min) - * @return random integer in [min,max) - */ - static BigInt random_integer(RandomNumberGenerator& rng, - const BigInt& min, - const BigInt& max); - - /** - * Create a power of two - * @param n the power of two to create - * @return bigint representing 2^n - */ - static BigInt power_of_2(size_t n) - { - BigInt b; - b.set_bit(n); - return b; - } - - /** - * Encode the integer value from a BigInt to a std::vector of bytes - * @param n the BigInt to use as integer source - * @result secure_vector of bytes containing the bytes of the integer - */ - static std::vector<uint8_t> encode(const BigInt& n) - { - std::vector<uint8_t> output(n.bytes()); - n.binary_encode(output.data()); - return output; - } - - /** - * Encode the integer value from a BigInt to a secure_vector of bytes - * @param n the BigInt to use as integer source - * @result secure_vector of bytes containing the bytes of the integer - */ - static secure_vector<uint8_t> encode_locked(const BigInt& n) - { - secure_vector<uint8_t> output(n.bytes()); - n.binary_encode(output.data()); - return output; - } - - /** - * Encode the integer value from a BigInt to a byte array - * @param buf destination byte array for the encoded integer - * @param n the BigInt to use as integer source - */ - static void encode(uint8_t buf[], const BigInt& n) - { - n.binary_encode(buf); - } - - /** - * Create a BigInt from an integer in a byte array - * @param buf the binary value to load - * @param length size of buf - * @result BigInt representing the integer in the byte array - */ - static BigInt decode(const uint8_t buf[], size_t length) - { - return BigInt(buf, length); - } - - /** - * Create a BigInt from an integer in a byte array - * @param buf the binary value to load - * @result BigInt representing the integer in the byte array - */ - static BigInt decode(const secure_vector<uint8_t>& buf) - { - return BigInt(buf); - } - - /** - * Create a BigInt from an integer in a byte array - * @param buf the binary value to load - * @result BigInt representing the integer in the byte array - */ - static BigInt decode(const std::vector<uint8_t>& buf) - { - return BigInt(buf); - } - - /** - * Encode the integer value from a BigInt to a std::vector of bytes - * @param n the BigInt to use as integer source - * @param base number-base of resulting byte array representation - * @result secure_vector of bytes containing the integer with given base - */ - static std::vector<uint8_t> encode(const BigInt& n, Base base); - - /** - * Encode the integer value from a BigInt to a secure_vector of bytes - * @param n the BigInt to use as integer source - * @param base number-base of resulting byte array representation - * @result secure_vector of bytes containing the integer with given base - */ - static secure_vector<uint8_t> encode_locked(const BigInt& n, - Base base); - - /** - * Encode the integer value from a BigInt to a byte array - * @param buf destination byte array for the encoded integer - * value with given base - * @param n the BigInt to use as integer source - * @param base number-base of resulting byte array representation - */ - static void encode(uint8_t buf[], const BigInt& n, Base base); - - /** - * Create a BigInt from an integer in a byte array - * @param buf the binary value to load - * @param length size of buf - * @param base number-base of the integer in buf - * @result BigInt representing the integer in the byte array - */ - static BigInt decode(const uint8_t buf[], size_t length, - Base base); - - /** - * Create a BigInt from an integer in a byte array - * @param buf the binary value to load - * @param base number-base of the integer in buf - * @result BigInt representing the integer in the byte array - */ - static BigInt decode(const secure_vector<uint8_t>& buf, - Base base) - { - if(base == Binary) - return BigInt(buf); - return BigInt::decode(buf.data(), buf.size(), base); - } - - /** - * Create a BigInt from an integer in a byte array - * @param buf the binary value to load - * @param base number-base of the integer in buf - * @result BigInt representing the integer in the byte array - */ - static BigInt decode(const std::vector<uint8_t>& buf, Base base) - { - if(base == Binary) - return BigInt(buf); - return BigInt::decode(buf.data(), buf.size(), base); - } - - /** - * Encode a BigInt to a byte array according to IEEE 1363 - * @param n the BigInt to encode - * @param bytes the length of the resulting secure_vector<uint8_t> - * @result a secure_vector<uint8_t> containing the encoded BigInt - */ - static secure_vector<uint8_t> encode_1363(const BigInt& n, size_t bytes); - - static void encode_1363(uint8_t out[], size_t bytes, const BigInt& n); - - /** - * Encode two BigInt to a byte array according to IEEE 1363 - * @param n1 the first BigInt to encode - * @param n2 the second BigInt to encode - * @param bytes the length of the encoding of each single BigInt - * @result a secure_vector<uint8_t> containing the concatenation of the two encoded BigInt - */ - static secure_vector<uint8_t> encode_fixed_length_int_pair(const BigInt& n1, const BigInt& n2, size_t bytes); - - /** - * Set output = vec[idx].m_reg in constant time - * All words of vec must have the same size - */ - static void const_time_lookup( - secure_vector<word>& output, - const std::vector<BigInt>& vec, - size_t idx); - - private: - secure_vector<word> m_reg; - Sign m_signedness = Positive; - }; - -/* -* Arithmetic Operators -*/ -BigInt BOTAN_PUBLIC_API(2,0) operator+(const BigInt& x, const BigInt& y); -BigInt BOTAN_PUBLIC_API(2,7) operator+(const BigInt& x, word y); -inline BigInt operator+(word x, const BigInt& y) { return y + x; } - -BigInt BOTAN_PUBLIC_API(2,0) operator-(const BigInt& x, const BigInt& y); -BigInt BOTAN_PUBLIC_API(2,7) operator-(const BigInt& x, word y); - -BigInt BOTAN_PUBLIC_API(2,0) operator*(const BigInt& x, const BigInt& y); -BigInt BOTAN_PUBLIC_API(2,8) operator*(const BigInt& x, word y); -inline BigInt operator*(word x, const BigInt& y) { return y*x; } - -BigInt BOTAN_PUBLIC_API(2,0) operator/(const BigInt& x, const BigInt& d); -BigInt BOTAN_PUBLIC_API(2,0) operator%(const BigInt& x, const BigInt& m); -word BOTAN_PUBLIC_API(2,0) operator%(const BigInt& x, word m); -BigInt BOTAN_PUBLIC_API(2,0) operator<<(const BigInt& x, size_t n); -BigInt BOTAN_PUBLIC_API(2,0) operator>>(const BigInt& x, size_t n); - -/* -* Comparison Operators -*/ -inline bool operator==(const BigInt& a, const BigInt& b) - { return (a.cmp(b) == 0); } -inline bool operator!=(const BigInt& a, const BigInt& b) - { return (a.cmp(b) != 0); } -inline bool operator<=(const BigInt& a, const BigInt& b) - { return (a.cmp(b) <= 0); } -inline bool operator>=(const BigInt& a, const BigInt& b) - { return (a.cmp(b) >= 0); } -inline bool operator<(const BigInt& a, const BigInt& b) - { return (a.cmp(b) < 0); } -inline bool operator>(const BigInt& a, const BigInt& b) - { return (a.cmp(b) > 0); } - -inline bool operator==(const BigInt& a, word b) - { return (a.cmp_word(b) == 0); } -inline bool operator!=(const BigInt& a, word b) - { return (a.cmp_word(b) != 0); } -inline bool operator<=(const BigInt& a, word b) - { return (a.cmp_word(b) <= 0); } -inline bool operator>=(const BigInt& a, word b) - { return (a.cmp_word(b) >= 0); } -inline bool operator<(const BigInt& a, word b) - { return (a.cmp_word(b) < 0); } -inline bool operator>(const BigInt& a, word b) - { return (a.cmp_word(b) > 0); } - -/* -* I/O Operators -*/ -BOTAN_PUBLIC_API(2,0) std::ostream& operator<<(std::ostream&, const BigInt&); -BOTAN_PUBLIC_API(2,0) std::istream& operator>>(std::istream&, BigInt&); - -} - -namespace std { - -template<> -inline void swap<Botan::BigInt>(Botan::BigInt& x, Botan::BigInt& y) - { - x.swap(y); - } - -} - -#endif |