Botan 3.0.0-rc1
Crypto and TLS for C&
Classes | Public Types | Public Member Functions | Static Public Member Functions | 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
 
 BigInt (const std::string &str)
 
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 (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)
 
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 (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 ()
 

Detailed Description

Arbitrary precision integer

Definition at line 24 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 };
@ Hexadecimal
Definition: bigint.h:30

◆ 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 17 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 ( const std::string &  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 70 of file bigint.cpp.

71 {
72 Base base = Decimal;
73 size_t markers = 0;
74 bool negative = false;
75
76 if(str.length() > 0 && str[0] == '-')
77 {
78 markers += 1;
79 negative = true;
80 }
81
82 if(str.length() > markers + 2 && str[markers ] == '0' &&
83 str[markers + 1] == 'x')
84 {
85 markers += 2;
86 base = Hexadecimal;
87 }
88
89 *this = decode(cast_char_ptr_to_uint8(str.data()) + markers,
90 str.length() - markers, base);
91
92 if(negative) set_sign(Negative);
93 else set_sign(Positive);
94 }
static BigInt decode(const uint8_t buf[], size_t length)
Definition: bigint.h:805
void set_sign(Sign sign)
Definition: bigint.h:592
const uint8_t * cast_char_ptr_to_uint8(const char *s)
Definition: mem_ops.h:183

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

97 {
98 binary_decode(input, length);
99 }
void binary_decode(const uint8_t buf[], size_t length)
Definition: bigint.cpp:431

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

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

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

131 {
132 randomize(rng, bits, set_high_bit);
133 }
void randomize(RandomNumberGenerator &rng, size_t bitsize, bool set_high_bit=true)
Definition: big_rand.cpp:17
size_t bits() const
Definition: bigint.cpp:312

References bits(), and randomize().

◆ BigInt() [9/9]

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

Move constructor

Definition at line 147 of file bigint.h.

148 {
149 this->swap(other);
150 }
void swap(BigInt &other)
Definition: bigint.h:174

◆ ~BigInt()

Botan::BigInt::~BigInt ( )
inline

Definition at line 152 of file bigint.h.

void const_time_unpoison() const
Definition: bigint.h:750

Member Function Documentation

◆ abs()

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

Definition at line 391 of file bigint.cpp.

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

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 15 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 {
23 bigint_add2(mutable_data(), size() - 1, y, y_words);
24 }
25 else
26 {
27 const int32_t relative_size = bigint_cmp(data(), x_sw, y, y_words);
28
29 if(relative_size >= 0)
30 {
31 // *this >= y
32 bigint_sub2(mutable_data(), x_sw, y, y_words);
33 }
34 else
35 {
36 // *this < y
37 bigint_sub2_rev(mutable_data(), y, y_words);
38 }
39
40 //this->sign_fixup(relative_size, y_sign);
41 if(relative_size < 0)
42 set_sign(y_sign);
43 else if(relative_size == 0)
45 }
46
47 return (*this);
48 }
static SIMD_4x64 y
size_t sig_words() const
Definition: bigint.h:615
word * mutable_data()
Definition: bigint.h:643
size_t size() const
Definition: bigint.h:609
void grow_to(size_t n) const
Definition: bigint.h:665
const word * data() const
Definition: bigint.h:649
Sign sign() const
Definition: bigint.h:568
void bigint_sub2_rev(word x[], const word y[], size_t y_size)
Definition: mp_core.h:324
word bigint_sub2(word x[], size_t x_size, const word y[], size_t y_size)
Definition: mp_core.h:300
void bigint_add2(word x[], size_t x_size, const word y[], size_t y_size)
Definition: mp_core.h:280
int32_t bigint_cmp(const word x[], size_t x_size, const word y[], size_t y_size)
Definition: mp_core.h:529

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(), size(), and y.

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

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

Referenced by 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 712 of file bigint.h.

713 {
714 binary_decode(buf.data(), buf.size());
715 }

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

432 {
433 clear();
434
435 const size_t full_words = length / sizeof(word);
436 const size_t extra_bytes = length % sizeof(word);
437
438 secure_vector<word> reg((round_up(full_words + (extra_bytes > 0 ? 1 : 0), 8)));
439
440 for(size_t i = 0; i != full_words; ++i)
441 {
442 reg[i] = load_be<word>(buf + length - sizeof(word)*(i+1), 0);
443 }
444
445 if(extra_bytes > 0)
446 {
447 for(size_t i = 0; i != extra_bytes; ++i)
448 reg[full_words] = (reg[full_words] << 8) | buf[i];
449 }
450
451 m_data.swap(reg);
452 }
void clear()
Definition: bigint.h:379
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 398 of file bigint.cpp.

399 {
400 this->binary_encode(buf, bytes());
401 }
void binary_encode(uint8_t buf[]) const
Definition: bigint.cpp:398
size_t bytes() const
Definition: bigint.cpp:297

References binary_encode(), and bytes().

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

407 {
408 const size_t full_words = len / sizeof(word);
409 const size_t extra_bytes = len % sizeof(word);
410
411 for(size_t i = 0; i != full_words; ++i)
412 {
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 {
419 const word w = word_at(full_words);
420
421 for(size_t i = 0; i != extra_bytes; ++i)
422 {
423 output[extra_bytes - i - 1] = get_byte_var(sizeof(word) - i - 1, w);
424 }
425 }
426 }
word word_at(size_t n) const
Definition: bigint.h:537
constexpr void store_be(uint16_t in, uint8_t out[2])
Definition: loadstor.h:449
constexpr uint8_t get_byte_var(size_t byte_num, T input)
Definition: loadstor.h:39

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

313 {
314 const size_t words = sig_words();
315
316 if(words == 0)
317 return 0;
318
319 const size_t full_words = (words - 1) * BOTAN_MP_WORD_BITS;
320 const size_t top_bits = BOTAN_MP_WORD_BITS - top_bits_free();
321
322 return full_words + top_bits;
323 }
size_t top_bits_free() const
Definition: bigint.cpp:302
#define BOTAN_MP_WORD_BITS
Definition: build.h:52

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::gcd(), Botan::generate_dsa_primes(), Botan::generate_rsa_prime(), Botan::inverse_mod(), Botan::is_lucas_probable_prime(), 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*(), 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 135 of file bigint.cpp.

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

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

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

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

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

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

157 {
158 if(check_signs)
159 {
160 if(other.is_positive() && this->is_negative())
161 return -1;
162
163 if(other.is_negative() && this->is_positive())
164 return 1;
165
166 if(other.is_negative() && this->is_negative())
167 return (-bigint_cmp(this->data(), this->size(),
168 other.data(), other.size()));
169 }
170
171 return bigint_cmp(this->data(), this->size(),
172 other.data(), other.size());
173 }

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

142 {
143 if(is_negative())
144 return -1; // other is positive ...
145
146 const size_t sw = this->sig_words();
147 if(sw > 1)
148 return 1; // must be larger since other is just one word ...
149
150 return bigint_cmp(this->data(), sw, &other, 1);
151 }
bool is_negative() const
Definition: bigint.h:556

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 474 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:121

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

457 {
458 const size_t which = n / BOTAN_MP_WORD_BITS;
459 const word mask = static_cast<word>(set_it) << (n % BOTAN_MP_WORD_BITS);
460 m_data.set_word_at(which, word_at(which) | mask);
461 }

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

749{}

Referenced by Botan::gcd().

◆ const_time_unpoison()

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

Definition at line 750 of file bigint.h.

750{}

Referenced by Botan::gcd().

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

455 {
456 if(this->is_negative() || value.is_negative())
457 throw Invalid_Argument("BigInt::ct_cond_add requires both values to be positive");
458 this->grow_to(1 + value.sig_words());
459
460 bigint_cnd_add(static_cast<word>(predicate),
461 this->mutable_data(), this->size(),
462 value.data(), value.sig_words());
463 }
word bigint_cnd_add(word cnd, word x[], word x_size, const word y[], size_t y_size)
Definition: mp_core.h:42

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

Referenced by Botan::gcd(), 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.

488 {
489 const size_t t_words = size();
490 const size_t o_words = other.size();
491
492 if(o_words < t_words)
493 grow_to(o_words);
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 {
501 const word o_word = other.word_at(i);
502 const word t_word = this->word_at(i);
503 this->set_word_at(i, mask.select(o_word, t_word));
504 }
505
506 const bool different_sign = sign() != other.sign();
507 cond_flip_sign(predicate && different_sign);
508 }
void set_word_at(size_t i, word w)
Definition: bigint.h:542
void cond_flip_sign(bool predicate)
Definition: bigint.cpp:474

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

Referenced by 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 465 of file bigint.cpp.

466 {
467 const size_t max_words = std::max(size(), other.size());
468 grow_to(max_words);
469 other.grow_to(max_words);
470
471 bigint_cnd_swap(predicate, this->mutable_data(), other.mutable_data(), max_words);
472 }
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(), Botan::ct_modulo(), and Botan::gcd().

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

366 {
367 if(mod.is_negative() || this->is_negative())
368 throw Invalid_Argument("BigInt::ct_reduce_below both values must be positive");
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 {
382 word borrow = bigint_sub3(ws.data(), data(), sz, mod.data(), mod_words);
383
384 CT::Mask<word>::is_zero(borrow).select_n(mutable_data(), ws.data(), data(), sz);
385 }
386 }
static Mask< T > is_zero(T x)
Definition: ct_utils.h:139
word bigint_sub3(word z[], const word x[], size_t x_size, const word y[], size_t y_size)
Definition: mp_core.h:346
constexpr void clear_mem(T *ptr, size_t n)
Definition: mem_ops.h:115

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

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

817 {
818 return BigInt(buf);
819 }

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

839 {
840 if(base == Binary)
841 return BigInt(buf);
842 return BigInt::decode(buf.data(), buf.size(), base);
843 }

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

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

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

781 {
782 std::vector<uint8_t> output(n.bytes());
783 n.binary_encode(output.data());
784 return output;
785 }

References binary_encode(), and bytes().

Referenced by botan_generate_srp6_verifier(), botan_srp6_client_agree(), 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/2]

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

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

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/2]

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

Definition at line 118 of file big_code.cpp.

119 {
120 if(n.bytes() > bytes)
121 throw Encoding_Error("encode_1363: n is too large to encode properly");
122
123 n.binary_encode(output, bytes);
124 }

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

130 {
131 if(n1.is_negative() || n2.is_negative())
132 throw Encoding_Error("encode_fixed_length_int_pair: values must be positive");
133 if(n1.bytes() > bytes || n2.bytes() > bytes)
134 throw Encoding_Error("encode_fixed_length_int_pair: values too large to encode properly");
135 secure_vector<uint8_t> output(2 * bytes);
136 n1.binary_encode(output.data() , bytes);
137 n2.binary_encode(output.data() + bytes, bytes);
138 return output;
139 }

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

793 {
794 secure_vector<uint8_t> output(n.bytes());
795 n.binary_encode(output.data());
796 return output;
797 }

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

203 {
204 const size_t words = sig_words();
205
206 if(words > size)
207 throw Encoding_Error("BigInt::encode_words value too large to encode");
208
209 clear_mem(out, size);
210 copy_mem(out, data(), words);
211 }
constexpr void copy_mem(T *out, const T *in, size_t n)
Definition: mem_ops.h:126

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

584 {
586 }
Sign reverse_sign() const
Definition: bigint.h:573

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

111 {
112 const size_t input_bits = 8 * length;
113
114 BigInt bn;
115 bn.binary_decode(input, length);
116
117 if(input_bits > max_bits)
118 {
119 const size_t bits_to_shift = input_bits - max_bits;
120
121 bn >>= bits_to_shift;
122 }
123
124 return bn;
125 }

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

52 {
53 if(n >= 0)
54 return BigInt::from_u64(static_cast<uint64_t>(n));
55 else
56 return -BigInt::from_u64(static_cast<uint64_t>(-n));
57 }
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.

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

References set_word_at().

Referenced by 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 43 of file bigint.cpp.

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

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

484 {
485 return ((word_at(n / BOTAN_MP_WORD_BITS) >> (n % BOTAN_MP_WORD_BITS)) & 1);
486 }

References BOTAN_MP_WORD_BITS.

Referenced by Botan::ct_divide(), Botan::ct_divide_word(), Botan::ct_modulo(), Botan::inverse_mod(), Botan::is_lucas_probable_prime(), 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 239 of file bigint.cpp.

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

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

654{ 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 659 of file bigint.h.

659{ 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 175 of file bigint.cpp.

176 {
177 if(this->sign() != other.sign())
178 return false;
179
180 return bigint_ct_is_eq(this->data(), this->sig_words(),
181 other.data(), other.sig_words()).is_set();
182 }
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:617

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

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

185 {
186 if(this->is_negative() && other.is_positive())
187 return true;
188
189 if(this->is_positive() && other.is_negative())
190 return false;
191
192 if(other.is_negative() && this->is_negative())
193 {
194 return bigint_ct_is_lt(other.data(), other.sig_words(),
195 this->data(), this->sig_words()).is_set();
196 }
197
198 return bigint_ct_is_lt(this->data(), this->sig_words(),
199 other.data(), other.sig_words()).is_set();
200 }
bool is_positive() const
Definition: bigint.h:562
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:580

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

Referenced by 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 428 of file bigint.h.

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

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

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

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

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

474 {
475 m_data.mask_bits(n);
476 }

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

51 {
52 if(this->is_negative() || s.is_negative() || mod.is_negative())
53 throw Invalid_Argument("BigInt::mod_add expects all arguments are positive");
54
55 BOTAN_DEBUG_ASSERT(*this < mod);
56 BOTAN_DEBUG_ASSERT(s < mod);
57
58 /*
59 t + s or t + s - p == t - (p - s)
60
61 So first compute ws = p - s
62
63 Then compute t + s and t - ws
64
65 If t - ws does not borrow, then that is the correct valued
66 */
67
68 const size_t mod_sw = mod.sig_words();
69 BOTAN_ARG_CHECK(mod_sw > 0, "BigInt::mod_add modulus must be positive");
70
71 this->grow_to(mod_sw);
72 s.grow_to(mod_sw);
73
74 // First mod_sw for p - s, 2*mod_sw for bigint_addsub workspace
75 if(ws.size() < 3*mod_sw)
76 ws.resize(3*mod_sw);
77
78 word borrow = bigint_sub3(&ws[0], mod.data(), mod_sw, s.data(), mod_sw);
79 BOTAN_DEBUG_ASSERT(borrow == 0);
80 BOTAN_UNUSED(borrow);
81
82 // Compute t - ws
83 borrow = bigint_sub3(&ws[mod_sw], this->data(), mod_sw, &ws[0], mod_sw);
84
85 // Compute t + s
86 bigint_add3_nc(&ws[mod_sw*2], this->data(), mod_sw, s.data(), mod_sw);
87
88 CT::conditional_copy_mem(borrow, &ws[0], &ws[mod_sw*2], &ws[mod_sw], mod_sw);
89 set_words(&ws[0], mod_sw);
90
91 return (*this);
92 }
#define BOTAN_DEBUG_ASSERT(expr)
Definition: assert.h:122
#define BOTAN_UNUSED(...)
Definition: assert.h:141
#define BOTAN_ARG_CHECK(expr, msg)
Definition: assert.h:36
void set_words(const word w[], size_t len)
Definition: bigint.h:547
Mask< T > conditional_copy_mem(T cnd, T *to, const T *from0, const T *from1, size_t elems)
Definition: ct_utils.h:360
word bigint_add3_nc(word z[], const word x[], size_t x_size, const word y[], size_t y_size)
Definition: mp_core.h:250

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 121 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:335

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

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

95 {
96 if(this->is_negative() || s.is_negative() || mod.is_negative())
97 throw Invalid_Argument("BigInt::mod_sub expects all arguments are positive");
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 if(mod_sw == 4)
112 bigint_mod_sub_n<4>(mutable_data(), s.data(), mod.data(), ws.data());
113 else if(mod_sw == 6)
114 bigint_mod_sub_n<6>(mutable_data(), s.data(), mod.data(), ws.data());
115 else
116 bigint_mod_sub(mutable_data(), s.data(), mod.data(), mod_sw, ws.data());
117
118 return (*this);
119 }
void bigint_mod_sub(word t[], const word s[], const word mod[], size_t mod_sw, word ws[])
Definition: mp_core.h:691

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

161 {
162 const size_t x_sw = sig_words();
163 const size_t y_sw = y.sig_words();
164 set_sign((sign() == y.sign()) ? Positive : Negative);
165
166 if(x_sw == 0 || y_sw == 0)
167 {
168 clear();
170 }
171 else if(x_sw == 1 && y_sw)
172 {
173 grow_to(y_sw + 1);
174 bigint_linmul3(mutable_data(), y.data(), y_sw, word_at(0));
175 }
176 else if(y_sw == 1 && x_sw)
177 {
178 word carry = bigint_linmul2(mutable_data(), x_sw, y.word_at(0));
179 set_word_at(x_sw, carry);
180 }
181 else
182 {
183 const size_t new_size = x_sw + y_sw + 1;
184 ws.resize(new_size);
185 secure_vector<word> z_reg(new_size);
186
187 bigint_mul(z_reg.data(), z_reg.size(),
188 data(), size(), x_sw,
189 y.data(), y.size(), y_sw,
190 ws.data(), ws.size());
191
192 this->swap_reg(z_reg);
193 }
194
195 return (*this);
196 }
void swap_reg(secure_vector< word > &reg)
Definition: bigint.h:180
void bigint_linmul3(word z[], const word x[], size_t x_size, word y)
Definition: mp_core.h:508
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:297
void carry(int64_t &h0, int64_t &h1)
word bigint_linmul2(word x[], size_t x_size, word y)
Definition: mp_core.h:493

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(), word_at(), and y.

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:43

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

294{ return (!is_nonzero()); }
bool is_nonzero() const
Definition: bigint.h:428

◆ operator%=() [1/2]

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

Modulo operator

Parameters
ythe modulus to reduce this by

Definition at line 244 of file big_ops2.cpp.

245 {
246 return (*this = (*this) % mod);
247 }

◆ operator%=() [2/2]

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

Modulo operator

Parameters
ythe modulus (word) to reduce this by

Definition at line 252 of file big_ops2.cpp.

253 {
254 if(mod == 0)
255 throw Invalid_Argument("BigInt::operator%= divide by zero");
256
257 word remainder = 0;
258
259 if(is_power_of_2(mod))
260 {
261 remainder = (word_at(0) & (mod - 1));
262 }
263 else
264 {
265 const size_t sw = sig_words();
266 for(size_t i = sw; i > 0; --i)
267 remainder = bigint_modop(remainder, word_at(i-1), mod);
268 }
269
270 if(remainder && sign() == BigInt::Negative)
271 remainder = mod - remainder;
272
273 m_data.set_to_zero();
274 m_data.set_word_at(0, remainder);
276 return remainder;
277 }
constexpr bool is_power_of_2(T arg)
Definition: bit_ops.h:45
word bigint_modop(word n1, word n0, word d)
Definition: mp_core.h:759

References Botan::bigint_modop(), 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 154 of file big_ops2.cpp.

155 {
156 secure_vector<word> ws;
157 return this->mul(y, ws);
158 }
BigInt & mul(const BigInt &y, secure_vector< word > &ws)
Definition: big_ops2.cpp:160

References mul().

◆ operator*=() [2/2]

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

*= operator

Parameters
ythe word to multiply with this

Definition at line 215 of file big_ops2.cpp.

216 {
217 if(y == 0)
218 {
219 clear();
221 }
222
223 const word carry = bigint_linmul2(mutable_data(), size(), y);
225
226 return (*this);
227 }

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

◆ operator++() [1/2]

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

Increment operator

Definition at line 267 of file bigint.h.

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

◆ operator++() [2/2]

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

Postfix increment operator

Definition at line 277 of file bigint.h.

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

◆ operator+=() [1/2]

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

+= operator

Parameters
ythe BigInt to add to this

Definition at line 190 of file bigint.h.

191 {
192 return add(y.data(), y.sig_words(), y.sign());
193 }
BigInt & add(const word y[], size_t y_words, Sign sign)
Definition: big_ops2.cpp:15

References y.

◆ operator+=() [2/2]

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

+= operator

Parameters
ythe word to add to this

Definition at line 199 of file bigint.h.

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

References y.

◆ operator-()

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

Unary negation operator

Returns
negative this

Definition at line 328 of file bigint.cpp.

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

References flip_sign().

◆ operator--() [1/2]

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

Decrement operator

Definition at line 272 of file bigint.h.

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

◆ operator--() [2/2]

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

Postfix decrement operator

Definition at line 282 of file bigint.h.

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

◆ operator-=() [1/2]

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

-= operator

Parameters
ythe BigInt to subtract from this

Definition at line 208 of file bigint.h.

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

References y.

◆ operator-=() [2/2]

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

-= operator

Parameters
ythe word to subtract from this

Definition at line 217 of file bigint.h.

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

References y.

◆ operator/=()

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

/= operator

Parameters
ythe BigInt to divide this by

Definition at line 232 of file big_ops2.cpp.

233 {
234 if(y.sig_words() == 1 && is_power_of_2(y.word_at(0)))
235 (*this) >>= (y.bits() - 1);
236 else
237 (*this) = (*this) / y;
238 return (*this);
239 }

References Botan::is_power_of_2(), and y.

◆ operator<<=()

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

Left shift operator

Parameters
shiftthe number of bits to shift this left by

Definition at line 282 of file big_ops2.cpp.

283 {
284 const size_t shift_words = shift / BOTAN_MP_WORD_BITS;
285 const size_t shift_bits = shift % BOTAN_MP_WORD_BITS;
286 const size_t size = sig_words();
287
288 const size_t bits_free = top_bits_free();
289
290 const size_t new_size = size + shift_words + (bits_free < shift_bits);
291
292 m_data.grow_to(new_size);
293
294 bigint_shl1(m_data.mutable_data(), new_size, size, shift_words, shift_bits);
295
296 return (*this);
297 }
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:413

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

158 {
159 if(this != &other)
160 this->swap(other);
161
162 return (*this);
163 }

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

303 {
304 const size_t shift_words = shift / BOTAN_MP_WORD_BITS;
305 const size_t shift_bits = shift % BOTAN_MP_WORD_BITS;
306
307 bigint_shr1(m_data.mutable_data(), m_data.size(), shift_words, shift_bits);
308
309 if(is_negative() && is_zero())
311
312 return (*this);
313 }
void bigint_shr1(word x[], size_t x_size, size_t word_shift, size_t bit_shift)
Definition: mp_core.h:431

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

769 {
770 BigInt b;
771 b.set_bit(n);
772 return b;
773 }
PolynomialVector b
Definition: kyber.cpp:858

References b.

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

47 {
48 if(min.is_negative() || max.is_negative() || max <= min)
49 throw Invalid_Argument("BigInt::random_integer invalid range");
50
51 BigInt r;
52
53 const size_t bits = max.bits();
54
55 do
56 {
57 r.randomize(rng, bits, false);
58 }
59 while(r < min || r >= max);
60
61 return r;
62 }

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

Referenced by botan_mp_rand_range(), Botan::is_miller_rabin_probable_prime(), 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 17 of file big_rand.cpp.

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

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

Referenced by BigInt(), 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 335 of file bigint.cpp.

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

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

667{ m_data.resize(s); }

Referenced by 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 133 of file big_ops2.cpp.

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

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

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

574 {
575 if(sign() == Positive)
576 return Negative;
577 return Positive;
578 }

◆ set_bit()

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

Set bit at specified position

Parameters
nbit position to set

Definition at line 443 of file bigint.h.

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

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

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

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

543 {
544 m_data.set_word_at(i, w);
545 }

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

548 {
549 m_data.set_words(w, len);
550 }

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

568{ 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>>(), 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 198 of file big_ops2.cpp.

199 {
200 const size_t sw = sig_words();
201
202 secure_vector<word> z(2*sw);
203 ws.resize(z.size());
204
205 bigint_sqr(z.data(), z.size(),
206 data(), size(), sw,
207 ws.data(), ws.size());
208
209 swap_reg(z);
211
212 return (*this);
213 }
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:356

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

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

References y.

◆ swap()

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

Swap this value with another

Parameters
otherBigInt to swap values with

Definition at line 174 of file bigint.h.

175 {
176 m_data.swap(other.m_data);
177 std::swap(m_signedness, other.m_signedness);
178 }

Referenced by Botan::EC_Point::add_affine(), Botan::EC_Point::mult2(), Botan::EC_Point::swap(), and std::swap< Botan::BigInt >().

◆ swap_reg()

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

Definition at line 180 of file bigint.h.

181 {
182 m_data.swap(reg);
183 // sign left unchanged
184 }

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 14 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 {
39 word remainder = 0;
40 ct_divide_word(value, conversion_radix, value, remainder);
41 digit_groups[i] = remainder;
42 }
43
44 BOTAN_ASSERT_NOMSG(value.is_zero());
45
46 // Extract digits from the groups
47 std::vector<uint8_t> digits(digit_blocks * radix_digits);
48
49 for(size_t i = 0; i != digit_blocks; ++i)
50 {
51 word remainder = digit_groups[i];
52 for(size_t j = 0; j != radix_digits; ++j)
53 {
54 // Compiler should convert div/mod by 10 into mul by magic constant
55 const word digit = remainder % 10;
56 remainder /= 10;
57 digits[radix_digits*i + j] = static_cast<uint8_t>(digit);
58 }
59 }
60
61 // remove leading zeros
62 while(!digits.empty() && digits.back() == 0)
63 {
64 digits.pop_back();
65 }
66
67 BOTAN_ASSERT_NOMSG(digit_estimate >= digits.size());
68
69 // Reverse the digits to big-endian and format to text
70 std::string s;
71 s.reserve(1 + digits.size());
72
73 if(is_negative())
74 s += "-";
75
76 // Reverse and convert to textual digits
77 for(auto i = digits.rbegin(); i != digits.rend(); ++i)
78 {
79 s.push_back(*i + '0'); // assumes ASCII
80 }
81
82 if(s.empty())
83 s += "0";
84
85 return s;
86 }
void ct_divide_word(const BigInt &x, word y, BigInt &q_out, word &r_out)
Definition: divide.cpp:84

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

89 {
90 const size_t this_bytes = this->bytes();
91 std::vector<uint8_t> bits(std::max<size_t>(1, this_bytes));
92
93 if(this_bytes > 0)
94 this->binary_encode(bits.data());
95
96 std::string hrep;
97 if(is_negative())
98 hrep += "-";
99 hrep += "0x";
100 hrep += hex_encode(bits);
101 return hrep;
102 }
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 270 of file bigint.cpp.

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

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

303 {
304 const size_t words = sig_words();
305
306 const word top_word = word_at(words - 1);
307 const size_t bits_used = high_bit(top_word);
308 CT::unpoison(bits_used);
309 return BOTAN_MP_WORD_BITS - bits_used;
310 }
void unpoison(const T *p, size_t n)
Definition: ct_utils.h:58
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(), and operator<<=().

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

61 {
62 BigInt bn;
63 bn.grow_to(size);
64 return bn;
65 }

References grow_to(), and size().

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

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

538 {
539 return m_data.get_word_at(n);
540 }

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

◆ zero()

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

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