Botan::BigInt Class Reference

#include <bigint.h>

Public Types
enum	Base : uint16_t { Decimal = 10 , Hexadecimal = 16 , Binary = 256 }
enum	Sign : uint8_t { Negative = 0 , Positive = 1 }

Public Member Functions
std::span< const word >	_as_span () const
void	_assign_from_bytes (std::span< const uint8_t > bytes)
void	_const_time_poison () const
void	_const_time_unpoison () const
const word *	_data () const
BigInt	abs () const
BigInt &	add (const word y[], size_t y_words, Sign sign)
	BigInt ()=default
	BigInt (BigInt &&other) noexcept
	BigInt (const BigInt &other)=default
	BigInt (const uint8_t buf[], size_t length)
	BigInt (const uint8_t buf[], size_t length, Base base)
	BigInt (RandomNumberGenerator &rng, size_t bits, bool set_high_bit=true)
	Create a random BigInt of the specified size.
	BigInt (std::span< const uint8_t > bytes)
	BigInt (std::string_view str)
	BigInt (uint64_t n)
void	binary_decode (const uint8_t buf[], size_t length)
void	binary_decode (std::span< const uint8_t > buf)
void	binary_encode (uint8_t buf[]) const
void	binary_encode (uint8_t buf[], size_t len) const
size_t	bits () const
uint8_t	byte_at (size_t n) const
size_t	bytes () const
void	clear ()
void	clear_bit (size_t n)
int32_t	cmp (const BigInt &n, bool check_signs=true) const
int32_t	cmp_word (word n) const
void	cond_flip_sign (bool predicate)
void	conditionally_set_bit (size_t n, bool set_it)
void	const_time_poison () const
void	const_time_unpoison () const
void	ct_cond_add (bool predicate, const BigInt &value)
void	ct_cond_assign (bool predicate, const BigInt &other)
void	ct_cond_swap (bool predicate, BigInt &other)
void	ct_reduce_below (const BigInt &mod, secure_vector< word > &ws, size_t bound)
void	ct_shift_left (size_t shift)
const word *	data () const
void	encode_words (word out[], size_t size) const
void	flip_sign ()
bool	get_bit (size_t n) const
uint32_t	get_substring (size_t offset, size_t length) const
secure_vector< word > &	get_word_vector ()
const secure_vector< word > &	get_word_vector () const
void	grow_to (size_t n) const
bool	is_equal (const BigInt &n) const
bool	is_even () const
bool	is_less_than (const BigInt &n) const
bool	is_negative () const
bool	is_nonzero () const
bool	is_odd () const
bool	is_positive () const
bool	is_zero () const
void	mask_bits (size_t n)
BigInt &	mod_add (const BigInt &y, const BigInt &mod, secure_vector< word > &ws)
BigInt &	mod_mul (uint8_t y, const BigInt &mod, secure_vector< word > &ws)
BigInt &	mod_sub (const BigInt &y, const BigInt &mod, secure_vector< word > &ws)
BigInt &	mul (const BigInt &y, secure_vector< word > &ws)
word *	mutable_data ()
bool	operator! () const
BigInt &	operator%= (const BigInt &y)
word	operator%= (word y)
BigInt &	operator*= (const BigInt &y)
BigInt &	operator*= (word y)
BigInt &	operator++ ()
BigInt	operator++ (int)
BigInt &	operator+= (const BigInt &y)
BigInt &	operator+= (word y)
BigInt	operator- () const
BigInt &	operator-- ()
BigInt	operator-- (int)
BigInt &	operator-= (const BigInt &y)
BigInt &	operator-= (word y)
BigInt &	operator/= (const BigInt &y)
BigInt &	operator<<= (size_t shift)
BigInt &	operator= (BigInt &&other) noexcept
BigInt &	operator= (const BigInt &)=default
BigInt &	operator>>= (size_t shift)
void	randomize (RandomNumberGenerator &rng, size_t bitsize, bool set_high_bit=true)
size_t	reduce_below (const BigInt &mod, secure_vector< word > &ws)
void	resize (size_t s)
BigInt &	rev_sub (const word y[], size_t y_words, secure_vector< word > &ws)
Sign	reverse_sign () const
template<typename T = std::vector<uint8_t>>
T	serialize () const
template<typename T = std::vector<uint8_t>>
T	serialize (size_t len) const
void	serialize_to (std::span< uint8_t > out) const
void	set_bit (size_t n)
void	set_sign (Sign sign)
void	set_word_at (size_t i, word w)
void	set_words (const word w[], size_t len)
size_t	sig_words () const
Sign	sign () const
int	signum () const
size_t	size () const
BigInt &	square (secure_vector< word > &ws)
BigInt &	sub (const word y[], size_t y_words, Sign sign)
void	swap (BigInt &other) noexcept
void	swap_reg (secure_vector< word > &reg)
std::string	to_dec_string () const
std::string	to_hex_string () const
uint32_t	to_u32bit () const
size_t	top_bits_free () const
word	word_at (size_t n) const
	~BigInt ()

Static Public Member Functions
static BigInt	_from_words (secure_vector< word > &words)
static BigInt	add2 (const BigInt &x, const word y[], size_t y_words, Sign y_sign)
static BigInt	decode (const uint8_t buf[], size_t length)
static BigInt	decode (const uint8_t buf[], size_t length, Base base)
static BigInt	decode (std::span< const uint8_t > buf)
static BigInt	decode (std::span< const uint8_t > buf, Base base)
static std::vector< uint8_t >	encode (const BigInt &n)
static secure_vector< uint8_t >	encode_1363 (const BigInt &n, size_t bytes)
static void	encode_1363 (std::span< uint8_t > out, const BigInt &n)
static void	encode_1363 (uint8_t out[], size_t bytes, const BigInt &n)
static secure_vector< uint8_t >	encode_fixed_length_int_pair (const BigInt &n1, const BigInt &n2, size_t bytes)
static secure_vector< uint8_t >	encode_locked (const BigInt &n)
static BigInt	from_bytes (std::span< const uint8_t > bytes)
static BigInt	from_bytes_with_max_bits (const uint8_t buf[], size_t length, size_t max_bits)
static BigInt	from_radix_digits (std::string_view digits, size_t radix)
static BigInt	from_s32 (int32_t n)
static BigInt	from_string (std::string_view str)
static BigInt	from_u64 (uint64_t n)
static BigInt	from_word (word n)
static BigInt	one ()
static BigInt	power_of_2 (size_t n)
static BigInt	random_integer (RandomNumberGenerator &rng, const BigInt &min, const BigInt &max)
static BigInt	with_capacity (size_t n)
static BigInt	zero ()

Friends
void	swap (BigInt &x, BigInt &y) noexcept

Detailed Description

Arbitrary precision integer

Definition at line 26 of file bigint.h.

Member Enumeration Documentation

Base

enum Botan::BigInt::Base : uint16_t

Base enumerator for encoding and decoding

Enumerator
Decimal
Hexadecimal
Binary

Definition at line 31 of file bigint.h.

                : uint16_t /* NOLINT(*-use-enum-class) */ {
         Decimal BOTAN_DEPRECATED("All functions using this enum are deprecated") = 10,
         Hexadecimal BOTAN_DEPRECATED("All functions using this enum are deprecated") = 16,
         Binary BOTAN_DEPRECATED("All functions using this enum are deprecated") = 256
      };

Sign

enum Botan::BigInt::Sign : uint8_t

Sign symbol definitions for positive and negative numbers

Enumerator
Negative
Positive

Definition at line 40 of file bigint.h.

: uint8_t /* NOLINT(*-use-enum-class) */ { Negative = 0, Positive = 1 };

Constructor & Destructor Documentation

BigInt() [1/9]

Botan::BigInt::BigInt ( )

default

Create empty (zero) BigInt

Referenced by _from_words(), abs(), add(), add2(), BigInt(), BigInt(), BigInt(), cmp(), ct_cond_add(), ct_cond_assign(), ct_cond_swap(), ct_reduce_below(), decode(), decode(), decode(), decode(), encode(), encode_1363(), encode_1363(), encode_1363(), encode_fixed_length_int_pair(), encode_locked(), from_bytes(), from_bytes_with_max_bits(), from_radix_digits(), from_s32(), from_string(), from_u64(), from_word(), is_equal(), is_less_than(), mod_add(), mod_mul(), mod_sub(), mul(), one(), operator%=(), operator*=(), operator*=(), operator++(), operator++(), operator+=(), operator+=(), operator-(), operator--(), operator--(), operator-=(), operator-=(), operator/=(), operator<<=(), operator=(), operator=(), operator>>=(), power_of_2(), random_integer(), reduce_below(), rev_sub(), square(), sub(), swap(), swap, to_dec_string(), with_capacity(), and zero().

BigInt() [2/9]

Botan::BigInt::BigInt

(

uint64_t

n

)

Create BigInt from an unsigned 64 bit integer

Parameters

n	initial value of this BigInt

Prefer BigInt::from_u64

Definition at line 20 of file bigint.cpp.

                         {
   if constexpr(sizeof(word) == 8) {
      m_data.set_word_at(0, static_cast<word>(n));
   } else {
      m_data.set_word_at(1, static_cast<word>(n >> 32));
      m_data.set_word_at(0, static_cast<word>(n));
   }
}

BigInt() [3/9]

Botan::BigInt::BigInt ( const BigInt & other )

default

Copy Constructor

Parameters

other

the BigInt to copy

References BigInt().

BigInt() [4/9]

Botan::BigInt::BigInt ( std::string_view str )

inlineexplicit

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.

Parameters

str	the string to parse for an integer value

Definition at line 98 of file bigint.h.

{ *this = BigInt::from_string(str); }

References BigInt(), and from_string().

BigInt() [5/9]

Botan::BigInt::BigInt ( const uint8_t buf[], size_t length )

inline

Create a BigInt from an integer in a byte array

Parameters

buf	the byte array holding the value
length	size of buf

Definition at line 133 of file bigint.h.

{ assign_from_bytes(std::span{buf, length}); }

BigInt() [6/9]

Botan::BigInt::BigInt ( std::span< const uint8_t > bytes )

inlineexplicit

Create a BigInt from an integer in a byte array

Parameters

bytes

the byte vector holding the value

Definition at line 139 of file bigint.h.

{ assign_from_bytes(bytes); }

References bytes().

BigInt() [7/9]

Botan::BigInt::BigInt	(	const uint8_t	buf[],
		size_t	length,
		Base	base )

Create a BigInt from an integer in a byte array

Parameters

buf	the byte array holding the value
length	size of buf
Base Types	is the number base of the integer in buf

Definition at line 92 of file bigint.cpp.

                                                              {
   *this = decode(input, length, base);
}

References decode().

BigInt() [8/9]

Botan::BigInt::BigInt	(	RandomNumberGenerator &	rng,
		size_t	bits,
		bool	set_high_bit = true )

Create a random BigInt of the specified size.

Parameters

Random Number Generators	random number generator
bits	size in bits
set_high_bit	if true, the highest bit is always set

See also

randomize

Definition at line 114 of file bigint.cpp.

                                                                         {
   randomize(rng, bits, set_high_bit);
}

References bits(), and randomize().

BigInt() [9/9]

Botan::BigInt::BigInt ( BigInt && other )

inlinenoexcept

Move constructor

Definition at line 183 of file bigint.h.

{ this->swap(other); }

References BigInt(), and swap().

~BigInt()

Botan::BigInt::~BigInt ( )

inline

Definition at line 185 of file bigint.h.

{ _const_time_unpoison(); }

References _const_time_unpoison().

Member Function Documentation

_as_span()

std::span< const word > Botan::BigInt::_as_span ( ) const

inline

Return a span over the register

Warning

this is an implementation detail which is not for public use and not covered by SemVer.

Returns

span over the internal register

Definition at line 1023 of file bigint.h.

{ return m_data.const_span(); }

References _as_span().

Referenced by _as_span(), Botan::Montgomery_Int::Montgomery_Int(), and Botan::Barrett_Reduction::reduce().

_assign_from_bytes()

void Botan::BigInt::_assign_from_bytes ( std::span< const uint8_t > bytes )

inline

Read integer value from a byte vector (big endian)

Warning

this is an implementation detail which is not for public use and not covered by SemVer. In applications use BigInt::from_bytes

Parameters

bytes

the span of bytes to load

Definition at line 1044 of file bigint.h.

{ assign_from_bytes(bytes); }

References bytes().

Referenced by Botan::generate_dsa_primes(), Botan::ASN1::integer_from_contents(), and Botan::RFC6979_Nonce_Generator::nonce_for().

_const_time_poison()

void Botan::BigInt::_const_time_poison

(

)

const

Mark this BigInt as holding secret data

Warning

this is an implementation detail which is not for public use and not covered by SemVer.

Definition at line 555 of file bigint.cpp.

                                      {
   CT::poison(m_data.const_data(), m_data.size());
}

References Botan::CT::poison().

Referenced by const_time_poison().

_const_time_unpoison()

void Botan::BigInt::_const_time_unpoison

(

)

const

Mark this BigInt as no longer holding secret data

Warning

this is an implementation detail which is not for public use and not covered by SemVer.

Definition at line 559 of file bigint.cpp.

                                        {
   CT::unpoison(m_data.const_data(), m_data.size());
}

References Botan::CT::unpoison().

Referenced by const_time_unpoison(), and ~BigInt().

_data()

const word * Botan::BigInt::_data ( ) const

inline

Return a const pointer to the register

Warning

this is an implementation detail which is not for public use and not covered by SemVer.

Returns

a pointer to the start of the internal register

Definition at line 1033 of file bigint.h.

{ return m_data.const_data(); }

Referenced by add(), Botan::EC_Point::add(), add2(), Botan::EC_Point::add_affine(), cmp(), cmp_word(), ct_cond_add(), Botan::ct_divide(), Botan::ct_divide_pow2k(), Botan::ct_modulo(), ct_reduce_below(), ct_shift_left(), encode_words(), is_equal(), is_less_than(), mod_add(), mod_sub(), mul(), Botan::Montgomery_Params::mul(), Botan::Montgomery_Params::mul(), Botan::Montgomery_Params::mul_by(), Botan::Barrett_Reduction::multiply(), Botan::operator*(), Botan::operator*(), Botan::operator+(), operator+=(), Botan::operator-(), operator-=(), Botan::operator<<(), Botan::operator>>(), reduce_below(), Botan::Montgomery_Params::sqr(), Botan::Montgomery_Params::sqr(), Botan::Montgomery_Params::sqr(), Botan::Barrett_Reduction::square(), and square().

_from_words()

BigInt Botan::BigInt::_from_words ( secure_vector< word > & words )

inlinestatic

Create a BigInt from a word vector

Warning

this is an implementation detail which is not for public use and not covered by SemVer.

Definition at line 1052 of file bigint.h.

                                                            {
         BigInt bn;
         bn.m_data.swap(words);
         return bn;
      }

References BigInt().

Referenced by Botan::Montgomery_Int::value().

abs()

BigInt Botan::BigInt::abs

(

)

const

Return the absolute value of this integer

Returns

absolute (positive) value of this

Definition at line 386 of file bigint.cpp.

                         {
   BigInt x = (*this);
   x.set_sign(Positive);
   return x;
}

References BigInt(), Positive, and set_sign().

Referenced by Botan::abs().

add()

BigInt & Botan::BigInt::add	(	const word	y[],
		size_t	y_words,
		Sign	sign )

Add a signed word array to *this

Parameters

y	the words of the addend
y_words	the number of words in y
sign	the sign of the addend

Returns

reference to *this

Definition at line 32 of file big_ops2.cpp.

                                                               {
   const size_t x_sw = sig_words();
 
   grow_to(std::max(x_sw, y_words) + 1);
 
   if(sign() == y_sign) {
      const word carry = bigint_add2(mutable_data(), size() - 1, y, y_words);
      mutable_data()[size() - 1] += carry;
   } else {
      const int32_t relative_size = bigint_cmp(_data(), x_sw, y, y_words);
 
      if(relative_size >= 0) {
         // *this >= y
         bigint_sub2(mutable_data(), x_sw, y, y_words);
      } else {
         // *this < y: compute *this = y - *this
         bigint_sub2_rev(mutable_data(), y, y_words);
      }
 
      if(relative_size < 0) {
         set_sign(y_sign);
      } else if(relative_size == 0) {
         set_sign(Positive);
      }
   }
 
   return (*this);
}

References _data(), BigInt(), Botan::bigint_add2(), Botan::bigint_cmp(), Botan::bigint_sub2(), Botan::bigint_sub2_rev(), Botan::carry(), grow_to(), mutable_data(), Positive, set_sign(), sig_words(), sign(), and size().

Referenced by operator+=(), operator+=(), and sub().

add2()

BigInt Botan::BigInt::add2 ( const BigInt & x, const word y[], size_t y_words, BigInt::Sign y_sign )

static

Add a signed word array to an integer

Parameters

x	the first addend
y	the words of the second addend
y_words	the number of words in y
y_sign	the sign of the second addend

Returns

the sum

Definition at line 20 of file big_ops3.cpp.

                                                                                     {
   const size_t x_sw = x.sig_words();
 
   BigInt z = BigInt::with_capacity(std::max(x_sw, y_size) + 1);
 
   if(x.sign() == y_sign) {
      const word carry = bigint_add3(z.mutable_data(), x._data(), x_sw, y, y_size);
      z.mutable_data()[std::max(x_sw, y_size)] += carry;
      z.set_sign(x.sign());
   } else {
      const int32_t relative_size = bigint_cmp(x.data(), x_sw, y, y_size);
 
      if(relative_size < 0) {
         // x < y so z = abs(y - x)
         // NOLINTNEXTLINE(*-suspicious-call-argument) intentionally swapping x and y here
         bigint_sub3(z.mutable_data(), y, y_size, x.data(), x_sw);
         z.set_sign(y_sign);
      } else if(relative_size == 0) {
         // Positive zero (nothing to do in this case)
      } else {
         /*
         * We know at this point that x >= y so if y_size is larger than
         * x_sw, we are guaranteed they are just leading zeros which can
         * be ignored
         */
         y_size = std::min(x_sw, y_size);
         bigint_sub3(z.mutable_data(), x.data(), x_sw, y, y_size);
         z.set_sign(x.sign());
      }
   }
 
   return z;
}

References _data(), BigInt(), Botan::bigint_add3(), Botan::bigint_cmp(), Botan::bigint_sub3(), Botan::carry(), data(), mutable_data(), set_sign(), sig_words(), sign(), and with_capacity().

Referenced by Botan::operator+(), Botan::operator+(), Botan::operator-(), and Botan::operator-().

binary_decode() [1/2]

void Botan::BigInt::binary_decode ( const uint8_t buf[], size_t length )

inline

Read integer value from a byte array with given size

Parameters

buf	byte array buffer containing the integer
length	size of buf

Definition at line 836 of file bigint.h.

                                                                                                      {
         this->assign_from_bytes(std::span{buf, length});
      }

References binary_decode(), and BOTAN_DEPRECATED.

Referenced by binary_decode(), and binary_decode().

binary_decode() [2/2]

void Botan::BigInt::binary_decode ( std::span< const uint8_t > buf )

inline

Read integer value from a byte vector

Parameters

buf	the vector to load from

Definition at line 844 of file bigint.h.

                                                                                              {
         this->assign_from_bytes(buf);
      }

References binary_decode().

binary_encode() [1/2]

void Botan::BigInt::binary_encode ( uint8_t buf[] ) const

inline

Store BigInt-value in a given byte array

Parameters

buf	destination byte array for the integer value

Definition at line 811 of file bigint.h.

                                                                                         {
         this->serialize_to(std::span{buf, this->bytes()});
      }

References binary_encode(), bytes(), and serialize_to().

Referenced by binary_encode(), and serialize_to().

binary_encode() [2/2]

void Botan::BigInt::binary_encode	(	uint8_t	buf[],
		size_t	len ) const

Store BigInt-value in a given byte array. If len is less than the size of the value, then it will be truncated. If len is greater than the size of the value, it will be zero-padded. If len exactly equals this->bytes(), this function behaves identically to binary_encode.

Zero-padding the binary encoding is useful to ensure that other applications correctly parse the encoded value as "positive integer", as a leading 1-bit may be interpreted as a sign bit.

Parameters

buf	destination byte array for the integer value
len	how many bytes to write

Definition at line 404 of file bigint.cpp.

                                                             {
   const size_t full_words = len / sizeof(word);
   const size_t extra_bytes = len % sizeof(word);
 
   for(size_t i = 0; i != full_words; ++i) {
      const word w = word_at(i);
      store_be(w, output + (len - (i + 1) * sizeof(word)));
   }
 
   if(extra_bytes > 0) {
      const word w = word_at(full_words);
 
      for(size_t i = 0; i != extra_bytes; ++i) {
         output[extra_bytes - i - 1] = get_byte_var(sizeof(word) - i - 1, w);
      }
   }
}

References Botan::get_byte_var(), Botan::store_be(), and word_at().

bits()

size_t Botan::BigInt::bits

(

)

const

Get the bit length of the integer

Returns

bit length of the represented integer value

Definition at line 307 of file bigint.cpp.

                          {
   const size_t words = sig_words();
 
   if(words == 0) {
      return 0;
   }
 
   const size_t full_words = (words - 1) * WordInfo<word>::bits;
   const size_t top_bits = WordInfo<word>::bits - top_bits_free();
 
   return full_words + top_bits;
}

References sig_words(), and top_bits_free().

Referenced by BigInt(), bytes(), Botan::ct_divide(), Botan::ct_divide_pow2k(), Botan::ct_divide_word(), Botan::ct_mod_word(), Botan::ct_modulo(), Botan::BER_Decoder::decode(), Botan::BER_Decoder::decode_constrained_integer(), Botan::DL_Group::DL_Group(), Botan::EC_Group::EC_Group(), Botan::generate_dsa_primes(), Botan::generate_rfc6979_nonce(), Botan::generate_rsa_prime(), Botan::inverse_mod_general(), Botan::is_lucas_probable_prime(), Botan::is_perfect_square(), Botan::is_prime(), Botan::TPM_PrivateKey::key_length(), Botan::monty_multi_exp(), Botan::EC_Point::mul(), Botan::EC_Point_Base_Point_Precompute::mul(), Botan::EC_Point_Var_Point_Precompute::mul(), Botan::EC_Point_Multi_Point_Precompute::multi_exp(), Botan::RFC6979_Nonce_Generator::nonce_for(), operator/=(), Botan::passes_miller_rabin_test(), Botan::DL_Group::power_b_p(), Botan::power_mod(), random_integer(), Botan::random_prime(), Botan::RSA_PrivateKey::RSA_PrivateKey(), Botan::srp6_client_agree(), Botan::srp6_group_identifier(), to_dec_string(), to_hex_string(), to_u32bit(), Botan::DL_Group::verify_element_pair(), and Botan::EC_Group::verify_group().

byte_at()

uint8_t Botan::BigInt::byte_at

(

size_t

n

)

const

Return a byte of the big-endian encoding of this integer

Parameters

n	the offset to get a byte from

Returns

byte at offset n

Definition at line 118 of file bigint.cpp.

                                      {
   return get_byte_var(sizeof(word) - (n % sizeof(word)) - 1, word_at(n / sizeof(word)));
}

References Botan::get_byte_var(), and word_at().

Referenced by Botan::BER_Decoder::decode(), Botan::BER_Decoder::decode_constrained_integer(), and to_u32bit().

bytes()

size_t Botan::BigInt::bytes

(

)

const

Give byte length of the integer

Returns

byte length of the represented integer value

Definition at line 294 of file bigint.cpp.

                           {
   return round_up(bits(), 8) / 8;
}

References bits(), and Botan::round_up().

Referenced by _assign_from_bytes(), Botan::base58_decode(), BigInt(), binary_encode(), encode_1363(), encode_1363(), encode_fixed_length_int_pair(), Botan::ASN1::integer_contents(), Botan::OS2ECP(), serialize(), serialize_to(), and to_hex_string().

clear()

void Botan::BigInt::clear ( )

inline

Zeroize the BigInt. The size of the underlying register is not modified.

Definition at line 441 of file bigint.h.

                   {
         m_data.set_to_zero();
         m_signedness = Positive;
      }

References clear(), and Positive.

Referenced by clear(), mul(), operator*=(), operator-=(), and randomize().

clear_bit()

void Botan::BigInt::clear_bit

(

size_t

n

)

Clear bit at specified position

Parameters

n	bit position to clear

Definition at line 285 of file bigint.cpp.

                               {
   const size_t which = n / WordInfo<word>::bits;
 
   if(which < size()) {
      const word mask = ~(static_cast<word>(1) << (n % WordInfo<word>::bits));
      m_data.set_word_at(which, word_at(which) & mask);
   }
}

References size(), and word_at().

cmp()

int32_t Botan::BigInt::cmp	(	const BigInt &	n,
		bool	check_signs = true ) const

Compare this to another BigInt

Parameters

n	the BigInt value to compare with
check_signs	include sign in comparison?

Returns

if (this<n) return -1, if (this>n) return 1, if both values are identical return 0 [like Perl's <=> operator]

Definition at line 138 of file bigint.cpp.

                                                               {
   if(check_signs) {
      if(other.signum() >= 0 && this->signum() < 0) {
         return -1;
      }
 
      if(other.signum() < 0 && this->signum() >= 0) {
         return 1;
      }
 
      if(other.signum() < 0 && this->signum() < 0) {
         return (-bigint_cmp(this->_data(), this->size(), other._data(), other.size()));
      }
   }
 
   return bigint_cmp(this->_data(), this->size(), other._data(), other.size());
}

References _data(), BigInt(), Botan::bigint_cmp(), signum(), and size().

Referenced by Botan::operator<=(), and Botan::operator>=().

cmp_word()

int32_t Botan::BigInt::cmp_word

(

word

n

)

const

Compare this to an integer

Parameters

n	the value to compare with

Returns

if (this<n) return -1, if (this>n) return 1, if both values are identical return 0 [like Perl's <=> operator]

Definition at line 122 of file bigint.cpp.

                                         {
   if(signum() < 0) {
      return -1;  // other is positive ...
   }
 
   const size_t sw = this->sig_words();
   if(sw > 1) {
      return 1;  // must be larger since other is just one word ...
   }
 
   return bigint_cmp(this->_data(), sw, &other, 1);
}

References _data(), Botan::bigint_cmp(), sig_words(), and signum().

Referenced by Botan::operator!=(), Botan::operator<(), Botan::operator<=(), Botan::operator==(), Botan::operator>(), and Botan::operator>=().

cond_flip_sign()

void Botan::BigInt::cond_flip_sign

(

bool

predicate

)

If predicate is true flip the sign of *this

Definition at line 521 of file bigint.cpp.

                                          {
   // This code is assuming Negative == 0, Positive == 1
 
   const auto mask = CT::Mask<uint8_t>::expand_bool(predicate);
 
   const uint8_t current_sign = static_cast<uint8_t>(sign());
 
   const uint8_t new_sign = mask.select(current_sign ^ 1, current_sign);
 
   set_sign(static_cast<Sign>(new_sign));
}

References Botan::CT::Mask< T >::expand_bool(), set_sign(), and sign().

Referenced by ct_cond_assign(), and Botan::operator*().

conditionally_set_bit()

void Botan::BigInt::conditionally_set_bit ( size_t n, bool set_it )

inline

Conditionally set bit at specified position. Note if set_it is false, nothing happens, and if the bit is already set, it remains set.

Parameters

n	bit position to set
set_it	if the bit should be set

Definition at line 526 of file bigint.h.

                                                        {
         const size_t which = n / (sizeof(word) * 8);
         const word mask = static_cast<word>(set_it) << (n % (sizeof(word) * 8));
         m_data.set_word_at(which, word_at(which) | mask);
      }

References word_at().

Referenced by Botan::ct_divide(), Botan::ct_divide_pow2k(), Botan::ct_divide_word(), Botan::ct_modulo(), and set_bit().

const_time_poison()

void Botan::BigInt::const_time_poison ( ) const

inline

Mark this value as secret for constant time analysis tooling

Definition at line 885 of file bigint.h.

{ _const_time_poison(); }

References _const_time_poison(), BOTAN_DEPRECATED, and const_time_poison().

Referenced by const_time_poison().

const_time_unpoison()

void Botan::BigInt::const_time_unpoison ( ) const

inline

Mark this value as no longer secret for constant time analysis tooling

Definition at line 890 of file bigint.h.

{ _const_time_unpoison(); }

References _const_time_unpoison(), and const_time_unpoison().

Referenced by const_time_unpoison().

ct_cond_add()

void Botan::BigInt::ct_cond_add	(	bool	predicate,
		const BigInt &	value )

If predicate is true add value to *this

Definition at line 449 of file bigint.cpp.

                                                            {
   if(this->signum() < 0 || value.signum() < 0) {
      throw Invalid_Argument("BigInt::ct_cond_add requires both values to be positive");
   }
   const size_t v_words = value.sig_words();
 
   // The carry can propagate through every existing word of *this, so the
   // output needs one slot above whichever input is wider.
   this->grow_to(std::max(this->size(), v_words) + 1);
 
   const auto mask = CT::Mask<word>::expand(static_cast<word>(predicate)).value();
 
   word carry = 0;
 
   word* x = this->mutable_data();
   const word* y = value._data();
 
   for(size_t i = 0; i != v_words; ++i) {
      x[i] = word_add(x[i], y[i] & mask, &carry);
   }
 
   for(size_t i = v_words; i != size(); ++i) {
      x[i] = word_add(x[i], static_cast<word>(0), &carry);
   }
}

References _data(), BigInt(), Botan::carry(), Botan::CT::Mask< T >::expand(), grow_to(), mutable_data(), sig_words(), signum(), size(), and Botan::word_add().

Referenced by Botan::inverse_mod_general(), and Botan::is_lucas_probable_prime().

ct_cond_assign()

void Botan::BigInt::ct_cond_assign	(	bool	predicate,
		const BigInt &	other )

If predicate is true assign other to *this Uses a masked operation to avoid side channels

Definition at line 533 of file bigint.cpp.

                                                               {
   const size_t t_words = size();
   const size_t o_words = other.size();
 
   if(t_words < o_words) {
      grow_to(o_words);
   }
 
   const size_t r_words = std::max(t_words, o_words);
 
   const auto mask = CT::Mask<word>::expand_bool(predicate);
 
   for(size_t i = 0; i != r_words; ++i) {
      const word o_word = other.word_at(i);
      const word t_word = this->word_at(i);
      this->set_word_at(i, mask.select(o_word, t_word));
   }
 
   const auto same_sign = CT::Mask<word>::is_equal(sign(), other.sign()).as_choice();
   cond_flip_sign((mask.as_choice() && !same_sign).as_bool());
}

References BigInt(), cond_flip_sign(), Botan::CT::Mask< T >::expand_bool(), grow_to(), Botan::CT::Mask< T >::is_equal(), set_word_at(), sign(), size(), and word_at().

Referenced by Botan::inverse_mod_general(), Botan::is_lucas_probable_prime(), and Botan::power_mod().

ct_cond_swap()

void Botan::BigInt::ct_cond_swap	(	bool	predicate,
		BigInt &	other )

If predicate is true swap *this and other Uses a masked operation to avoid side channels

Definition at line 513 of file bigint.cpp.

                                                       {
   const size_t max_words = std::max(size(), other.size());
   grow_to(max_words);
   other.grow_to(max_words);
 
   bigint_cnd_swap(static_cast<word>(predicate), this->mutable_data(), other.mutable_data(), max_words);
}

References BigInt(), Botan::bigint_cnd_swap(), grow_to(), mutable_data(), and size().

ct_reduce_below()

void Botan::BigInt::ct_reduce_below	(	const BigInt &	mod,
		secure_vector< word > &	ws,
		size_t	bound )

Return *this % 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 use modulo operator.

Performs exactly bound subtractions, so if *this is >= bound*mod then the result will not be fully reduced. If bound is zero, nothing happens.

Definition at line 361 of file bigint.cpp.

                                                                                     {
   if(mod.signum() < 0 || this->signum() < 0) {
      throw Invalid_Argument("BigInt::ct_reduce_below both values must be positive");
   }
 
   const size_t mod_words = mod.sig_words();
 
   grow_to(mod_words);
 
   const size_t sz = size();
 
   ws.resize(sz);
 
   clear_mem(ws.data(), sz);
 
   for(size_t i = 0; i != bound; ++i) {
      const word borrow = bigint_sub3(ws.data(), _data(), sz, mod._data(), mod_words);
 
      CT::Mask<word>::is_zero(borrow).select_n(mutable_data(), ws.data(), _data(), sz);
   }
}

References _data(), BigInt(), Botan::bigint_sub3(), Botan::clear_mem(), grow_to(), Botan::CT::Mask< T >::is_zero(), mutable_data(), sig_words(), signum(), and size().

ct_shift_left()

void Botan::BigInt::ct_shift_left

(

size_t

shift

)

Shift shift bits to the left, runtime is independent of the value of shift.

Definition at line 475 of file bigint.cpp.

                                       {
   BOTAN_ASSERT_NOMSG(size() > 0);
 
   constexpr size_t bits_in_word = sizeof(word) * 8;
   const size_t word_shift = shift >> ceil_log2(bits_in_word);             // shift / bits_in_word
   const size_t bit_shift = shift & ((1 << ceil_log2(bits_in_word)) - 1);  // shift % bits_in_word
   const size_t iterations = std::max(size(), bits_in_word) - 1;           // uint64_t i; i << 64 is undefined behaviour
 
   const size_t n = size();
 
   // Workspace 1 word larger to catch overflow from bigint_shl2
   secure_vector<word> ws(n + 1);
 
   // In every iteration, shift one bit and one word to the left and use the
   // shift results only when they are within the shift range.
   for(size_t i = 0; i < iterations; ++i) {
      // Shift left by 1 bit, dropping overflow
      bigint_shl2(ws.data(), n + 1, _data(), n, 1);
      ws[n] = 0;
 
      // Conditionally assign the bit-shift result
      const auto bmask = CT::Mask<word>::expand_bool(i < bit_shift);
      for(size_t j = 0; j != n; ++j) {
         m_data.set_word_at(j, bmask.select(ws[j], word_at(j)));
      }
 
      // Shift left by 1 word, dropping the most significant word
      bigint_shl2(ws.data(), n + 1, _data(), n - 1 /* ignore msw */, WordInfo<word>::bits);
      ws[0] = 0;
 
      // Conditionally assign the word-shift result
      const auto wmask = CT::Mask<word>::expand_bool(i < word_shift);
      for(size_t j = 0; j != n; ++j) {
         m_data.set_word_at(j, wmask.select(ws[j], word_at(j)));
      }
   }
}

References _data(), Botan::bigint_shl2(), BOTAN_ASSERT_NOMSG, Botan::ceil_log2(), Botan::CT::Mask< T >::expand_bool(), size(), and word_at().

data()

const word * Botan::BigInt::data ( ) const

inline

Return a const pointer to the register

Returns

a pointer to the start of the internal register

Definition at line 718 of file bigint.h.

{ return m_data.const_data(); }

References data().

Referenced by add2(), data(), Botan::FPE::fe1_decrypt(), and Botan::FPE::fe1_encrypt().

decode() [1/4]

BigInt Botan::BigInt::decode ( const uint8_t buf[], size_t length )

inlinestatic

Create a BigInt from an integer in a byte array

Parameters

buf	the binary value to load
length	size of buf

Returns

BigInt representing the integer in the byte array

Definition at line 943 of file bigint.h.

                                                                                                        {
         return BigInt::from_bytes(std::span{buf, length});
      }

References BigInt(), decode(), and from_bytes().

Referenced by BigInt(), decode(), decode(), decode(), and Botan::OS2ECP().

decode() [2/4]

BigInt Botan::BigInt::decode ( const uint8_t buf[], size_t length, Base base )

static

Create a BigInt from an integer in a byte array

Parameters

buf	the binary value to load
length	size of buf
Base Types	number-base of the integer in buf

Returns

BigInt representing the integer in the byte array

Definition at line 210 of file big_code.cpp.

                                                                   {
   if(base == Binary) {
      return BigInt::from_bytes(std::span{buf, length});
   } else if(base == Hexadecimal) {
      const std::string_view sv{cast_uint8_ptr_to_char(buf), length};
      return BigInt::from_radix_digits(sv, 16);
   } else if(base == Decimal) {
      const std::string_view sv{cast_uint8_ptr_to_char(buf), length};
      return BigInt::from_radix_digits(sv, 10);
   } else {
      throw Invalid_Argument("Unknown BigInt decoding method");
   }
}

References BigInt(), Binary, Botan::cast_uint8_ptr_to_char(), Decimal, from_bytes(), from_radix_digits(), and Hexadecimal.

decode() [3/4]

BigInt Botan::BigInt::decode ( std::span< const uint8_t > buf )

inlinestatic

Create a BigInt from an integer in a byte array

Parameters

buf	the binary value to load

Returns

BigInt representing the integer in the byte array

Definition at line 952 of file bigint.h.

                                                                                                {
         return BigInt::from_bytes(buf);
      }

References BigInt(), decode(), and from_bytes().

decode() [4/4]

BigInt Botan::BigInt::decode ( std::span< const uint8_t > buf, Base base )

static

Create a BigInt from an integer in a byte array

Parameters

buf	the binary value to load
Base Types	number-base of the integer in buf

Returns

BigInt representing the integer in the byte array

Definition at line 200 of file big_code.cpp.

                                                           {
   if(base == Binary) {
      return BigInt::from_bytes(buf);
   }
   return BigInt::decode(buf.data(), buf.size(), base);
}

References BigInt(), Binary, decode(), and from_bytes().

encode()

std::vector< uint8_t > Botan::BigInt::encode ( const BigInt & n )

inlinestatic

Encode the integer value from a BigInt to a std::vector of bytes

Parameters

n	the BigInt to use as integer source

Returns

secure_vector of bytes containing the bytes of the integer

Definition at line 917 of file bigint.h.

                                                                                                {
         return n.serialize<std::vector<uint8_t>>(n.bytes());
      }

References BigInt(), and encode().

Referenced by encode().

encode_1363() [1/3]

secure_vector< uint8_t > Botan::BigInt::encode_1363 ( const BigInt & n, size_t bytes )

inlinestatic

Encode a BigInt to a byte array according to IEEE 1363

Parameters

n	the BigInt to encode
bytes	the length of the resulting secure_vector<uint8_t>

Returns

a secure_vector<uint8_t> containing the encoded BigInt

Definition at line 981 of file bigint.h.

                                                                               {
         return n.serialize<secure_vector<uint8_t>>(bytes);
      }

References BigInt(), bytes(), and encode_1363().

Referenced by encode_1363(), encode_1363(), encode_1363(), Botan::EC_Point::x_bytes(), Botan::EC_Point::xy_bytes(), and Botan::EC_Point::y_bytes().

encode_1363() [2/3]

void Botan::BigInt::encode_1363 ( std::span< uint8_t > out, const BigInt & n )

inlinestatic

Encode an integer as a fixed length big-endian string per IEEE 1363

Parameters

out	the buffer to write to; its size determines the encoding length
n	the integer to encode

Definition at line 990 of file bigint.h.

                                                                                                                {
         n.serialize_to(out);
      }

References BigInt(), and encode_1363().

encode_1363() [3/3]

void Botan::BigInt::encode_1363 ( uint8_t out[], size_t bytes, const BigInt & n )

inlinestatic

Encode an integer as a fixed length big-endian string per IEEE 1363

Parameters

out	the buffer to write to
bytes	the length of the encoding
n	the integer to encode

Definition at line 1001 of file bigint.h.

                                                                            {
         n.serialize_to(std::span{out, bytes});
      }

References BigInt(), bytes(), and encode_1363().

encode_fixed_length_int_pair()

secure_vector< uint8_t > Botan::BigInt::encode_fixed_length_int_pair ( const BigInt & n1, const BigInt & n2, size_t bytes )

static

Encode two BigInt to a byte array according to IEEE 1363

Parameters

n1	the first BigInt to encode
n2	the second BigInt to encode
bytes	the length of the encoding of each single BigInt

Returns

a secure_vector<uint8_t> containing the concatenation of the two encoded BigInt

Definition at line 186 of file big_code.cpp.

                                                                                                            {
   if(n1.signum() < 0 || n2.signum() < 0) {
      throw Encoding_Error("encode_fixed_length_int_pair: values must be positive");
   }
   if(n1.bytes() > bytes || n2.bytes() > bytes) {
      throw Encoding_Error("encode_fixed_length_int_pair: values too large to encode properly");
   }
   secure_vector<uint8_t> output(2 * bytes);
   BufferStuffer stuffer(output);
   n1.serialize_to(stuffer.next(bytes));
   n2.serialize_to(stuffer.next(bytes));
   return output;
}

References BigInt(), bytes(), Botan::BufferStuffer::next(), serialize_to(), and signum().

encode_locked()

secure_vector< uint8_t > Botan::BigInt::encode_locked ( const BigInt & n )

inlinestatic

Encode the integer value from a BigInt to a secure_vector of bytes

Parameters

n	the BigInt to use as integer source

Returns

secure_vector of bytes containing the bytes of the integer

Definition at line 926 of file bigint.h.

                                                                                                           {
         return n.serialize<secure_vector<uint8_t>>(n.bytes());
      }

References BigInt(), and encode_locked().

Referenced by encode_locked().

encode_words()

void Botan::BigInt::encode_words	(	word	out[],
		size_t	size ) const

Place the value into out, zero-padding up to size words Throw if *this cannot be represented in size words

Definition at line 180 of file bigint.cpp.

                                                       {
   const size_t words = sig_words();
 
   if(words > size) {
      throw Encoding_Error("BigInt::encode_words value too large to encode");
   }
 
   clear_mem(out, size);
   copy_mem(out, _data(), words);
}

References _data(), Botan::clear_mem(), Botan::copy_mem(), sig_words(), and size().

flip_sign()

void Botan::BigInt::flip_sign ( )

inline

Flip the sign of this BigInt

Definition at line 657 of file bigint.h.

{ set_sign(reverse_sign()); }

References flip_sign(), reverse_sign(), and set_sign().

Referenced by Botan::ct_divide_word(), flip_sign(), Botan::is_lucas_probable_prime(), and operator-().

from_bytes()

BigInt Botan::BigInt::from_bytes ( std::span< const uint8_t > bytes )

static

Create a BigInt from an integer in a byte array

Parameters

bytes

the binary value to load

Returns

BigInt representing the integer in the byte array

Definition at line 83 of file bigint.cpp.

                                                      {
   BigInt r;
   r.assign_from_bytes(input);
   return r;
}

References BigInt().

Referenced by botan_srp6_client_agree(), botan_srp6_server_session_step1(), botan_srp6_server_session_step2(), Botan::TLS::Client_Key_Exchange::Client_Key_Exchange(), decode(), decode(), decode(), decode(), Botan::BER_Decoder::decode_octet_string_bigint(), from_bytes_with_max_bits(), from_radix_digits(), Botan::TPM_PrivateKey::get_e(), Botan::TPM_PrivateKey::get_n(), Botan::TLS::Callbacks::tls_deserialize_peer_public_key(), and Botan::EC_Scalar::to_bigint().

from_bytes_with_max_bits()

BigInt Botan::BigInt::from_bytes_with_max_bits ( const uint8_t buf[], size_t length, size_t max_bits )

static

Create a BigInt from an integer in a byte array

Note this function is primarily used for implementing signature schemes and is not useful in typical applications.

Parameters

buf	the byte array holding the value
length	size of buf
max_bits	if the resulting integer is more than max_bits, it will be shifted so it is at most max_bits in length.

Definition at line 97 of file bigint.cpp.

                                                                                             {
   const size_t input_bits = 8 * length;
 
   auto bn = BigInt::from_bytes(std::span{input, length});
 
   if(input_bits > max_bits) {
      const size_t bits_to_shift = input_bits - max_bits;
 
      bn >>= bits_to_shift;
   }
 
   return bn;
}

References BigInt(), and from_bytes().

from_radix_digits()

BigInt Botan::BigInt::from_radix_digits ( std::string_view digits, size_t radix )

static

Create BigInt from a sequence of digits

The string is interpreted as a sequence of digits in base radix.

Each character must be interpretable as such a digit; there is no support for whitespace or prefixes (eg '0x' or '-').

Currently radix must be 10 or 16.

Parameters

digits	the sequence of digits
radix	the base

Definition at line 125 of file big_code.cpp.

                                                                    {
   if(radix == 16) {
      secure_vector<uint8_t> binary;
 
      if(digits.size() % 2 == 1) {
         // Handle lack of leading 0
         const char buf0_with_leading_0[2] = {'0', digits[0]};
 
         binary = hex_decode_locked(buf0_with_leading_0, 2);
 
         if(digits.size() > 1) {
            binary += hex_decode_locked(&digits[1], digits.size() - 1, false);
         }
      } else {
         binary = hex_decode_locked(digits, false);
      }
 
      return BigInt::from_bytes(binary);
   } else if(radix == 10) {
      // Use the largest power of 10 that fits in a word, accumulating
      // groups of digits into word-sized chunks to minimize the number
      // of multiprecision multiplications.
      constexpr word conversion_radix = decimal_conversion_radix();
      constexpr size_t radix_digits = decimal_conversion_radix_digits();
 
      BigInt r;
 
      // Handle the initial partial block (if digit count is not a multiple of radix_digits)
      const size_t partial_block = digits.size() % radix_digits;
 
      if(partial_block > 0) {
         word acc = 0;
         for(size_t i = 0; i < partial_block; ++i) {
            const char c = digits[i];
            BOTAN_ARG_CHECK(c >= '0' && c <= '9', "Invalid decimal character");
            acc = acc * 10 + static_cast<word>(c - '0');
         }
         r += acc;
      }
 
      // Process full blocks of radix_digits
      for(size_t i = partial_block; i != digits.size(); i += radix_digits) {
         word acc = 0;
         for(size_t j = 0; j < radix_digits; ++j) {
            const char c = digits[i + j];
            BOTAN_ARG_CHECK(c >= '0' && c <= '9', "Invalid decimal character");
            acc = acc * 10 + static_cast<word>(c - '0');
         }
         r *= conversion_radix;
         r += acc;
      }
 
      return r;
   } else {
      throw Invalid_Argument("BigInt::from_radix_digits unknown radix");
   }
}

References BigInt(), BOTAN_ARG_CHECK, from_bytes(), and Botan::hex_decode_locked().

Referenced by botan_mp_set_from_radix_str(), decode(), and from_string().

from_s32()

BigInt Botan::BigInt::from_s32 ( int32_t n )

static

Create BigInt from a signed 32 bit integer

Parameters

n	initial value of this BigInt

Definition at line 42 of file bigint.cpp.

                                 {
   if(n >= 0) {
      return BigInt::from_u64(static_cast<uint64_t>(n));
   } else {
      return -BigInt::from_u64(static_cast<uint64_t>(-static_cast<int64_t>(n)));
   }
}

References BigInt(), and from_u64().

Referenced by botan_mp_set_from_int(), Botan::EC_Group::EC_Group(), Botan::EC_Group::EC_Group(), Botan::EC_Point::randomize_repr(), Botan::sqrt_modulo_prime(), and Botan::EC_Group::verify_group().

from_string()

BigInt Botan::BigInt::from_string ( std::string_view str )

static

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.

A prefix of "-" will result in a negative integer

Parameters

str	the string to parse for an integer value

Definition at line 57 of file bigint.cpp.

                                             {
   size_t prefix_bytes = 0;
   bool negative = false;
   size_t radix = 10;
 
   if(!str.empty() && str[0] == '-') {
      prefix_bytes += 1;
      negative = true;
   }
 
   if(str.length() > prefix_bytes + 2 && str[prefix_bytes] == '0' && str[prefix_bytes + 1] == 'x') {
      prefix_bytes += 2;
      radix = 16;
   }
 
   BigInt r = BigInt::from_radix_digits(str.substr(prefix_bytes), radix);
 
   if(negative) {
      r.set_sign(Negative);
   } else {
      r.set_sign(Positive);
   }
 
   return r;
}

References BigInt(), from_radix_digits(), Negative, Positive, and set_sign().

Referenced by BigInt().

from_u64()

BigInt Botan::BigInt::from_u64 ( uint64_t n )

static

Create BigInt from an unsigned 64 bit integer

Parameters

n	initial value of this BigInt

Definition at line 30 of file bigint.cpp.

                                  {
   return BigInt(n);
}

References BigInt().

Referenced by Botan::DER_Encoder::encode(), Botan::DER_Encoder::encode(), from_s32(), one(), and Botan::RSA_PrivateKey::RSA_PrivateKey().

from_word()

BigInt Botan::BigInt::from_word ( word n )

static

Create BigInt from a word (limb)

Parameters

n	initial value of this BigInt

Definition at line 35 of file bigint.cpp.

                               {
   BigInt bn;
   bn.set_word_at(0, n);
   return bn;
}

References BigInt(), and set_word_at().

Referenced by Botan::DL_Group::DL_Group(), Botan::is_bailie_psw_probable_prime(), Botan::is_lucas_probable_prime(), Botan::is_miller_rabin_probable_prime(), Botan::operator%(), Botan::random_prime(), Botan::sqrt_modulo_prime(), and Botan::DL_Group::verify_group().

get_bit()

bool Botan::BigInt::get_bit ( size_t n ) const

inline

Return bit value at specified position

Parameters

n	the bit offset to test

Returns

true, if the bit at position n is set, false otherwise

Definition at line 549 of file bigint.h.

{ return ((word_at(n / (sizeof(word) * 8)) >> (n % (sizeof(word) * 8))) & 1) == 1; }

References word_at().

Referenced by Botan::ct_divide(), Botan::ct_divide_word(), Botan::ct_mod_word(), Botan::ct_modulo(), Botan::EC_Point::encode(), Botan::inverse_mod_general(), is_even(), Botan::is_lucas_probable_prime(), is_odd(), Botan::EC_Point::mul(), and Botan::power_mod().

get_substring()

uint32_t Botan::BigInt::get_substring	(	size_t	offset,
		size_t	length ) const

Return (a maximum of) 32 bits of the complete value

Parameters

offset	the offset to start extracting
length	amount of bits to extract (starting at offset)

Returns

the integer extracted from the register starting at offset with specified length

Definition at line 239 of file bigint.cpp.

                                                                 {
   if(length == 0 || length > 32) {
      throw Invalid_Argument("BigInt::get_substring invalid substring length");
   }
 
   const uint32_t mask = 0xFFFFFFFF >> (32 - length);
 
   const size_t word_offset = offset / WordInfo<word>::bits;
   const size_t wshift = (offset % WordInfo<word>::bits);
 
   /*
   * The substring is contained within one or at most two words. The
   * offset and length are not secret, so we can perform conditional
   * operations on those values.
   */
   const word w0 = word_at(word_offset);
 
   if(wshift == 0 || (offset + length) / WordInfo<word>::bits == word_offset) {
      return static_cast<uint32_t>(w0 >> wshift) & mask;
   } else {
      const word w1 = word_at(word_offset + 1);
      return static_cast<uint32_t>((w0 >> wshift) | (w1 << (WordInfo<word>::bits - wshift))) & mask;
   }
}

References word_at().

Referenced by Botan::monty_multi_exp(), Botan::EC_Point_Base_Point_Precompute::mul(), Botan::EC_Point_Var_Point_Precompute::mul(), and Botan::EC_Point_Multi_Point_Precompute::multi_exp().

get_word_vector() [1/2]

secure_vector< word > & Botan::BigInt::get_word_vector ( )

inline

Don't use this function in application code

Definition at line 723 of file bigint.h.

                                                                                           {
         return m_data.mutable_vector();
      }

References get_word_vector().

Referenced by get_word_vector(), and get_word_vector().

get_word_vector() [2/2]

const secure_vector< word > & Botan::BigInt::get_word_vector ( ) const

inline

Don't use this function in application code

Definition at line 730 of file bigint.h.

                                                                                                       {
         return m_data.const_vector();
      }

References get_word_vector().

grow_to()

void Botan::BigInt::grow_to ( size_t n ) const

inline

Increase internal register buffer to at least n words

Parameters

n	new size of register

Definition at line 738 of file bigint.h.

{ m_data.grow_to(n); }

References grow_to().

Referenced by add(), ct_cond_add(), ct_cond_assign(), ct_cond_swap(), ct_reduce_below(), grow_to(), mod_add(), mod_sub(), mul(), Botan::Montgomery_Params::mul(), Botan::Montgomery_Params::mul(), Botan::Montgomery_Params::mul_by(), Botan::Montgomery_Params::redc(), Botan::Barrett_Reduction::reduce(), reduce_below(), Botan::Montgomery_Params::sqr(), Botan::vartime_divide(), Botan::vartime_divide_pow2k(), and with_capacity().

is_equal()

bool Botan::BigInt::is_equal

(

const BigInt &

n

)

const

Compare this to another BigInt

Parameters

n	the BigInt value to compare with

Returns

true if this == n or false otherwise

Definition at line 156 of file bigint.cpp.

                                               {
   if(this->sign() != other.sign()) {
      return false;
   }
 
   return bigint_ct_is_eq(this->_data(), this->size(), other._data(), other.size()).as_bool();
}

References _data(), BigInt(), Botan::bigint_ct_is_eq(), sign(), and size().

Referenced by Botan::operator!=().

is_even()

bool Botan::BigInt::is_even ( ) const

inline

Test if the integer has an even value

Returns

true if the integer is even, false otherwise

Definition at line 481 of file bigint.h.

{ return !get_bit(0); }

References get_bit().

Referenced by Botan::generate_rsa_prime(), Botan::inverse_mod(), Botan::inverse_mod_general(), Botan::is_bailie_psw_probable_prime(), Botan::is_lucas_probable_prime(), Botan::is_miller_rabin_probable_prime(), Botan::is_prime(), Botan::passes_miller_rabin_test(), and Botan::random_prime().

is_less_than()

bool Botan::BigInt::is_less_than

(

const BigInt &

n

)

const

Compare this to another BigInt

Parameters

n	the BigInt value to compare with

Returns

true if this < n or false otherwise

Definition at line 164 of file bigint.cpp.

                                                   {
   if(this->signum() < 0 && other.signum() >= 0) {
      return true;
   }
 
   if(this->signum() >= 0 && other.signum() < 0) {
      return false;
   }
 
   if(other.signum() < 0 && this->signum() < 0) {
      return bigint_ct_is_lt(other._data(), other.size(), this->_data(), this->size()).as_bool();
   }
 
   return bigint_ct_is_lt(this->_data(), this->size(), other._data(), other.size()).as_bool();
}

References _data(), BigInt(), Botan::bigint_ct_is_lt(), signum(), and size().

Referenced by Botan::operator<(), and Botan::operator>().

is_negative()

bool Botan::BigInt::is_negative ( ) const

inline

Tests if the sign of the integer is negative

Returns

true, iff the integer has a negative sign

Definition at line 623 of file bigint.h.

{ return signum() < 0; }

References is_negative(), and signum().

Referenced by Botan::BER_Decoder::decode_constrained_integer(), and is_negative().

is_nonzero()

bool Botan::BigInt::is_nonzero ( ) const

inline

Test if the integer is not zero

Returns

true if the integer is non-zero, false otherwise

Definition at line 504 of file bigint.h.

{ return signum() != 0; }

References is_nonzero(), and signum().

Referenced by is_nonzero().

is_odd()

bool Botan::BigInt::is_odd ( ) const

inline

Test if the integer has an odd value

Returns

true if the integer is odd, false otherwise

Definition at line 487 of file bigint.h.

{ return get_bit(0); }

References get_bit().

Referenced by Botan::inverse_mod_general(), Botan::inverse_mod_public_prime(), Botan::inverse_mod_rsa_public_modulus(), Botan::inverse_mod_secret_prime(), Botan::is_lucas_probable_prime(), Botan::jacobi(), Botan::power_mod(), and Botan::sqrt_modulo_prime().

is_positive()

bool Botan::BigInt::is_positive ( ) const

inline

Tests if the sign of the integer is positive

Note that this is testing the sign, thus it returns true also for zero Prefer signum which is unambiguous

Returns

true, iff the integer has a positive sign

Definition at line 633 of file bigint.h.

                                                                                                  {
         return signum() >= 0;
      }

References is_positive(), and signum().

Referenced by is_positive().

is_zero()

bool Botan::BigInt::is_zero ( ) const

inline

Test if the integer is zero

Returns

true if the integer is zero, false otherwise

Definition at line 510 of file bigint.h.

{ return sig_words() == 0; }

References sig_words().

Referenced by Botan::EC_Point::add(), Botan::EC_Point::add_affine(), Botan::ct_divide(), Botan::DL_Group::DL_Group(), Botan::EC_PrivateKey::EC_PrivateKey(), Botan::gcd(), Botan::inverse_mod(), Botan::inverse_mod_general(), Botan::EC_Scalar_Data_BN::is_zero(), operator!(), Botan::operator%(), Botan::operator<<(), Botan::operator>>(), Botan::power_mod(), Botan::RSA_PrivateKey::RSA_PrivateKey(), Botan::EC_Group_Data::scalar_deserialize(), set_sign(), Botan::srp6_client_agree(), Botan::SRP6_Server_Session::step2(), to_dec_string(), Botan::vartime_divide(), and Botan::DL_Group::verify_public_element().

mask_bits()

void Botan::BigInt::mask_bits ( size_t n )

inline

Clear all but the lowest n bits

Parameters

n	amount of bits to keep

Definition at line 542 of file bigint.h.

{ m_data.mask_bits(n); }

References mask_bits().

Referenced by Botan::inverse_mod_general(), and mask_bits().

mod_add()

BigInt & Botan::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

Parameters

y	the BigInt to add - assumed y >= 0 and y < mod
mod	the positive modulus
ws	a temp workspace

Definition at line 61 of file big_ops2.cpp.

                                                                                   {
   if(this->signum() < 0 || s.signum() < 0 || mod.signum() < 0) {
      throw Invalid_Argument("BigInt::mod_add expects all arguments are positive");
   }
 
   BOTAN_DEBUG_ASSERT(*this < mod);
   BOTAN_DEBUG_ASSERT(s < mod);
 
   /*
   t + s or t + s - p == t - (p - s)
 
   So first compute ws = p - s
 
   Then compute t + s and t - ws
 
   If t - ws does not borrow, then that is the correct valued
   */
 
   const size_t mod_sw = mod.sig_words();
   BOTAN_ARG_CHECK(mod_sw > 0, "BigInt::mod_add modulus must be positive");
 
   this->grow_to(mod_sw);
   s.grow_to(mod_sw);
 
   // First mod_sw for p - s, 2*mod_sw for bigint_addsub workspace
   if(ws.size() < 3 * mod_sw) {
      ws.resize(3 * mod_sw);
   }
 
   // NOLINTBEGIN(readability-container-data-pointer)
 
   word borrow = bigint_sub3(&ws[0], mod._data(), mod_sw, s._data(), mod_sw);
   BOTAN_DEBUG_ASSERT(borrow == 0);
   BOTAN_UNUSED(borrow);
 
   // Compute t - ws
   borrow = bigint_sub3(&ws[mod_sw], this->_data(), mod_sw, &ws[0], mod_sw);
 
   // Compute t + s
   bigint_add3(&ws[mod_sw * 2], this->_data(), mod_sw, s._data(), mod_sw);
 
   CT::conditional_copy_mem(borrow, &ws[0], &ws[mod_sw * 2], &ws[mod_sw], mod_sw);
   set_words(&ws[0], mod_sw);
 
   // NOLINTEND(readability-container-data-pointer)
 
   return (*this);
}

References _data(), BigInt(), Botan::bigint_add3(), Botan::bigint_sub3(), BOTAN_ARG_CHECK, BOTAN_DEBUG_ASSERT, BOTAN_UNUSED, Botan::CT::conditional_copy_mem(), grow_to(), set_words(), sig_words(), and signum().

Referenced by Botan::EC_Point::mult2().

mod_mul()

BigInt & Botan::BigInt::mod_mul	(	uint8_t	y,
		const BigInt &	mod,
		secure_vector< word > &	ws )

Set *this to (*this * y) % mod This function assumes *this is >= 0 && < mod y should be small, less than 16

Parameters

y	the small integer to multiply by
mod	the positive modulus
ws	a temp workspace

Definition at line 138 of file big_ops2.cpp.

                                                                             {
   BOTAN_ARG_CHECK(this->signum() >= 0, "*this must be positive");
   BOTAN_ARG_CHECK(y < 16, "y too large");
 
   BOTAN_DEBUG_ASSERT(*this < mod);
 
   *this *= static_cast<word>(y);
   this->reduce_below(mod, ws);
   return (*this);
}

References BigInt(), BOTAN_ARG_CHECK, BOTAN_DEBUG_ASSERT, reduce_below(), and signum().

mod_sub()

BigInt & Botan::BigInt::mod_sub	(	const BigInt &	y,
		const BigInt &	mod,
		secure_vector< word > &	ws )

Set *this to (*this - y) % mod This function assumes *this is >= 0 && < mod

Parameters

y	the BigInt to subtract - assumed y >= 0 and y < mod
mod	the positive modulus
ws	a temp workspace

Definition at line 110 of file big_ops2.cpp.

                                                                                   {
   if(this->signum() < 0 || s.signum() < 0 || mod.signum() < 0) {
      throw Invalid_Argument("BigInt::mod_sub expects all arguments are positive");
   }
 
   // We are assuming in this function that *this and s are no more than mod_sw words long
   BOTAN_DEBUG_ASSERT(*this < mod);
   BOTAN_DEBUG_ASSERT(s < mod);
 
   const size_t mod_sw = mod.sig_words();
 
   this->grow_to(mod_sw);
   s.grow_to(mod_sw);
 
   if(ws.size() < mod_sw) {
      ws.resize(mod_sw);
   }
 
   const word borrow = bigint_sub3(ws.data(), mutable_data(), mod_sw, s._data(), mod_sw);
 
   // Conditionally add back the modulus
   bigint_cnd_add(borrow, ws.data(), mod._data(), mod_sw);
 
   unchecked_copy_memory(mutable_data(), ws.data(), mod_sw);
 
   return (*this);
}

References _data(), BigInt(), Botan::bigint_cnd_add(), Botan::bigint_sub3(), BOTAN_DEBUG_ASSERT, grow_to(), mutable_data(), sig_words(), signum(), and Botan::unchecked_copy_memory().

Referenced by Botan::EC_Point::add(), Botan::EC_Point::add_affine(), and Botan::EC_Point::mult2().

mul()

BigInt & Botan::BigInt::mul	(	const BigInt &	y,
		secure_vector< word > &	ws )

Multiply this with y

Parameters

y	the BigInt to multiply with this
ws	a temp workspace

Definition at line 165 of file big_ops2.cpp.

                                                            {
   const size_t x_sw = sig_words();
   const size_t y_sw = y.sig_words();
   set_sign((sign() == y.sign()) ? Positive : Negative);
 
   if(x_sw == 0 || y_sw == 0) {
      clear();
      set_sign(Positive);
   } else if(x_sw == 1 && y_sw > 0) {
      grow_to(y_sw + 1);
      bigint_linmul3(mutable_data(), y._data(), y_sw, word_at(0));
   } else {
      const size_t new_size = x_sw + y_sw + 1;
      if(ws.size() < new_size) {
         ws.resize(new_size);
      }
      secure_vector<word> z_reg(new_size);
 
      bigint_mul(z_reg.data(), z_reg.size(), _data(), size(), x_sw, y._data(), y.size(), y_sw, ws.data(), ws.size());
 
      this->swap_reg(z_reg);
   }
 
   return (*this);
}

References _data(), BigInt(), Botan::bigint_linmul3(), Botan::bigint_mul(), clear(), grow_to(), mutable_data(), Negative, Positive, set_sign(), sig_words(), sign(), size(), swap_reg(), and word_at().

Referenced by operator*=().

mutable_data()

word * Botan::BigInt::mutable_data ( )

inline

Return a mutable pointer to the register

Returns

a pointer to the start of the internal register

Definition at line 712 of file bigint.h.

{ return m_data.mutable_data(); }

References BOTAN_DEPRECATED, and mutable_data().

Referenced by add(), add2(), ct_cond_add(), ct_cond_swap(), Botan::ct_divide(), Botan::ct_divide_pow2k(), Botan::ct_modulo(), ct_reduce_below(), mod_sub(), mul(), Botan::Montgomery_Params::mul(), Botan::Montgomery_Params::mul(), Botan::Montgomery_Params::mul_by(), mutable_data(), Botan::operator*(), Botan::operator*(), operator*=(), Botan::operator<<(), Botan::operator>>(), Botan::Montgomery_Params::redc(), Botan::Montgomery_Params::sqr(), Botan::vartime_divide(), and Botan::vartime_divide_pow2k().

one()

BigInt Botan::BigInt::one ( )

inlinestatic

Create a 1-value BigInt

Definition at line 55 of file bigint.h.

{ return BigInt::from_u64(1); }

References BigInt(), and from_u64().

Referenced by Botan::is_lucas_probable_prime(), Botan::is_perfect_square(), Botan::X509_CA::new_crl(), Botan::power_mod(), Botan::EC_Group_Data::scalar_one(), and Botan::EC_Group_Data::scalar_random().

operator!()

bool Botan::BigInt::operator! ( ) const

inline

! operator

Returns

true iff this is zero, otherwise false

Definition at line 327 of file bigint.h.

{ return is_zero(); }

References is_zero().

operator%=() [1/2]

BigInt & Botan::BigInt::operator%=

(

const BigInt &

y

)

Modulo operator

Parameters

y	the modulus to reduce this by

Definition at line 232 of file big_ops2.cpp.

                                          {
   return (*this = (*this) % mod);
}

References BigInt().

operator%=() [2/2]

word Botan::BigInt::operator%=

(

word

y

)

Modulo operator

Parameters

y	the modulus (word) to reduce this by

Definition at line 239 of file big_ops2.cpp.

                              {
   if(mod == 0) {
      throw Invalid_Argument("BigInt::operator%= divide by zero");
   }
 
   word remainder = 0;
 
   if(is_power_of_2(mod)) {
      remainder = (word_at(0) & (mod - 1));
   } else {
      const divide_precomp redc_mod(mod);
      const size_t sw = sig_words();
      for(size_t i = sw; i > 0; --i) {
         remainder = redc_mod.vartime_mod_2to1(remainder, word_at(i - 1));
      }
   }
 
   if(remainder != 0 && sign() == BigInt::Negative) {
      remainder = mod - remainder;
   }
 
   m_data.set_to_zero();
   m_data.set_word_at(0, remainder);
   set_sign(BigInt::Positive);
   return remainder;
}

References Botan::is_power_of_2(), Negative, Positive, set_sign(), sig_words(), sign(), Botan::divide_precomp< W >::vartime_mod_2to1(), and word_at().

operator*=() [1/2]

BigInt & Botan::BigInt::operator*=

(

const BigInt &

y

)

*= operator

Parameters

y	the BigInt to multiply with this

Definition at line 160 of file big_ops2.cpp.

                                        {
   secure_vector<word> ws;
   return this->mul(y, ws);
}

References BigInt(), and mul().

operator*=() [2/2]

BigInt & Botan::BigInt::operator*=

(

word

y

)

*= operator

Parameters

y	the word to multiply with this

Definition at line 205 of file big_ops2.cpp.

                               {
   if(y == 0) {
      clear();
      set_sign(Positive);
   }
 
   const word carry = bigint_linmul2(mutable_data(), size(), y);
   set_word_at(size(), carry);
 
   return (*this);
}

References BigInt(), Botan::bigint_linmul2(), Botan::carry(), clear(), mutable_data(), Positive, set_sign(), set_word_at(), and size().

operator++() [1/2]

BigInt & Botan::BigInt::operator++ ( )

inline

Increment operator

Definition at line 292 of file bigint.h.

{ return (*this += 1); }

References BigInt().

operator++() [2/2]

BigInt Botan::BigInt::operator++ ( int )

inline

Postfix increment operator

Definition at line 302 of file bigint.h.

                             {
         BigInt x = (*this);
         ++(*this);
         return x;
      }

References BigInt().

operator+=() [1/2]

BigInt & Botan::BigInt::operator+=

(

const BigInt &

y

)

+= operator

Parameters

y	the BigInt to add to this

Definition at line 16 of file big_ops2.cpp.

                                        {
   if(&y == this) {
      return *this <<= 1;
   }
   return add(y._data(), y.sig_words(), y.sign());
}

References _data(), add(), BigInt(), sig_words(), and sign().

operator+=() [2/2]

BigInt & Botan::BigInt::operator+= ( word y )

inline

+= operator

Parameters

y	the word to add to this

Definition at line 233 of file bigint.h.

{ return add(&y, 1, Positive); }

References add(), BigInt(), and Positive.

operator-()

BigInt Botan::BigInt::operator-

(

)

const

Unary negation operator

Returns

negative this

Definition at line 323 of file bigint.cpp.

                               {
   BigInt x = (*this);
   x.flip_sign();
   return x;
}

References BigInt(), and flip_sign().

operator--() [1/2]

BigInt & Botan::BigInt::operator-- ( )

inline

Decrement operator

Definition at line 297 of file bigint.h.

{ return (*this -= 1); }

References BigInt().

operator--() [2/2]

BigInt Botan::BigInt::operator-- ( int )

inline

Postfix decrement operator

Definition at line 311 of file bigint.h.

                             {
         BigInt x = (*this);
         --(*this);
         return x;
      }

References BigInt().

operator-=() [1/2]

BigInt & Botan::BigInt::operator-=

(

const BigInt &

y

)

-= operator

Parameters

y	the BigInt to subtract from this

Definition at line 23 of file big_ops2.cpp.

                                        {
   if(&y == this) {
      this->clear();
      this->set_sign(Positive);
      return *this;
   }
   return sub(y._data(), y.sig_words(), y.sign());
}

References _data(), BigInt(), clear(), Positive, set_sign(), sig_words(), sign(), and sub().

operator-=() [2/2]

BigInt & Botan::BigInt::operator-= ( word y )

inline

-= operator

Parameters

y	the word to subtract from this

Definition at line 245 of file bigint.h.

{ return sub(&y, 1, Positive); }

References BigInt(), Positive, and sub().

operator/=()

BigInt & Botan::BigInt::operator/=

(

const BigInt &

y

)

/= operator

Parameters

y	the BigInt to divide this by

Definition at line 220 of file big_ops2.cpp.

                                        {
   if(y.sig_words() == 1 && signum() >= 0 && y.signum() >= 0 && is_power_of_2(y.word_at(0))) {
      (*this) >>= (y.bits() - 1);
   } else {
      (*this) = (*this) / y;
   }
   return (*this);
}

References BigInt(), bits(), Botan::is_power_of_2(), sig_words(), signum(), and word_at().

operator<<=()

BigInt & Botan::BigInt::operator<<=

(

size_t

shift

)

Left shift operator

Parameters

shift

the number of bits to shift this left by

Definition at line 269 of file big_ops2.cpp.

                                      {
   if(shift >= 65536) {
      throw Invalid_Argument("BigInt left shift count too large");
   }
 
   const size_t sw = sig_words();
   const size_t new_size = sw + (shift + WordInfo<word>::bits - 1) / WordInfo<word>::bits;
 
   m_data.grow_to(new_size);
 
   bigint_shl1(m_data.mutable_data(), new_size, sw, shift);
 
   return (*this);
}

References BigInt(), Botan::bigint_shl1(), and sig_words().

operator=() [1/2]

BigInt & Botan::BigInt::operator= ( BigInt && other )

inlinenoexcept

Move assignment

Definition at line 190 of file bigint.h.

                                               {
         if(this != &other) {
            this->swap(other);
         }
 
         return (*this);
      }

References BigInt(), and swap().

operator=() [2/2]

BigInt & Botan::BigInt::operator= ( const BigInt & )

default

Copy assignment

References BigInt().

operator>>=()

BigInt & Botan::BigInt::operator>>=

(

size_t

shift

)

Right shift operator

Parameters

shift

the number of bits to shift this right by

Definition at line 287 of file big_ops2.cpp.

                                      {
   bigint_shr1(m_data.mutable_data(), m_data.size(), shift);
 
   if(sig_words() == 0 && m_signedness == Negative) {
      m_signedness = Positive;
   }
 
   return (*this);
}

References BigInt(), Botan::bigint_shr1(), Negative, Positive, and sig_words().

power_of_2()

BigInt Botan::BigInt::power_of_2 ( size_t n )

inlinestatic

Create a power of two

Parameters

n	the power of two to create

Returns

bigint representing 2^n

Definition at line 906 of file bigint.h.

                                         {
         BigInt b;
         b.set_bit(n);
         return b;
      }

References BigInt(), and set_bit().

Referenced by Botan::EC_Group::EC_Group(), Botan::inverse_mod_general(), Botan::is_perfect_square(), and Botan::sqrt_modulo_prime().

random_integer()

BigInt Botan::BigInt::random_integer ( RandomNumberGenerator & rng, const BigInt & min, const BigInt & max )

static

Generate a random integer within a range

Parameters

Random Number Generators	a random number generator
min	the minimum value (must be non-negative)
max	the maximum value (must be non-negative and > min)

Returns

random integer in [min,max)

Definition at line 44 of file big_rand.cpp.

                                                                                              {
   if(min.signum() < 0 || max.signum() < 0 || max <= min) {
      throw Invalid_Argument("BigInt::random_integer invalid range");
   }
 
   /*
   If min is > 1 then we generate a random number `r` in [0,max-min)
   and return min + r.
 
   This same logic could also be reasonably chosen for min == 1, but
   that breaks certain tests which expect stability of this function
   when generating within [1,n)
   */
   if(min > 1) {
      const BigInt diff = max - min;
      // This call is recursive, but will not recurse further
      return min + BigInt::random_integer(rng, BigInt::zero(), diff);
   }
 
   BOTAN_DEBUG_ASSERT(min <= 1);
 
   const size_t bits = max.bits();
 
   for(;;) {
      BigInt r;
      r.randomize(rng, bits, false);
      if(r >= min && r < max) {
         return r;
      }
   }
}

References BigInt(), bits(), BOTAN_DEBUG_ASSERT, random_integer(), randomize(), signum(), and zero().

Referenced by botan_mp_rand_range(), Botan::is_miller_rabin_probable_prime(), random_integer(), Botan::EC_Point::randomize_repr(), and Botan::EC_Group_Data::scalar_random().

randomize()

void Botan::BigInt::randomize	(	RandomNumberGenerator &	rng,
		size_t	bitsize,
		bool	set_high_bit = true )

Fill BigInt with a random number with size of bitsize

If set_high_bit is true, the highest bit will be set, which causes the entropy to be bits-1. Otherwise the highest bit is randomly chosen by the rng, causing the entropy to be bits.

Parameters

Random Number Generators	the random number generator to use
bitsize	number of bits the created random value should have
set_high_bit	if true, the highest bit is always set

Definition at line 19 of file big_rand.cpp.

                                                                                    {
   set_sign(Positive);
 
   if(bitsize == 0) {
      clear();
   } else {
      secure_vector<uint8_t> array = rng.random_vec(round_up(bitsize, 8) / 8);
 
      // Always cut unwanted bits
      if(bitsize % 8 > 0) {
         array[0] &= 0xFF >> (8 - (bitsize % 8));
      }
 
      // Set the highest bit if wanted
      if(set_high_bit) {
         array[0] |= 0x80 >> ((bitsize % 8) > 0 ? (8 - bitsize % 8) : 0);
      }
 
      assign_from_bytes(array);
   }
}

References clear(), Positive, Botan::RandomNumberGenerator::random_vec(), Botan::round_up(), and set_sign().

Referenced by BigInt(), Botan::DL_Group::DL_Group(), and random_integer().

reduce_below()

size_t Botan::BigInt::reduce_below	(	const BigInt &	mod,
		secure_vector< word > &	ws )

Return *this % 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 use modulo operator.

Definition at line 329 of file bigint.cpp.

                                                                    {
   if(p.signum() < 0 || this->signum() < 0) {
      throw Invalid_Argument("BigInt::reduce_below both values must be positive");
   }
 
   const size_t p_words = p.sig_words();
 
   if(size() < p_words + 1) {
      grow_to(p_words + 1);
   }
 
   if(ws.size() < p_words + 1) {
      ws.resize(p_words + 1);
   }
 
   clear_mem(ws.data(), ws.size());
 
   size_t reductions = 0;
 
   for(;;) {
      const word borrow = bigint_sub3(ws.data(), _data(), p_words + 1, p._data(), p_words);
      if(borrow > 0) {
         break;
      }
 
      ++reductions;
      swap_reg(ws);
   }
 
   return reductions;
}

References _data(), BigInt(), Botan::bigint_sub3(), Botan::clear_mem(), grow_to(), sig_words(), signum(), size(), and swap_reg().

Referenced by mod_mul(), Botan::vartime_divide(), and Botan::vartime_divide_pow2k().

resize()

void Botan::BigInt::resize ( size_t s )

inline

Resize the internal register, adjusting the sign if the value becomes zero

Parameters

s	the new size of the register in words

Definition at line 744 of file bigint.h.

                                                                          {
         m_data.resize(s);
         set_sign(sign());  // handle possible zero
      }

References resize(), set_sign(), and sign().

Referenced by resize().

rev_sub()

BigInt & Botan::BigInt::rev_sub	(	const word	y[],
		size_t	y_words,
		secure_vector< word > &	ws )

Set *this to y - *this

Parameters

y	the BigInt to subtract from as a sequence of words
y_words	length of y in words
ws	a temp workspace

Definition at line 149 of file big_ops2.cpp.

                                                                            {
   BOTAN_UNUSED(ws);
   BigInt y_bn;
   y_bn.m_data.set_words(y, y_sw);
   *this = y_bn - *this;
   return (*this);
}

References BigInt(), and BOTAN_UNUSED.

reverse_sign()

Sign Botan::BigInt::reverse_sign ( ) const

inline

Return the sign opposite to that of this integer

Returns

the opposite sign of the represented integer value

Definition at line 647 of file bigint.h.

                                {
         if(sign() == Positive) {
            return Negative;
         }
         return Positive;
      }

References Negative, Positive, and sign().

Referenced by flip_sign(), and Botan::operator-().

serialize() [1/2]

template<typename T = std::vector<uint8_t>>

T Botan::BigInt::serialize ( ) const

inline

Serialize the value of this BigInt as a big endian encoding.

Definition at line 803 of file bigint.h.

                          {
         return serialize<T>(this->bytes());
      }

References bytes(), and serialize().

serialize() [2/2]

template<typename T = std::vector<uint8_t>>

T Botan::BigInt::serialize ( size_t len ) const

inline

Serialize the value of this BigInt as a big endian encoding, always returning the specified number of bytes.

Throws if the BigInt is too large to encode in the length specified.

Definition at line 790 of file bigint.h.

                                    {
         // TODO this supports std::vector and secure_vector
         // it would be nice if this also could work with std::array as in
         //   bn.serialize_to<std::array<uint8_t, 32>>(32);
         T out(len);
         this->serialize_to(out);
         return out;
      }

References serialize_to().

Referenced by Botan::base58_decode(), Botan::ASN1::integer_contents(), Botan::X509_Serial_Number::magnitude(), Botan::EC_Group_Data::scalar_from_bigint(), serialize(), Botan::Montgomery_Int::serialize(), Botan::sm2_compute_za(), Botan::srp6_client_agree(), and Botan::SRP6_Server_Session::step2().

serialize_to()

void Botan::BigInt::serialize_to

(

std::span< uint8_t >

out

)

const

Serialize the absolute value of this BigInt as a big endian encoding.

If out is smaller than the total bytes of the BigInt then an exception is thrown.

If out is larger than the total bytes of the BigInt then the necessary number of zeros are prefixed to produce the desired output length

Zero-padding the binary encoding is useful to ensure that other applications correctly parse the encoded value as "positive integer", as a leading 1-bit may be interpreted as a sign bit. It also is necessary when using a fixed size encoding for the integers.

Parameters

out	destination byte span for the integer value

Definition at line 395 of file bigint.cpp.

                                                       {
   BOTAN_ARG_CHECK(this->bytes() <= output.size(), "Insufficient output space");
 
   this->binary_encode(output.data(), output.size());
}

References binary_encode(), BOTAN_ARG_CHECK, and bytes().

Referenced by binary_encode(), Botan::EC_Point::encode(), encode_fixed_length_int_pair(), Botan::EC_AffinePoint::from_bigint_xy(), Botan::RFC6979_Nonce_Generator::nonce_for(), Botan::RFC6979_Nonce_Generator::RFC6979_Nonce_Generator(), serialize(), and to_hex_string().

set_bit()

void Botan::BigInt::set_bit ( size_t n )

inline

Set bit at specified position

Parameters

n	bit position to set

Definition at line 516 of file bigint.h.

{ conditionally_set_bit(n, true); }

References conditionally_set_bit().

Referenced by Botan::ct_divide_pow2k(), Botan::EC_Group::EC_Group(), Botan::generate_dsa_primes(), Botan::generate_rsa_prime(), power_of_2(), and Botan::vartime_divide_pow2k().

set_sign()

void Botan::BigInt::set_sign ( Sign sign )

inline

Set sign of the integer

Parameters

sign	new Sign to set

Definition at line 663 of file bigint.h.

                               {
         if(sign == Negative && is_zero()) {
            sign = Positive;
         }
 
         m_signedness = sign;
      }

References is_zero(), Negative, Positive, and sign().

Referenced by abs(), add(), add2(), cond_flip_sign(), flip_sign(), from_string(), Botan::ASN1::integer_from_contents(), Botan::inverse_mod_general(), Botan::lcm(), mul(), operator%=(), Botan::operator*(), operator*=(), operator-=(), Botan::operator<<(), Botan::operator>>(), randomize(), resize(), square(), to_dec_string(), and Botan::vartime_divide().

set_word_at()

void Botan::BigInt::set_word_at ( size_t i, word w )

inline

Set the word at a specified position of the internal register

Parameters

i	position in the register
w	the value to set

Definition at line 608 of file bigint.h.

{ m_data.set_word_at(i, w); }

References set_word_at().

Referenced by ct_cond_assign(), from_word(), operator*=(), and set_word_at().

set_words()

void Botan::BigInt::set_words ( const word w[], size_t len )

inline

Replace the internal register with the given words

Parameters

w	the words to set
len	the number of words in w

Definition at line 615 of file bigint.h.

                                                                                               {
         m_data.set_words(w, len);
      }

References set_words().

Referenced by mod_add(), and set_words().

sig_words()

size_t Botan::BigInt::sig_words ( ) const

inline

Return how many words we need to hold this value

Returns

significant words of the represented integer value

Definition at line 687 of file bigint.h.

{ return m_data.sig_words(); }

Referenced by add(), add2(), bits(), cmp_word(), ct_cond_add(), Botan::ct_divide(), Botan::ct_divide_pow2k(), Botan::ct_divide_word(), Botan::ct_modulo(), ct_reduce_below(), encode_words(), Botan::Barrett_Reduction::for_public_modulus(), Botan::Barrett_Reduction::for_secret_modulus(), Botan::gcd(), is_zero(), mod_add(), mod_sub(), mul(), Botan::Montgomery_Params::mul(), Botan::Montgomery_Params::mul(), Botan::Montgomery_Params::mul_by(), Botan::operator%(), Botan::operator%(), operator%=(), Botan::operator*(), Botan::operator*(), Botan::operator+(), operator+=(), Botan::operator-(), operator-=(), Botan::operator/(), operator/=(), Botan::operator<<(), operator<<=(), Botan::operator>>(), operator>>=(), Botan::Barrett_Reduction::reduce(), reduce_below(), signum(), Botan::Montgomery_Params::sqr(), square(), top_bits_free(), Botan::vartime_divide(), and Botan::vartime_divide_pow2k().

sign()

Sign Botan::BigInt::sign ( ) const

inline

Return the sign of the integer

Returns

the sign of the integer

Definition at line 641 of file bigint.h.

{ return (m_signedness); }

Referenced by add(), add2(), cond_flip_sign(), ct_cond_assign(), is_equal(), mul(), Botan::operator%(), operator%=(), Botan::operator*(), Botan::operator*(), Botan::operator+(), operator+=(), operator-=(), Botan::operator<<(), Botan::operator>>(), resize(), reverse_sign(), set_sign(), signum(), and sub().

signum()

int Botan::BigInt::signum ( ) const

inline

Return the signum of this integer

Returns

-1 if negative, 0 if zero, 1 if positive

Definition at line 493 of file bigint.h.

                         {
         if(sig_words() == 0) {
            return 0;
         }
         return (sign() == Negative) ? -1 : 1;
      }

References Negative, sig_words(), and sign().

Referenced by Botan::EC_Point::_is_x_eq_to_v_mod_order(), cmp(), cmp_word(), ct_cond_add(), Botan::ct_divide_pow2k(), Botan::ct_divide_word(), Botan::ct_mod_word(), Botan::ct_modulo(), ct_reduce_below(), Botan::BER_Decoder::decode(), Botan::FPE_FE1::decrypt(), encode_fixed_length_int_pair(), Botan::FPE_FE1::encrypt(), Botan::Barrett_Reduction::for_public_modulus(), Botan::Barrett_Reduction::for_secret_modulus(), Botan::EC_AffinePoint::from_bigint_xy(), Botan::ASN1::integer_contents(), Botan::inverse_mod(), Botan::inverse_mod_general(), Botan::inverse_mod_public_prime(), Botan::inverse_mod_rsa_public_modulus(), Botan::inverse_mod_secret_prime(), is_less_than(), Botan::is_lucas_probable_prime(), is_negative(), is_nonzero(), is_positive(), mod_add(), mod_mul(), mod_sub(), Botan::Montgomery_Int::Montgomery_Int(), Botan::monty_multi_exp(), Botan::monty_precompute(), Botan::EC_Point::mul(), Botan::EC_Point_Base_Point_Precompute::mul(), Botan::EC_Point_Var_Point_Precompute::mul(), Botan::EC_Point_Multi_Point_Precompute::multi_exp(), Botan::operator%(), Botan::operator%(), Botan::operator/(), operator/=(), Botan::operator>>(), Botan::power_mod(), random_integer(), Botan::random_prime(), Botan::Barrett_Reduction::reduce(), reduce_below(), Botan::SRP6_Server_Session::step1(), to_dec_string(), to_hex_string(), to_u32bit(), Botan::vartime_divide(), and Botan::vartime_divide_pow2k().

size()

size_t Botan::BigInt::size ( ) const

inline

Give size of internal register

Returns

size of internal register in words

Definition at line 681 of file bigint.h.

{ return m_data.size(); }

Referenced by add(), Botan::EC_Point::add(), Botan::EC_Point::add_affine(), clear_bit(), cmp(), ct_cond_add(), ct_cond_assign(), ct_cond_swap(), Botan::ct_divide_pow2k(), ct_reduce_below(), ct_shift_left(), encode_words(), is_equal(), is_less_than(), Botan::low_zero_bits(), mul(), Botan::Montgomery_Params::mul(), Botan::Montgomery_Params::mul(), Botan::Montgomery_Params::mul_by(), Botan::Barrett_Reduction::multiply(), Botan::operator*(), operator*=(), reduce_below(), Botan::Montgomery_Params::sqr(), Botan::Montgomery_Params::sqr(), Botan::Montgomery_Params::sqr(), Botan::Barrett_Reduction::square(), square(), and with_capacity().

square()

BigInt & Botan::BigInt::square

(

secure_vector< word > &

ws

)

Square value of *this

Parameters

ws	a temp workspace

Definition at line 191 of file big_ops2.cpp.

                                              {
   const size_t sw = sig_words();
 
   secure_vector<word> z(2 * sw);
   ws.resize(z.size());
 
   bigint_sqr(z.data(), z.size(), _data(), size(), sw, ws.data(), ws.size());
 
   swap_reg(z);
   set_sign(BigInt::Positive);
 
   return (*this);
}

References _data(), BigInt(), Botan::bigint_sqr(), Positive, set_sign(), sig_words(), size(), and swap_reg().

Referenced by Botan::EC_Group_Data::EC_Group_Data(), Botan::sqrt_modulo_prime(), Botan::square(), Botan::DL_Group::square_mod_q(), and Botan::EC_Group::verify_group().

sub()

BigInt & Botan::BigInt::sub ( const word y[], size_t y_words, Sign sign )

inline

Subtract a signed word array from *this

Parameters

y	the words of the subtrahend
y_words	the number of words in y
sign	the sign of the subtrahend

Returns

reference to *this

Definition at line 358 of file bigint.h.

                                                             {
         return add(y, y_words, sign == Positive ? Negative : Positive);
      }

References add(), BigInt(), Negative, Positive, and sign().

Referenced by operator-=(), and operator-=().

swap()

void Botan::BigInt::swap ( BigInt & other )

inlinenoexcept

Swap this value with another

Parameters

other

BigInt to swap values with

Definition at line 207 of file bigint.h.

                                        {
         m_data.swap(other.m_data);
         std::swap(m_signedness, other.m_signedness);
      }

References BigInt().

Referenced by Botan::EC_Point::add_affine(), BigInt(), Botan::EC_Point::mult2(), and operator=().

swap_reg()

void Botan::BigInt::swap_reg ( secure_vector< word > & reg )

inline

Swap the internal register with the provided one, leaving the sign unchanged

Parameters

reg	the register to swap with

Definition at line 218 of file bigint.h.

                                                                                            {
         m_data.swap(reg);
         // sign left unchanged
      }

References swap_reg().

Referenced by mul(), reduce_below(), square(), and swap_reg().

to_dec_string()

std::string Botan::BigInt::to_dec_string

(

)

const

Convert this value to a decimal string. Warning: decimal conversions are relatively slow

If the integer is zero then "0" is returned. If the integer is negative then "-" is prefixed.

Definition at line 40 of file big_code.cpp.

                                      {
   // Use the largest power of 10 that fits in a word
   constexpr word conversion_radix = decimal_conversion_radix();
   constexpr size_t radix_digits = decimal_conversion_radix_digits();
 
   // (over-)estimate of the number of digits needed; log2(10) ~ 3.3219
   const size_t digit_estimate = static_cast<size_t>(1 + (static_cast<double>(this->bits()) / 3.32));
 
   // (over-)estimate of db such that conversion_radix^db > *this
   const size_t digit_blocks = (digit_estimate + radix_digits - 1) / radix_digits;
 
   BigInt value = *this;
   value.set_sign(Positive);
 
   // Extract groups of digits into words
   std::vector<word> digit_groups(digit_blocks);
 
   for(size_t i = 0; i != digit_blocks; ++i) {
      word remainder = 0;
      ct_divide_word(value, conversion_radix, value, remainder);
      digit_groups[i] = remainder;
   }
 
   BOTAN_ASSERT_NOMSG(value.is_zero());
 
   // Extract digits from the groups
   std::vector<uint8_t> digits(digit_blocks * radix_digits);
 
   for(size_t i = 0; i != digit_blocks; ++i) {
      word remainder = digit_groups[i];
      for(size_t j = 0; j != radix_digits; ++j) {
         const word new_remainder = divide_10(remainder);
         const word digit = remainder - new_remainder * 10;
         digits[radix_digits * i + j] = static_cast<uint8_t>(digit);
         remainder = new_remainder;
      }
   }
 
   // remove leading zeros
   while(!digits.empty() && digits.back() == 0) {
      digits.pop_back();
   }
 
   BOTAN_ASSERT_NOMSG(digit_estimate >= digits.size());
 
   // Reverse the digits to big-endian and format to text
   std::string s;
   s.reserve(1 + digits.size());
 
   if(signum() < 0) {
      s += "-";
   }
 
   // Reverse and convert to textual digits
   // TODO(Botan4) use std::ranges::reverse_view here once available (need newer Clang)
   // NOLINTNEXTLINE(modernize-loop-convert)
   for(auto i = digits.rbegin(); i != digits.rend(); ++i) {
      s.push_back(*i + '0');  // assumes ASCII
   }
 
   if(s.empty()) {
      s += "0";
   }
 
   return s;
}

References BigInt(), bits(), BOTAN_ASSERT_NOMSG, Botan::ct_divide_word(), Botan::divide_10(), is_zero(), Positive, set_sign(), and signum().

Referenced by Botan::operator<<().

to_hex_string()

std::string Botan::BigInt::to_hex_string

(

)

const

Convert this value to a hexadecimal string.

If the integer is negative then "-" is prefixed. Then a prefix of "0x" is added. Follows is a sequence of hexadecimal characters in uppercase.

The number of hexadecimal characters is always an even number, with a zero prefix being included if necessary. For example encoding the integer "5" results in "0x05"

Definition at line 107 of file big_code.cpp.

                                      {
   const size_t this_bytes = this->bytes();
   std::vector<uint8_t> bits(std::max<size_t>(1, this_bytes));
 
   if(this_bytes > 0) {
      this->serialize_to(bits);
   }
 
   std::string hrep;
   if(signum() < 0) {
      hrep += "-";
   }
   hrep += "0x";
   hrep += hex_encode(bits);
   return hrep;
}

References bits(), bytes(), Botan::hex_encode(), serialize_to(), and signum().

Referenced by Botan::operator<<().

to_u32bit()

uint32_t Botan::BigInt::to_u32bit

(

)

const

Convert this value into a uint32_t, if it is in the range [0 ... 2**32-1], or otherwise throw an exception.

Returns

the value as a uint32_t if conversion is possible

Definition at line 267 of file bigint.cpp.

                                 {
   if(signum() < 0) {
      throw Encoding_Error("BigInt::to_u32bit: Number is negative");
   }
   if(bits() > 32) {
      throw Encoding_Error("BigInt::to_u32bit: Number is too big to convert");
   }
 
   uint32_t out = 0;
   for(size_t i = 0; i != 4; ++i) {
      out = (out << 8) | byte_at(3 - i);
   }
   return out;
}

References bits(), byte_at(), and signum().

top_bits_free()

size_t Botan::BigInt::top_bits_free

(

)

const

Get the number of high bits unset in the top (allocated) word of this integer. Returns (sizeof(word) * 8) only iff *this is zero. Ignores sign.

Definition at line 298 of file bigint.cpp.

                                   {
   const size_t words = sig_words();
 
   const word top_word = word_at(words - 1);
   const size_t bits_used = high_bit(CT::value_barrier(top_word));
   CT::unpoison(bits_used);
   return WordInfo<word>::bits - bits_used;
}

References Botan::high_bit(), sig_words(), Botan::CT::unpoison(), Botan::CT::value_barrier(), and word_at().

Referenced by bits(), Botan::vartime_divide(), and Botan::vartime_divide_pow2k().

with_capacity()

BigInt Botan::BigInt::with_capacity ( size_t n )

static

Create BigInt of specified size, all zeros

Parameters

n	size of the internal register in words

Definition at line 51 of file bigint.cpp.

                                        {
   BigInt bn;
   bn.grow_to(size);
   return bn;
}

References BigInt(), grow_to(), and size().

Referenced by add2(), Botan::ct_divide(), Botan::ct_divide_pow2k(), Botan::ct_divide_word(), Botan::ct_modulo(), Botan::gcd(), Botan::Montgomery_Params::mul(), Botan::operator*(), Botan::operator*(), Botan::operator<<(), and Botan::operator>>().

word_at()

word Botan::BigInt::word_at ( size_t n ) const

inline

Return the word at a specified position of the internal register

Parameters

n	position in the register

Returns

value at position n

Definition at line 601 of file bigint.h.

{ return m_data.get_word_at(n); }

References word_at().

Referenced by binary_encode(), byte_at(), clear_bit(), conditionally_set_bit(), ct_cond_assign(), ct_shift_left(), Botan::EC_Group::EC_group_identity_from_order(), get_bit(), get_substring(), Botan::is_prime(), Botan::jacobi(), Botan::low_zero_bits(), mul(), Botan::operator%(), Botan::operator%(), operator%=(), Botan::operator*(), Botan::operator/(), operator/=(), top_bits_free(), Botan::vartime_divide(), Botan::vartime_divide_pow2k(), and word_at().

zero()

BigInt Botan::BigInt::zero ( )

inlinestatic

Create a 0-value BigInt

Definition at line 50 of file bigint.h.

{ return BigInt(); }

References BigInt().

Referenced by botan_mp_mod_inverse(), Botan::ct_divide_pow2k(), Botan::EC_Group_Data::gk_x_mod_order(), Botan::inverse_mod(), Botan::is_perfect_square(), Botan::operator<<(), Botan::operator>>(), Botan::power_mod(), random_integer(), Botan::random_safe_prime(), Botan::X509_CA::update_crl(), Botan::vartime_divide(), and Botan::vartime_divide_pow2k().

Friends And Related Symbol Documentation

swap

void swap ( BigInt & x, BigInt & y )

friend

Definition at line 212 of file bigint.h.

{ x.swap(y); }

References BigInt().

---

The documentation for this class was generated from the following files:

• src/lib/math/bigint/bigint.h
• src/lib/math/bigint/big_code.cpp
• src/lib/math/bigint/big_ops2.cpp
• src/lib/math/bigint/big_ops3.cpp
• src/lib/math/bigint/big_rand.cpp
• src/lib/math/bigint/bigint.cpp