8#include <botan/bigint.h>
10#include <botan/internal/bit_ops.h>
11#include <botan/internal/ct_utils.h>
12#include <botan/internal/loadstor.h>
13#include <botan/internal/mem_utils.h>
14#include <botan/internal/mp_core.h>
15#include <botan/internal/rounding.h>
20 if constexpr(
sizeof(
word) == 8) {
21 m_data.set_word_at(0,
static_cast<word>(n));
23 m_data.set_word_at(1,
static_cast<word>(n >> 32));
24 m_data.set_word_at(0,
static_cast<word>(n));
62 bool negative =
false;
64 if(!str.empty() && str[0] ==
'-') {
69 if(str.length() > markers + 2 && str[markers] ==
'0' && str[markers + 1] ==
'x') {
89 r.assign_from_bytes(input);
97 *
this =
decode(input, length, base);
102 const size_t input_bits = 8 * length;
106 if(input_bits > max_bits) {
107 const size_t bits_to_shift = input_bits - max_bits;
109 bn >>= bits_to_shift;
188 throw Encoding_Error(
"BigInt::encode_words value too large to encode");
195void BigInt::Data::set_to_zero() {
196 m_reg.resize(m_reg.capacity());
201void BigInt::Data::mask_bits(
size_t n) {
203 return set_to_zero();
206 const size_t top_word = n / WordInfo<word>::bits;
208 if(top_word <
size()) {
209 const word mask = (
static_cast<word>(1) << (n % WordInfo<word>::bits)) - 1;
210 const size_t len =
size() - (top_word + 1);
214 m_reg[top_word] &= mask;
215 invalidate_sig_words();
219size_t BigInt::Data::calc_sig_words()
const {
220 const size_t sz = m_reg.size();
225 for(
size_t i = 0; i != sz; ++i) {
226 const word w = m_reg[sz - i - 1];
244 if(length == 0 || length > 32) {
248 const uint32_t mask = 0xFFFFFFFF >> (32 - length);
261 return static_cast<uint32_t
>(w0 >> wshift) & mask;
276 throw Encoding_Error(
"BigInt::to_u32bit: Number is too big to convert");
280 for(
size_t i = 0; i != 4; ++i) {
281 out = (out << 8) |
byte_at(3 - i);
294 m_data.set_word_at(which,
word_at(which) & mask);
321 return full_words + top_bits;
335 throw Invalid_Argument(
"BigInt::reduce_below both values must be positive");
340 if(
size() < p_words + 1) {
344 if(ws.size() < p_words + 1) {
345 ws.resize(p_words + 1);
350 size_t reductions = 0;
367 throw Invalid_Argument(
"BigInt::ct_reduce_below both values must be positive");
370 const size_t mod_words = mod.
sig_words();
374 const size_t sz =
size();
380 for(
size_t i = 0; i != bound; ++i) {
409 const size_t full_words = len /
sizeof(
word);
410 const size_t extra_bytes = len %
sizeof(
word);
412 for(
size_t i = 0; i != full_words; ++i) {
417 if(extra_bytes > 0) {
420 for(
size_t i = 0; i != extra_bytes; ++i) {
429void BigInt::assign_from_bytes(std::span<const uint8_t>
bytes) {
432 const size_t length =
bytes.size();
433 const size_t full_words = length /
sizeof(
word);
434 const size_t extra_bytes = length %
sizeof(
word);
438 for(
size_t i = 0; i != full_words; ++i) {
445 std::array<uint8_t,
sizeof(
word)> last_partial_word = {0};
446 copy_mem(std::span{last_partial_word}.last(extra_bytes),
bytes);
455 throw Invalid_Argument(
"BigInt::ct_cond_add requires both values to be positive");
457 const size_t v_words = value.
sig_words();
468 for(
size_t i = 0; i != v_words; ++i) {
472 for(
size_t i = v_words; i !=
size(); ++i) {
482 clear_mem(result.mutable_data() + result.size() - 1, 1);
494 constexpr size_t bits_in_word =
sizeof(
word) * 8;
495 const size_t word_shift = shift >>
ceil_log2(bits_in_word);
496 const size_t bit_shift = shift & ((1 <<
ceil_log2(bits_in_word)) - 1);
497 const size_t iterations = std::max(
size(), bits_in_word) - 1;
503 for(
size_t i = 0; i < iterations; ++i) {
506 shl_word(*
this, tmp);
512 const size_t max_words = std::max(
size(), other.
size());
524 const uint8_t current_sign =
static_cast<uint8_t
>(
sign());
526 const uint8_t new_sign = mask.select(current_sign ^ 1, current_sign);
532 const size_t t_words =
size();
533 const size_t o_words = other.
size();
535 if(o_words < t_words) {
539 const size_t r_words = std::max(t_words, o_words);
543 for(
size_t i = 0; i != r_words; ++i) {
554 CT::poison(m_data.const_data(), m_data.size());
#define BOTAN_ASSERT_NOMSG(expr)
#define BOTAN_DEBUG_ASSERT(expr)
#define BOTAN_ARG_CHECK(expr, msg)
void ct_cond_add(bool predicate, const BigInt &value)
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)
void set_word_at(size_t i, word w)
void ct_cond_assign(bool predicate, const BigInt &other)
void grow_to(size_t n) const
uint32_t to_u32bit() const
size_t top_bits_free() const
void ct_reduce_below(const BigInt &mod, secure_vector< word > &ws, size_t bound)
bool is_less_than(const BigInt &n) const
int32_t cmp(const BigInt &n, bool check_signs=true) const
void ct_shift_left(size_t shift)
void binary_encode(uint8_t buf[]) const
word word_at(size_t n) const
void randomize(RandomNumberGenerator &rng, size_t bitsize, bool set_high_bit=true)
int32_t cmp_word(word n) const
void cond_flip_sign(bool predicate)
static BigInt from_string(std::string_view str)
void _const_time_unpoison() const
void serialize_to(std::span< uint8_t > out) const
static BigInt from_bytes(std::span< const uint8_t > bytes)
void _const_time_poison() const
uint8_t byte_at(size_t n) const
static BigInt from_u64(uint64_t n)
const word * _data() const
void encode_words(word out[], size_t size) const
static BigInt from_s32(int32_t n)
void ct_cond_swap(bool predicate, BigInt &other)
static BigInt from_word(word n)
size_t reduce_below(const BigInt &mod, secure_vector< word > &ws)
static BigInt from_bytes_with_max_bits(const uint8_t buf[], size_t length, size_t max_bits)
static BigInt with_capacity(size_t n)
void swap_reg(secure_vector< word > ®)
uint32_t get_substring(size_t offset, size_t length) const
static constexpr Mask< T > expand(T v)
static constexpr Mask< T > is_equal(T x, T y)
static constexpr Mask< T > expand_bool(bool v)
static constexpr Mask< T > is_zero(T x)
constexpr T value_barrier(T x)
constexpr void unpoison(const T *p, size_t n)
constexpr void poison(const T *p, size_t n)
constexpr void bigint_cnd_swap(W cnd, W x[], W y[], size_t size)
std::span< const uint8_t > as_span_of_bytes(const char *s, size_t len)
constexpr auto word_add(W x, W y, W *carry) -> W
constexpr void copy_mem(T *out, const T *in, size_t n)
constexpr auto bigint_sub3(W z[], const W x[], size_t x_size, const W y[], size_t y_size) -> W
constexpr size_t round_up(size_t n, size_t align_to)
constexpr uint8_t ceil_log2(T x)
constexpr auto bigint_ct_is_eq(const W x[], size_t x_size, const W y[], size_t y_size) -> CT::Mask< W >
constexpr int32_t bigint_cmp(const W x[], size_t x_size, const W y[], size_t y_size)
constexpr void bigint_shl2(W y[], const W x[], size_t x_size, size_t shift)
void carry(int64_t &h0, int64_t &h1)
BOTAN_FORCE_INLINE constexpr size_t high_bit(T n)
constexpr auto bigint_ct_is_lt(const W x[], size_t x_size, const W y[], size_t y_size, bool lt_or_equal=false) -> CT::Mask< W >
std::vector< T, secure_allocator< T > > secure_vector
constexpr uint8_t get_byte_var(size_t byte_num, T input)
std::conditional_t< HasNative64BitRegisters, std::uint64_t, uint32_t > word
constexpr auto store_be(ParamTs &&... params)
constexpr void clear_mem(T *ptr, size_t n)
constexpr auto load_be(ParamTs &&... params)
BOTAN_FORCE_INLINE constexpr T ct_is_zero(T x)