10#define BOTAN_BIGINT_H_
12#include <botan/exceptn.h>
13#include <botan/mem_ops.h>
14#include <botan/secmem.h>
15#include <botan/types.h>
20class RandomNumberGenerator;
30 enum Base { Decimal = 10, Hexadecimal = 16, Binary = 256 };
35 enum Sign { Negative = 0, Positive = 1 };
50 static BigInt one() {
return BigInt::from_word(1); }
56 static BigInt from_u64(uint64_t n);
62 static BigInt from_word(word n);
68 static BigInt from_s32(int32_t n);
89 explicit BigInt(std::string_view str);
96 BigInt(
const uint8_t buf[],
size_t length);
102 template <
typename Alloc>
103 explicit BigInt(
const std::vector<uint8_t, Alloc>& vec) :
BigInt(vec.data(), vec.size()) {}
111 BigInt(
const uint8_t buf[],
size_t length, Base base);
124 static BigInt from_bytes_with_max_bits(
const uint8_t buf[],
size_t length,
size_t max_bits);
141 static BigInt with_capacity(
size_t n);
171 m_data.swap(other.m_data);
172 std::swap(m_signedness, other.m_signedness);
234 word operator%=(word y);
288 static BigInt add2(
const BigInt& x,
const word y[],
size_t y_words, Sign y_sign);
290 BigInt& add(
const word y[],
size_t y_words, Sign sign);
293 return add(y, y_words, sign == Positive ? Negative : Positive);
371 m_data.set_to_zero();
372 m_signedness = Positive;
382 int32_t cmp(
const BigInt& n,
bool check_signs =
true)
const;
389 bool is_equal(
const BigInt& n)
const;
396 bool is_less_than(
const BigInt& n)
const;
404 int32_t cmp_word(word n)
const;
410 bool is_even()
const {
return (get_bit(0) == 0); }
416 bool is_odd()
const {
return (get_bit(0) == 1); }
428 bool is_zero()
const {
return (sig_words() == 0); }
434 void set_bit(
size_t n) { conditionally_set_bit(n,
true); }
447 m_data.set_word_at(which, word_at(which) | mask);
454 void clear_bit(
size_t n);
476 uint32_t get_substring(
size_t offset,
size_t length)
const;
492 std::string to_dec_string()
const;
505 std::string to_hex_string()
const;
511 uint8_t byte_at(
size_t n)
const;
518 word
word_at(
size_t n)
const {
return m_data.get_word_at(n); }
522 void set_words(
const word w[],
size_t len) { m_data.set_words(w, len); }
546 if(sign() == Positive) {
562 if(sign == Negative && is_zero()) {
578 size_t size()
const {
return m_data.size(); }
590 size_t bytes()
const;
603 size_t top_bits_free()
const;
615 const word*
data()
const {
return m_data.const_data(); }
631 void grow_to(
size_t n)
const { m_data.grow_to(n); }
633 void resize(
size_t s) { m_data.resize(s); }
652 void binary_encode(uint8_t buf[])
const;
664 void binary_encode(uint8_t buf[],
size_t len)
const;
671 void binary_decode(
const uint8_t buf[],
size_t length);
677 template <
typename Alloc>
679 binary_decode(buf.data(), buf.size());
686 void encode_words(word out[],
size_t size)
const;
692 void ct_cond_assign(
bool predicate,
const BigInt& other);
698 void ct_cond_swap(
bool predicate,
BigInt& other);
703 void ct_cond_add(
bool predicate,
const BigInt& value);
709 void ct_shift_left(
size_t shift);
714 void cond_flip_sign(
bool predicate);
716#if defined(BOTAN_HAS_VALGRIND)
717 void const_time_poison()
const;
718 void const_time_unpoison()
const;
750 std::vector<uint8_t> output(n.
bytes());
779 template <
typename Alloc>
791 static BigInt decode(
const uint8_t buf[],
size_t length, Base base);
799 template <
typename Alloc>
804 return BigInt::decode(buf.data(), buf.size(), base);
814 static void encode_1363(std::span<uint8_t> out,
const BigInt& n);
816 static void encode_1363(uint8_t out[],
size_t bytes,
const BigInt& n);
830 word* mutable_data() {
831 invalidate_sig_words();
835 const word* const_data()
const {
return m_reg.data(); }
837 secure_vector<word>& mutable_vector() {
838 invalidate_sig_words();
842 const secure_vector<word>& const_vector()
const {
return m_reg; }
844 word get_word_at(
size_t n)
const {
845 if(n < m_reg.size()) {
851 void set_word_at(
size_t i, word w) {
852 invalidate_sig_words();
853 if(i >= m_reg.size()) {
862 void set_words(
const word w[],
size_t len) {
863 invalidate_sig_words();
864 m_reg.assign(w, w + len);
868 m_reg.resize(m_reg.capacity());
873 void set_size(
size_t s) {
874 invalidate_sig_words();
876 m_reg.resize(s + (8 - (s % 8)));
879 void mask_bits(
size_t n) {
881 return set_to_zero();
887 if(top_word < size()) {
889 const size_t len = size() - (top_word + 1);
893 m_reg[top_word] &= mask;
894 invalidate_sig_words();
898 void grow_to(
size_t n)
const {
900 if(n <= m_reg.capacity()) {
903 m_reg.resize(n + (8 - (n % 8)));
908 size_t size()
const {
return m_reg.size(); }
910 void shrink_to_fit(
size_t min_size = 0) {
911 const size_t words = std::max(min_size, sig_words());
915 void resize(
size_t s) { m_reg.resize(s); }
917 void swap(Data& other) {
918 m_reg.swap(other.m_reg);
919 std::swap(m_sig_words, other.m_sig_words);
922 void swap(secure_vector<word>& reg) {
924 invalidate_sig_words();
927 void invalidate_sig_words()
const { m_sig_words = sig_words_npos; }
929 size_t sig_words()
const {
930 if(m_sig_words == sig_words_npos) {
931 m_sig_words = calc_sig_words();
939 static const size_t sig_words_npos =
static_cast<size_t>(-1);
941 size_t calc_sig_words()
const;
943 mutable secure_vector<word> m_reg;
944 mutable size_t m_sig_words = sig_words_npos;
948 Sign m_signedness = Positive;
1000 return (a.
cmp(b) <= 0);
1004 return (a.
cmp(b) >= 0);
1042BOTAN_PUBLIC_API(2, 0) std::ostream& operator<<(std::ostream&, const BigInt&);
#define BOTAN_DEBUG_ASSERT(expr)
static BigInt decode(const std::vector< uint8_t, Alloc > &buf)
void conditionally_set_bit(size_t n, bool set_it)
bool is_equal(const BigInt &n) const
static BigInt decode(const uint8_t buf[], size_t length)
BigInt & sub(const word y[], size_t y_words, Sign sign)
secure_vector< word > & get_word_vector()
void set_word_at(size_t i, word w)
BigInt(const BigInt &other)=default
void grow_to(size_t n) const
Sign reverse_sign() const
const secure_vector< word > & get_word_vector() const
static BigInt add2(const BigInt &x, const word y[], size_t y_words, Sign y_sign)
void set_words(const word w[], size_t len)
bool is_less_than(const BigInt &n) const
int32_t cmp(const BigInt &n, bool check_signs=true) const
BigInt & operator+=(word y)
const word * data() const
BigInt & operator=(BigInt &&other)
static secure_vector< uint8_t > encode_locked(const BigInt &n)
void binary_encode(uint8_t buf[]) const
word word_at(size_t n) const
BigInt & operator-=(const BigInt &y)
friend void swap(BigInt &x, BigInt &y)
void binary_decode(const std::vector< uint8_t, Alloc > &buf)
int32_t cmp_word(word n) const
static std::vector< uint8_t > encode(const BigInt &n)
static BigInt power_of_2(size_t n)
BigInt & operator-=(word y)
BigInt & operator+=(const BigInt &y)
void const_time_poison() const
BigInt & operator=(const BigInt &)=default
static BigInt decode(const std::vector< uint8_t, Alloc > &buf, Base base)
void const_time_unpoison() const
BigInt(const std::vector< uint8_t, Alloc > &vec)
bool get_bit(size_t n) const
void swap_reg(secure_vector< word > ®)
int(* final)(unsigned char *, CTX *)
#define BOTAN_PUBLIC_API(maj, min)
#define BOTAN_MP_WORD_BITS
uint32_t to_u32bit(std::string_view str_view)
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)
BigInt square(const BigInt &x)
OctetString operator+(const OctetString &k1, const OctetString &k2)
bool operator>(const ASN1_Time &, const ASN1_Time &)
BigInt abs(const BigInt &n)
BigInt operator-(const BigInt &x, const BigInt &y)
constexpr auto operator/=(Strong< T1, Tags... > &a, T2 b)
bool operator!=(const AlgorithmIdentifier &a1, const AlgorithmIdentifier &a2)
constexpr auto operator<<=(Strong< T1, Tags... > &a, T2 b)
bool operator==(const AlgorithmIdentifier &a1, const AlgorithmIdentifier &a2)
std::vector< T, secure_allocator< T > > secure_vector
constexpr void clear_mem(T *ptr, size_t n)
constexpr auto operator*=(Strong< T1, Tags... > &a, T2 b)