Botan 3.14.1
Crypto and TLS for C&
Botan::BigInt Class Referencefinal

#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.

31 : uint16_t /* NOLINT(*-use-enum-class) */ {
32 Decimal BOTAN_DEPRECATED("All functions using this enum are deprecated") = 10,
33 Hexadecimal BOTAN_DEPRECATED("All functions using this enum are deprecated") = 16,
34 Binary BOTAN_DEPRECATED("All functions using this enum are deprecated") = 256
35 };
#define BOTAN_DEPRECATED(msg)
Definition api.h:73

◆ 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.

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

Constructor & Destructor Documentation

◆ BigInt() [1/9]

◆ BigInt() [2/9]

Botan::BigInt::BigInt ( uint64_t n)

Create BigInt from an unsigned 64 bit integer

Parameters
ninitial value of this BigInt

Prefer BigInt::from_u64

Definition at line 18 of file bigint.cpp.

18 {
19 // Preallocate so that set_word_at does not branch on the value of n
20 if constexpr(sizeof(word) == 8) {
21 m_data.grow_to(1);
22 m_data.set_word_at(0, static_cast<word>(n));
23 } else {
24 m_data.grow_to(2);
25 m_data.set_word_at(1, static_cast<word>(n >> 32));
26 m_data.set_word_at(0, static_cast<word>(n));
27 }
28}
std::conditional_t< HasNative64BitRegisters, std::uint64_t, uint32_t > word
The native machine word, used as the limb type for multiprecision integers.
Definition types.h:131

◆ BigInt() [3/9]

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

Copy Constructor

Parameters
otherthe 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
strthe string to parse for an integer value

Definition at line 98 of file bigint.h.

98{ *this = BigInt::from_string(str); }
static BigInt from_string(std::string_view str)
Definition bigint.cpp:58

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
bufthe byte array holding the value
lengthsize of buf

Definition at line 133 of file bigint.h.

133{ 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
bytesthe byte vector holding the value

Definition at line 139 of file bigint.h.

139{ assign_from_bytes(bytes); }
size_t bytes() const
Definition bigint.cpp:295

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
bufthe byte array holding the value
lengthsize of buf
Base Typesis the number base of the integer in buf

Definition at line 93 of file bigint.cpp.

93 {
94 *this = decode(input, length, base);
95}
static BigInt decode(const uint8_t buf[], size_t length)
Definition bigint.h:943

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 Generatorsrandom number generator
bitssize in bits
set_high_bitif true, the highest bit is always set
See also
randomize

Definition at line 115 of file bigint.cpp.

115 {
116 randomize(rng, bits, set_high_bit);
117}
void randomize(RandomNumberGenerator &rng, size_t bitsize, bool set_high_bit=true)
Definition big_rand.cpp:20
size_t bits() const
Definition bigint.cpp:308

References bits(), and randomize().

◆ BigInt() [9/9]

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

Move constructor

Definition at line 183 of file bigint.h.

183{ this->swap(other); }
void swap(BigInt &other) noexcept
Definition bigint.h:207

References BigInt(), and swap().

◆ ~BigInt()

Botan::BigInt::~BigInt ( )
inline

Definition at line 185 of file bigint.h.

void _const_time_unpoison() const
Definition bigint.cpp:562

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.

1023{ 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
bytesthe span of bytes to load

Definition at line 1044 of file bigint.h.

1044{ 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 558 of file bigint.cpp.

558 {
559 CT::poison(m_data.const_data(), m_data.size());
560}
constexpr void poison(const T *p, size_t n)
Definition ct_utils.h:56

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 562 of file bigint.cpp.

562 {
563 CT::unpoison(m_data.const_data(), m_data.size());
564}
constexpr void unpoison(const T *p, size_t n)
Definition ct_utils.h:67

References Botan::CT::unpoison().

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

◆ _data()

◆ _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.

1052 {
1053 BigInt bn;
1054 bn.m_data.swap(words);
1055 return bn;
1056 }
BigInt()=default

References BigInt().

Referenced by Botan::ct_divide_word(), Botan::is_perfect_square(), Botan::srp6_client_agree(), and 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 387 of file bigint.cpp.

387 {
388 BigInt x = (*this);
389 x.set_sign(Positive);
390 return x;
391}

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
ythe words of the addend
y_wordsthe number of words in y
signthe sign of the addend
Returns
reference to *this

Definition at line 32 of file big_ops2.cpp.

32 {
33 const size_t x_sw = sig_words();
34
35 grow_to(std::max(x_sw, y_words) + 1);
36
37 if(sign() == y_sign) {
38 const word carry = bigint_add2(mutable_data(), size() - 1, y, y_words);
39 mutable_data()[size() - 1] += carry;
40 } else {
41 const int32_t relative_size = bigint_cmp(_data(), x_sw, y, y_words);
42
43 if(relative_size >= 0) {
44 // *this >= y
45 bigint_sub2(mutable_data(), x_sw, y, y_words);
46 } else {
47 // *this < y: compute *this = y - *this
48 bigint_sub2_rev(mutable_data(), y, y_words);
49 }
50
51 if(relative_size < 0) {
52 set_sign(y_sign);
53 } else if(relative_size == 0) {
55 }
56 }
57
58 return (*this);
59}
size_t sig_words() const
Definition bigint.h:687
word * mutable_data()
Definition bigint.h:712
size_t size() const
Definition bigint.h:681
void grow_to(size_t n) const
Definition bigint.h:738
const word * _data() const
Definition bigint.h:1033
Sign sign() const
Definition bigint.h:641
void set_sign(Sign sign)
Definition bigint.h:663
constexpr auto bigint_add2(W x[], size_t x_size, const W y[], size_t y_size) -> W
Definition mp_core.h:98
constexpr int32_t bigint_cmp(const W x[], size_t x_size, const W y[], size_t y_size)
Definition mp_core.h:463
constexpr auto bigint_sub2(W x[], size_t x_size, const W y[], size_t y_size) -> W
Definition mp_core.h:152
constexpr void bigint_sub2_rev(W x[], const W y[], size_t y_size)
Definition mp_core.h:178

References _data(), BigInt(), Botan::bigint_add2(), Botan::bigint_cmp(), Botan::bigint_sub2(), Botan::bigint_sub2_rev(), 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
xthe first addend
ythe words of the second addend
y_wordsthe number of words in y
y_signthe sign of the second addend
Returns
the sum

Definition at line 20 of file big_ops3.cpp.

20 {
21 const size_t x_sw = x.sig_words();
22
23 BigInt z = BigInt::with_capacity(std::max(x_sw, y_size) + 1);
24
25 if(x.sign() == y_sign) {
26 const word carry = bigint_add3(z.mutable_data(), x._data(), x_sw, y, y_size);
27 z.mutable_data()[std::max(x_sw, y_size)] += carry;
28 z.set_sign(x.sign());
29 } else {
30 const int32_t relative_size = bigint_cmp(x.data(), x_sw, y, y_size);
31
32 if(relative_size < 0) {
33 // x < y so z = abs(y - x)
34 // NOLINTNEXTLINE(*-suspicious-call-argument) intentionally swapping x and y here
35 bigint_sub3(z.mutable_data(), y, y_size, x.data(), x_sw);
36 z.set_sign(y_sign);
37 } else if(relative_size == 0) {
38 // Positive zero (nothing to do in this case)
39 } else {
40 /*
41 * We know at this point that x >= y so if y_size is larger than
42 * x_sw, we are guaranteed they are just leading zeros which can
43 * be ignored
44 */
45 y_size = std::min(x_sw, y_size);
46 bigint_sub3(z.mutable_data(), x.data(), x_sw, y, y_size);
47 z.set_sign(x.sign());
48 }
49 }
50
51 return z;
52}
static BigInt with_capacity(size_t n)
Definition bigint.cpp:52
constexpr auto bigint_add3(W z[], const W x[], size_t x_size, const W y[], size_t y_size) -> W
Definition mp_core.h:124
constexpr auto bigint_sub3(W z[], const W x[], size_t x_size, const W y[], size_t y_size) -> W
Definition mp_core.h:196

References _data(), BigInt(), Botan::bigint_add3(), Botan::bigint_cmp(), Botan::bigint_sub3(), 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
bufbyte array buffer containing the integer
lengthsize of buf

Definition at line 836 of file bigint.h.

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

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
bufthe vector to load from

Definition at line 844 of file bigint.h.

844 {
845 this->assign_from_bytes(buf);
846 }

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
bufdestination byte array for the integer value

Definition at line 811 of file bigint.h.

811 {
812 this->serialize_to(std::span{buf, this->bytes()});
813 }
void serialize_to(std::span< uint8_t > out) const
Definition bigint.cpp:396

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
bufdestination byte array for the integer value
lenhow many bytes to write

Definition at line 405 of file bigint.cpp.

405 {
406 const size_t full_words = len / sizeof(word);
407 const size_t extra_bytes = len % sizeof(word);
408
409 for(size_t i = 0; i != full_words; ++i) {
410 const word w = word_at(i);
411 store_be(w, output + (len - (i + 1) * sizeof(word)));
412 }
413
414 if(extra_bytes > 0) {
415 const word w = word_at(full_words);
416
417 for(size_t i = 0; i != extra_bytes; ++i) {
418 output[extra_bytes - i - 1] = get_byte_var(sizeof(word) - i - 1, w);
419 }
420 }
421}
word word_at(size_t n) const
Definition bigint.h:601
constexpr uint8_t get_byte_var(size_t byte_num, T input)
Definition loadstor.h:69
constexpr auto store_be(ParamTs &&... params)
Definition loadstor.h:745

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 308 of file bigint.cpp.

308 {
309 const size_t words = sig_words();
310
311 if(words == 0) {
312 return 0;
313 }
314
315 const size_t full_words = (words - 1) * WordInfo<word>::bits;
316 const size_t top_bits = WordInfo<word>::bits - top_bits_free();
317
318 return full_words + top_bits;
319}
size_t top_bits_free() const
Definition bigint.cpp:299

References sig_words(), and top_bits_free().

Referenced by BigInt(), bytes(), Botan::BER_Decoder::decode(), Botan::BER_Decoder::decode_constrained_integer(), Botan::Cert_Extension::TNAuthList::Entry::decode_from(), 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_perfect_square(), Botan::TPM_PrivateKey::key_length(), Botan::make_monty_exp_avx512(), 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::DL_Group::power_b_p(), Botan::power_mod(), random_integer(), Botan::random_prime(), Botan::EC_Group::register_custom_group(), 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
nthe offset to get a byte from
Returns
byte at offset n

Definition at line 119 of file bigint.cpp.

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

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

Referenced by Botan::BER_Decoder::decode(), Botan::BER_Decoder::decode_constrained_integer(), Botan::Cert_Extension::TNAuthList::Entry::decode_from(), 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 295 of file bigint.cpp.

295 {
296 return ceil_tobytes(bits());
297}
BOTAN_FORCE_INLINE constexpr T ceil_tobytes(T bits)
Definition bit_ops.h:176

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

Referenced by _assign_from_bytes(), 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.

441 {
442 m_data.set_to_zero();
443 m_signedness = Positive;
444 }

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
nbit position to clear

Definition at line 286 of file bigint.cpp.

286 {
287 const size_t which = n / WordInfo<word>::bits;
288
289 if(which < size()) {
290 const word mask = ~(static_cast<word>(1) << (n % WordInfo<word>::bits));
291 m_data.set_word_at(which, word_at(which) & mask);
292 }
293}

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
nthe BigInt value to compare with
check_signsinclude 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 139 of file bigint.cpp.

139 {
140 if(check_signs) {
141 if(other.signum() >= 0 && this->signum() < 0) {
142 return -1;
143 }
144
145 if(other.signum() < 0 && this->signum() >= 0) {
146 return 1;
147 }
148
149 if(other.signum() < 0 && this->signum() < 0) {
150 return (-bigint_cmp(this->_data(), this->size(), other._data(), other.size()));
151 }
152 }
153
154 return bigint_cmp(this->_data(), this->size(), other._data(), other.size());
155}

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
nthe 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 123 of file bigint.cpp.

123 {
124 if(signum() < 0) {
125 return -1; // other is positive ...
126 }
127
128 const size_t sw = this->sig_words();
129 if(sw > 1) {
130 return 1; // must be larger since other is just one word ...
131 }
132
133 return bigint_cmp(this->_data(), sw, &other, 1);
134}
int signum() const
Definition bigint.h:493

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 524 of file bigint.cpp.

524 {
525 // This code is assuming Negative == 0, Positive == 1
526
527 const auto mask = CT::Mask<uint8_t>::expand_bool(predicate);
528
529 const uint8_t current_sign = static_cast<uint8_t>(sign());
530
531 const uint8_t new_sign = mask.select(current_sign ^ 1, current_sign);
532
533 set_sign(static_cast<Sign>(new_sign));
534}
static constexpr Mask< T > expand_bool(bool v)
Definition ct_utils.h:402

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
nbit position to set
set_itif the bit should be set

Definition at line 526 of file bigint.h.

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

References word_at().

Referenced by 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.

void _const_time_poison() const
Definition bigint.cpp:558

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.

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 452 of file bigint.cpp.

452 {
453 if(this->signum() < 0 || value.signum() < 0) {
454 throw Invalid_Argument("BigInt::ct_cond_add requires both values to be positive");
455 }
456 const size_t v_words = value.sig_words();
457
458 // The carry can propagate through every existing word of *this, so the
459 // output needs one slot above whichever input is wider.
460 this->grow_to(std::max(this->size(), v_words) + 1);
461
462 const auto mask = CT::Mask<word>::expand(static_cast<word>(predicate)).value();
463
464 word carry = 0;
465
466 word* x = this->mutable_data();
467 const word* y = value._data();
468
469 for(size_t i = 0; i != v_words; ++i) {
470 x[i] = word_add(x[i], y[i] & mask, &carry);
471 }
472
473 for(size_t i = v_words; i != size(); ++i) {
474 x[i] = word_add(x[i], static_cast<word>(0), &carry);
475 }
476}
static constexpr Mask< T > expand(T v)
Definition ct_utils.h:397
constexpr auto word_add(W x, W y, W *carry) -> W
Definition mp_asmi.h:260

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

Referenced by Botan::inverse_mod_general().

◆ 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 536 of file bigint.cpp.

536 {
537 const size_t t_words = size();
538 const size_t o_words = other.size();
539
540 if(t_words < o_words) {
541 grow_to(o_words);
542 }
543
544 const size_t r_words = std::max(t_words, o_words);
545
546 const auto mask = CT::Mask<word>::expand_bool(predicate);
547
548 for(size_t i = 0; i != r_words; ++i) {
549 const word o_word = other.word_at(i);
550 const word t_word = this->word_at(i);
551 this->set_word_at(i, mask.select(o_word, t_word));
552 }
553
554 const auto same_sign = CT::Mask<word>::is_equal(sign(), other.sign()).as_choice();
555 cond_flip_sign((mask.as_choice() && !same_sign).as_bool());
556}
void set_word_at(size_t i, word w)
Definition bigint.h:608
void cond_flip_sign(bool predicate)
Definition bigint.cpp:524
static constexpr Mask< T > is_equal(T x, T y)
Definition ct_utils.h:447

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(), 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 516 of file bigint.cpp.

516 {
517 const size_t max_words = std::max(size(), other.size());
518 grow_to(max_words);
519 other.grow_to(max_words);
520
521 bigint_cnd_swap(static_cast<word>(predicate), this->mutable_data(), other.mutable_data(), max_words);
522}
constexpr void bigint_cnd_swap(W cnd, W x[], W y[], size_t size)
Definition mp_core.h:33

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 362 of file bigint.cpp.

362 {
363 if(mod.signum() < 0 || this->signum() < 0) {
364 throw Invalid_Argument("BigInt::ct_reduce_below both values must be positive");
365 }
366
367 const size_t mod_words = mod.sig_words();
368
369 grow_to(mod_words);
370
371 const size_t sz = size();
372
373 ws.resize(sz);
374
375 clear_mem(ws.data(), sz);
376
377 for(size_t i = 0; i != bound; ++i) {
378 const word borrow = bigint_sub3(ws.data(), _data(), sz, mod._data(), mod_words);
379
380 CT::Mask<word>::is_zero(borrow).select_n(mutable_data(), ws.data(), _data(), sz);
381 }
382}
static constexpr Mask< T > is_zero(T x)
Definition ct_utils.h:442
constexpr void clear_mem(T *ptr, size_t n)
Definition mem_ops.h:118

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

Referenced by mod_mul().

◆ 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 478 of file bigint.cpp.

478 {
480
481 constexpr size_t bits_in_word = sizeof(word) * 8;
482 const size_t word_shift = shift >> ceil_log2(bits_in_word); // shift / bits_in_word
483 const size_t bit_shift = shift & ((1 << ceil_log2(bits_in_word)) - 1); // shift % bits_in_word
484 const size_t iterations = std::max(size(), bits_in_word) - 1; // uint64_t i; i << 64 is undefined behaviour
485
486 const size_t n = size();
487
488 // Workspace 1 word larger to catch overflow from bigint_shl2
489 secure_vector<word> ws(n + 1);
490
491 // In every iteration, shift one bit and one word to the left and use the
492 // shift results only when they are within the shift range.
493 for(size_t i = 0; i < iterations; ++i) {
494 // Shift left by 1 bit, dropping overflow
495 bigint_shl2(ws.data(), n + 1, _data(), n, 1);
496 ws[n] = 0;
497
498 // Conditionally assign the bit-shift result
499 const auto bmask = CT::Mask<word>::expand_bool(i < bit_shift);
500 for(size_t j = 0; j != n; ++j) {
501 m_data.set_word_at(j, bmask.select(ws[j], word_at(j)));
502 }
503
504 // Shift left by 1 word, dropping the most significant word
505 bigint_shl2(ws.data(), n + 1, _data(), n - 1 /* ignore msw */, WordInfo<word>::bits);
506 ws[0] = 0;
507
508 // Conditionally assign the word-shift result
509 const auto wmask = CT::Mask<word>::expand_bool(i < word_shift);
510 for(size_t j = 0; j != n; ++j) {
511 m_data.set_word_at(j, wmask.select(ws[j], word_at(j)));
512 }
513 }
514}
#define BOTAN_ASSERT_NOMSG(expr)
Definition assert.h:82
constexpr uint8_t ceil_log2(T x)
Definition bit_ops.h:140
std::vector< T, secure_allocator< T > > secure_vector
Definition secmem.h:128
constexpr void bigint_shl2(W y[], size_t y_size, const W x[], size_t x_size, size_t shift)
Definition mp_core.h:359

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.

718{ 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
bufthe binary value to load
lengthsize of buf
Returns
BigInt representing the integer in the byte array

Definition at line 943 of file bigint.h.

943 {
944 return BigInt::from_bytes(std::span{buf, length});
945 }
static BigInt from_bytes(std::span< const uint8_t > bytes)
Definition bigint.cpp:84

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
bufthe binary value to load
lengthsize of buf
Base Typesnumber-base of the integer in buf
Returns
BigInt representing the integer in the byte array

Definition at line 211 of file big_code.cpp.

211 {
212 if(base == Binary) {
213 return BigInt::from_bytes(std::span{buf, length});
214 } else if(base == Hexadecimal) {
215 const std::string_view sv{cast_uint8_ptr_to_char(buf), length};
216 return BigInt::from_radix_digits(sv, 16);
217 } else if(base == Decimal) {
218 const std::string_view sv{cast_uint8_ptr_to_char(buf), length};
219 return BigInt::from_radix_digits(sv, 10);
220 } else {
221 throw Invalid_Argument("Unknown BigInt decoding method");
222 }
223}
static BigInt from_radix_digits(std::string_view digits, size_t radix)
Definition big_code.cpp:126
const char * cast_uint8_ptr_to_char(const uint8_t *b)
Definition mem_ops.h:323

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
bufthe binary value to load
Returns
BigInt representing the integer in the byte array

Definition at line 952 of file bigint.h.

952 {
953 return BigInt::from_bytes(buf);
954 }

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
bufthe binary value to load
Base Typesnumber-base of the integer in buf
Returns
BigInt representing the integer in the byte array

Definition at line 201 of file big_code.cpp.

201 {
202 if(base == Binary) {
203 return BigInt::from_bytes(buf);
204 }
205 return BigInt::decode(buf.data(), buf.size(), base);
206}

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
nthe 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.

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

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
nthe BigInt to encode
bytesthe 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.

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

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
outthe buffer to write to; its size determines the encoding length
nthe integer to encode

Definition at line 990 of file bigint.h.

990 {
991 n.serialize_to(out);
992 }

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
outthe buffer to write to
bytesthe length of the encoding
nthe integer to encode

Definition at line 1001 of file bigint.h.

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

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
n1the first BigInt to encode
n2the second BigInt to encode
bytesthe 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 187 of file big_code.cpp.

187 {
188 if(n1.signum() < 0 || n2.signum() < 0) {
189 throw Encoding_Error("encode_fixed_length_int_pair: values must be positive");
190 }
191 if(n1.bytes() > bytes || n2.bytes() > bytes) {
192 throw Encoding_Error("encode_fixed_length_int_pair: values too large to encode properly");
193 }
194 secure_vector<uint8_t> output(2 * bytes);
195 BufferStuffer stuffer(output);
196 n1.serialize_to(stuffer.next(bytes));
197 n2.serialize_to(stuffer.next(bytes));
198 return output;
199}

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
nthe 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.

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

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 181 of file bigint.cpp.

181 {
182 const size_t words = sig_words();
183
184 if(words > size) {
185 throw Encoding_Error("BigInt::encode_words value too large to encode");
186 }
187
188 clear_mem(out, size);
189 copy_mem(out, _data(), words);
190}
constexpr void copy_mem(T *out, const T *in, size_t n)
Definition mem_ops.h:144

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.

Sign reverse_sign() const
Definition bigint.h:647

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

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

◆ from_bytes()

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

◆ 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
bufthe byte array holding the value
lengthsize of buf
max_bitsif the resulting integer is more than max_bits, it will be shifted so it is at most max_bits in length.

Definition at line 98 of file bigint.cpp.

98 {
99 const size_t input_bits = 8 * length;
100
101 auto bn = BigInt::from_bytes(std::span{input, length});
102
103 if(input_bits > max_bits) {
104 const size_t bits_to_shift = input_bits - max_bits;
105
106 bn >>= bits_to_shift;
107 }
108
109 return bn;
110}

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
digitsthe sequence of digits
radixthe base

Definition at line 126 of file big_code.cpp.

126 {
127 if(radix == 16) {
129
130 if(digits.size() % 2 == 1) {
131 // Handle lack of leading 0
132 const char buf0_with_leading_0[2] = {'0', digits[0]};
133
134 binary = hex_decode_locked(buf0_with_leading_0, 2);
135
136 if(digits.size() > 1) {
137 binary += hex_decode_locked(&digits[1], digits.size() - 1, false);
138 }
139 } else {
140 binary = hex_decode_locked(digits, false);
141 }
142
143 return BigInt::from_bytes(binary);
144 } else if(radix == 10) {
145 // Use the largest power of 10 that fits in a word, accumulating
146 // groups of digits into word-sized chunks to minimize the number
147 // of multiprecision multiplications.
148 constexpr word conversion_radix = decimal_conversion_radix();
149 constexpr size_t radix_digits = decimal_conversion_radix_digits();
150
151 BigInt r;
152
153 // Handle the initial partial block (if digit count is not a multiple of radix_digits)
154 const size_t partial_block = digits.size() % radix_digits;
155
156 if(partial_block > 0) {
157 word acc = 0;
158 for(size_t i = 0; i < partial_block; ++i) {
159 const char c = digits[i];
160 BOTAN_ARG_CHECK(c >= '0' && c <= '9', "Invalid decimal character");
161 acc = acc * 10 + static_cast<word>(c - '0');
162 }
163 r += acc;
164 }
165
166 // Process full blocks of radix_digits
167 for(size_t i = partial_block; i != digits.size(); i += radix_digits) {
168 word acc = 0;
169 for(size_t j = 0; j < radix_digits; ++j) {
170 const char c = digits[i + j];
171 BOTAN_ARG_CHECK(c >= '0' && c <= '9', "Invalid decimal character");
172 acc = acc * 10 + static_cast<word>(c - '0');
173 }
174 r *= conversion_radix;
175 r += acc;
176 }
177
178 return r;
179 } else {
180 throw Invalid_Argument("BigInt::from_radix_digits unknown radix");
181 }
182}
#define BOTAN_ARG_CHECK(expr, msg)
Definition assert.h:33
secure_vector< uint8_t > hex_decode_locked(const char input[], size_t input_length, bool ignore_ws)
Definition hex.cpp:142

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
ninitial value of this BigInt

Definition at line 43 of file bigint.cpp.

43 {
44 if(n >= 0) {
45 return BigInt::from_u64(static_cast<uint64_t>(n));
46 } else {
47 return -BigInt::from_u64(static_cast<uint64_t>(-static_cast<int64_t>(n)));
48 }
49}
static BigInt from_u64(uint64_t n)
Definition bigint.cpp:31

References BigInt(), and from_u64().

Referenced by botan_mp_set_from_int(), Botan::EC_Group::EC_Group(), Botan::EC_Point::randomize_repr(), Botan::EC_Group::register_custom_group(), 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
strthe string to parse for an integer value

Definition at line 58 of file bigint.cpp.

58 {
59 size_t prefix_bytes = 0;
60 bool negative = false;
61 size_t radix = 10;
62
63 if(!str.empty() && str[0] == '-') {
64 prefix_bytes += 1;
65 negative = true;
66 }
67
68 if(str.length() > prefix_bytes + 2 && str[prefix_bytes] == '0' && str[prefix_bytes + 1] == 'x') {
69 prefix_bytes += 2;
70 radix = 16;
71 }
72
73 BigInt r = BigInt::from_radix_digits(str.substr(prefix_bytes), radix);
74
75 if(negative) {
76 r.set_sign(Negative);
77 } else {
78 r.set_sign(Positive);
79 }
80
81 return r;
82}

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
ninitial value of this BigInt

Definition at line 31 of file bigint.cpp.

31 {
32 return BigInt(n);
33}

References BigInt().

Referenced by Botan::DER_Encoder::encode(), Botan::DER_Encoder::encode(), Botan::Cert_Extension::TNAuthList::Entry::encode_into(), from_s32(), Botan::generate_rsa_prime(), one(), and Botan::RSA_PrivateKey::RSA_PrivateKey().

◆ from_word()

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

Create BigInt from a word (limb)

Parameters
ninitial value of this BigInt

Definition at line 36 of file bigint.cpp.

36 {
37 BigInt bn;
38 bn.set_word_at(0, n);
39 return bn;
40}

References BigInt(), and set_word_at().

Referenced by Botan::DL_Group::DL_Group(), 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
nthe bit offset to test
Returns
true, if the bit at position n is set, false otherwise

Definition at line 549 of file bigint.h.

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

References word_at().

Referenced by Botan::EC_Point::encode(), Botan::inverse_mod_general(), is_even(), 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
offsetthe offset to start extracting
lengthamount of bits to extract (starting at offset)
Returns
the integer extracted from the register starting at offset with specified length

Definition at line 240 of file bigint.cpp.

240 {
241 if(length == 0 || length > 32) {
242 throw Invalid_Argument("BigInt::get_substring invalid substring length");
243 }
244
245 const uint32_t mask = 0xFFFFFFFF >> (32 - length);
246
247 const size_t word_offset = offset / WordInfo<word>::bits;
248 const size_t wshift = (offset % WordInfo<word>::bits);
249
250 /*
251 * The substring is contained within one or at most two words. The
252 * offset and length are not secret, so we can perform conditional
253 * operations on those values.
254 */
255 const word w0 = word_at(word_offset);
256
257 if(wshift == 0 || (offset + length) / WordInfo<word>::bits == word_offset) {
258 return static_cast<uint32_t>(w0 >> wshift) & mask;
259 } else {
260 const word w1 = word_at(word_offset + 1);
261 return static_cast<uint32_t>((w0 >> wshift) | (w1 << (WordInfo<word>::bits - wshift))) & mask;
262 }
263}

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.

723 {
724 return m_data.mutable_vector();
725 }

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.

730 {
731 return m_data.const_vector();
732 }

References get_word_vector().

◆ grow_to()

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

◆ is_equal()

bool Botan::BigInt::is_equal ( const BigInt & n) const

Compare this to another BigInt

Parameters
nthe BigInt value to compare with
Returns
true if this == n or false otherwise

Definition at line 157 of file bigint.cpp.

157 {
158 if(this->sign() != other.sign()) {
159 return false;
160 }
161
162 return bigint_ct_is_eq(this->_data(), this->size(), other._data(), other.size()).as_bool();
163}
constexpr auto bigint_ct_is_eq(const W x[], size_t x_size, const W y[], size_t y_size) -> CT::Mask< W >
Definition mp_core.h:543

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.

481{ return !get_bit(0); }
bool get_bit(size_t n) const
Definition bigint.h:549

References get_bit().

Referenced by Botan::generate_rsa_prime(), Botan::inverse_mod(), Botan::inverse_mod_general(), Botan::is_bailie_psw_probable_prime(), Botan::is_bailie_psw_probable_prime_vartime(), and Botan::random_prime().

◆ is_less_than()

bool Botan::BigInt::is_less_than ( const BigInt & n) const

Compare this to another BigInt

Parameters
nthe BigInt value to compare with
Returns
true if this < n or false otherwise

Definition at line 165 of file bigint.cpp.

165 {
166 if(this->signum() < 0 && other.signum() >= 0) {
167 return true;
168 }
169
170 if(this->signum() >= 0 && other.signum() < 0) {
171 return false;
172 }
173
174 if(other.signum() < 0 && this->signum() < 0) {
175 return bigint_ct_is_lt(other._data(), other.size(), this->_data(), this->size()).as_bool();
176 }
177
178 return bigint_ct_is_lt(this->_data(), this->size(), other._data(), other.size()).as_bool();
179}
constexpr auto bigint_ct_is_lt(const W x[], size_t x_size, const W y[], size_t y_size, bool lt_or_equal=false) -> CT::Mask< W >
Definition mp_core.h:510

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.

623{ return signum() < 0; }

References is_negative(), and signum().

Referenced by Botan::BER_Decoder::decode_constrained_integer(), Botan::Cert_Extension::TNAuthList::Entry::decode_from(), 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.

504{ 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.

487{ 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::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.

633 {
634 return signum() >= 0;
635 }

References is_positive(), and signum().

Referenced by is_positive().

◆ is_zero()

◆ mask_bits()

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

Clear all but the lowest n bits

Parameters
namount of bits to keep

Definition at line 542 of file bigint.h.

542{ 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
ythe BigInt to add - assumed y >= 0 and y < mod
modthe positive modulus
wsa temp workspace

Definition at line 61 of file big_ops2.cpp.

61 {
62 if(this->signum() < 0 || s.signum() < 0 || mod.signum() < 0) {
63 throw Invalid_Argument("BigInt::mod_add expects all arguments are positive");
64 }
65
66 BOTAN_DEBUG_ASSERT(*this < mod);
67 BOTAN_DEBUG_ASSERT(s < mod);
68
69 /*
70 t + s or t + s - p == t - (p - s)
71
72 So first compute ws = p - s
73
74 Then compute t + s and t - ws
75
76 If t - ws does not borrow, then that is the correct valued
77 */
78
79 const size_t mod_sw = mod.sig_words();
80 BOTAN_ARG_CHECK(mod_sw > 0, "BigInt::mod_add modulus must be positive");
81
82 this->grow_to(mod_sw);
83 s.grow_to(mod_sw);
84
85 // First mod_sw for p - s, 2*mod_sw for bigint_addsub workspace
86 if(ws.size() < 3 * mod_sw) {
87 ws.resize(3 * mod_sw);
88 }
89
90 // NOLINTBEGIN(readability-container-data-pointer)
91
92 word borrow = bigint_sub3(&ws[0], mod._data(), mod_sw, s._data(), mod_sw);
93 BOTAN_DEBUG_ASSERT(borrow == 0);
94 BOTAN_UNUSED(borrow);
95
96 // Compute t - ws
97 borrow = bigint_sub3(&ws[mod_sw], this->_data(), mod_sw, &ws[0], mod_sw);
98
99 // Compute t + s
100 bigint_add3(&ws[mod_sw * 2], this->_data(), mod_sw, s._data(), mod_sw);
101
102 CT::conditional_copy_mem(borrow, &ws[0], &ws[mod_sw * 2], &ws[mod_sw], mod_sw);
103 set_words(&ws[0], mod_sw);
104
105 // NOLINTEND(readability-container-data-pointer)
106
107 return (*this);
108}
#define BOTAN_UNUSED
Definition assert.h:151
#define BOTAN_DEBUG_ASSERT(expr)
Definition assert.h:136
void set_words(const word w[], size_t len)
Definition bigint.h:615
constexpr Mask< T > conditional_copy_mem(Mask< T > mask, T *dest, const T *if_set, const T *if_unset, size_t elems)
Definition ct_utils.h:737

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
ythe small integer to multiply by
modthe positive modulus
wsa temp workspace

Definition at line 138 of file big_ops2.cpp.

138 {
139 BOTAN_ARG_CHECK(this->signum() >= 0, "*this must be positive");
140 BOTAN_ARG_CHECK(y < 16, "y too large");
141
142 BOTAN_DEBUG_ASSERT(*this < mod);
143
144 *this *= static_cast<word>(y);
145 // Since *this < mod, the product is less than y * mod
146 this->ct_reduce_below(mod, ws, y);
147 return (*this);
148}
void ct_reduce_below(const BigInt &mod, secure_vector< word > &ws, size_t bound)
Definition bigint.cpp:362

References BigInt(), BOTAN_ARG_CHECK, BOTAN_DEBUG_ASSERT, ct_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
ythe BigInt to subtract - assumed y >= 0 and y < mod
modthe positive modulus
wsa temp workspace

Definition at line 110 of file big_ops2.cpp.

110 {
111 if(this->signum() < 0 || s.signum() < 0 || mod.signum() < 0) {
112 throw Invalid_Argument("BigInt::mod_sub expects all arguments are positive");
113 }
114
115 // We are assuming in this function that *this and s are no more than mod_sw words long
116 BOTAN_DEBUG_ASSERT(*this < mod);
117 BOTAN_DEBUG_ASSERT(s < mod);
118
119 const size_t mod_sw = mod.sig_words();
120
121 this->grow_to(mod_sw);
122 s.grow_to(mod_sw);
123
124 if(ws.size() < mod_sw) {
125 ws.resize(mod_sw);
126 }
127
128 const word borrow = bigint_sub3(ws.data(), mutable_data(), mod_sw, s._data(), mod_sw);
129
130 // Conditionally add back the modulus
131 bigint_cnd_add(borrow, ws.data(), mod._data(), mod_sw);
132
133 unchecked_copy_memory(mutable_data(), ws.data(), mod_sw);
134
135 return (*this);
136}
constexpr W bigint_cnd_add(W cnd, W x[], const W y[], size_t size)
Definition mp_core.h:49
void unchecked_copy_memory(T *out, const T *in, size_t n)
Definition mem_utils.h:44

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
ythe BigInt to multiply with this
wsa temp workspace

Definition at line 166 of file big_ops2.cpp.

166 {
167 const size_t x_sw = sig_words();
168 const size_t y_sw = y.sig_words();
169 set_sign((sign() == y.sign()) ? Positive : Negative);
170
171 if(x_sw == 0 || y_sw == 0) {
172 clear();
174 } else if(x_sw == 1 && y_sw > 0) {
175 grow_to(y_sw + 1);
176 bigint_linmul3(mutable_data(), y._data(), y_sw, word_at(0));
177 } else {
178 const size_t new_size = x_sw + y_sw + 1;
179 if(ws.size() < new_size) {
180 ws.resize(new_size);
181 }
182 secure_vector<word> z_reg(new_size);
183
184 bigint_mul(z_reg.data(), z_reg.size(), _data(), size(), x_sw, y._data(), y.size(), y_sw, ws.data(), ws.size());
185
186 this->swap_reg(z_reg);
187 }
188
189 return (*this);
190}
void clear()
Definition bigint.h:441
void swap_reg(secure_vector< word > &reg)
Definition bigint.h:218
constexpr void bigint_linmul3(W z[], const W x[], size_t x_size, W y)
Definition mp_core.h:420
void bigint_mul(word z[], size_t z_size, const word x[], size_t x_size, size_t x_sw, const word y[], size_t y_size, size_t y_sw, word workspace[], size_t ws_size)
Definition mp_karat.cpp:283

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

◆ one()

BigInt Botan::BigInt::one ( )
inlinestatic

Create a 1-value BigInt

Definition at line 55 of file bigint.h.

55{ return BigInt::from_u64(1); }

References BigInt(), and from_u64().

Referenced by 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.

327{ return is_zero(); }
bool is_zero() const
Definition bigint.h:510

References is_zero().

◆ operator%=() [1/2]

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

Modulo operator

Parameters
ythe modulus to reduce this by

Definition at line 236 of file big_ops2.cpp.

236 {
237 return (*this = (*this) % mod);
238}

References BigInt().

◆ operator%=() [2/2]

word Botan::BigInt::operator%= ( word y)

Modulo operator

Parameters
ythe modulus (word) to reduce this by

Definition at line 243 of file big_ops2.cpp.

243 {
244 if(mod == 0) {
245 throw Invalid_Argument("BigInt::operator%= divide by zero");
246 }
247
248 word remainder = 0;
249
250 if(is_power_of_2(mod)) {
251 remainder = (word_at(0) & (mod - 1));
252 } else {
253 const auto redc_mod = divide_precomp<word>::setup_vartime(mod);
254 const size_t sw = sig_words();
255 for(size_t i = sw; i > 0; --i) {
256 remainder = redc_mod.mod_2to1(remainder, word_at(i - 1));
257 }
258 }
259
260 if(remainder != 0 && sign() == BigInt::Negative) {
261 remainder = mod - remainder;
262 }
263
264 m_data.set_to_zero();
265 m_data.set_word_at(0, remainder);
267 return remainder;
268}
static constexpr divide_precomp setup_vartime(W divisor)
Definition mp_core.h:687
BOTAN_FORCE_INLINE constexpr bool is_power_of_2(T arg)
Definition bit_ops.h:62

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

◆ operator*=() [1/2]

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

*= operator

Parameters
ythe BigInt to multiply with this

Definition at line 161 of file big_ops2.cpp.

161 {
163 return this->mul(y, ws);
164}
BigInt & mul(const BigInt &y, secure_vector< word > &ws)
Definition big_ops2.cpp:166

References BigInt(), and mul().

◆ operator*=() [2/2]

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

*= operator

Parameters
ythe word to multiply with this

Definition at line 206 of file big_ops2.cpp.

206 {
207 if(y == 0) {
208 clear();
210 }
211
212 const size_t x_sw = sig_words();
213 grow_to(x_sw + 1);
214
215 const word carry = bigint_linmul2(mutable_data(), x_sw, y);
216 mutable_data()[x_sw] = carry;
217
218 return (*this);
219}
constexpr auto bigint_linmul2(W x[], size_t x_size, W y) -> W
Definition mp_core.h:409

References BigInt(), Botan::bigint_linmul2(), clear(), grow_to(), mutable_data(), Positive, set_sign(), and sig_words().

◆ operator++() [1/2]

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

Increment operator

Definition at line 292 of file bigint.h.

292{ 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.

302 {
303 BigInt x = (*this);
304 ++(*this);
305 return x;
306 }

References BigInt().

◆ operator+=() [1/2]

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

+= operator

Parameters
ythe BigInt to add to this

Definition at line 16 of file big_ops2.cpp.

16 {
17 if(&y == this) {
18 return *this <<= 1;
19 }
20 return add(y._data(), y.sig_words(), y.sign());
21}
BigInt & add(const word y[], size_t y_words, Sign sign)
Definition big_ops2.cpp:32

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

◆ operator+=() [2/2]

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

+= operator

Parameters
ythe word to add to this

Definition at line 233 of file bigint.h.

233{ 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 324 of file bigint.cpp.

324 {
325 BigInt x = (*this);
326 x.flip_sign();
327 return x;
328}

References BigInt(), and flip_sign().

◆ operator--() [1/2]

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

Decrement operator

Definition at line 297 of file bigint.h.

297{ 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.

311 {
312 BigInt x = (*this);
313 --(*this);
314 return x;
315 }

References BigInt().

◆ operator-=() [1/2]

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

-= operator

Parameters
ythe BigInt to subtract from this

Definition at line 23 of file big_ops2.cpp.

23 {
24 if(&y == this) {
25 this->clear();
26 this->set_sign(Positive);
27 return *this;
28 }
29 return sub(y._data(), y.sig_words(), y.sign());
30}
BigInt & sub(const word y[], size_t y_words, Sign sign)
Definition bigint.h:358

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

◆ operator-=() [2/2]

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

-= operator

Parameters
ythe word to subtract from this

Definition at line 245 of file bigint.h.

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

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

◆ operator/=()

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

/= operator

Parameters
ythe BigInt to divide this by

Definition at line 224 of file big_ops2.cpp.

224 {
225 if(y.sig_words() == 1 && signum() >= 0 && y.signum() >= 0 && is_power_of_2(y.word_at(0))) {
226 (*this) >>= (y.bits() - 1);
227 } else {
228 (*this) = (*this) / y;
229 }
230 return (*this);
231}

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
shiftthe number of bits to shift this left by

Definition at line 273 of file big_ops2.cpp.

273 {
274 if(shift >= 65536) {
275 throw Invalid_Argument("BigInt left shift count too large");
276 }
277
278 const size_t sw = sig_words();
279 const size_t new_size = sw + (shift + WordInfo<word>::bits - 1) / WordInfo<word>::bits;
280
281 m_data.grow_to(new_size);
282
283 bigint_shl1(m_data.mutable_data(), new_size, sw, shift);
284
285 return (*this);
286}
constexpr void bigint_shl1(W x[], size_t x_size, size_t x_words, size_t shift)
Definition mp_core.h:313

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.

190 {
191 if(this != &other) {
192 this->swap(other);
193 }
194
195 return (*this);
196 }

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
shiftthe number of bits to shift this right by

Definition at line 291 of file big_ops2.cpp.

291 {
292 bigint_shr1(m_data.mutable_data(), m_data.size(), shift);
293
294 if(sig_words() == 0 && m_signedness == Negative) {
295 m_signedness = Positive;
296 }
297
298 return (*this);
299}
constexpr void bigint_shr1(W x[], size_t x_size, size_t shift)
Definition mp_core.h:335

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
nthe power of two to create
Returns
bigint representing 2^n

Definition at line 906 of file bigint.h.

906 {
907 BigInt b;
908 b.set_bit(n);
909 return b;
910 }

References BigInt(), and set_bit().

Referenced by Botan::ct_divide_pow2k(), Botan::inverse_mod_general(), Botan::EC_Group::register_custom_group(), 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 Generatorsa random number generator
minthe minimum value (must be non-negative)
maxthe maximum value (must be non-negative and > min)
Returns
random integer in [min,max)

Definition at line 45 of file big_rand.cpp.

45 {
46 if(min.signum() < 0 || max.signum() < 0 || max <= min) {
47 throw Invalid_Argument("BigInt::random_integer invalid range");
48 }
49
50 /*
51 If min is > 1 then we generate a random number `r` in [0,max-min)
52 and return min + r.
53
54 This same logic could also be reasonably chosen for min == 1, but
55 that breaks certain tests which expect stability of this function
56 when generating within [1,n)
57 */
58 if(min > 1) {
59 const BigInt diff = max - min;
60 // This call is recursive, but will not recurse further
61 return min + BigInt::random_integer(rng, BigInt::zero(), diff);
62 }
63
64 BOTAN_DEBUG_ASSERT(min <= 1);
65
66 const size_t bits = max.bits();
67
68 for(;;) {
69 BigInt r;
70 r.randomize(rng, bits, false);
71 if(r >= min && r < max) {
72 return r;
73 }
74 }
75}
static BigInt zero()
Definition bigint.h:50
static BigInt random_integer(RandomNumberGenerator &rng, const BigInt &min, const BigInt &max)
Definition big_rand.cpp:45

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

Referenced by botan_mp_rand_range(), 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 Generatorsthe random number generator to use
bitsizenumber of bits the created random value should have
set_high_bitif true, the highest bit is always set

Definition at line 20 of file big_rand.cpp.

20 {
22
23 if(bitsize == 0) {
24 clear();
25 } else {
26 secure_vector<uint8_t> array = rng.random_vec(ceil_tobytes(bitsize));
27
28 // Always cut unwanted bits
29 if(bitsize % 8 > 0) {
30 array[0] &= 0xFF >> (8 - (bitsize % 8));
31 }
32
33 // Set the highest bit if wanted
34 if(set_high_bit) {
35 array[0] |= 0x80 >> ((bitsize % 8) > 0 ? (8 - bitsize % 8) : 0);
36 }
37
38 assign_from_bytes(array);
39 }
40}

References Botan::ceil_tobytes(), clear(), Positive, Botan::RandomNumberGenerator::random_vec(), 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 330 of file bigint.cpp.

330 {
331 if(p.signum() < 0 || this->signum() < 0) {
332 throw Invalid_Argument("BigInt::reduce_below both values must be positive");
333 }
334
335 const size_t p_words = p.sig_words();
336
337 if(size() < p_words + 1) {
338 grow_to(p_words + 1);
339 }
340
341 if(ws.size() < p_words + 1) {
342 ws.resize(p_words + 1);
343 }
344
345 clear_mem(ws.data(), ws.size());
346
347 size_t reductions = 0;
348
349 for(;;) {
350 const word borrow = bigint_sub3(ws.data(), _data(), p_words + 1, p._data(), p_words);
351 if(borrow > 0) {
352 break;
353 }
354
355 ++reductions;
356 swap_reg(ws);
357 }
358
359 return reductions;
360}

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

◆ resize()

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

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

Parameters
sthe new size of the register in words

Definition at line 744 of file bigint.h.

744 {
745 m_data.resize(s);
746 set_sign(sign()); // handle possible zero
747 }

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
ythe BigInt to subtract from as a sequence of words
y_wordslength of y in words
wsa temp workspace

Definition at line 150 of file big_ops2.cpp.

150 {
151 BOTAN_UNUSED(ws);
152 BigInt y_bn;
153 y_bn.m_data.set_words(y, y_sw);
154 *this = y_bn - *this;
155 return (*this);
156}

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.

647 {
648 if(sign() == Positive) {
649 return Negative;
650 }
651 return Positive;
652 }

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.

803 {
804 return serialize<T>(this->bytes());
805 }
T serialize() const
Definition bigint.h:803

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.

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

References serialize_to().

Referenced by Botan::ASN1::integer_contents(), Botan::X509_Serial_Number::magnitude(), Botan::EC_Group_Data::scalar_from_bigint(), serialize(), Botan::Montgomery_Int::serialize(), 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
outdestination byte span for the integer value

Definition at line 396 of file bigint.cpp.

396 {
397 BOTAN_ARG_CHECK(this->bytes() <= output.size(), "Insufficient output space");
398
399 this->binary_encode(output.data(), output.size());
400}
void binary_encode(uint8_t buf[]) const
Definition bigint.h:811

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
nbit position to set

Definition at line 516 of file bigint.h.

516{ conditionally_set_bit(n, true); }
void conditionally_set_bit(size_t n, bool set_it)
Definition bigint.h:526

References conditionally_set_bit().

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

◆ set_sign()

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

◆ 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
iposition in the register
wthe value to set

Definition at line 608 of file bigint.h.

608{ m_data.set_word_at(i, w); }

References set_word_at().

Referenced by ct_cond_assign(), from_word(), 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
wthe words to set
lenthe number of words in w

Definition at line 615 of file bigint.h.

615 {
616 m_data.set_words(w, len);
617 }

References set_words().

Referenced by mod_add(), and set_words().

◆ sig_words()

◆ 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.

641{ 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.

493 {
494 if(sig_words() == 0) {
495 return 0;
496 }
497 return (sign() == Negative) ? -1 : 1;
498 }

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_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(), is_negative(), is_nonzero(), is_positive(), mod_add(), mod_mul(), Botan::mod_small_primes(), 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(), and to_u32bit().

◆ size()

◆ square()

BigInt & Botan::BigInt::square ( secure_vector< word > & ws)

Square value of *this

Parameters
wsa temp workspace

Definition at line 192 of file big_ops2.cpp.

192 {
193 const size_t sw = sig_words();
194
195 secure_vector<word> z(2 * sw);
196 ws.resize(z.size());
197
198 bigint_sqr(z.data(), z.size(), _data(), size(), sw, ws.data(), ws.size());
199
200 swap_reg(z);
202
203 return (*this);
204}
void bigint_sqr(word z[], size_t z_size, const word x[], size_t x_size, size_t x_sw, word workspace[], size_t ws_size)
Definition mp_karat.cpp:327

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
ythe words of the subtrahend
y_wordsthe number of words in y
signthe sign of the subtrahend
Returns
reference to *this

Definition at line 358 of file bigint.h.

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

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
otherBigInt to swap values with

Definition at line 207 of file bigint.h.

207 {
208 m_data.swap(other.m_data);
209 std::swap(m_signedness, other.m_signedness);
210 }

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
regthe register to swap with

Definition at line 218 of file bigint.h.

218 {
219 m_data.swap(reg);
220 // sign left unchanged
221 }

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.

40 {
41 // Use the largest power of 10 that fits in a word
42 constexpr word conversion_radix = decimal_conversion_radix();
43 constexpr size_t radix_digits = decimal_conversion_radix_digits();
44
45 // (over-)estimate of the number of digits needed; log2(10) ~ 3.3219
46 const size_t digit_estimate = static_cast<size_t>(1 + (static_cast<double>(this->bits()) / 3.32));
47
48 // (over-)estimate of db such that conversion_radix^db > *this
49 const size_t digit_blocks = (digit_estimate + radix_digits - 1) / radix_digits;
50
51 BigInt value = *this;
52 value.set_sign(Positive);
53
54 // Extract groups of digits into words
55 std::vector<word> digit_groups(digit_blocks);
56
57 for(size_t i = 0; i != digit_blocks; ++i) {
58 word remainder = 0;
59 ct_divide_word(value, conversion_radix, value, remainder);
60 digit_groups[i] = remainder;
61 }
62
63 BOTAN_ASSERT_NOMSG(value.is_zero());
64
65 // Extract digits from the groups
66 std::vector<uint8_t> digits(digit_blocks * radix_digits);
67
68 constexpr auto div_10 = divide_precomp<word>::setup(10);
69
70 for(size_t i = 0; i != digit_blocks; ++i) {
71 word remainder = digit_groups[i];
72 for(size_t j = 0; j != radix_digits; ++j) {
73 const auto [q, digit] = div_10.divmod_2to1_ct(0, remainder);
74 digits[radix_digits * i + j] = static_cast<uint8_t>(digit);
75 remainder = q;
76 }
77 }
78
79 // remove leading zeros
80 while(!digits.empty() && digits.back() == 0) {
81 digits.pop_back();
82 }
83
84 BOTAN_ASSERT_NOMSG(digit_estimate >= digits.size());
85
86 // Reverse the digits to big-endian and format to text
87 std::string s;
88 s.reserve(1 + digits.size());
89
90 if(signum() < 0) {
91 s += '-';
92 }
93
94 // Reverse and convert to textual digits
95 // TODO(Botan4) use std::ranges::reverse_view here once available (need newer Clang)
96 // NOLINTNEXTLINE(modernize-loop-convert)
97 for(auto i = digits.rbegin(); i != digits.rend(); ++i) {
98 s.push_back(*i + '0'); // assumes ASCII
99 }
100
101 if(s.empty()) {
102 s += '0';
103 }
104
105 return s;
106}
static constexpr divide_precomp setup(W divisor)
Definition mp_core.h:695
void ct_divide_word(const BigInt &x, word y, BigInt &q_out, word &r_out)
Definition divide.cpp:205

References BigInt(), bits(), BOTAN_ASSERT_NOMSG, Botan::ct_divide_word(), is_zero(), Positive, set_sign(), Botan::divide_precomp< W >::setup(), 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 108 of file big_code.cpp.

108 {
109 const size_t this_bytes = this->bytes();
110 std::vector<uint8_t> bits(std::max<size_t>(1, this_bytes));
111
112 if(this_bytes > 0) {
113 this->serialize_to(bits);
114 }
115
116 std::string hrep;
117 if(signum() < 0) {
118 hrep += '-';
119 }
120 hrep += "0x";
121 hrep += hex_encode(bits);
122 return hrep;
123}
void hex_encode(char output[], const uint8_t input[], size_t input_length, bool uppercase)
Definition hex.cpp:34

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 268 of file bigint.cpp.

268 {
269 if(signum() < 0) {
270 throw Encoding_Error("BigInt::to_u32bit: Number is negative");
271 }
272 if(bits() > 32) {
273 throw Encoding_Error("BigInt::to_u32bit: Number is too big to convert");
274 }
275
276 uint32_t out = 0;
277 for(size_t i = 0; i != 4; ++i) {
278 out = (out << 8) | byte_at(3 - i);
279 }
280 return out;
281}
uint8_t byte_at(size_t n) const
Definition bigint.cpp:119

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 299 of file bigint.cpp.

299 {
300 const size_t words = sig_words();
301
302 const word top_word = word_at(words - 1);
303 const size_t bits_used = high_bit(CT::value_barrier(top_word));
304 CT::unpoison(bits_used);
305 return WordInfo<word>::bits - bits_used;
306}
constexpr T value_barrier(T x)
BOTAN_FORCE_INLINE constexpr size_t high_bit(T n)
Definition bit_ops.h:73

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

Referenced by bits().

◆ with_capacity()

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

Create BigInt of specified size, all zeros

Parameters
nsize of the internal register in words

Definition at line 52 of file bigint.cpp.

52 {
53 BigInt bn;
54 bn.grow_to(size);
55 return bn;
56}

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

Referenced by add2(), 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
nposition in the register
Returns
value at position n

Definition at line 601 of file bigint.h.

601{ 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::jacobi(), Botan::low_zero_bits(), mul(), Botan::operator%(), Botan::operator%(), operator%=(), Botan::operator*(), Botan::operator/(), operator/=(), top_bits_free(), and word_at().

◆ zero()

◆ swap

void swap ( BigInt & x,
BigInt & y )
friend

Definition at line 212 of file bigint.h.

212{ x.swap(y); }

References BigInt().


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