Botan 3.9.0
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
BigIntadd (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 worddata () 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)
BigIntmod_add (const BigInt &y, const BigInt &mod, secure_vector< word > &ws)
BigIntmod_mul (uint8_t y, const BigInt &mod, secure_vector< word > &ws)
BigIntmod_sub (const BigInt &y, const BigInt &mod, secure_vector< word > &ws)
BigIntmul (const BigInt &y, secure_vector< word > &ws)
wordmutable_data ()
bool operator! () const
BigIntoperator%= (const BigInt &y)
word operator%= (word y)
BigIntoperator*= (const BigInt &y)
BigIntoperator*= (word y)
BigIntoperator++ ()
BigInt operator++ (int)
BigIntoperator+= (const BigInt &y)
BigIntoperator+= (word y)
BigInt operator- () const
BigIntoperator-- ()
BigInt operator-- (int)
BigIntoperator-= (const BigInt &y)
BigIntoperator-= (word y)
BigIntoperator/= (const BigInt &y)
BigIntoperator<<= (size_t shift)
BigIntoperator= (BigInt &&other) noexcept
BigIntoperator= (const BigInt &)=default
BigIntoperator>>= (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)
BigIntrev_sub (const word y[], size_t y_words, secure_vector< word > &ws)
Sign reverse_sign () const
template<typename T = std::vector<uint8_t>>
serialize () const
template<typename T = std::vector<uint8_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
size_t size () const
BigIntsquare (secure_vector< word > &ws)
BigIntsub (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_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 25 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 30 of file bigint.h.

30 : uint16_t {
31 Decimal BOTAN_DEPRECATED("All functions using this enum are deprecated") = 10,
32 Hexadecimal BOTAN_DEPRECATED("All functions using this enum are deprecated") = 16,
33 Binary BOTAN_DEPRECATED("All functions using this enum are deprecated") = 256
34 };
#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 39 of file bigint.h.

39: uint8_t { 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 19 of file bigint.cpp.

19 {
20 if constexpr(sizeof(word) == 8) {
21 m_data.set_word_at(0, static_cast<word>(n));
22 } else {
23 m_data.set_word_at(1, static_cast<word>(n >> 32));
24 m_data.set_word_at(0, static_cast<word>(n));
25 }
26}
std::conditional_t< HasNative64BitRegisters, std::uint64_t, uint32_t > word
Definition types.h:119

◆ BigInt() [3/9]

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

Copy Constructor

Parameters
otherthe BigInt to copy

References BigInt(), and from_string().

◆ BigInt() [4/9]

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

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

59 {
60 Base base = Decimal;
61 size_t markers = 0;
62 bool negative = false;
63
64 if(!str.empty() && str[0] == '-') {
65 markers += 1;
66 negative = true;
67 }
68
69 if(str.length() > markers + 2 && str[markers] == '0' && str[markers + 1] == 'x') {
70 markers += 2;
71 base = Hexadecimal;
72 }
73
74 *this = decode(as_span_of_bytes(str).subspan(markers), base);
75
76 if(negative) {
78 } else {
80 }
81}
static BigInt decode(const uint8_t buf[], size_t length)
Definition bigint.h:857
void set_sign(Sign sign)
Definition bigint.h:592
std::span< const uint8_t > as_span_of_bytes(const char *s, size_t len)
Definition mem_utils.h:28

References Botan::as_span_of_bytes(), Decimal, decode(), Hexadecimal, Negative, Positive, and set_sign().

◆ 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 117 of file bigint.h.

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

References BigInt().

◆ 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 123 of file bigint.h.

123{ assign_from_bytes(bytes); }
size_t bytes() const
Definition bigint.cpp:298

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
baseis the number base of the integer in buf

Definition at line 96 of file bigint.cpp.

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

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

Definition at line 118 of file bigint.cpp.

118 {
119 randomize(rng, bits, set_high_bit);
120}
void randomize(RandomNumberGenerator &rng, size_t bitsize, bool set_high_bit=true)
Definition big_rand.cpp:18
size_t bits() const
Definition bigint.cpp:311

References bits(), and randomize().

◆ BigInt() [9/9]

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

Move constructor

Definition at line 167 of file bigint.h.

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

References BigInt(), and swap().

◆ ~BigInt()

Botan::BigInt::~BigInt ( )
inline

Definition at line 169 of file bigint.h.

void _const_time_unpoison() const
Definition bigint.cpp:557

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 926 of file bigint.h.

926{ 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 947 of file bigint.h.

947{ assign_from_bytes(bytes); }

References bytes().

Referenced by Botan::BER_Decoder::decode(), Botan::generate_dsa_primes(), 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 553 of file bigint.cpp.

553 {
554 CT::poison(m_data.const_data(), m_data.size());
555}
constexpr void poison(const T *p, size_t n)
Definition ct_utils.h:54

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

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

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 955 of file bigint.h.

955 {
956 BigInt bn;
957 bn.m_data.swap(words);
958 return bn;
959 }
BigInt()=default

References BigInt().

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

◆ abs()

BigInt Botan::BigInt::abs ( ) const
Returns
absolute (positive) value of this

Definition at line 390 of file bigint.cpp.

390 {
391 BigInt x = (*this);
392 x.set_sign(Positive);
393 return x;
394}

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

Referenced by Botan::abs().

◆ add()

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

Definition at line 16 of file big_ops2.cpp.

16 {
17 const size_t x_sw = sig_words();
18
19 grow_to(std::max(x_sw, y_words) + 1);
20
21 if(sign() == y_sign) {
22 word carry = bigint_add2(mutable_data(), size() - 1, y, y_words);
23 mutable_data()[size() - 1] += carry;
24 } else {
25 const int32_t relative_size = bigint_cmp(_data(), x_sw, y, y_words);
26
27 if(relative_size >= 0) {
28 // *this >= y
29 bigint_sub2(mutable_data(), x_sw, y, y_words);
30 } else {
31 // *this < y: compute *this = y - *this
32 bigint_sub2_rev(mutable_data(), y, y_words);
33 }
34
35 if(relative_size < 0) {
36 set_sign(y_sign);
37 } else if(relative_size == 0) {
39 }
40 }
41
42 return (*this);
43}
size_t sig_words() const
Definition bigint.h:615
word * mutable_data()
Definition bigint.h:640
size_t size() const
Definition bigint.h:609
void grow_to(size_t n) const
Definition bigint.h:666
const word * _data() const
Definition bigint.h:936
Sign sign() const
Definition bigint.h:571
constexpr auto bigint_add2(W x[], size_t x_size, const W y[], size_t y_size) -> W
Definition mp_core.h:96
constexpr int32_t bigint_cmp(const W x[], size_t x_size, const W y[], size_t y_size)
Definition mp_core.h:428
void carry(int64_t &h0, int64_t &h1)
constexpr auto bigint_sub2(W x[], size_t x_size, const W y[], size_t y_size) -> W
Definition mp_core.h:150
constexpr void bigint_sub2_rev(W x[], const W y[], size_t y_size)
Definition mp_core.h:176

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

Definition at line 19 of file big_ops3.cpp.

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

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
bufbyte array buffer containing the integer
lengthsize of buf

Definition at line 757 of file bigint.h.

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

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 765 of file bigint.h.

765 {
766 this->assign_from_bytes(buf);
767 }

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 732 of file bigint.h.

732 {
733 this->serialize_to(std::span{buf, this->bytes()});
734 }
void serialize_to(std::span< uint8_t > out) const
Definition bigint.cpp:399

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

408 {
409 const size_t full_words = len / sizeof(word);
410 const size_t extra_bytes = len % sizeof(word);
411
412 for(size_t i = 0; i != full_words; ++i) {
413 const word w = word_at(i);
414 store_be(w, output + (len - (i + 1) * sizeof(word)));
415 }
416
417 if(extra_bytes > 0) {
418 const word w = word_at(full_words);
419
420 for(size_t i = 0; i != extra_bytes; ++i) {
421 output[extra_bytes - i - 1] = get_byte_var(sizeof(word) - i - 1, w);
422 }
423 }
424}
word word_at(size_t n) const
Definition bigint.h:547
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 311 of file bigint.cpp.

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

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::DER_Encoder::encode(), 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::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
Parameters
nthe offset to get a byte from
Returns
byte at offset n

Definition at line 122 of file bigint.cpp.

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

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

298 {
299 return round_up(bits(), 8) / 8;
300}
constexpr size_t round_up(size_t n, size_t align_to)
Definition rounding.h:26

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

Referenced by _assign_from_bytes(), Botan::base58_decode(), BigInt(), binary_encode(), Botan::DER_Encoder::encode(), encode_1363(), encode_1363(), encode_fixed_length_int_pair(), 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 399 of file bigint.h.

399 {
400 m_data.set_to_zero();
401 m_signedness = Positive;
402 }

References clear(), and Positive.

Referenced by clear(), Botan::BER_Decoder::decode(), mul(), 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 289 of file bigint.cpp.

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

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

142 {
143 if(check_signs) {
144 if(other.is_positive() && this->is_negative()) {
145 return -1;
146 }
147
148 if(other.is_negative() && this->is_positive()) {
149 return 1;
150 }
151
152 if(other.is_negative() && this->is_negative()) {
153 return (-bigint_cmp(this->_data(), this->size(), other._data(), other.size()));
154 }
155 }
156
157 return bigint_cmp(this->_data(), this->size(), other._data(), other.size());
158}

References _data(), BigInt(), Botan::bigint_cmp(), is_negative(), is_positive(), 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 126 of file bigint.cpp.

126 {
127 if(is_negative()) {
128 return -1; // other is positive ...
129 }
130
131 const size_t sw = this->sig_words();
132 if(sw > 1) {
133 return 1; // must be larger since other is just one word ...
134 }
135
136 return bigint_cmp(this->_data(), sw, &other, 1);
137}
bool is_negative() const
Definition bigint.h:559

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

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

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

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 473 of file bigint.h.

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

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

Definition at line 803 of file bigint.h.

void _const_time_poison() const
Definition bigint.cpp:553

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

Definition at line 805 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 453 of file bigint.cpp.

453 {
454 if(this->is_negative() || value.is_negative()) {
455 throw Invalid_Argument("BigInt::ct_cond_add requires both values to be positive");
456 }
457 const size_t v_words = value.sig_words();
458
459 this->grow_to(1 + v_words);
460
461 const auto mask = CT::Mask<word>::expand(static_cast<word>(predicate)).value();
462
463 word carry = 0;
464
465 word* x = this->mutable_data();
466 const word* y = value._data();
467
468 for(size_t i = 0; i != v_words; ++i) {
469 x[i] = word_add(x[i], y[i] & mask, &carry);
470 }
471
472 for(size_t i = v_words; i != size(); ++i) {
473 x[i] = word_add(x[i], static_cast<word>(0), &carry);
474 }
475}
static constexpr Mask< T > expand(T v)
Definition ct_utils.h:420
constexpr auto word_add(W x, W y, W *carry) -> W
Definition mp_asmi.h:191

References _data(), BigInt(), Botan::carry(), Botan::CT::Mask< T >::expand(), grow_to(), is_negative(), mutable_data(), sig_words(), 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 531 of file bigint.cpp.

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

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

511 {
512 const size_t max_words = std::max(size(), other.size());
513 grow_to(max_words);
514 other.grow_to(max_words);
515
516 bigint_cnd_swap(static_cast<word>(predicate), this->mutable_data(), other.mutable_data(), max_words);
517}
constexpr void bigint_cnd_swap(W cnd, W x[], W y[], size_t size)
Definition mp_core.h:31

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

Referenced by Botan::ct_divide(), and Botan::ct_modulo().

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

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

References _data(), BigInt(), Botan::bigint_sub3(), Botan::clear_mem(), grow_to(), is_negative(), Botan::CT::Mask< T >::is_zero(), mutable_data(), sig_words(), 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 477 of file bigint.cpp.

477 {
478 auto shl_bit = [](const BigInt& a, BigInt& result) {
479 BOTAN_DEBUG_ASSERT(a.size() + 1 == result.size());
480 bigint_shl2(result.mutable_data(), a._data(), a.size(), 1);
481 // shl2 may have shifted a bit into the next word, which must be dropped
482 clear_mem(result.mutable_data() + result.size() - 1, 1);
483 };
484
485 auto shl_word = [](const BigInt& a, BigInt& result) {
486 // the most significant word is not copied, aka. shifted out
487 bigint_shl2(result.mutable_data(), a._data(), a.size() - 1 /* ignore msw */, WordInfo<word>::bits);
488 // we left-shifted by a full word, the least significant word must be zero'ed
489 clear_mem(result.mutable_data(), 1);
490 };
491
493
494 constexpr size_t bits_in_word = sizeof(word) * 8;
495 const size_t word_shift = shift >> ceil_log2(bits_in_word); // shift / bits_in_word
496 const size_t bit_shift = shift & ((1 << ceil_log2(bits_in_word)) - 1); // shift % bits_in_word
497 const size_t iterations = std::max(size(), bits_in_word) - 1; // uint64_t i; i << 64 is undefined behaviour
498
499 // In every iteration, shift one bit and one word to the left and use the
500 // shift results only when they are within the shift range.
501 BigInt tmp;
502 tmp.resize(size() + 1 /* to hold the shifted-out word */);
503 for(size_t i = 0; i < iterations; ++i) {
504 shl_bit(*this, tmp);
505 ct_cond_assign(i < bit_shift, tmp);
506 shl_word(*this, tmp);
507 ct_cond_assign(i < word_shift, tmp);
508 }
509}
#define BOTAN_ASSERT_NOMSG(expr)
Definition assert.h:75
#define BOTAN_DEBUG_ASSERT(expr)
Definition assert.h:129
void ct_cond_assign(bool predicate, const BigInt &other)
Definition bigint.cpp:531
constexpr uint8_t ceil_log2(T x)
Definition bit_ops.h:120
constexpr void bigint_shl2(W y[], const W x[], size_t x_size, size_t shift)
Definition mp_core.h:352

References _data(), BigInt(), Botan::bigint_shl2(), BOTAN_ASSERT_NOMSG, BOTAN_DEBUG_ASSERT, Botan::ceil_log2(), Botan::clear_mem(), ct_cond_assign(), resize(), and size().

◆ 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 646 of file bigint.h.

646{ 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 857 of file bigint.h.

857 {
858 return BigInt::from_bytes(std::span{buf, length});
859 }
static BigInt from_bytes(std::span< const uint8_t > bytes)
Definition bigint.cpp:87

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

Referenced by BigInt(), BigInt(), botan_mp_set_from_radix_str(), 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
basenumber-base of the integer in buf
Returns
BigInt representing the integer in the byte array

Definition at line 148 of file big_code.cpp.

148 {
149 if(base == Binary) {
150 return BigInt::from_bytes(std::span{buf, length});
151 } else if(base == Hexadecimal) {
152 BigInt r;
154
155 if(length % 2 == 1) {
156 // Handle lack of leading 0
157 const char buf0_with_leading_0[2] = {'0', static_cast<char>(buf[0])};
158
159 binary = hex_decode_locked(buf0_with_leading_0, 2);
160
161 if(length > 1) {
162 binary += hex_decode_locked(cast_uint8_ptr_to_char(&buf[1]), length - 1, false);
163 }
164 } else {
165 binary = hex_decode_locked(cast_uint8_ptr_to_char(buf), length, false);
166 }
167
168 r.assign_from_bytes(binary);
169 return r;
170 } else if(base == Decimal) {
171 BigInt r;
172 // This could be made faster using the same trick as to_dec_string
173 for(size_t i = 0; i != length; ++i) {
174 const char c = buf[i];
175
176 if(c < '0' || c > '9') {
177 throw Invalid_Argument("BigInt::decode: invalid decimal char");
178 }
179
180 const uint8_t x = c - '0';
181 BOTAN_ASSERT_NOMSG(x < 10);
182
183 r *= 10;
184 r += x;
185 }
186 return r;
187 } else {
188 throw Invalid_Argument("Unknown BigInt decoding method");
189 }
190}
secure_vector< uint8_t > hex_decode_locked(const char input[], size_t input_length, bool ignore_ws)
Definition hex.cpp:136
const char * cast_uint8_ptr_to_char(const uint8_t *b)
Definition mem_ops.h:282
std::vector< T, secure_allocator< T > > secure_vector
Definition secmem.h:69

References BigInt(), Binary, BOTAN_ASSERT_NOMSG, Botan::cast_uint8_ptr_to_char(), Decimal, from_bytes(), Botan::hex_decode_locked(), 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 866 of file bigint.h.

866 {
867 return BigInt::from_bytes(buf);
868 }

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
basenumber-base of the integer in buf
Returns
BigInt representing the integer in the byte array

Definition at line 138 of file big_code.cpp.

138 {
139 if(base == Binary) {
140 return BigInt::from_bytes(buf);
141 }
142 return BigInt::decode(buf.data(), buf.size(), base);
143}

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 831 of file bigint.h.

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

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 895 of file bigint.h.

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

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

Definition at line 899 of file bigint.h.

899 {
900 n.serialize_to(out);
901 }

References BigInt(), and encode_1363().

◆ encode_1363() [3/3]

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

Definition at line 904 of file bigint.h.

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

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 124 of file big_code.cpp.

124 {
125 if(n1.is_negative() || n2.is_negative()) {
126 throw Encoding_Error("encode_fixed_length_int_pair: values must be positive");
127 }
128 if(n1.bytes() > bytes || n2.bytes() > bytes) {
129 throw Encoding_Error("encode_fixed_length_int_pair: values too large to encode properly");
130 }
131 secure_vector<uint8_t> output(2 * bytes);
132 BufferStuffer stuffer(output);
133 n1.serialize_to(stuffer.next(bytes));
134 n2.serialize_to(stuffer.next(bytes));
135 return output;
136}

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

◆ 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 840 of file bigint.h.

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

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

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

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 586 of file bigint.h.

Sign reverse_sign() const
Definition bigint.h:576

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

Referenced by Botan::ct_divide_word(), Botan::BER_Decoder::decode(), flip_sign(), Botan::is_lucas_probable_prime(), 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 101 of file bigint.cpp.

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

References BigInt(), and from_bytes().

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

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

References BigInt(), and from_u64().

Referenced by botan_mp_set_from_int(), 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
strthe string to parse for an integer value

Definition at line 83 of file bigint.cpp.

83 {
84 return BigInt(str);
85}

References BigInt().

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

29 {
30 return BigInt(n);
31}

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

Definition at line 34 of file bigint.cpp.

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

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
nthe bit offset to test
Returns
true, if the bit at position n is set, false otherwise

Definition at line 496 of file bigint.h.

496{ 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
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 243 of file bigint.cpp.

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

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 651 of file bigint.h.

651 {
652 return m_data.mutable_vector();
653 }

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 658 of file bigint.h.

658 {
659 return m_data.const_vector();
660 }

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

160 {
161 if(this->sign() != other.sign()) {
162 return false;
163 }
164
165 return bigint_ct_is_eq(this->_data(), this->sig_words(), other._data(), other.sig_words()).as_bool();
166}
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:508

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

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 439 of file bigint.h.

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

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::jacobi(), 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
nthe BigInt value to compare with
Returns
true if this < n or false otherwise

Definition at line 168 of file bigint.cpp.

168 {
169 if(this->is_negative() && other.is_positive()) {
170 return true;
171 }
172
173 if(this->is_positive() && other.is_negative()) {
174 return false;
175 }
176
177 if(other.is_negative() && this->is_negative()) {
178 return bigint_ct_is_lt(other._data(), other.sig_words(), this->_data(), this->sig_words()).as_bool();
179 }
180
181 return bigint_ct_is_lt(this->_data(), this->sig_words(), other._data(), other.sig_words()).as_bool();
182}
bool is_positive() const
Definition bigint.h:565
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:475

References _data(), BigInt(), Botan::bigint_ct_is_lt(), is_negative(), is_positive(), and sig_words().

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

◆ 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 451 of file bigint.h.

451{ return (!is_zero()); }
bool is_zero() const
Definition bigint.h:457

References is_zero().

Referenced by Botan::ct_modulo(), Botan::inverse_mod_general(), and operator!().

◆ 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 445 of file bigint.h.

445{ return get_bit(0); }

References get_bit().

Referenced by Botan::inverse_mod_general(), Botan::inverse_mod_rsa_public_modulus(), Botan::inverse_mod_secret_prime(), Botan::is_lucas_probable_prime(), 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

Returns
true, iff the integer has a positive sign

Definition at line 565 of file bigint.h.

565{ return (sign() == Positive); }

References Positive, and sign().

Referenced by cmp(), Botan::ct_mod_word(), Botan::inverse_mod_rsa_public_modulus(), Botan::inverse_mod_secret_prime(), is_less_than(), Botan::is_lucas_probable_prime(), Botan::operator%(), Botan::Barrett_Reduction::reduce(), and Botan::vartime_divide().

◆ 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 489 of file bigint.h.

489{ 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 45 of file big_ops2.cpp.

45 {
46 if(this->is_negative() || s.is_negative() || mod.is_negative()) {
47 throw Invalid_Argument("BigInt::mod_add expects all arguments are positive");
48 }
49
50 BOTAN_DEBUG_ASSERT(*this < mod);
51 BOTAN_DEBUG_ASSERT(s < mod);
52
53 /*
54 t + s or t + s - p == t - (p - s)
55
56 So first compute ws = p - s
57
58 Then compute t + s and t - ws
59
60 If t - ws does not borrow, then that is the correct valued
61 */
62
63 const size_t mod_sw = mod.sig_words();
64 BOTAN_ARG_CHECK(mod_sw > 0, "BigInt::mod_add modulus must be positive");
65
66 this->grow_to(mod_sw);
67 s.grow_to(mod_sw);
68
69 // First mod_sw for p - s, 2*mod_sw for bigint_addsub workspace
70 if(ws.size() < 3 * mod_sw) {
71 ws.resize(3 * mod_sw);
72 }
73
74 // NOLINTBEGIN(readability-container-data-pointer)
75
76 word borrow = bigint_sub3(&ws[0], mod._data(), mod_sw, s._data(), mod_sw);
77 BOTAN_DEBUG_ASSERT(borrow == 0);
78 BOTAN_UNUSED(borrow);
79
80 // Compute t - ws
81 borrow = bigint_sub3(&ws[mod_sw], this->_data(), mod_sw, &ws[0], mod_sw);
82
83 // Compute t + s
84 bigint_add3(&ws[mod_sw * 2], this->_data(), mod_sw, s._data(), mod_sw);
85
86 CT::conditional_copy_mem(borrow, &ws[0], &ws[mod_sw * 2], &ws[mod_sw], mod_sw);
87 set_words(&ws[0], mod_sw);
88
89 // NOLINTEND(readability-container-data-pointer)
90
91 return (*this);
92}
#define BOTAN_UNUSED
Definition assert.h:144
#define BOTAN_ARG_CHECK(expr, msg)
Definition assert.h:33
void set_words(const word w[], size_t len)
Definition bigint.h:551
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:760

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

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 122 of file big_ops2.cpp.

122 {
123 BOTAN_ARG_CHECK(this->is_negative() == false, "*this must be positive");
124 BOTAN_ARG_CHECK(y < 16, "y too large");
125
126 BOTAN_DEBUG_ASSERT(*this < mod);
127
128 *this *= static_cast<word>(y);
129 this->reduce_below(mod, ws);
130 return (*this);
131}
size_t reduce_below(const BigInt &mod, secure_vector< word > &ws)
Definition bigint.cpp:333

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

◆ 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 94 of file big_ops2.cpp.

94 {
95 if(this->is_negative() || s.is_negative() || mod.is_negative()) {
96 throw Invalid_Argument("BigInt::mod_sub expects all arguments are positive");
97 }
98
99 // We are assuming in this function that *this and s are no more than mod_sw words long
100 BOTAN_DEBUG_ASSERT(*this < mod);
101 BOTAN_DEBUG_ASSERT(s < mod);
102
103 const size_t mod_sw = mod.sig_words();
104
105 this->grow_to(mod_sw);
106 s.grow_to(mod_sw);
107
108 if(ws.size() < mod_sw) {
109 ws.resize(mod_sw);
110 }
111
112 const word borrow = bigint_sub3(ws.data(), mutable_data(), mod_sw, s._data(), mod_sw);
113
114 // Conditionally add back the modulus
115 bigint_cnd_add(borrow, ws.data(), mod._data(), mod_sw);
116
117 copy_mem(mutable_data(), ws.data(), mod_sw);
118
119 return (*this);
120}
constexpr W bigint_cnd_add(W cnd, W x[], const W y[], size_t size)
Definition mp_core.h:47

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

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 149 of file big_ops2.cpp.

149 {
150 const size_t x_sw = sig_words();
151 const size_t y_sw = y.sig_words();
152 set_sign((sign() == y.sign()) ? Positive : Negative);
153
154 if(x_sw == 0 || y_sw == 0) {
155 clear();
157 } else if(x_sw == 1 && y_sw > 0) {
158 grow_to(y_sw + 1);
159 bigint_linmul3(mutable_data(), y._data(), y_sw, word_at(0));
160 } else {
161 const size_t new_size = x_sw + y_sw + 1;
162 if(ws.size() < new_size) {
163 ws.resize(new_size);
164 }
165 secure_vector<word> z_reg(new_size);
166
167 bigint_mul(z_reg.data(), z_reg.size(), _data(), size(), x_sw, y._data(), y.size(), y_sw, ws.data(), ws.size());
168
169 this->swap_reg(z_reg);
170 }
171
172 return (*this);
173}
void clear()
Definition bigint.h:399
void swap_reg(secure_vector< word > &reg)
Definition bigint.h:198
constexpr void bigint_linmul3(W z[], const W x[], size_t x_size, W y)
Definition mp_core.h:405
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()

◆ one()

BigInt Botan::BigInt::one ( )
inlinestatic

◆ operator!()

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

! operator

Returns
true iff this is zero, otherwise false

Definition at line 307 of file bigint.h.

307{ return (!is_nonzero()); }
bool is_nonzero() const
Definition bigint.h:451

References is_nonzero().

◆ operator%=() [1/2]

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

Modulo operator

Parameters
ythe modulus to reduce this by

Definition at line 216 of file big_ops2.cpp.

216 {
217 return (*this = (*this) % mod);
218}

References BigInt().

◆ operator%=() [2/2]

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

Modulo operator

Parameters
ythe modulus (word) to reduce this by

Definition at line 223 of file big_ops2.cpp.

223 {
224 if(mod == 0) {
225 throw Invalid_Argument("BigInt::operator%= divide by zero");
226 }
227
228 word remainder = 0;
229
230 if(is_power_of_2(mod)) {
231 remainder = (word_at(0) & (mod - 1));
232 } else {
233 const size_t sw = sig_words();
234 for(size_t i = sw; i > 0; --i) {
235 remainder = bigint_modop_vartime(remainder, word_at(i - 1), mod);
236 }
237 }
238
239 if(remainder != 0 && sign() == BigInt::Negative) {
240 remainder = mod - remainder;
241 }
242
243 m_data.set_to_zero();
244 m_data.set_word_at(0, remainder);
246 return remainder;
247}
BOTAN_FORCE_INLINE constexpr bool is_power_of_2(T arg)
Definition bit_ops.h:45
constexpr auto bigint_modop_vartime(W n1, W n0, W d) -> W
Definition mp_core.h:568

References Botan::bigint_modop_vartime(), Botan::is_power_of_2(), Negative, Positive, set_sign(), 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 144 of file big_ops2.cpp.

144 {
146 return this->mul(y, ws);
147}
BigInt & mul(const BigInt &y, secure_vector< word > &ws)
Definition big_ops2.cpp:149

References BigInt(), and mul().

◆ operator*=() [2/2]

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

*= operator

Parameters
ythe word to multiply with this

Definition at line 189 of file big_ops2.cpp.

189 {
190 if(y == 0) {
191 clear();
193 }
194
195 const word carry = bigint_linmul2(mutable_data(), size(), y);
197
198 return (*this);
199}
constexpr auto bigint_linmul2(W x[], size_t x_size, W y) -> W
Definition mp_core.h:394

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 272 of file bigint.h.

272{ return (*this += 1); }

References BigInt().

◆ operator++() [2/2]

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

Postfix increment operator

Definition at line 282 of file bigint.h.

282 {
283 BigInt x = (*this);
284 ++(*this);
285 return x;
286 }

References BigInt().

◆ operator+=() [1/2]

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

+= operator

Parameters
ythe BigInt to add to this

Definition at line 207 of file bigint.h.

207{ return add(y._data(), y.sig_words(), y.sign()); }
BigInt & add(const word y[], size_t y_words, Sign sign)
Definition big_ops2.cpp:16

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 213 of file bigint.h.

213{ 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 327 of file bigint.cpp.

327 {
328 BigInt x = (*this);
329 x.flip_sign();
330 return x;
331}

References BigInt(), and flip_sign().

◆ operator--() [1/2]

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

Decrement operator

Definition at line 277 of file bigint.h.

277{ return (*this -= 1); }

References BigInt().

◆ operator--() [2/2]

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

Postfix decrement operator

Definition at line 291 of file bigint.h.

291 {
292 BigInt x = (*this);
293 --(*this);
294 return x;
295 }

References BigInt().

◆ operator-=() [1/2]

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

-= operator

Parameters
ythe BigInt to subtract from this

Definition at line 219 of file bigint.h.

219{ return sub(y._data(), y.sig_words(), y.sign()); }
BigInt & sub(const word y[], size_t y_words, Sign sign)
Definition bigint.h:316

References _data(), BigInt(), 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 225 of file bigint.h.

225{ 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 204 of file big_ops2.cpp.

204 {
205 if(y.sig_words() == 1 && is_power_of_2(y.word_at(0))) {
206 (*this) >>= (y.bits() - 1);
207 } else {
208 (*this) = (*this) / y;
209 }
210 return (*this);
211}

References BigInt(), bits(), Botan::is_power_of_2(), sig_words(), 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 252 of file big_ops2.cpp.

252 {
253 const size_t sw = sig_words();
254 const size_t new_size = sw + (shift + WordInfo<word>::bits - 1) / WordInfo<word>::bits;
255
256 m_data.grow_to(new_size);
257
258 bigint_shl1(m_data.mutable_data(), new_size, sw, shift);
259
260 return (*this);
261}
constexpr void bigint_shl1(W x[], size_t x_size, size_t x_words, size_t shift)
Definition mp_core.h:309

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

◆ operator=() [1/2]

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

Move assignment

Definition at line 174 of file bigint.h.

174 {
175 if(this != &other) {
176 this->swap(other);
177 }
178
179 return (*this);
180 }

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 266 of file big_ops2.cpp.

266 {
267 bigint_shr1(m_data.mutable_data(), m_data.size(), shift);
268
269 if(is_negative() && is_zero()) {
271 }
272
273 return (*this);
274}
constexpr void bigint_shr1(W x[], size_t x_size, size_t shift)
Definition mp_core.h:328

References BigInt(), Botan::bigint_shr1(), is_negative(), is_zero(), Positive, and set_sign().

◆ 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 820 of file bigint.h.

820 {
821 BigInt b;
822 b.set_bit(n);
823 return b;
824 }

References BigInt(), and set_bit().

Referenced by Botan::EC_Group::EC_Group(), Botan::Barrett_Reduction::for_public_modulus(), 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
Parameters
rnga 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 43 of file big_rand.cpp.

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

References BigInt(), bits(), BOTAN_DEBUG_ASSERT, is_negative(), random_integer(), randomize(), 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
rngthe 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 18 of file big_rand.cpp.

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

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

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

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

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

◆ resize()

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

Definition at line 668 of file bigint.h.

668{ m_data.resize(s); }

References resize().

Referenced by ct_shift_left(), and 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 133 of file big_ops2.cpp.

133 {
134 BOTAN_UNUSED(ws);
135 BigInt y_bn;
136 y_bn.m_data.set_words(y, y_sw);
137 *this = y_bn - *this;
138 return (*this);
139}

References BigInt(), and BOTAN_UNUSED.

◆ reverse_sign()

Sign Botan::BigInt::reverse_sign ( ) const
inline
Returns
the opposite sign of the represented integer value

Definition at line 576 of file bigint.h.

576 {
577 if(sign() == Positive) {
578 return Negative;
579 }
580 return Positive;
581 }

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 724 of file bigint.h.

724 {
725 return serialize<T>(this->bytes());
726 }
T serialize() const
Definition bigint.h:724

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 711 of file bigint.h.

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

References serialize_to().

Referenced by Botan::base58_decode(), Botan::DER_Encoder::encode(), Botan::FPE_FE1::FPE_FE1(), 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
outdestination byte span for the integer value

Definition at line 399 of file bigint.cpp.

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

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 463 of file bigint.h.

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

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::random_prime().

◆ set_sign()

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

Set sign of the integer

Parameters
signnew Sign to set

Definition at line 592 of file bigint.h.

592 {
593 if(sign == Negative && is_zero()) {
594 sign = Positive;
595 }
596
597 m_signedness = sign;
598 }

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

Referenced by abs(), add(), add2(), BigInt(), cond_flip_sign(), flip_sign(), Botan::inverse_mod_general(), Botan::lcm(), mul(), operator%=(), Botan::operator*(), operator*=(), Botan::operator>>(), operator>>=(), randomize(), square(), to_dec_string(), and Botan::vartime_divide().

◆ set_word_at()

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

Definition at line 549 of file bigint.h.

549{ 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

Definition at line 551 of file bigint.h.

551 {
552 m_data.set_words(w, len);
553 }

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 571 of file bigint.h.

571{ return (m_signedness); }

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

◆ size()

◆ square()

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

Square value of *this

Parameters
wsa temp workspace

Definition at line 175 of file big_ops2.cpp.

175 {
176 const size_t sw = sig_words();
177
178 secure_vector<word> z(2 * sw);
179 ws.resize(z.size());
180
181 bigint_sqr(z.data(), z.size(), _data(), size(), sw, ws.data(), ws.size());
182
183 swap_reg(z);
185
186 return (*this);
187}
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::sqrt_modulo_prime(), Botan::square(), and Botan::DL_Group::square_mod_q().

◆ sub()

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

Definition at line 316 of file bigint.h.

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

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 191 of file bigint.h.

191 {
192 m_data.swap(other.m_data);
193 std::swap(m_signedness, other.m_signedness);
194 }

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

Definition at line 198 of file bigint.h.

198 {
199 m_data.swap(reg);
200 // sign left unchanged
201 }

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 37 of file big_code.cpp.

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

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

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 104 of file big_code.cpp.

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

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

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

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

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

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

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

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

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

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

50 {
51 BigInt bn;
52 bn.grow_to(size);
53 return bn;
54}

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
nposition in the register
Returns
value at position n

Definition at line 547 of file bigint.h.

547{ return m_data.get_word_at(n); }

References word_at().

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

◆ zero()

◆ swap

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

Definition at line 196 of file bigint.h.

196{ x.swap(y); }

References BigInt().


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