Botan 3.3.0
Crypto and TLS for C&
Public Types | Public Member Functions | Static Public Member Functions | Friends | List of all members
Botan::BigInt Class Referencefinal

#include <bigint.h>

Public Types

enum  Base { Decimal = 10 , Hexadecimal = 16 , Binary = 256 }
 
enum  Sign { Negative = 0 , Positive = 1 }
 

Public Member Functions

BigInt abs () const
 
BigIntadd (const word y[], size_t y_words, Sign sign)
 
 BigInt ()=default
 
 BigInt (BigInt &&other)
 
 BigInt (const BigInt &other)=default
 
template<typename Alloc >
 BigInt (const std::vector< uint8_t, Alloc > &vec)
 
 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::string_view str)
 
 BigInt (uint64_t n)
 
template<typename Alloc >
void binary_decode (const std::vector< uint8_t, Alloc > &buf)
 
void binary_decode (const uint8_t buf[], size_t length)
 
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)
 
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)
 
word * mutable_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)
 
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
 
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)
 
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 add2 (const BigInt &x, const word y[], size_t y_words, Sign y_sign)
 
template<typename Alloc >
static BigInt decode (const std::vector< uint8_t, Alloc > &buf)
 
template<typename Alloc >
static BigInt decode (const std::vector< uint8_t, Alloc > &buf, Base base)
 
static BigInt decode (const uint8_t buf[], size_t length)
 
static BigInt decode (const uint8_t buf[], size_t length, 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_with_max_bits (const uint8_t buf[], size_t length, size_t max_bits)
 
static BigInt from_s32 (int32_t n)
 
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)
 

Detailed Description

Arbitrary precision integer

Definition at line 25 of file bigint.h.

Member Enumeration Documentation

◆ Base

Base enumerator for encoding and decoding

Enumerator
Decimal 
Hexadecimal 
Binary 

Definition at line 30 of file bigint.h.

30{ Decimal = 10, Hexadecimal = 16, Binary = 256 };

◆ Sign

Sign symbol definitions for positive and negative numbers

Enumerator
Negative 
Positive 

Definition at line 35 of file bigint.h.

35{ Negative = 0, Positive = 1 };

Constructor & Destructor Documentation

◆ BigInt() [1/9]

Botan::BigInt::BigInt ( )
default

Create empty (zero) BigInt

◆ BigInt() [2/9]

Botan::BigInt::BigInt ( uint64_t n)

Create BigInt from an unsigned 64 bit integer

Parameters
ninitial value of this BigInt

Definition at line 18 of file bigint.cpp.

18 {
19#if BOTAN_MP_WORD_BITS == 64
20 m_data.set_word_at(0, n);
21#else
22 m_data.set_word_at(1, static_cast<word>(n >> 32));
23 m_data.set_word_at(0, static_cast<word>(n));
24#endif
25}

◆ BigInt() [3/9]

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

Copy Constructor

Parameters
otherthe BigInt to copy

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

67 {
68 Base base = Decimal;
69 size_t markers = 0;
70 bool negative = false;
71
72 if(str.length() > 0 && str[0] == '-') {
73 markers += 1;
74 negative = true;
75 }
76
77 if(str.length() > markers + 2 && str[markers] == '0' && str[markers + 1] == 'x') {
78 markers += 2;
79 base = Hexadecimal;
80 }
81
82 *this = decode(cast_char_ptr_to_uint8(str.data()) + markers, str.length() - markers, base);
83
84 if(negative) {
86 } else {
88 }
89}
static BigInt decode(const uint8_t buf[], size_t length)
Definition bigint.h:772
void set_sign(Sign sign)
Definition bigint.h:561
const uint8_t * cast_char_ptr_to_uint8(const char *s)
Definition mem_ops.h:272

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

◆ BigInt() [5/9]

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

Create a BigInt from an integer in a byte array

Parameters
bufthe byte array holding the value
lengthsize of buf

Definition at line 91 of file bigint.cpp.

91 {
92 binary_decode(input, length);
93}
void binary_decode(const uint8_t buf[], size_t length)
Definition bigint.cpp:403

References binary_decode().

◆ BigInt() [6/9]

template<typename Alloc >
Botan::BigInt::BigInt ( const std::vector< uint8_t, Alloc > & vec)
inlineexplicit

Create a BigInt from an integer in a byte array

Parameters
vecthe byte vector holding the value

Definition at line 103 of file bigint.h.

103: BigInt(vec.data(), vec.size()) {}
BigInt()=default

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

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

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

121 {
122 randomize(rng, bits, set_high_bit);
123}
void randomize(RandomNumberGenerator &rng, size_t bitsize, bool set_high_bit=true)
Definition big_rand.cpp:18
size_t bits() const
Definition bigint.cpp:290

References bits(), and randomize().

◆ BigInt() [9/9]

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

Move constructor

Definition at line 146 of file bigint.h.

146{ this->swap(other); }
friend void swap(BigInt &x, BigInt &y)
Definition bigint.h:175

◆ ~BigInt()

Botan::BigInt::~BigInt ( )
inline

Definition at line 148 of file bigint.h.

void const_time_unpoison() const
Definition bigint.h:722

Member Function Documentation

◆ abs()

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

Definition at line 369 of file bigint.cpp.

369 {
370 BigInt x = (*this);
371 x.set_sign(Positive);
372 return x;
373}

References 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 bigint_add2(mutable_data(), size() - 1, y, y_words);
23 } else {
24 const int32_t relative_size = bigint_cmp(data(), x_sw, y, y_words);
25
26 if(relative_size >= 0) {
27 // *this >= y
28 bigint_sub2(mutable_data(), x_sw, y, y_words);
29 } else {
30 // *this < y
31 bigint_sub2_rev(mutable_data(), y, y_words);
32 }
33
34 //this->sign_fixup(relative_size, y_sign);
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:584
word * mutable_data()
Definition bigint.h:609
size_t size() const
Definition bigint.h:578
void grow_to(size_t n) const
Definition bigint.h:631
const word * data() const
Definition bigint.h:615
Sign sign() const
Definition bigint.h:540
void bigint_sub2_rev(word x[], const word y[], size_t y_size)
Definition mp_core.h:298
word bigint_sub2(word x[], size_t x_size, const word y[], size_t y_size)
Definition mp_core.h:273
void bigint_add2(word x[], size_t x_size, const word y[], size_t y_size)
Definition mp_core.h:259
int32_t bigint_cmp(const word x[], size_t x_size, const word y[], size_t y_size)
Definition mp_core.h:490

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

Referenced by Botan::Modular_Reducer::reduce().

◆ 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_words) + 1);
23
24 if(x.sign() == y_sign) {
25 bigint_add3(z.mutable_data(), x.data(), x_sw, y, y_words);
26 z.set_sign(x.sign());
27 } else {
28 const int32_t relative_size = bigint_sub_abs(z.mutable_data(), x.data(), x_sw, y, y_words);
29
30 //z.sign_fixup(relative_size, y_sign);
31 if(relative_size < 0) {
32 z.set_sign(y_sign);
33 } else if(relative_size == 0) {
34 z.set_sign(BigInt::Positive);
35 } else {
36 z.set_sign(x.sign());
37 }
38 }
39
40 return z;
41}
static BigInt with_capacity(size_t n)
Definition bigint.cpp:58
void bigint_add3(word z[], const word x[], size_t x_size, const word y[], size_t y_size)
Definition mp_core.h:266
CT::Mask< word > bigint_sub_abs(word z[], const word x[], const word y[], size_t N, word ws[])
Definition mp_core.h:355

References Botan::bigint_add3(), Botan::bigint_sub_abs(), data(), mutable_data(), Positive, set_sign(), sig_words(), sign(), and with_capacity().

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

◆ binary_decode() [1/2]

template<typename Alloc >
void Botan::BigInt::binary_decode ( const std::vector< uint8_t, Alloc > & buf)
inline

Read integer value from a byte vector

Parameters
bufthe vector to load from

Definition at line 678 of file bigint.h.

678 {
679 binary_decode(buf.data(), buf.size());
680 }

◆ binary_decode() [2/2]

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

Read integer value from a byte array with given size

Parameters
bufbyte array buffer containing the integer
lengthsize of buf

Definition at line 403 of file bigint.cpp.

403 {
404 clear();
405
406 const size_t full_words = length / sizeof(word);
407 const size_t extra_bytes = length % sizeof(word);
408
409 secure_vector<word> reg((round_up(full_words + (extra_bytes > 0 ? 1 : 0), 8)));
410
411 for(size_t i = 0; i != full_words; ++i) {
412 reg[i] = load_be<word>(buf + length - sizeof(word) * (i + 1), 0);
413 }
414
415 if(extra_bytes > 0) {
416 for(size_t i = 0; i != extra_bytes; ++i) {
417 reg[full_words] = (reg[full_words] << 8) | buf[i];
418 }
419 }
420
421 m_data.swap(reg);
422}
void clear()
Definition bigint.h:370
size_t round_up(size_t n, size_t align_to)
Definition rounding.h:21

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

Referenced by BigInt(), decode(), from_bytes_with_max_bits(), Botan::generate_dsa_primes(), Botan::RFC6979_Nonce_Generator::nonce_for(), and randomize().

◆ binary_encode() [1/2]

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

Store BigInt-value in a given byte array

Parameters
bufdestination byte array for the integer value

Definition at line 375 of file bigint.cpp.

375 {
376 this->binary_encode(buf, bytes());
377}
void binary_encode(uint8_t buf[]) const
Definition bigint.cpp:375
size_t bytes() const
Definition bigint.cpp:277

References binary_encode(), and bytes().

Referenced by Botan::base58_decode(), binary_encode(), encode(), Botan::DER_Encoder::encode(), encode_1363(), encode_1363(), encode_1363(), encode_fixed_length_int_pair(), encode_locked(), Botan::GOST_3410_PublicKey::public_key_bits(), and to_hex_string().

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

Parameters
bufdestination byte array for the integer value
lenhow many bytes to write

Definition at line 382 of file bigint.cpp.

382 {
383 const size_t full_words = len / sizeof(word);
384 const size_t extra_bytes = len % sizeof(word);
385
386 for(size_t i = 0; i != full_words; ++i) {
387 const word w = word_at(i);
388 store_be(w, output + (len - (i + 1) * sizeof(word)));
389 }
390
391 if(extra_bytes > 0) {
392 const word w = word_at(full_words);
393
394 for(size_t i = 0; i != extra_bytes; ++i) {
395 output[extra_bytes - i - 1] = get_byte_var(sizeof(word) - i - 1, w);
396 }
397 }
398}
word word_at(size_t n) const
Definition bigint.h:518
constexpr void store_be(T in, OutR &&out_range)
Definition loadstor.h:358
constexpr uint8_t get_byte_var(size_t byte_num, T input)
Definition loadstor.h:27

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

290 {
291 const size_t words = sig_words();
292
293 if(words == 0) {
294 return 0;
295 }
296
297 const size_t full_words = (words - 1) * BOTAN_MP_WORD_BITS;
298 const size_t top_bits = BOTAN_MP_WORD_BITS - top_bits_free();
299
300 return full_words + top_bits;
301}
size_t top_bits_free() const
Definition bigint.cpp:281
#define BOTAN_MP_WORD_BITS
Definition build.h:50

References BOTAN_MP_WORD_BITS, sig_words(), and top_bits_free().

Referenced by BigInt(), bytes(), Botan::ct_divide(), Botan::ct_divide_word(), Botan::ct_modulo(), Botan::BER_Decoder::decode(), Botan::BER_Decoder::decode_constrained_integer(), Botan::DL_Group::DL_Group(), Botan::EC_Point_Base_Point_Precompute::EC_Point_Base_Point_Precompute(), Botan::EC_Point_Var_Point_Precompute::EC_Point_Var_Point_Precompute(), Botan::DER_Encoder::encode(), Botan::generate_dsa_primes(), Botan::generate_rsa_prime(), Botan::inverse_mod(), Botan::is_perfect_square(), Botan::is_prime(), Botan::TPM_PrivateKey::key_length(), Botan::monty_multi_exp(), Botan::EC_Point_Base_Point_Precompute::mul(), Botan::EC_Point_Var_Point_Precompute::mul(), Botan::EC_Point_Multi_Point_Precompute::multi_exp(), Botan::operator*(), operator/=(), Botan::passes_miller_rabin_test(), Botan::DL_Group::power_g_p(), Botan::power_mod(), random_integer(), Botan::random_prime(), Botan::RSA_PrivateKey::RSA_PrivateKey(), Botan::srp6_client_agree(), Botan::srp6_group_identifier(), to_dec_string(), to_hex_string(), and to_u32bit().

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

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

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

◆ clear()

void Botan::BigInt::clear ( )
inline

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

Definition at line 370 of file bigint.h.

370 {
371 m_data.set_to_zero();
372 m_signedness = Positive;
373 }

Referenced by Botan::EC_Point::add(), Botan::EC_Point::add_affine(), binary_decode(), 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 268 of file bigint.cpp.

268 {
269 const size_t which = n / BOTAN_MP_WORD_BITS;
270
271 if(which < size()) {
272 const word mask = ~(static_cast<word>(1) << (n % BOTAN_MP_WORD_BITS));
273 m_data.set_word_at(which, word_at(which) & mask);
274 }
275}

References BOTAN_MP_WORD_BITS, 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 145 of file bigint.cpp.

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

References Botan::bigint_cmp(), data(), 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 129 of file bigint.cpp.

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

References Botan::bigint_cmp(), data(), 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 475 of file bigint.cpp.

475 {
476 // This code is assuming Negative == 0, Positive == 1
477
478 const auto mask = CT::Mask<uint8_t>::expand(predicate);
479
480 const uint8_t current_sign = static_cast<uint8_t>(sign());
481
482 const uint8_t new_sign = mask.select(current_sign ^ 1, current_sign);
483
484 set_sign(static_cast<Sign>(new_sign));
485}
static Mask< T > expand(T v)
Definition ct_utils.h:109

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

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

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

444 {
445 const size_t which = n / BOTAN_MP_WORD_BITS;
446 const word mask = static_cast<word>(set_it) << (n % BOTAN_MP_WORD_BITS);
447 m_data.set_word_at(which, word_at(which) | mask);
448 }

References BOTAN_MP_WORD_BITS.

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

◆ const_time_poison()

void Botan::BigInt::const_time_poison ( ) const
inline

Definition at line 720 of file bigint.h.

720{}

Referenced by Botan::gcd().

◆ const_time_unpoison()

void Botan::BigInt::const_time_unpoison ( ) const
inline

Definition at line 722 of file bigint.h.

722{}

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

424 {
425 if(this->is_negative() || value.is_negative()) {
426 throw Invalid_Argument("BigInt::ct_cond_add requires both values to be positive");
427 }
428 this->grow_to(1 + value.sig_words());
429
430 bigint_cnd_add(static_cast<word>(predicate), this->mutable_data(), this->size(), value.data(), value.sig_words());
431}
word bigint_cnd_add(word cnd, word x[], word x_size, const word y[], size_t y_size)
Definition mp_core.h:40

References Botan::bigint_cnd_add(), data(), grow_to(), is_negative(), mutable_data(), sig_words(), and size().

Referenced by Botan::inverse_mod(), 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 487 of file bigint.cpp.

487 {
488 const size_t t_words = size();
489 const size_t o_words = other.size();
490
491 if(o_words < t_words) {
492 grow_to(o_words);
493 }
494
495 const size_t r_words = std::max(t_words, o_words);
496
497 const auto mask = CT::Mask<word>::expand(predicate);
498
499 for(size_t i = 0; i != r_words; ++i) {
500 const word o_word = other.word_at(i);
501 const word t_word = this->word_at(i);
502 this->set_word_at(i, mask.select(o_word, t_word));
503 }
504
505 const bool different_sign = sign() != other.sign();
506 cond_flip_sign(predicate && different_sign);
507}
void set_word_at(size_t i, word w)
Definition bigint.h:520
void cond_flip_sign(bool predicate)
Definition bigint.cpp:475

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

Referenced by ct_shift_left(), Botan::inverse_mod(), 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 467 of file bigint.cpp.

467 {
468 const size_t max_words = std::max(size(), other.size());
469 grow_to(max_words);
470 other.grow_to(max_words);
471
472 bigint_cnd_swap(predicate, this->mutable_data(), other.mutable_data(), max_words);
473}
void bigint_cnd_swap(word cnd, word x[], word y[], size_t size)
Definition mp_core.h:29

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

344 {
345 if(mod.is_negative() || this->is_negative()) {
346 throw Invalid_Argument("BigInt::ct_reduce_below both values must be positive");
347 }
348
349 const size_t mod_words = mod.sig_words();
350
351 grow_to(mod_words);
352
353 const size_t sz = size();
354
355 ws.resize(sz);
356
357 clear_mem(ws.data(), sz);
358
359 for(size_t i = 0; i != bound; ++i) {
360 word borrow = bigint_sub3(ws.data(), data(), sz, mod.data(), mod_words);
361
362 CT::Mask<word>::is_zero(borrow).select_n(mutable_data(), ws.data(), data(), sz);
363 }
364}
static Mask< T > is_zero(T x)
Definition ct_utils.h:123
word bigint_sub3(word z[], const word x[], size_t x_size, const word y[], size_t y_size)
Definition mp_core.h:321
constexpr void clear_mem(T *ptr, size_t n)
Definition mem_ops.h:120

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

Referenced by Botan::Modular_Reducer::reduce().

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

433 {
434 auto shl_bit = [](const BigInt& a, BigInt& result) {
435 BOTAN_DEBUG_ASSERT(a.size() + 1 == result.size());
436 bigint_shl2(result.mutable_data(), a.data(), a.size(), 0, 1);
437 // shl2 may have shifted a bit into the next word, which must be dropped
438 clear_mem(result.mutable_data() + result.size() - 1, 1);
439 };
440
441 auto shl_word = [](const BigInt& a, BigInt& result) {
442 // the most significant word is not copied, aka. shifted out
443 bigint_shl2(result.mutable_data(), a.data(), a.size() - 1 /* ignore msw */, 1, 0);
444 // we left-shifted by a full word, the least significant word must be zero'ed
445 clear_mem(result.mutable_data(), 1);
446 };
447
449
450 constexpr size_t bits_in_word = sizeof(word) * 8;
451 const size_t word_shift = shift >> ceil_log2(bits_in_word); // shift / bits_in_word
452 const size_t bit_shift = shift & ((1 << ceil_log2(bits_in_word)) - 1); // shift % bits_in_word
453 const size_t iterations = std::max(size(), bits_in_word) - 1; // uint64_t i; i << 64 is undefined behaviour
454
455 // In every iteration, shift one bit and one word to the left and use the
456 // shift results only when they are within the shift range.
457 BigInt tmp;
458 tmp.resize(size() + 1 /* to hold the shifted-out word */);
459 for(size_t i = 0; i < iterations; ++i) {
460 shl_bit(*this, tmp);
461 ct_cond_assign(i < bit_shift, tmp);
462 shl_word(*this, tmp);
463 ct_cond_assign(i < word_shift, tmp);
464 }
465}
#define BOTAN_ASSERT_NOMSG(expr)
Definition assert.h:59
#define BOTAN_DEBUG_ASSERT(expr)
Definition assert.h:98
void ct_cond_assign(bool predicate, const BigInt &other)
Definition bigint.cpp:487
void bigint_shl2(word y[], const word x[], size_t x_size, size_t word_shift, size_t bit_shift)
Definition mp_core.h:417
constexpr uint8_t ceil_log2(T x)
Definition bit_ops.h:122

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

◆ data()

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

◆ decode() [1/4]

template<typename Alloc >
static BigInt Botan::BigInt::decode ( const std::vector< uint8_t, Alloc > & 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 780 of file bigint.h.

780 {
781 return BigInt(buf);
782 }

◆ decode() [2/4]

template<typename Alloc >
static BigInt Botan::BigInt::decode ( const std::vector< uint8_t, Alloc > & buf,
Base base )
inlinestatic

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

800 {
801 if(base == Binary) {
802 return BigInt(buf);
803 }
804 return BigInt::decode(buf.data(), buf.size(), base);
805 }

◆ decode() [3/4]

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

◆ decode() [4/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 151 of file big_code.cpp.

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

References Binary, binary_decode(), BOTAN_ASSERT_NOMSG, Botan::cast_uint8_ptr_to_char(), Decimal, Botan::hex_decode_locked(), and Hexadecimal.

◆ encode()

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

749 {
750 std::vector<uint8_t> output(n.bytes());
751 n.binary_encode(output.data());
752 return output;
753 }

References binary_encode(), and bytes().

Referenced by botan_srp6_client_agree(), botan_srp6_generate_verifier(), botan_srp6_server_session_step1(), Botan::CRL_Entry::decode_from(), Botan::FPE_FE1::FPE_FE1(), and Botan::TLS::Server_Key_Exchange::Server_Key_Exchange().

◆ encode_1363() [1/3]

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

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

105 {
106 if(n.bytes() > bytes) {
107 throw Encoding_Error("encode_1363: n is too large to encode properly");
108 }
109
110 secure_vector<uint8_t> output(bytes);
111 n.binary_encode(output.data(), output.size());
112 return output;
113}

References binary_encode(), and bytes().

Referenced by Botan::EC_Group::DER_encode(), Botan::EC_Point::encode(), Botan::RFC6979_Nonce_Generator::nonce_for(), Botan::EC_PrivateKey::private_key_bits(), Botan::DL_PublicKey::public_key_as_bytes(), Botan::RFC6979_Nonce_Generator::RFC6979_Nonce_Generator(), Botan::Montgomery_Int::serialize(), Botan::sm2_compute_za(), Botan::srp6_client_agree(), and Botan::SRP6_Server_Session::step2().

◆ encode_1363() [2/3]

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

Definition at line 115 of file big_code.cpp.

115 {
116 if(n.bytes() > output.size()) {
117 throw Encoding_Error("encode_1363: n is too large to encode properly");
118 }
119
120 n.binary_encode(output.data(), output.size());
121}

References binary_encode(), and bytes().

◆ encode_1363() [3/3]

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

Definition at line 124 of file big_code.cpp.

124 {
125 if(n.bytes() > bytes) {
126 throw Encoding_Error("encode_1363: n is too large to encode properly");
127 }
128
129 n.binary_encode(output, bytes);
130}

References binary_encode(), and bytes().

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

135 {
136 if(n1.is_negative() || n2.is_negative()) {
137 throw Encoding_Error("encode_fixed_length_int_pair: values must be positive");
138 }
139 if(n1.bytes() > bytes || n2.bytes() > bytes) {
140 throw Encoding_Error("encode_fixed_length_int_pair: values too large to encode properly");
141 }
142 secure_vector<uint8_t> output(2 * bytes);
143 n1.binary_encode(output.data(), bytes);
144 n2.binary_encode(output.data() + bytes, bytes);
145 return output;
146}

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

◆ encode_locked()

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

760 {
761 secure_vector<uint8_t> output(n.bytes());
762 n.binary_encode(output.data());
763 return output;
764 }

References binary_encode(), and bytes().

Referenced by Botan::DL_PrivateKey::raw_private_key_bits(), and Botan::EC_PrivateKey::raw_private_key_bits().

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

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

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

◆ flip_sign()

void Botan::BigInt::flip_sign ( )
inline

Flip the sign of this BigInt

Definition at line 555 of file bigint.h.

Sign reverse_sign() const
Definition bigint.h:545

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

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

103 {
104 const size_t input_bits = 8 * length;
105
106 BigInt bn;
107 bn.binary_decode(input, length);
108
109 if(input_bits > max_bits) {
110 const size_t bits_to_shift = input_bits - max_bits;
111
112 bn >>= bits_to_shift;
113 }
114
115 return bn;
116}

References binary_decode().

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

49 {
50 if(n >= 0) {
51 return BigInt::from_u64(static_cast<uint64_t>(n));
52 } else {
53 return -BigInt::from_u64(static_cast<uint64_t>(-n));
54 }
55}
static BigInt from_u64(uint64_t n)
Definition bigint.cpp:28

References from_u64().

Referenced by botan_mp_set_from_int(), and Botan::sqrt_modulo_prime().

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

28 {
29 BigInt bn;
30
31#if BOTAN_MP_WORD_BITS == 64
32 bn.set_word_at(0, n);
33#else
34 bn.set_word_at(1, static_cast<word>(n >> 32));
35 bn.set_word_at(0, static_cast<word>(n));
36#endif
37
38 return bn;
39}

References set_word_at().

Referenced by Botan::DER_Encoder::encode(), Botan::DER_Encoder::encode(), from_s32(), 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 42 of file bigint.cpp.

42 {
43 BigInt bn;
44 bn.set_word_at(0, n);
45 return bn;
46}

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

467{ return ((word_at(n / BOTAN_MP_WORD_BITS) >> (n % BOTAN_MP_WORD_BITS)) & 1); }

References BOTAN_MP_WORD_BITS.

Referenced by Botan::ct_divide(), Botan::ct_divide_word(), Botan::ct_modulo(), Botan::EC_Point::encode(), Botan::inverse_mod(), Botan::operator*(), 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 222 of file bigint.cpp.

222 {
223 if(length == 0 || length > 32) {
224 throw Invalid_Argument("BigInt::get_substring invalid substring length");
225 }
226
227 const uint32_t mask = 0xFFFFFFFF >> (32 - length);
228
229 const size_t word_offset = offset / BOTAN_MP_WORD_BITS;
230 const size_t wshift = (offset % BOTAN_MP_WORD_BITS);
231
232 /*
233 * The substring is contained within one or at most two words. The
234 * offset and length are not secret, so we can perform conditional
235 * operations on those values.
236 */
237 const word w0 = word_at(word_offset);
238
239 if(wshift == 0 || (offset + length) / BOTAN_MP_WORD_BITS == word_offset) {
240 return static_cast<uint32_t>(w0 >> wshift) & mask;
241 } else {
242 const word w1 = word_at(word_offset + 1);
243 return static_cast<uint32_t>((w0 >> wshift) | (w1 << (BOTAN_MP_WORD_BITS - wshift))) & mask;
244 }
245}

References BOTAN_MP_WORD_BITS, and 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 620 of file bigint.h.

620{ return m_data.mutable_vector(); }

Referenced by Botan::EC_Point_Var_Point_Precompute::EC_Point_Var_Point_Precompute().

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

625{ return m_data.const_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 163 of file bigint.cpp.

163 {
164 if(this->sign() != other.sign()) {
165 return false;
166 }
167
168 return bigint_ct_is_eq(this->data(), this->sig_words(), other.data(), other.sig_words()).as_bool();
169}
CT::Mask< word > bigint_ct_is_eq(const word x[], size_t x_size, const word y[], size_t y_size)
Definition mp_core.h:568

References Botan::bigint_ct_is_eq(), data(), sig_words(), and sign().

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

◆ is_even()

bool Botan::BigInt::is_even ( ) const
inline

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

171 {
172 if(this->is_negative() && other.is_positive()) {
173 return true;
174 }
175
176 if(this->is_positive() && other.is_negative()) {
177 return false;
178 }
179
180 if(other.is_negative() && this->is_negative()) {
181 return bigint_ct_is_lt(other.data(), other.sig_words(), this->data(), this->sig_words()).as_bool();
182 }
183
184 return bigint_ct_is_lt(this->data(), this->sig_words(), other.data(), other.sig_words()).as_bool();
185}
bool is_positive() const
Definition bigint.h:534
CT::Mask< word > bigint_ct_is_lt(const word x[], size_t x_size, const word y[], size_t y_size, bool lt_or_equal=false)
Definition mp_core.h:536

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

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

◆ is_negative()

bool Botan::BigInt::is_negative ( ) const
inline

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

422{ return (!is_zero()); }
bool is_zero() const
Definition bigint.h:428

Referenced by Botan::ct_modulo(), Botan::inverse_mod(), and Botan::Modular_Reducer::reduce().

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

416{ return (get_bit(0) == 1); }

Referenced by Botan::inverse_mod(), 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 534 of file bigint.h.

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

Referenced by cmp(), is_less_than(), Botan::operator%(), Botan::redc_p192(), Botan::redc_p224(), Botan::redc_p256(), Botan::redc_p384(), and Botan::redc_p521().

◆ is_zero()

bool Botan::BigInt::is_zero ( ) const
inline

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

460{ m_data.mask_bits(n); }

Referenced by Botan::inverse_mod(), Botan::redc_p192(), Botan::redc_p224(), Botan::redc_p256(), Botan::redc_p384(), Botan::redc_p521(), and Botan::Modular_Reducer::reduce().

◆ 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 word borrow = bigint_sub3(&ws[0], mod.data(), mod_sw, s.data(), mod_sw);
75 BOTAN_DEBUG_ASSERT(borrow == 0);
76 BOTAN_UNUSED(borrow);
77
78 // Compute t - ws
79 borrow = bigint_sub3(&ws[mod_sw], this->data(), mod_sw, &ws[0], mod_sw);
80
81 // Compute t + s
82 bigint_add3_nc(&ws[mod_sw * 2], this->data(), mod_sw, s.data(), mod_sw);
83
84 CT::conditional_copy_mem(borrow, &ws[0], &ws[mod_sw * 2], &ws[mod_sw], mod_sw);
85 set_words(&ws[0], mod_sw);
86
87 return (*this);
88}
#define BOTAN_UNUSED
Definition assert.h:118
#define BOTAN_ARG_CHECK(expr, msg)
Definition assert.h:29
void set_words(const word w[], size_t len)
Definition bigint.h:522
Mask< T > conditional_copy_mem(Mask< T > mask, T *to, const T *from0, const T *from1, size_t elems)
Definition ct_utils.h:286
word bigint_add3_nc(word z[], const word x[], size_t x_size, const word y[], size_t y_size)
Definition mp_core.h:228

References Botan::bigint_add3_nc(), Botan::bigint_sub3(), BOTAN_ARG_CHECK, BOTAN_DEBUG_ASSERT, BOTAN_UNUSED, Botan::CT::conditional_copy_mem(), data(), grow_to(), is_negative(), set_words(), and sig_words().

Referenced by Botan::Montgomery_Int::add(), Botan::EC_Point::mult2(), and Botan::Montgomery_Int::operator+().

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

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

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

Referenced by Botan::Montgomery_Int::mul_by_2(), Botan::Montgomery_Int::mul_by_3(), Botan::Montgomery_Int::mul_by_4(), Botan::Montgomery_Int::mul_by_8(), and Botan::EC_Point::mult2().

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

90 {
91 if(this->is_negative() || s.is_negative() || mod.is_negative()) {
92 throw Invalid_Argument("BigInt::mod_sub expects all arguments are positive");
93 }
94
95 // We are assuming in this function that *this and s are no more than mod_sw words long
96 BOTAN_DEBUG_ASSERT(*this < mod);
97 BOTAN_DEBUG_ASSERT(s < mod);
98
99 const size_t mod_sw = mod.sig_words();
100
101 this->grow_to(mod_sw);
102 s.grow_to(mod_sw);
103
104 if(ws.size() < mod_sw) {
105 ws.resize(mod_sw);
106 }
107
108 if(mod_sw == 4) {
109 bigint_mod_sub_n<4>(mutable_data(), s.data(), mod.data(), ws.data());
110 } else if(mod_sw == 6) {
111 bigint_mod_sub_n<6>(mutable_data(), s.data(), mod.data(), ws.data());
112 } else {
113 bigint_mod_sub(mutable_data(), s.data(), mod.data(), mod_sw, ws.data());
114 }
115
116 return (*this);
117}
void bigint_mod_sub(word t[], const word s[], const word mod[], size_t mod_sw, word ws[])
Definition mp_core.h:633

References Botan::bigint_mod_sub(), BOTAN_DEBUG_ASSERT, data(), grow_to(), is_negative(), mutable_data(), and sig_words().

Referenced by Botan::EC_Point::add(), Botan::EC_Point::add_affine(), Botan::EC_Point::mult2(), Botan::Montgomery_Int::operator-(), and Botan::Montgomery_Int::sub().

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

156 {
157 const size_t x_sw = sig_words();
158 const size_t y_sw = y.sig_words();
159 set_sign((sign() == y.sign()) ? Positive : Negative);
160
161 if(x_sw == 0 || y_sw == 0) {
162 clear();
164 } else if(x_sw == 1 && y_sw) {
165 grow_to(y_sw + 1);
166 bigint_linmul3(mutable_data(), y.data(), y_sw, word_at(0));
167 } else if(y_sw == 1 && x_sw) {
168 word carry = bigint_linmul2(mutable_data(), x_sw, y.word_at(0));
169 set_word_at(x_sw, carry);
170 } else {
171 const size_t new_size = x_sw + y_sw + 1;
172 ws.resize(new_size);
173 secure_vector<word> z_reg(new_size);
174
175 bigint_mul(z_reg.data(), z_reg.size(), data(), size(), x_sw, y.data(), y.size(), y_sw, ws.data(), ws.size());
176
177 this->swap_reg(z_reg);
178 }
179
180 return (*this);
181}
void swap_reg(secure_vector< word > &reg)
Definition bigint.h:177
void bigint_linmul3(word z[], const word x[], size_t x_size, word y)
Definition mp_core.h:468
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:282
void carry(int64_t &h0, int64_t &h1)
word bigint_linmul2(word x[], size_t x_size, word y)
Definition mp_core.h:452

References Botan::bigint_linmul2(), Botan::bigint_linmul3(), Botan::bigint_mul(), Botan::carry(), clear(), data(), grow_to(), mutable_data(), Negative, Positive, set_sign(), set_word_at(), sig_words(), sign(), size(), swap_reg(), and word_at().

Referenced by operator*=(), and Botan::Modular_Reducer::reduce().

◆ mutable_data()

word * Botan::BigInt::mutable_data ( )
inline

◆ one()

static BigInt Botan::BigInt::one ( )
inlinestatic

Create a 1-value BigInt

Definition at line 50 of file bigint.h.

50{ return BigInt::from_word(1); }
static BigInt from_word(word n)
Definition bigint.cpp:42

Referenced by Botan::is_lucas_probable_prime(), Botan::is_perfect_square(), Botan::power_mod(), and Botan::EC_Group::random_scalar().

◆ operator!()

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

! operator

Returns
true iff this is zero, otherwise false

Definition at line 286 of file bigint.h.

286{ return (!is_nonzero()); }
bool is_nonzero() const
Definition bigint.h:422

◆ operator%=() [1/2]

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

Modulo operator

Parameters
ythe modulus to reduce this by

Definition at line 224 of file big_ops2.cpp.

224 {
225 return (*this = (*this) % mod);
226}

◆ operator%=() [2/2]

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

Modulo operator

Parameters
ythe modulus (word) to reduce this by

Definition at line 231 of file big_ops2.cpp.

231 {
232 if(mod == 0) {
233 throw Invalid_Argument("BigInt::operator%= divide by zero");
234 }
235
236 word remainder = 0;
237
238 if(is_power_of_2(mod)) {
239 remainder = (word_at(0) & (mod - 1));
240 } else {
241 const size_t sw = sig_words();
242 for(size_t i = sw; i > 0; --i) {
243 remainder = bigint_modop_vartime(remainder, word_at(i - 1), mod);
244 }
245 }
246
247 if(remainder && sign() == BigInt::Negative) {
248 remainder = mod - remainder;
249 }
250
251 m_data.set_to_zero();
252 m_data.set_word_at(0, remainder);
254 return remainder;
255}
word bigint_modop_vartime(word n1, word n0, word d)
Definition mp_core.h:697
constexpr bool is_power_of_2(T arg)
Definition bit_ops.h:45

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

151 {
152 secure_vector<word> ws;
153 return this->mul(y, ws);
154}
BigInt & mul(const BigInt &y, secure_vector< word > &ws)
Definition big_ops2.cpp:156

References mul().

◆ operator*=() [2/2]

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

*= operator

Parameters
ythe word to multiply with this

Definition at line 197 of file big_ops2.cpp.

197 {
198 if(y == 0) {
199 clear();
201 }
202
203 const word carry = bigint_linmul2(mutable_data(), size(), y);
205
206 return (*this);
207}

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

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

◆ operator++() [2/2]

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

Postfix increment operator

Definition at line 261 of file bigint.h.

261 {
262 BigInt x = (*this);
263 ++(*this);
264 return x;
265 }

◆ operator+=() [1/2]

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

+= operator

Parameters
ythe BigInt to add to this

Definition at line 186 of file bigint.h.

186{ 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(), 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 192 of file bigint.h.

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

◆ operator-()

BigInt Botan::BigInt::operator- ( ) const

Unary negation operator

Returns
negative this

Definition at line 306 of file bigint.cpp.

306 {
307 BigInt x = (*this);
308 x.flip_sign();
309 return x;
310}

References flip_sign().

◆ operator--() [1/2]

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

Decrement operator

Definition at line 256 of file bigint.h.

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

◆ operator--() [2/2]

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

Postfix decrement operator

Definition at line 270 of file bigint.h.

270 {
271 BigInt x = (*this);
272 --(*this);
273 return x;
274 }

◆ operator-=() [1/2]

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

-= operator

Parameters
ythe BigInt to subtract from this

Definition at line 198 of file bigint.h.

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

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

◆ operator-=() [2/2]

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

-= operator

Parameters
ythe word to subtract from this

Definition at line 204 of file bigint.h.

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

◆ operator/=()

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

/= operator

Parameters
ythe BigInt to divide this by

Definition at line 212 of file big_ops2.cpp.

212 {
213 if(y.sig_words() == 1 && is_power_of_2(y.word_at(0))) {
214 (*this) >>= (y.bits() - 1);
215 } else {
216 (*this) = (*this) / y;
217 }
218 return (*this);
219}

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

260 {
261 const size_t shift_words = shift / BOTAN_MP_WORD_BITS;
262 const size_t shift_bits = shift % BOTAN_MP_WORD_BITS;
263 const size_t size = sig_words();
264
265 const size_t bits_free = top_bits_free();
266
267 const size_t new_size = size + shift_words + (bits_free < shift_bits);
268
269 m_data.grow_to(new_size);
270
271 bigint_shl1(m_data.mutable_data(), new_size, size, shift_words, shift_bits);
272
273 return (*this);
274}
void bigint_shl1(word x[], size_t x_size, size_t x_words, size_t word_shift, size_t bit_shift)
Definition mp_core.h:382

References Botan::bigint_shl1(), BOTAN_MP_WORD_BITS, sig_words(), size(), and top_bits_free().

◆ operator=() [1/2]

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

Move assignment

Definition at line 153 of file bigint.h.

153 {
154 if(this != &other) {
155 this->swap(other);
156 }
157
158 return (*this);
159 }

◆ operator=() [2/2]

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

Copy assignment

◆ operator>>=()

BigInt & Botan::BigInt::operator>>= ( size_t shift)

Right shift operator

Parameters
shiftthe number of bits to shift this right by

Definition at line 279 of file big_ops2.cpp.

279 {
280 const size_t shift_words = shift / BOTAN_MP_WORD_BITS;
281 const size_t shift_bits = shift % BOTAN_MP_WORD_BITS;
282
283 bigint_shr1(m_data.mutable_data(), m_data.size(), shift_words, shift_bits);
284
285 if(is_negative() && is_zero()) {
287 }
288
289 return (*this);
290}
void bigint_shr1(word x[], size_t x_size, size_t word_shift, size_t bit_shift)
Definition mp_core.h:397

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

◆ power_of_2()

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

738 {
739 BigInt b;
740 b.set_bit(n);
741 return b;
742 }

References set_bit().

Referenced by Botan::inverse_mod(), Botan::is_perfect_square(), Botan::Montgomery_Params::Montgomery_Params(), Botan::Montgomery_Params::Montgomery_Params(), 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 BigInt r;
67
68 do {
69 r.randomize(rng, bits, false);
70 } while(r < min || r >= max);
71
72 return r;
73}
static BigInt zero()
Definition bigint.h:45
static BigInt random_integer(RandomNumberGenerator &rng, const BigInt &min, const BigInt &max)
Definition big_rand.cpp:43

References 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_Group::random_scalar(), and Botan::EC_Point::randomize_repr().

◆ 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) {
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) ? (8 - bitsize % 8) : 0);
34 }
35
36 binary_decode(array);
37 }
38}

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

Referenced by BigInt(), Botan::DL_Group::DL_Group(), Botan::EC_Point_Var_Point_Precompute::EC_Point_Var_Point_Precompute(), 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 312 of file bigint.cpp.

312 {
313 if(p.is_negative() || this->is_negative()) {
314 throw Invalid_Argument("BigInt::reduce_below both values must be positive");
315 }
316
317 const size_t p_words = p.sig_words();
318
319 if(size() < p_words + 1) {
320 grow_to(p_words + 1);
321 }
322
323 if(ws.size() < p_words + 1) {
324 ws.resize(p_words + 1);
325 }
326
327 clear_mem(ws.data(), ws.size());
328
329 size_t reductions = 0;
330
331 for(;;) {
332 word borrow = bigint_sub3(ws.data(), data(), p_words + 1, p.data(), p_words);
333 if(borrow) {
334 break;
335 }
336
337 ++reductions;
338 swap_reg(ws);
339 }
340
341 return reductions;
342}

References Botan::bigint_sub3(), Botan::clear_mem(), data(), 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 633 of file bigint.h.

633{ m_data.resize(s); }

Referenced by ct_shift_left(), and Botan::EC_Point::force_all_affine().

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

130 {
131 if(this->sign() != BigInt::Positive) {
132 throw Invalid_State("BigInt::sub_rev requires this is positive");
133 }
134
135 const size_t x_sw = this->sig_words();
136
137 ws.resize(std::max(x_sw, y_sw));
138 clear_mem(ws.data(), ws.size());
139
140 const int32_t relative_size = bigint_sub_abs(ws.data(), data(), x_sw, y, y_sw);
141
142 this->cond_flip_sign(relative_size > 0);
143 this->swap_reg(ws);
144
145 return (*this);
146}

References Botan::bigint_sub_abs(), Botan::clear_mem(), cond_flip_sign(), data(), Positive, sig_words(), sign(), and swap_reg().

Referenced by Botan::Modular_Reducer::reduce().

◆ reverse_sign()

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

Definition at line 545 of file bigint.h.

545 {
546 if(sign() == Positive) {
547 return Negative;
548 }
549 return Positive;
550 }

Referenced by Botan::operator-().

◆ set_bit()

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

Set bit at specified position

Parameters
nbit position to set

Definition at line 434 of file bigint.h.

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

Referenced by Botan::EC_Point_Var_Point_Precompute::EC_Point_Var_Point_Precompute(), Botan::generate_dsa_primes(), Botan::generate_rsa_prime(), Botan::Modular_Reducer::Modular_Reducer(), 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 561 of file bigint.h.

561 {
562 if(sign == Negative && is_zero()) {
563 sign = Positive;
564 }
565
566 m_signedness = sign;
567 }

Referenced by abs(), add(), add2(), BigInt(), cond_flip_sign(), Botan::inverse_mod(), Botan::lcm(), mul(), operator%=(), Botan::operator*(), operator*=(), Botan::operator<<(), Botan::operator>>(), operator>>=(), randomize(), Botan::Modular_Reducer::reduce(), 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 520 of file bigint.h.

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

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

◆ set_words()

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

Definition at line 522 of file bigint.h.

522{ m_data.set_words(w, len); }

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

◆ sig_words()

size_t Botan::BigInt::sig_words ( ) const
inline

◆ sign()

Sign Botan::BigInt::sign ( ) const
inline

Return the sign of the integer

Returns
the sign of the integer

Definition at line 540 of file bigint.h.

540{ 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>>(), and rev_sub().

◆ size()

size_t Botan::BigInt::size ( ) const
inline

◆ square()

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

Square value of *this

Parameters
wsa temp workspace

Definition at line 183 of file big_ops2.cpp.

183 {
184 const size_t sw = sig_words();
185
186 secure_vector<word> z(2 * sw);
187 ws.resize(z.size());
188
189 bigint_sqr(z.data(), z.size(), data(), size(), sw, ws.data(), ws.size());
190
191 swap_reg(z);
193
194 return (*this);
195}
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:326

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

Referenced by Botan::square().

◆ sub()

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

Definition at line 292 of file bigint.h.

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

◆ swap()

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

Swap this value with another

Parameters
otherBigInt to swap values with

Definition at line 170 of file bigint.h.

170 {
171 m_data.swap(other.m_data);
172 std::swap(m_signedness, other.m_signedness);
173 }

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

◆ swap_reg()

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

Definition at line 177 of file bigint.h.

177 {
178 m_data.swap(reg);
179 // sign left unchanged
180 }

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

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

15 {
16 // Use the largest power of 10 that fits in a word
17#if(BOTAN_MP_WORD_BITS == 64)
18 const word conversion_radix = 10000000000000000000U;
19 const word radix_digits = 19;
20#else
21 const word conversion_radix = 1000000000U;
22 const word radix_digits = 9;
23#endif
24
25 // (over-)estimate of the number of digits needed; log2(10) ~ 3.3219
26 const size_t digit_estimate = static_cast<size_t>(1 + (this->bits() / 3.32));
27
28 // (over-)estimate of db such that conversion_radix^db > *this
29 const size_t digit_blocks = (digit_estimate + radix_digits - 1) / radix_digits;
30
31 BigInt value = *this;
32 value.set_sign(Positive);
33
34 // Extract groups of digits into words
35 std::vector<word> digit_groups(digit_blocks);
36
37 for(size_t i = 0; i != digit_blocks; ++i) {
38 word remainder = 0;
39 ct_divide_word(value, conversion_radix, value, remainder);
40 digit_groups[i] = remainder;
41 }
42
43 BOTAN_ASSERT_NOMSG(value.is_zero());
44
45 // Extract digits from the groups
46 std::vector<uint8_t> digits(digit_blocks * radix_digits);
47
48 for(size_t i = 0; i != digit_blocks; ++i) {
49 word remainder = digit_groups[i];
50 for(size_t j = 0; j != radix_digits; ++j) {
51 // Compiler should convert div/mod by 10 into mul by magic constant
52 const word digit = remainder % 10;
53 remainder /= 10;
54 digits[radix_digits * i + j] = static_cast<uint8_t>(digit);
55 }
56 }
57
58 // remove leading zeros
59 while(!digits.empty() && digits.back() == 0) {
60 digits.pop_back();
61 }
62
63 BOTAN_ASSERT_NOMSG(digit_estimate >= digits.size());
64
65 // Reverse the digits to big-endian and format to text
66 std::string s;
67 s.reserve(1 + digits.size());
68
69 if(is_negative()) {
70 s += "-";
71 }
72
73 // Reverse and convert to textual digits
74 for(auto i = digits.rbegin(); i != digits.rend(); ++i) {
75 s.push_back(*i + '0'); // assumes ASCII
76 }
77
78 if(s.empty()) {
79 s += "0";
80 }
81
82 return s;
83}
void ct_divide_word(const BigInt &x, word y, BigInt &q_out, word &r_out)
Definition divide.cpp:80

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

85 {
86 const size_t this_bytes = this->bytes();
87 std::vector<uint8_t> bits(std::max<size_t>(1, this_bytes));
88
89 if(this_bytes > 0) {
90 this->binary_encode(bits.data());
91 }
92
93 std::string hrep;
94 if(is_negative()) {
95 hrep += "-";
96 }
97 hrep += "0x";
98 hrep += hex_encode(bits);
99 return hrep;
100}
void hex_encode(char output[], const uint8_t input[], size_t input_length, bool uppercase)
Definition hex.cpp:33

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

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

250 {
251 if(is_negative()) {
252 throw Encoding_Error("BigInt::to_u32bit: Number is negative");
253 }
254 if(bits() > 32) {
255 throw Encoding_Error("BigInt::to_u32bit: Number is too big to convert");
256 }
257
258 uint32_t out = 0;
259 for(size_t i = 0; i != 4; ++i) {
260 out = (out << 8) | byte_at(3 - i);
261 }
262 return out;
263}
uint8_t byte_at(size_t n) const
Definition bigint.cpp:125

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 BOTAN_MP_WORD_BITS only iff *this is zero. Ignores sign.

Definition at line 281 of file bigint.cpp.

281 {
282 const size_t words = sig_words();
283
284 const word top_word = word_at(words - 1);
285 const size_t bits_used = high_bit(top_word);
286 CT::unpoison(bits_used);
287 return BOTAN_MP_WORD_BITS - bits_used;
288}
void unpoison(const T *p, size_t n)
Definition ct_utils.h:55
constexpr size_t high_bit(T n)
Definition bit_ops.h:58

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

Referenced by bits(), operator<<=(), 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 58 of file bigint.cpp.

58 {
59 BigInt bn;
60 bn.grow_to(size);
61 return bn;
62}

References grow_to(), and size().

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

◆ word_at()

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

◆ zero()

static BigInt Botan::BigInt::zero ( )
inlinestatic

Friends And Related Symbol Documentation

◆ swap

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

Definition at line 175 of file bigint.h.

175{ x.swap(y); }

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