diff options
Diffstat (limited to 'src/lib/math/bigint/bigint.h')
| -rw-r--r-- | src/lib/math/bigint/bigint.h | 570 |
1 files changed, 570 insertions, 0 deletions
diff --git a/src/lib/math/bigint/bigint.h b/src/lib/math/bigint/bigint.h new file mode 100644 index 000000000..08b7d53fc --- /dev/null +++ b/src/lib/math/bigint/bigint.h @@ -0,0 +1,570 @@ +/* +* BigInt +* (C) 1999-2008,2012 Jack Lloyd +* 2007 FlexSecure +* +* Distributed under the terms of the Botan license +*/ + +#ifndef BOTAN_BIGINT_H__ +#define BOTAN_BIGINT_H__ + +#include <botan/rng.h> +#include <botan/secmem.h> +#include <botan/mp_types.h> +#include <iosfwd> + +namespace Botan { + +/** +* Arbitrary precision integer +*/ +class BOTAN_DLL BigInt + { + 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 + */ + struct BOTAN_DLL DivideByZero : public Exception + { DivideByZero() : Exception("BigInt divide by zero") {} }; + + /** + * Create empty BigInt + */ + BigInt() { m_signedness = Positive; } + + /** + * Create BigInt from 64 bit integer + * @param n initial value of this BigInt + */ + BigInt(u64bit 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 + */ + 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 + * @param base is the number base of the integer in buf + */ + BigInt(const byte buf[], size_t length, Base base = Binary); + + /** + * Create a random BigInt of the specified size + * @param rng random number generator + * @param bits size in bits + */ + BigInt(RandomNumberGenerator& rng, size_t bits); + + /** + * 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); + } + + /** + * += operator + * @param y the BigInt to add to this + */ + BigInt& operator+=(const BigInt& y); + + /** + * -= operator + * @param y the BigInt to subtract from this + */ + BigInt& operator-=(const BigInt& y); + + /** + * *= operator + * @param y the BigInt to multiply with this + */ + BigInt& operator*=(const BigInt& 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()); } + + /** + * 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] + */ + s32bit cmp(const BigInt& n, bool check_signs = true) 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); + + /** + * 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 (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 + */ + u32bit get_substring(size_t offset, size_t length) const; + + /** + * Convert this value into a u32bit, if it is in the range + * [0 ... 2**32-1], or otherwise throw an exception. + * @result the value as a u32bit if conversion is possible + */ + u32bit to_u32bit() const; + + /** + * @param n the offset to get a byte from + * @result byte at offset n + */ + byte byte_at(size_t n) const; + + /** + * 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); } + + /** + * 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; + + /** + * Flip the sign of this BigInt + */ + void flip_sign(); + + /** + * Set sign of the integer + * @param sign new Sign to set + */ + void set_sign(Sign 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[0]; + 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[0]; } + + /** + * Return a const pointer to the register + * @result a pointer to the start of the internal register + */ + const word* data() const { return &m_reg[0]; } + + /** + * Increase internal register buffer to at least n words + * @param n new size of register + */ + void grow_to(size_t n); + + /** + * Fill BigInt with a random number with size of bitsize + * @param rng the random number generator to use + * @param bitsize number of bits the created random value should have + */ + void randomize(RandomNumberGenerator& rng, size_t bitsize = 0); + + /** + * Store BigInt-value in a given byte array + * @param buf destination byte array for the integer value + */ + void binary_encode(byte 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 byte buf[], size_t length); + + /** + * Read integer value from a byte array (secure_vector<byte>) + * @param buf the array to load from + */ + void binary_decode(const secure_vector<byte>& buf) + { + binary_decode(&buf[0], 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; + + /** + * @param rng a random number generator + * @param min the minimum value + * @param max the maximum value + * @return random integer between min and 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 + * @param base number-base of resulting byte array representation + * @result secure_vector of bytes containing the integer with given base + */ + static std::vector<byte> encode(const BigInt& n, Base base = Binary); + + /** + * 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<byte> encode_locked(const BigInt& n, + Base base = Binary); + + /** + * 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(byte buf[], const BigInt& n, Base base = Binary); + + /** + * 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 byte buf[], size_t length, + Base base = Binary); + + /** + * 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<byte>& buf, + Base base = Binary) + { + return BigInt::decode(&buf[0], 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<byte>& buf, + Base base = Binary) + { + return BigInt::decode(&buf[0], 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<byte> + * @result a secure_vector<byte> containing the encoded BigInt + */ + static secure_vector<byte> encode_1363(const BigInt& n, size_t bytes); + + private: + secure_vector<word> m_reg; + Sign m_signedness; + }; + +/* +* Arithmetic Operators +*/ +BigInt BOTAN_DLL operator+(const BigInt& x, const BigInt& y); +BigInt BOTAN_DLL operator-(const BigInt& x, const BigInt& y); +BigInt BOTAN_DLL operator*(const BigInt& x, const BigInt& y); +BigInt BOTAN_DLL operator/(const BigInt& x, const BigInt& d); +BigInt BOTAN_DLL operator%(const BigInt& x, const BigInt& m); +word BOTAN_DLL operator%(const BigInt& x, word m); +BigInt BOTAN_DLL operator<<(const BigInt& x, size_t n); +BigInt BOTAN_DLL 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); } + +/* +* I/O Operators +*/ +BOTAN_DLL std::ostream& operator<<(std::ostream&, const BigInt&); +BOTAN_DLL std::istream& operator>>(std::istream&, BigInt&); + +} + +namespace std { + +template<> +inline void swap<Botan::BigInt>(Botan::BigInt& x, Botan::BigInt& y) + { + x.swap(y); + } + +} + +#endif |