Botan  2.9.0
Crypto and TLS for C++11
Classes | Public Types | Public Member Functions | Static Public Member Functions | List of all members
Botan::BigInt Class Referencefinal

#include <bigint.h>

Classes

class  DivideByZero
 

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 (uint64_t n)
 
 BigInt (const BigInt &other)=default
 
 BigInt (const std::string &str)
 
 BigInt (const uint8_t buf[], size_t length)
 
template<typename Alloc >
 BigInt (const std::vector< uint8_t, Alloc > &vec)
 
 BigInt (const uint8_t buf[], size_t length, Base base)
 
 BigInt (const uint8_t buf[], size_t length, size_t max_bits)
 
 BigInt (const word words[], size_t length)
 
 BigInt (RandomNumberGenerator &rng, size_t bits, bool set_high_bit=true)
 Create a random BigInt of the specified size. More...
 
 BigInt (Sign sign, size_t n)
 
 BigInt (BigInt &&other)
 
void binary_decode (const uint8_t buf[], size_t length)
 
void binary_decode (const secure_vector< uint8_t > &buf)
 
void binary_encode (uint8_t buf[]) 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_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
 
size_t encoded_size (Base base=Binary) 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)
 
void shrink_to_fit (size_t min_size=0)
 
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
 

Static Public Member Functions

static BigInt add2 (const BigInt &x, const word y[], size_t y_words, Sign y_sign)
 
static void const_time_lookup (secure_vector< word > &output, const std::vector< BigInt > &vec, size_t idx)
 
static BigInt decode (const uint8_t buf[], size_t length)
 
static BigInt decode (const secure_vector< uint8_t > &buf)
 
static BigInt decode (const std::vector< uint8_t > &buf)
 
static BigInt decode (const uint8_t buf[], size_t length, Base base)
 
static BigInt decode (const secure_vector< uint8_t > &buf, Base base)
 
static BigInt decode (const std::vector< uint8_t > &buf, Base base)
 
static std::vector< uint8_t > encode (const BigInt &n)
 
static void encode (uint8_t buf[], const BigInt &n)
 
static std::vector< uint8_t > encode (const BigInt &n, Base base)
 
static void encode (uint8_t buf[], const BigInt &n, Base base)
 
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 secure_vector< uint8_t > encode_locked (const BigInt &n, Base base)
 
static BigInt power_of_2 (size_t n)
 
static BigInt random_integer (RandomNumberGenerator &rng, const BigInt &min, const BigInt &max)
 

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

◆ Sign

Sign symbol definitions for positive and negative numbers

Enumerator
Negative 
Positive 

Definition at line 36 of file bigint.h.

Constructor & Destructor Documentation

◆ BigInt() [1/12]

Botan::BigInt::BigInt ( )
default

Create empty BigInt

◆ BigInt() [2/12]

Botan::BigInt::BigInt ( uint64_t  n)

Create BigInt from 64 bit integer

Parameters
ninitial value of this BigInt

Definition at line 24 of file bigint.cpp.

25  {
26  if(n > 0)
27  {
28 #if BOTAN_MP_WORD_BITS == 32
29  m_data.set_word_at(0, static_cast<word>(n));
30  m_data.set_word_at(1, static_cast<word>(n >> 32));
31 #else
32  m_data.set_word_at(0, n);
33 #endif
34  }
35 
36  }

◆ BigInt() [3/12]

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

Copy Constructor

Parameters
otherthe BigInt to copy

◆ BigInt() [4/12]

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

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

51  {
52  Base base = Decimal;
53  size_t markers = 0;
54  bool negative = false;
55 
56  if(str.length() > 0 && str[0] == '-')
57  {
58  markers += 1;
59  negative = true;
60  }
61 
62  if(str.length() > markers + 2 && str[markers ] == '0' &&
63  str[markers + 1] == 'x')
64  {
65  markers += 2;
66  base = Hexadecimal;
67  }
68 
69  *this = decode(cast_char_ptr_to_uint8(str.data()) + markers,
70  str.length() - markers, base);
71 
72  if(negative) set_sign(Negative);
73  else set_sign(Positive);
74  }
const uint8_t * cast_char_ptr_to_uint8(const char *s)
Definition: mem_ops.h:160
static BigInt decode(const uint8_t buf[], size_t length)
Definition: bigint.h:786
void set_sign(Sign sign)
Definition: bigint.h:566

◆ BigInt() [5/12]

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

References binary_decode().

77  {
78  binary_decode(input, length);
79  }
void binary_decode(const uint8_t buf[], size_t length)
Definition: bigint.cpp:397

◆ BigInt() [6/12]

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

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

◆ BigInt() [7/12]

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

References decode().

85  {
86  *this = decode(input, length, base);
87  }
static BigInt decode(const uint8_t buf[], size_t length)
Definition: bigint.h:786

◆ BigInt() [8/12]

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

Create a BigInt from an integer in a byte array

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

References binary_decode(), and bits().

90  {
91  const size_t max_bytes = std::min(length, (max_bits + 7) / 8);
92  binary_decode(buf, max_bytes);
93 
94  const size_t b = this->bits();
95  if(b > max_bits)
96  {
97  *this >>= (b - max_bits);
98  }
99  }
size_t bits() const
Definition: bigint.cpp:281
void binary_decode(const uint8_t buf[], size_t length)
Definition: bigint.cpp:397

◆ BigInt() [9/12]

Botan::BigInt::BigInt ( const word  words[],
size_t  length 
)

Create a BigInt from an array of words

Parameters
wordsthe words
lengthnumber of words

Definition at line 16 of file bigint.cpp.

17  {
18  m_data.set_words(words, length);
19  }

◆ BigInt() [10/12]

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

References bits(), and randomize().

105  {
106  randomize(rng, bits, set_high_bit);
107  }
size_t bits() const
Definition: bigint.cpp:281
void randomize(RandomNumberGenerator &rng, size_t bitsize, bool set_high_bit=true)
Definition: big_rand.cpp:17

◆ BigInt() [11/12]

Botan::BigInt::BigInt ( Sign  sign,
size_t  n 
)

Create BigInt of specified size, all zeros

Parameters
signthe sign
nsize of the internal register in words

Definition at line 41 of file bigint.cpp.

References size().

42  {
43  m_data.set_size(size);
44  m_signedness = s;
45  }
size_t size() const
Definition: bigint.h:583

◆ BigInt() [12/12]

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

Move constructor

Definition at line 135 of file bigint.h.

136  {
137  this->swap(other);
138  }
void swap(BigInt &other)
Definition: bigint.h:160

Member Function Documentation

◆ abs()

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

Definition at line 377 of file bigint.cpp.

References Positive, and set_sign().

Referenced by Botan::abs().

378  {
379  BigInt x = (*this);
380  x.set_sign(Positive);
381  return x;
382  }
BigInt()=default

◆ add()

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

Definition at line 15 of file big_ops2.cpp.

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

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  }
void bigint_sub2_rev(word x[], const word y[], size_t y_size)
Definition: mp_core.h:326
int32_t bigint_cmp(const word x[], size_t x_size, const word y[], size_t y_size)
Definition: mp_core.h:525
word bigint_sub2(word x[], size_t x_size, const word y[], size_t y_size)
Definition: mp_core.h:302
Sign sign() const
Definition: bigint.h:542
word * mutable_data()
Definition: bigint.h:617
const word * data() const
Definition: bigint.h:623
size_t size() const
Definition: bigint.h:583
size_t sig_words() const
Definition: bigint.h:589
void grow_to(size_t n) const
Definition: bigint.h:639
void bigint_add2(word x[], size_t x_size, const word y[], size_t y_size)
Definition: mp_core.h:282
void set_sign(Sign sign)
Definition: bigint.h:566

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

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

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

19  {
20  const size_t x_sw = x.sig_words();
21 
22  BigInt z(x.sign(), 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  }
28  else
29  {
30  const int32_t relative_size = bigint_sub_abs(z.mutable_data(), x.data(), x_sw, y, y_words);
31 
32  //z.sign_fixup(relative_size, y_sign);
33  if(relative_size < 0)
34  z.set_sign(y_sign);
35  else if(relative_size == 0)
36  z.set_sign(BigInt::Positive);
37  }
38 
39  return z;
40  }
CT::Mask< word > bigint_sub_abs(word z[], const word x[], const word y[], size_t N, word ws[])
Definition: mp_core.h:379
BigInt()=default
void bigint_add3(word z[], const word x[], size_t x_size, const word y[], size_t y_size)
Definition: mp_core.h:291

◆ binary_decode() [1/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 397 of file bigint.cpp.

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

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

398  {
399  const size_t WORD_BYTES = sizeof(word);
400 
401  clear();
402  secure_vector<word> reg((round_up((length / WORD_BYTES) + 1, 8)));
403 
404  // TODO can load a word at a time here
405  for(size_t i = 0; i != length / WORD_BYTES; ++i)
406  {
407  const size_t top = length - WORD_BYTES*i;
408  for(size_t j = WORD_BYTES; j > 0; --j)
409  reg[i] = (reg[i] << 8) | buf[top - j];
410  }
411 
412  for(size_t i = 0; i != length % WORD_BYTES; ++i)
413  reg[length / WORD_BYTES] = (reg[length / WORD_BYTES] << 8) | buf[i];
414 
415  m_data.swap(reg);
416  }
void clear()
Definition: bigint.h:365
size_t round_up(size_t n, size_t align_to)
Definition: rounding.h:21

◆ binary_decode() [2/2]

void Botan::BigInt::binary_decode ( const secure_vector< uint8_t > &  buf)
inline

Read integer value from a byte array (secure_vector<uint8_t>)

Parameters
bufthe array to load from

Definition at line 682 of file bigint.h.

683  {
684  binary_decode(buf.data(), buf.size());
685  }
void binary_decode(const uint8_t buf[], size_t length)
Definition: bigint.cpp:397

◆ binary_encode()

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

References byte_at(), and bytes().

Referenced by Botan::base58_decode(), botan_mp_to_bin(), encode(), encode_locked(), and Botan::GOST_3410_PublicKey::public_key_bits().

388  {
389  const size_t sig_bytes = bytes();
390  for(size_t i = 0; i != sig_bytes; ++i)
391  output[sig_bytes-i-1] = byte_at(i);
392  }
uint8_t byte_at(size_t n) const
Definition: bigint.h:500
size_t bytes() const
Definition: bigint.cpp:266

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

References sig_words(), and top_bits_free().

Referenced by BigInt(), botan_mp_num_bits(), bytes(), Botan::ct_divide(), Botan::ct_divide_u8(), Botan::ct_inverse_mod_odd_modulus(), Botan::ct_modulo(), Botan::BER_Decoder::decode(), Botan::BER_Decoder::decode_constrained_integer(), Botan::DL_Group::DL_Group(), Botan::DER_Encoder::encode(), encoded_size(), Botan::Fixed_Window_Exponentiator::execute(), Botan::Montgomery_Exponentiator::execute(), Botan::generate_dsa_primes(), Botan::generate_rsa_prime(), Botan::generate_srp6_verifier(), Botan::is_lucas_probable_prime(), Botan::is_perfect_square(), Botan::is_prime(), Botan::RSA_PublicKey::key_length(), Botan::TPM_PrivateKey::key_length(), Botan::monty_multi_exp(), Botan::PointGFp_Base_Point_Precompute::mul(), Botan::PointGFp_Var_Point_Precompute::mul(), Botan::PointGFp_Multi_Point_Precompute::multi_exp(), Botan::operator*(), Botan::operator/(), operator/=(), Botan::passes_miller_rabin_test(), Botan::DL_Group::power_g_p(), random_integer(), Botan::random_prime(), Botan::RSA_PrivateKey::RSA_PrivateKey(), Botan::Fixed_Window_Exponentiator::set_base(), Botan::Montgomery_Exponentiator::set_base(), Botan::srp6_group_identifier(), to_hex_string(), and to_u32bit().

282  {
283  const size_t words = sig_words();
284 
285  if(words == 0)
286  return 0;
287 
288  const size_t full_words = (words - 1) * BOTAN_MP_WORD_BITS;
289  const size_t top_bits = BOTAN_MP_WORD_BITS - top_bits_free();
290 
291  return full_words + top_bits;
292  }
size_t sig_words() const
Definition: bigint.h:589
size_t top_bits_free() const
Definition: bigint.cpp:271

◆ byte_at()

uint8_t Botan::BigInt::byte_at ( size_t  n) const
inline
Parameters
nthe offset to get a byte from
Returns
byte at offset n

Definition at line 500 of file bigint.h.

References Botan::get_byte().

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

501  {
502  return get_byte(sizeof(word) - (n % sizeof(word)) - 1,
503  word_at(n / sizeof(word)));
504  }
constexpr uint8_t get_byte(size_t byte_num, T input)
Definition: loadstor.h:39
word word_at(size_t n) const
Definition: bigint.h:511

◆ bytes()

size_t Botan::BigInt::bytes ( ) const

Give byte length of the integer

Returns
byte length of the represented integer value

Definition at line 266 of file bigint.cpp.

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

Referenced by Botan::base58_decode(), binary_encode(), botan_mp_num_bytes(), Botan::ECIES_KA_Operation::derive_secret(), Botan::DER_Encoder::encode(), Botan::PointGFp::encode(), encode(), encode_1363(), encode_fixed_length_int_pair(), encode_locked(), encoded_size(), Botan::EC_PrivateKey::private_key_bits(), Botan::GOST_3410_PublicKey::public_key_bits(), and Botan::SRP6_Server_Session::step1().

267  {
268  return round_up(bits(), 8) / 8;
269  }
size_t bits() const
Definition: bigint.cpp:281
size_t round_up(size_t n, size_t align_to)
Definition: rounding.h:21

◆ clear()

void Botan::BigInt::clear ( )
inline

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

Definition at line 365 of file bigint.h.

Referenced by Botan::PointGFp::add(), Botan::PointGFp::add_affine(), binary_decode(), botan_mp_clear(), mul(), operator*=(), and randomize().

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

◆ clear_bit()

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

Clear bit at specified position

Parameters
nbit position to clear

Definition at line 255 of file bigint.cpp.

References size(), and word_at().

Referenced by botan_mp_clear_bit().

256  {
257  const size_t which = n / BOTAN_MP_WORD_BITS;
258 
259  if(which < size())
260  {
261  const word mask = ~(static_cast<word>(1) << (n % BOTAN_MP_WORD_BITS));
262  m_data.set_word_at(which, word_at(which) & mask);
263  }
264  }
word word_at(size_t n) const
Definition: bigint.h:511
size_t size() const
Definition: bigint.h:583

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

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

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

125  {
126  if(check_signs)
127  {
128  if(other.is_positive() && this->is_negative())
129  return -1;
130 
131  if(other.is_negative() && this->is_positive())
132  return 1;
133 
134  if(other.is_negative() && this->is_negative())
135  return (-bigint_cmp(this->data(), this->sig_words(),
136  other.data(), other.sig_words()));
137  }
138 
139  return bigint_cmp(this->data(), this->sig_words(),
140  other.data(), other.sig_words());
141  }
bool is_negative() const
Definition: bigint.h:530
int32_t bigint_cmp(const word x[], size_t x_size, const word y[], size_t y_size)
Definition: mp_core.h:525
const word * data() const
Definition: bigint.h:623
size_t sig_words() const
Definition: bigint.h:589
bool is_positive() const
Definition: bigint.h:536

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

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

110  {
111  if(is_negative())
112  return -1; // other is positive ...
113 
114  const size_t sw = this->sig_words();
115  if(sw > 1)
116  return 1; // must be larger since other is just one word ...
117 
118  return bigint_cmp(this->data(), sw, &other, 1);
119  }
bool is_negative() const
Definition: bigint.h:530
int32_t bigint_cmp(const word x[], size_t x_size, const word y[], size_t y_size)
Definition: mp_core.h:525
const word * data() const
Definition: bigint.h:623
size_t sig_words() const
Definition: bigint.h:589

◆ cond_flip_sign()

void Botan::BigInt::cond_flip_sign ( bool  predicate)

If predicate is true flip the sign of *this

Definition at line 427 of file bigint.cpp.

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

Referenced by ct_cond_assign(), Botan::inverse_euclid(), and rev_sub().

428  {
429  // This code is assuming Negative == 0, Positive == 1
430 
431  const auto mask = CT::Mask<uint8_t>::expand(predicate);
432 
433  const uint8_t current_sign = static_cast<uint8_t>(sign());
434 
435  const uint8_t new_sign = mask.select(current_sign ^ 1, current_sign);
436 
437  set_sign(static_cast<Sign>(new_sign));
438  }
Sign sign() const
Definition: bigint.h:542
static Mask< T > expand(T v)
Definition: ct_utils.h:123
void set_sign(Sign sign)
Definition: bigint.h:566

◆ conditionally_set_bit()

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

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

References word_at().

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

246  {
247  const size_t which = n / BOTAN_MP_WORD_BITS;
248  const word mask = static_cast<word>(set_it) << (n % BOTAN_MP_WORD_BITS);
249  m_data.set_word_at(which, word_at(which) | mask);
250  }
word word_at(size_t n) const
Definition: bigint.h:511

◆ const_time_lookup()

void Botan::BigInt::const_time_lookup ( secure_vector< word > &  output,
const std::vector< BigInt > &  vec,
size_t  idx 
)
static

Set output = vec[idx].m_reg in constant time All words of vec must have the same size

Definition at line 477 of file bigint.cpp.

References BOTAN_ASSERT, Botan::clear_mem(), Botan::CT::Mask< T >::is_equal(), Botan::CT::poison(), size(), and Botan::CT::unpoison().

480  {
481  const size_t words = output.size();
482 
483  clear_mem(output.data(), output.size());
484 
485  CT::poison(&idx, sizeof(idx));
486 
487  for(size_t i = 0; i != vec.size(); ++i)
488  {
489  BOTAN_ASSERT(vec[i].size() >= words,
490  "Word size as expected in const_time_lookup");
491 
492  const auto mask = CT::Mask<word>::is_equal(i, idx);
493 
494  for(size_t w = 0; w != words; ++w)
495  {
496  const word viw = vec[i].word_at(w);
497  output[w] = mask.if_set_return(viw);
498  }
499  }
500 
501  CT::unpoison(idx);
502  CT::unpoison(output.data(), output.size());
503  }
void clear_mem(T *ptr, size_t n)
Definition: mem_ops.h:111
void poison(const T *p, size_t n)
Definition: ct_utils.h:48
#define BOTAN_ASSERT(expr, assertion_made)
Definition: assert.h:55
size_t size() const
Definition: bigint.h:583
void unpoison(const T *p, size_t n)
Definition: ct_utils.h:59
static Mask< T > is_equal(T x, T y)
Definition: ct_utils.h:149

◆ const_time_poison()

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

Definition at line 720 of file bigint.h.

720 {}

◆ const_time_unpoison()

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

Definition at line 721 of file bigint.h.

721 {}

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

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

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

441  {
442  const size_t t_words = size();
443  const size_t o_words = other.size();
444 
445  if(o_words < t_words)
446  grow_to(o_words);
447 
448  const size_t r_words = std::max(t_words, o_words);
449 
450  const auto mask = CT::Mask<word>::expand(predicate);
451 
452  for(size_t i = 0; i != r_words; ++i)
453  {
454  const word o_word = other.word_at(i);
455  const word t_word = this->word_at(i);
456  this->set_word_at(i, mask.select(o_word, t_word));
457  }
458 
459  if(sign() != other.sign())
460  {
461  cond_flip_sign(predicate);
462  }
463  }
Sign sign() const
Definition: bigint.h:542
word word_at(size_t n) const
Definition: bigint.h:511
static Mask< T > expand(T v)
Definition: ct_utils.h:123
size_t size() const
Definition: bigint.h:583
void cond_flip_sign(bool predicate)
Definition: bigint.cpp:427
void grow_to(size_t n) const
Definition: bigint.h:639
void set_word_at(size_t i, word w)
Definition: bigint.h:516

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

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

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

419  {
420  const size_t max_words = std::max(size(), other.size());
421  grow_to(max_words);
422  other.grow_to(max_words);
423 
424  bigint_cnd_swap(predicate, this->mutable_data(), other.mutable_data(), max_words);
425  }
word * mutable_data()
Definition: bigint.h:617
void bigint_cnd_swap(word cnd, word x[], word y[], size_t size)
Definition: mp_core.h:31
size_t size() const
Definition: bigint.h:583
void grow_to(size_t n) const
Definition: bigint.h:639

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

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

352  {
353  if(mod.is_negative() || this->is_negative())
354  throw Invalid_Argument("BigInt::ct_reduce_below both values must be positive");
355 
356  const size_t mod_words = mod.sig_words();
357 
358  grow_to(mod_words);
359 
360  const size_t sz = size();
361 
362  ws.resize(sz);
363 
364  clear_mem(ws.data(), sz);
365 
366  for(size_t i = 0; i != bound; ++i)
367  {
368  word borrow = bigint_sub3(ws.data(), data(), sz, mod.data(), mod_words);
369 
370  CT::Mask<word>::is_zero(borrow).select_n(mutable_data(), ws.data(), data(), sz);
371  }
372  }
bool is_negative() const
Definition: bigint.h:530
void clear_mem(T *ptr, size_t n)
Definition: mem_ops.h:111
word * mutable_data()
Definition: bigint.h:617
word bigint_sub3(word z[], const word x[], size_t x_size, const word y[], size_t y_size)
Definition: mp_core.h:344
const word * data() const
Definition: bigint.h:623
size_t size() const
Definition: bigint.h:583
void grow_to(size_t n) const
Definition: bigint.h:639
static Mask< T > is_zero(T x)
Definition: ct_utils.h:141

◆ data()

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

◆ decode() [1/6]

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

Create a BigInt from an integer in a byte array

Parameters
bufthe binary value to load
lengthsize of buf
Returns
BigInt representing the integer in the byte array

Definition at line 786 of file bigint.h.

Referenced by BigInt(), Botan::TLS::Client_Key_Exchange::Client_Key_Exchange(), decode(), Botan::BER_Decoder::decode_octet_string_bigint(), Botan::CRL_Entry::encode_into(), Botan::TPM_PrivateKey::get_e(), Botan::TPM_PrivateKey::get_n(), Botan::OCSP::CertID::is_id_for(), Botan::OS2ECP(), and Botan::TLS::Callbacks::tls_dh_agree().

787  {
788  return BigInt(buf, length);
789  }
BigInt()=default

◆ decode() [2/6]

static BigInt Botan::BigInt::decode ( const secure_vector< uint8_t > &  buf)
inlinestatic

Create a BigInt from an integer in a byte array

Parameters
bufthe binary value to load
Returns
BigInt representing the integer in the byte array

Definition at line 796 of file bigint.h.

797  {
798  return BigInt(buf);
799  }
BigInt()=default

◆ decode() [3/6]

static BigInt Botan::BigInt::decode ( const std::vector< uint8_t > &  buf)
inlinestatic

Create a BigInt from an integer in a byte array

Parameters
bufthe binary value to load
Returns
BigInt representing the integer in the byte array

Definition at line 806 of file bigint.h.

807  {
808  return BigInt(buf);
809  }
BigInt()=default

◆ decode() [4/6]

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

References Binary, binary_decode(), Botan::cast_uint8_ptr_to_char(), Botan::Charset::char2digit(), Decimal, Botan::hex_decode_locked(), Hexadecimal, Botan::Charset::is_digit(), and Botan::Charset::is_space().

156  {
157  BigInt r;
158  if(base == Binary)
159  r.binary_decode(buf, length);
160  else if(base == Hexadecimal)
161  {
162  secure_vector<uint8_t> binary;
163 
164  if(length % 2)
165  {
166  // Handle lack of leading 0
167  const char buf0_with_leading_0[2] =
168  { '0', static_cast<char>(buf[0]) };
169 
170  binary = hex_decode_locked(buf0_with_leading_0, 2);
171 
172  binary += hex_decode_locked(cast_uint8_ptr_to_char(&buf[1]),
173  length - 1,
174  false);
175  }
176  else
178  length, false);
179 
180  r.binary_decode(binary.data(), binary.size());
181  }
182  else if(base == Decimal)
183  {
184  for(size_t i = 0; i != length; ++i)
185  {
186  if(Charset::is_space(buf[i]))
187  continue;
188 
189  if(!Charset::is_digit(buf[i]))
190  throw Invalid_Argument("BigInt::decode: "
191  "Invalid character in decimal input");
192 
193  const uint8_t x = Charset::char2digit(buf[i]);
194 
195  if(x >= 10)
196  throw Invalid_Argument("BigInt: Invalid decimal string");
197 
198  r *= 10;
199  r += x;
200  }
201  }
202  else
203  throw Invalid_Argument("Unknown BigInt decoding method");
204  return r;
205  }
secure_vector< uint8_t > hex_decode_locked(const char input[], size_t input_length, bool ignore_ws)
Definition: hex.cpp:165
uint8_t char2digit(char c)
Definition: charset.cpp:231
bool is_space(char c)
Definition: charset.cpp:221
const char * cast_uint8_ptr_to_char(const uint8_t *b)
Definition: mem_ops.h:165
bool is_digit(char c)
Definition: charset.cpp:210
BigInt()=default

◆ decode() [5/6]

static BigInt Botan::BigInt::decode ( const secure_vector< uint8_t > &  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 853 of file bigint.h.

References decode().

855  {
856  if(base == Binary)
857  return BigInt(buf);
858  return BigInt::decode(buf.data(), buf.size(), base);
859  }
static BigInt decode(const uint8_t buf[], size_t length)
Definition: bigint.h:786
BigInt()=default

◆ decode() [6/6]

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

References decode().

868  {
869  if(base == Binary)
870  return BigInt(buf);
871  return BigInt::decode(buf.data(), buf.size(), base);
872  }
static BigInt decode(const uint8_t buf[], size_t length)
Definition: bigint.h:786
BigInt()=default

◆ encode() [1/4]

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

References binary_encode(), and bytes().

Referenced by Botan::TLS::Client_Key_Exchange::Client_Key_Exchange(), Botan::CRL_Entry::decode_from(), Botan::ECIES_KA_Operation::derive_secret(), Botan::DER_Encoder::encode(), encode(), encode_1363(), encode_locked(), Botan::FPE_FE1::FPE_FE1(), Botan::operator<<(), Botan::TLS::Server_Key_Exchange::Server_Key_Exchange(), and to_hex_string().

752  {
753  std::vector<uint8_t> output(n.bytes());
754  n.binary_encode(output.data());
755  return output;
756  }

◆ encode() [2/4]

static void Botan::BigInt::encode ( uint8_t  buf[],
const BigInt n 
)
inlinestatic

Encode the integer value from a BigInt to a byte array

Parameters
bufdestination byte array for the encoded integer
nthe BigInt to use as integer source

Definition at line 775 of file bigint.h.

References binary_encode().

776  {
777  n.binary_encode(buf);
778  }

◆ encode() [3/4]

std::vector< uint8_t > Botan::BigInt::encode ( const BigInt n,
Base  base 
)
static

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

Parameters
nthe BigInt to use as integer source
basenumber-base of resulting byte array representation
Returns
secure_vector of bytes containing the integer with given base

Definition at line 89 of file big_code.cpp.

References Binary, encode(), and encoded_size().

90  {
91  if(base == Binary)
92  return BigInt::encode(n);
93 
94  std::vector<uint8_t> output(n.encoded_size(base));
95  encode(output.data(), n, base);
96  for(size_t j = 0; j != output.size(); ++j)
97  if(output[j] == 0)
98  output[j] = '0';
99 
100  return output;
101  }
static std::vector< uint8_t > encode(const BigInt &n)
Definition: bigint.h:751

◆ encode() [4/4]

void Botan::BigInt::encode ( uint8_t  buf[],
const BigInt n,
Base  base 
)
static

Encode the integer value from a BigInt to a byte array

Parameters
bufdestination byte array for the encoded integer value with given base
nthe BigInt to use as integer source
basenumber-base of resulting byte array representation

Definition at line 54 of file big_code.cpp.

References Binary, binary_encode(), Botan::cast_uint8_ptr_to_char(), Botan::ct_divide_u8(), Decimal, Botan::Charset::digit2char(), encoded_size(), Botan::hex_encode(), Hexadecimal, is_zero(), Positive, and set_sign().

55  {
56  if(base == Binary)
57  {
58  n.binary_encode(output);
59  }
60  else if(base == Hexadecimal)
61  {
62  secure_vector<uint8_t> binary(n.encoded_size(Binary));
63  n.binary_encode(binary.data());
64 
66  binary.data(), binary.size());
67  }
68  else if(base == Decimal)
69  {
70  BigInt copy = n;
71  uint8_t remainder;
72  copy.set_sign(Positive);
73  const size_t output_size = n.encoded_size(Decimal);
74  for(size_t j = 0; j != output_size; ++j)
75  {
76  ct_divide_u8(copy, 10, copy, remainder);
77  output[output_size - 1 - j] = Charset::digit2char(remainder);
78  if(copy.is_zero())
79  break;
80  }
81  }
82  else
83  throw Invalid_Argument("Unknown BigInt encoding method");
84  }
void hex_encode(char output[], const uint8_t input[], size_t input_length, bool uppercase)
Definition: hex.cpp:14
void ct_divide_u8(const BigInt &x, uint8_t y, BigInt &q_out, uint8_t &r_out)
Definition: divide.cpp:82
const char * cast_uint8_ptr_to_char(const uint8_t *b)
Definition: mem_ops.h:165
char digit2char(uint8_t b)
Definition: charset.cpp:253
BigInt()=default

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

References bytes().

Referenced by Botan::PK_Verifier::check_signature(), Botan::EC_Group::DER_encode(), Botan::PointGFp::encode(), encode_fixed_length_int_pair(), Botan::RFC6979_Nonce_Generator::nonce_for(), Botan::EC_PrivateKey::private_key_bits(), Botan::DH_PublicKey::public_value(), 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().

124  {
125  secure_vector<uint8_t> output(bytes);
126  BigInt::encode_1363(output.data(), output.size(), n);
127  return output;
128  }
size_t bytes() const
Definition: bigint.cpp:266
static secure_vector< uint8_t > encode_1363(const BigInt &n, size_t bytes)
Definition: big_code.cpp:123

◆ encode_1363() [2/2]

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

Definition at line 131 of file big_code.cpp.

References Binary, bytes(), and encode().

132  {
133  const size_t n_bytes = n.bytes();
134  if(n_bytes > bytes)
135  throw Encoding_Error("encode_1363: n is too large to encode properly");
136 
137  const size_t leading_0s = bytes - n_bytes;
138  encode(&output[leading_0s], n, Binary);
139  }
static std::vector< uint8_t > encode(const BigInt &n)
Definition: bigint.h:751
size_t bytes() const
Definition: bigint.cpp:266

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

References bytes(), and encode_1363().

145  {
146  secure_vector<uint8_t> output(2 * bytes);
147  BigInt::encode_1363(output.data(), bytes, n1);
148  BigInt::encode_1363(output.data() + bytes, bytes, n2);
149  return output;
150  }
size_t bytes() const
Definition: bigint.cpp:266
static secure_vector< uint8_t > encode_1363(const BigInt &n, size_t bytes)
Definition: big_code.cpp:123

◆ encode_locked() [1/2]

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

References binary_encode(), and bytes().

Referenced by encode_locked().

764  {
765  secure_vector<uint8_t> output(n.bytes());
766  n.binary_encode(output.data());
767  return output;
768  }

◆ encode_locked() [2/2]

secure_vector< uint8_t > Botan::BigInt::encode_locked ( const BigInt n,
Base  base 
)
static

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

Parameters
nthe BigInt to use as integer source
basenumber-base of resulting byte array representation
Returns
secure_vector of bytes containing the integer with given base

Definition at line 106 of file big_code.cpp.

References Binary, encode(), encode_locked(), and encoded_size().

107  {
108  if(base == Binary)
109  return BigInt::encode_locked(n);
110 
111  secure_vector<uint8_t> output(n.encoded_size(base));
112  encode(output.data(), n, base);
113  for(size_t j = 0; j != output.size(); ++j)
114  if(output[j] == 0)
115  output[j] = '0';
116 
117  return output;
118  }
static std::vector< uint8_t > encode(const BigInt &n)
Definition: bigint.h:751
static secure_vector< uint8_t > encode_locked(const BigInt &n)
Definition: bigint.h:763

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

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

171  {
172  const size_t words = sig_words();
173 
174  if(words > size)
175  throw Encoding_Error("BigInt::encode_words value too large to encode");
176 
177  clear_mem(out, size);
178  copy_mem(out, data(), words);
179  }
void clear_mem(T *ptr, size_t n)
Definition: mem_ops.h:111
const word * data() const
Definition: bigint.h:623
size_t size() const
Definition: bigint.h:583
void copy_mem(T *out, const T *in, size_t n)
Definition: mem_ops.h:122
size_t sig_words() const
Definition: bigint.h:589

◆ encoded_size()

size_t Botan::BigInt::encoded_size ( Base  base = Binary) const
Parameters
basethe base to measure the size for
Returns
size of this integer in base base

Definition at line 297 of file bigint.cpp.

References Binary, bits(), bytes(), Decimal, and Hexadecimal.

Referenced by encode(), and encode_locked().

298  {
299  static const double LOG_2_BASE_10 = 0.30102999566;
300 
301  if(base == Binary)
302  return bytes();
303  else if(base == Hexadecimal)
304  return 2*bytes();
305  else if(base == Decimal)
306  return static_cast<size_t>((bits() * LOG_2_BASE_10) + 1);
307  else
308  throw Invalid_Argument("Unknown base for BigInt encoding");
309  }
size_t bits() const
Definition: bigint.cpp:281
size_t bytes() const
Definition: bigint.cpp:266

◆ flip_sign()

void Botan::BigInt::flip_sign ( )
inline

Flip the sign of this BigInt

Definition at line 557 of file bigint.h.

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

558  {
560  }
Sign reverse_sign() const
Definition: bigint.h:547
void set_sign(Sign sign)
Definition: bigint.h:566

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

Referenced by Botan::ct_divide(), Botan::ct_divide_u8(), Botan::ct_modulo(), Botan::PointGFp::encode(), Botan::is_lucas_probable_prime(), and Botan::operator*().

465  {
466  return ((word_at(n / BOTAN_MP_WORD_BITS) >> (n % BOTAN_MP_WORD_BITS)) & 1);
467  }
word word_at(size_t n) const
Definition: bigint.h:511

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

References byte_at(), and Botan::make_uint64().

Referenced by Botan::Fixed_Window_Exponentiator::execute(), Botan::monty_multi_exp(), Botan::PointGFp_Base_Point_Precompute::mul(), Botan::PointGFp_Var_Point_Precompute::mul(), and Botan::PointGFp_Multi_Point_Precompute::multi_exp().

208  {
209  if(length == 0 || length > 32)
210  throw Invalid_Argument("BigInt::get_substring invalid substring length");
211 
212  const size_t byte_offset = offset / 8;
213  const size_t shift = (offset % 8);
214  const uint32_t mask = 0xFFFFFFFF >> (32 - length);
215 
216  const uint8_t b0 = byte_at(byte_offset);
217  const uint8_t b1 = byte_at(byte_offset + 1);
218  const uint8_t b2 = byte_at(byte_offset + 2);
219  const uint8_t b3 = byte_at(byte_offset + 3);
220  const uint8_t b4 = byte_at(byte_offset + 4);
221  const uint64_t piece = make_uint64(0, 0, 0, b4, b3, b2, b1, b0);
222 
223  return static_cast<uint32_t>((piece >> shift) & mask);
224  }
constexpr uint64_t make_uint64(uint8_t i0, uint8_t i1, uint8_t i2, uint8_t i3, uint8_t i4, uint8_t i5, uint8_t i6, uint8_t i7)
Definition: loadstor.h:85
uint8_t byte_at(size_t n) const
Definition: bigint.h:500

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

Referenced by Botan::PointGFp::add_affine(), Botan::ct_inverse_mod_odd_modulus(), and Botan::Montgomery_Int::fix_size().

628 { return m_data.mutable_vector(); }

◆ get_word_vector() [2/2]

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

Don't use this function in application code

Definition at line 633 of file bigint.h.

633 { return m_data.const_vector(); }

◆ grow_to()

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

Increase internal register buffer to at least n words

Parameters
nnew size of register

Definition at line 639 of file bigint.h.

Referenced by add(), ct_cond_assign(), ct_cond_swap(), Botan::ct_inverse_mod_odd_modulus(), ct_reduce_below(), Botan::divide(), mod_add(), mod_sub(), mul(), Botan::Montgomery_Params::mul_by(), operator*=(), Botan::Montgomery_Params::redc(), Botan::redc_p521(), reduce_below(), and Botan::Montgomery_Params::square_this().

639 { m_data.grow_to(n); }

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

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

Referenced by Botan::operator!=().

144  {
145  if(this->sign() != other.sign())
146  return false;
147 
148  return bigint_ct_is_eq(this->data(), this->sig_words(),
149  other.data(), other.sig_words()).is_set();
150  }
Sign sign() const
Definition: bigint.h:542
const word * data() const
Definition: bigint.h:623
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:613
size_t sig_words() const
Definition: bigint.h:589

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

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

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

153  {
154  if(this->is_negative() && other.is_positive())
155  return true;
156 
157  if(this->is_positive() && other.is_negative())
158  return false;
159 
160  if(other.is_negative() && this->is_negative())
161  {
162  return !bigint_ct_is_lt(other.data(), other.sig_words(),
163  this->data(), this->sig_words(), true).is_set();
164  }
165 
166  return bigint_ct_is_lt(this->data(), this->sig_words(),
167  other.data(), other.sig_words()).is_set();
168  }
bool is_negative() const
Definition: bigint.h:530
const word * data() const
Definition: bigint.h:623
size_t sig_words() const
Definition: bigint.h:589
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:576
bool is_positive() const
Definition: bigint.h:536

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

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

414 { return (!is_zero()); }
bool is_zero() const
Definition: bigint.h:420

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

Referenced by botan_mp_is_odd(), Botan::inverse_euclid(), Botan::inverse_mod(), Botan::is_lucas_probable_prime(), Botan::normalized_montgomery_inverse(), and Botan::Power_Mod::set_modulus().

408 { return (get_bit(0) == 1); }
bool get_bit(size_t n) const
Definition: bigint.h:464

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

Referenced by botan_mp_is_positive(), cmp(), is_less_than(), Botan::low_zero_bits(), and Botan::operator%().

536 { return (sign() == Positive); }
Sign sign() const
Definition: bigint.h:542

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

Referenced by Botan::redc_p521(), and Botan::Modular_Reducer::reduce().

455  {
456  m_data.mask_bits(n);
457  }

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

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

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

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 
81  // Compute t - ws
82  borrow = bigint_sub3(&ws[mod_sw], this->data(), mod_sw, &ws[0], mod_sw);
83 
84  // Compute t + s
85  bigint_add3_nc(&ws[mod_sw*2], this->data(), mod_sw, s.data(), mod_sw);
86 
87  CT::conditional_copy_mem(borrow, &ws[0], &ws[mod_sw*2], &ws[mod_sw], mod_sw);
88  set_words(&ws[0], mod_sw);
89 
90  return (*this);
91  }
bool is_negative() const
Definition: bigint.h:530
word bigint_add3_nc(word z[], const word x[], size_t x_size, const word y[], size_t y_size)
Definition: mp_core.h:252
word bigint_sub3(word z[], const word x[], size_t x_size, const word y[], size_t y_size)
Definition: mp_core.h:344
const word * data() const
Definition: bigint.h:623
#define BOTAN_DEBUG_ASSERT(expr)
Definition: assert.h:123
void set_words(const word w[], size_t len)
Definition: bigint.h:521
Mask< T > conditional_copy_mem(T cnd, T *to, const T *from0, const T *from1, size_t elems)
Definition: ct_utils.h:339
#define BOTAN_ARG_CHECK(expr, msg)
Definition: assert.h:37
void grow_to(size_t n) const
Definition: bigint.h:639

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

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

140  {
141  BOTAN_ARG_CHECK(this->is_negative() == false, "*this must be positive");
142  BOTAN_ARG_CHECK(y < 16, "y too large");
143 
144  BOTAN_DEBUG_ASSERT(*this < mod);
145 
146  switch(y)
147  {
148  case 2:
149  *this <<= 1;
150  break;
151  case 4:
152  *this <<= 2;
153  break;
154  case 8:
155  *this <<= 3;
156  break;
157  default:
158  *this *= static_cast<word>(y);
159  break;
160  }
161 
162  this->reduce_below(mod, ws);
163  return (*this);
164  }
bool is_negative() const
Definition: bigint.h:530
#define BOTAN_DEBUG_ASSERT(expr)
Definition: assert.h:123
#define BOTAN_ARG_CHECK(expr, msg)
Definition: assert.h:37
size_t reduce_below(const BigInt &mod, secure_vector< word > &ws)
Definition: bigint.cpp:321

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

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

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

94  {
95  if(this->is_negative() || s.is_negative() || mod.is_negative())
96  throw Invalid_Argument("BigInt::mod_sub expects all arguments are positive");
97 
98  // We are assuming in this function that *this and s are no more than mod_sw words long
99  BOTAN_DEBUG_ASSERT(*this < mod);
100  BOTAN_DEBUG_ASSERT(s < mod);
101 
102  const size_t mod_sw = mod.sig_words();
103 
104  this->grow_to(mod_sw);
105  s.grow_to(mod_sw);
106 
107  if(ws.size() < mod_sw)
108  ws.resize(mod_sw);
109 
110 #if 0
111  //Faster but not const time:
112 
113  // Compute t - s
114  word borrow = bigint_sub3(ws.data(), data(), mod_sw, s.data(), mod_sw);
115 
116  if(borrow)
117  {
118  // If t < s, instead compute p - (s - t)
119  bigint_sub2_rev(mutable_data(), s.data(), mod_sw);
120  bigint_sub2_rev(mutable_data(), mod.data(), mod_sw);
121  }
122  else
123  {
124  // No borrow so we already have the result we need
125  swap_reg(ws);
126  }
127 #else
128  if(mod_sw == 4)
129  bigint_mod_sub_n<4>(mutable_data(), s.data(), mod.data(), ws.data());
130  else if(mod_sw == 6)
131  bigint_mod_sub_n<6>(mutable_data(), s.data(), mod.data(), ws.data());
132  else
133  bigint_mod_sub(mutable_data(), s.data(), mod.data(), mod_sw, ws.data());
134 #endif
135 
136  return (*this);
137  }
void bigint_sub2_rev(word x[], const word y[], size_t y_size)
Definition: mp_core.h:326
bool is_negative() const
Definition: bigint.h:530
word * mutable_data()
Definition: bigint.h:617
void swap_reg(secure_vector< word > &reg)
Definition: bigint.h:166
word bigint_sub3(word z[], const word x[], size_t x_size, const word y[], size_t y_size)
Definition: mp_core.h:344
const word * data() const
Definition: bigint.h:623
#define BOTAN_DEBUG_ASSERT(expr)
Definition: assert.h:123
void grow_to(size_t n) const
Definition: bigint.h:639
void bigint_mod_sub(word t[], const word s[], const word mod[], size_t mod_sw, word ws[])
Definition: mp_core.h:686

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

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

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

194  {
195  const size_t x_sw = sig_words();
196  const size_t y_sw = y.sig_words();
197  set_sign((sign() == y.sign()) ? Positive : Negative);
198 
199  if(x_sw == 0 || y_sw == 0)
200  {
201  clear();
203  }
204  else if(x_sw == 1 && y_sw)
205  {
206  grow_to(y_sw + 1);
207  bigint_linmul3(mutable_data(), y.data(), y_sw, word_at(0));
208  }
209  else if(y_sw == 1 && x_sw)
210  {
211  grow_to(x_sw + 1);
212  bigint_linmul2(mutable_data(), x_sw, y.word_at(0));
213  }
214  else
215  {
216  const size_t new_size = x_sw + y_sw + 1;
217  ws.resize(new_size);
218  secure_vector<word> z_reg(new_size);
219 
220  bigint_mul(z_reg.data(), z_reg.size(),
221  data(), size(), x_sw,
222  y.data(), y.size(), y_sw,
223  ws.data(), ws.size());
224 
225  this->swap_reg(z_reg);
226  }
227 
228  return (*this);
229  }
void bigint_linmul2(word x[], size_t x_size, word y)
Definition: mp_core.h:489
Sign sign() const
Definition: bigint.h:542
word * mutable_data()
Definition: bigint.h:617
void swap_reg(secure_vector< word > &reg)
Definition: bigint.h:166
word word_at(size_t n) const
Definition: bigint.h:511
const word * data() const
Definition: bigint.h:623
void bigint_linmul3(word z[], const word x[], size_t x_size, word y)
Definition: mp_core.h:504
size_t size() const
Definition: bigint.h:583
size_t sig_words() const
Definition: bigint.h:589
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:298
void clear()
Definition: bigint.h:365
void grow_to(size_t n) const
Definition: bigint.h:639
void set_sign(Sign sign)
Definition: bigint.h:566

◆ mutable_data()

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

◆ operator!()

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

! operator

Returns
true iff this is zero, otherwise false

Definition at line 280 of file bigint.h.

280 { return (!is_nonzero()); }
bool is_nonzero() const
Definition: bigint.h:414

◆ operator%=() [1/2]

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

Modulo operator

Parameters
ythe modulus to reduce this by

Definition at line 280 of file big_ops2.cpp.

281  {
282  return (*this = (*this) % mod);
283  }

◆ operator%=() [2/2]

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

Modulo operator

Parameters
ythe modulus (word) to reduce this by

Definition at line 288 of file big_ops2.cpp.

References Botan::bigint_modop(), Botan::is_power_of_2(), Negative, Positive, set_sign(), sig_words(), sign(), and word_at().

289  {
290  if(mod == 0)
291  throw BigInt::DivideByZero();
292 
293  word remainder = 0;
294 
295  if(is_power_of_2(mod))
296  {
297  remainder = (word_at(0) & (mod - 1));
298  }
299  else
300  {
301  const size_t sw = sig_words();
302  for(size_t i = sw; i > 0; --i)
303  remainder = bigint_modop(remainder, word_at(i-1), mod);
304  }
305 
306  if(remainder && sign() == BigInt::Negative)
307  remainder = mod - remainder;
308 
309  m_data.set_to_zero();
310  m_data.set_word_at(0, remainder);
312  return remainder;
313  }
Sign sign() const
Definition: bigint.h:542
word word_at(size_t n) const
Definition: bigint.h:511
constexpr bool is_power_of_2(T arg)
Definition: bit_ops.h:43
size_t sig_words() const
Definition: bigint.h:589
void set_sign(Sign sign)
Definition: bigint.h:566
word bigint_modop(word n1, word n0, word d)
Definition: mp_core.h:754

◆ operator*=() [1/2]

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

*= operator

Parameters
ythe BigInt to multiply with this

Definition at line 187 of file big_ops2.cpp.

References mul().

188  {
189  secure_vector<word> ws;
190  return this->mul(y, ws);
191  }
BigInt & mul(const BigInt &y, secure_vector< word > &ws)
Definition: big_ops2.cpp:193

◆ operator*=() [2/2]

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

*= operator

Parameters
ythe word to multiply with this

Definition at line 248 of file big_ops2.cpp.

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

249  {
250  if(y == 0)
251  {
252  clear();
254  }
255 
256  const size_t x_sw = sig_words();
257 
258  if(size() < x_sw + 1)
259  grow_to(x_sw + 1);
260  bigint_linmul2(mutable_data(), x_sw, y);
261 
262  return (*this);
263  }
void bigint_linmul2(word x[], size_t x_size, word y)
Definition: mp_core.h:489
word * mutable_data()
Definition: bigint.h:617
size_t size() const
Definition: bigint.h:583
size_t sig_words() const
Definition: bigint.h:589
void clear()
Definition: bigint.h:365
void grow_to(size_t n) const
Definition: bigint.h:639
void set_sign(Sign sign)
Definition: bigint.h:566

◆ operator++() [1/2]

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

Increment operator

Definition at line 253 of file bigint.h.

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

◆ operator++() [2/2]

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

Postfix increment operator

Definition at line 263 of file bigint.h.

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

◆ operator+=() [1/2]

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

+= operator

Parameters
ythe BigInt to add to this

Definition at line 176 of file bigint.h.

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

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

◆ operator+=() [2/2]

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

+= operator

Parameters
ythe word to add to this

Definition at line 185 of file bigint.h.

186  {
187  return add(&y, 1, Positive);
188  }
BigInt & add(const word y[], size_t y_words, Sign sign)
Definition: big_ops2.cpp:15

◆ operator-()

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

Unary negation operator

Returns
negative this

Definition at line 314 of file bigint.cpp.

References flip_sign().

315  {
316  BigInt x = (*this);
317  x.flip_sign();
318  return x;
319  }
BigInt()=default

◆ operator--() [1/2]

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

Decrement operator

Definition at line 258 of file bigint.h.

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

◆ operator--() [2/2]

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

Postfix decrement operator

Definition at line 268 of file bigint.h.

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

◆ operator-=() [1/2]

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

-= operator

Parameters
ythe BigInt to subtract from this

Definition at line 194 of file bigint.h.

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

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

◆ operator-=() [2/2]

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

-= operator

Parameters
ythe word to subtract from this

Definition at line 203 of file bigint.h.

204  {
205  return sub(&y, 1, Positive);
206  }
BigInt & sub(const word y[], size_t y_words, Sign sign)
Definition: bigint.h:286

◆ operator/=()

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

/= operator

Parameters
ythe BigInt to divide this by

Definition at line 268 of file big_ops2.cpp.

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

269  {
270  if(y.sig_words() == 1 && is_power_of_2(y.word_at(0)))
271  (*this) >>= (y.bits() - 1);
272  else
273  (*this) = (*this) / y;
274  return (*this);
275  }
constexpr bool is_power_of_2(T arg)
Definition: bit_ops.h:43

◆ operator<<=()

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

Left shift operator

Parameters
shiftthe number of bits to shift this left by

Definition at line 318 of file big_ops2.cpp.

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

319  {
320  const size_t shift_words = shift / BOTAN_MP_WORD_BITS;
321  const size_t shift_bits = shift % BOTAN_MP_WORD_BITS;
322  const size_t size = sig_words();
323 
324  const size_t bits_free = top_bits_free();
325 
326  const size_t new_size = size + shift_words + (bits_free < shift);
327 
328  m_data.grow_to(new_size);
329 
330  bigint_shl1(m_data.mutable_data(), new_size, size, shift_words, shift_bits);
331 
332  return (*this);
333  }
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:411
size_t size() const
Definition: bigint.h:583
size_t sig_words() const
Definition: bigint.h:589
size_t top_bits_free() const
Definition: bigint.cpp:271

◆ operator=() [1/2]

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

Move assignment

Definition at line 143 of file bigint.h.

144  {
145  if(this != &other)
146  this->swap(other);
147 
148  return (*this);
149  }
void swap(BigInt &other)
Definition: bigint.h:160

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

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

339  {
340  const size_t shift_words = shift / BOTAN_MP_WORD_BITS;
341  const size_t shift_bits = shift % BOTAN_MP_WORD_BITS;
342 
343  bigint_shr1(m_data.mutable_data(), m_data.size(), shift_words, shift_bits);
344 
345  if(is_negative() && is_zero())
347 
348  return (*this);
349  }
void bigint_shr1(word x[], size_t x_size, size_t word_shift, size_t bit_shift)
Definition: mp_core.h:429
bool is_negative() const
Definition: bigint.h:530
bool is_zero() const
Definition: bigint.h:420
void set_sign(Sign sign)
Definition: bigint.h:566

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

References set_bit().

Referenced by Botan::is_perfect_square(), Botan::Montgomery_Params::Montgomery_Params(), and Botan::ressol().

740  {
741  BigInt b;
742  b.set_bit(n);
743  return b;
744  }
BigInt()=default

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

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

Referenced by botan_mp_rand_range(), Botan::DSA_PrivateKey::DSA_PrivateKey(), Botan::is_miller_rabin_probable_prime(), Botan::EC_Group::random_scalar(), and Botan::PointGFp::randomize_repr().

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  }
size_t bits() const
Definition: bigint.cpp:281
BigInt()=default

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

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

Referenced by BigInt(), Botan::DH_PrivateKey::DH_PrivateKey(), Botan::ElGamal_PrivateKey::ElGamal_PrivateKey(), and random_integer().

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  }
void clear()
Definition: bigint.h:365
void binary_decode(const uint8_t buf[], size_t length)
Definition: bigint.cpp:397
size_t round_up(size_t n, size_t align_to)
Definition: rounding.h:21
void set_sign(Sign sign)
Definition: bigint.h:566

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

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

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

322  {
323  if(p.is_negative() || this->is_negative())
324  throw Invalid_Argument("BigInt::reduce_below both values must be positive");
325 
326  const size_t p_words = p.sig_words();
327 
328  if(size() < p_words + 1)
329  grow_to(p_words + 1);
330 
331  if(ws.size() < p_words + 1)
332  ws.resize(p_words + 1);
333 
334  clear_mem(ws.data(), ws.size());
335 
336  size_t reductions = 0;
337 
338  for(;;)
339  {
340  word borrow = bigint_sub3(ws.data(), data(), p_words + 1, p.data(), p_words);
341  if(borrow)
342  break;
343 
344  ++reductions;
345  swap_reg(ws);
346  }
347 
348  return reductions;
349  }
bool is_negative() const
Definition: bigint.h:530
void clear_mem(T *ptr, size_t n)
Definition: mem_ops.h:111
void swap_reg(secure_vector< word > &reg)
Definition: bigint.h:166
word bigint_sub3(word z[], const word x[], size_t x_size, const word y[], size_t y_size)
Definition: mp_core.h:344
const word * data() const
Definition: bigint.h:623
size_t size() const
Definition: bigint.h:583
void grow_to(size_t n) const
Definition: bigint.h:639

◆ resize()

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

Definition at line 650 of file bigint.h.

Referenced by Botan::PointGFp::force_all_affine().

650 { m_data.resize(s); }

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

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

167  {
168  if(this->sign() != BigInt::Positive)
169  throw Invalid_State("BigInt::sub_rev requires this is positive");
170 
171  const size_t x_sw = this->sig_words();
172 
173  ws.resize(std::max(x_sw, y_sw));
174  clear_mem(ws.data(), ws.size());
175 
176  const int32_t relative_size = bigint_sub_abs(ws.data(), data(), x_sw, y, y_sw);
177 
178  this->cond_flip_sign(relative_size > 0);
179  this->swap_reg(ws);
180 
181  return (*this);
182  }
void clear_mem(T *ptr, size_t n)
Definition: mem_ops.h:111
Sign sign() const
Definition: bigint.h:542
void swap_reg(secure_vector< word > &reg)
Definition: bigint.h:166
const word * data() const
Definition: bigint.h:623
CT::Mask< word > bigint_sub_abs(word z[], const word x[], const word y[], size_t N, word ws[])
Definition: mp_core.h:379
size_t sig_words() const
Definition: bigint.h:589
void cond_flip_sign(bool predicate)
Definition: bigint.cpp:427

◆ reverse_sign()

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

Definition at line 547 of file bigint.h.

Referenced by Botan::operator-().

548  {
549  if(sign() == Positive)
550  return Negative;
551  return Positive;
552  }
Sign sign() const
Definition: bigint.h:542

◆ set_bit()

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

Set bit at specified position

Parameters
nbit position to set

Definition at line 429 of file bigint.h.

Referenced by botan_mp_set_bit(), Botan::generate_dsa_primes(), Botan::generate_rsa_prime(), Botan::Modular_Reducer::Modular_Reducer(), power_of_2(), and Botan::random_prime().

430  {
431  conditionally_set_bit(n, true);
432  }
void conditionally_set_bit(size_t n, bool set_it)
Definition: bigint.cpp:245

◆ set_sign()

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

Set sign of the integer

Parameters
signnew Sign to set

Definition at line 566 of file bigint.h.

Referenced by abs(), add(), BigInt(), cond_flip_sign(), Botan::divide(), encode(), mul(), operator%=(), Botan::operator*(), operator*=(), operator>>=(), randomize(), Botan::Modular_Reducer::reduce(), square(), and to_dec_string().

567  {
568  if(sign == Negative && is_zero())
569  sign = Positive;
570 
571  m_signedness = sign;
572  }
Sign sign() const
Definition: bigint.h:542
bool is_zero() const
Definition: bigint.h:420

◆ set_word_at()

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

Definition at line 516 of file bigint.h.

Referenced by ct_cond_assign().

517  {
518  m_data.set_word_at(i, w);
519  }

◆ set_words()

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

Definition at line 521 of file bigint.h.

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

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

◆ shrink_to_fit()

void Botan::BigInt::shrink_to_fit ( size_t  min_size = 0)
inline

Resize the vector to the minimum word size to hold the integer, or min_size words, whichever is larger

Definition at line 645 of file bigint.h.

646  {
647  m_data.shrink_to_fit(min_size);
648  }

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

Referenced by add(), add2(), cond_flip_sign(), ct_cond_assign(), is_equal(), mul(), Botan::mul_add(), Botan::operator%(), operator%=(), Botan::operator*(), Botan::operator+(), operator+=(), operator-=(), Botan::operator<<(), Botan::operator>>(), and rev_sub().

542 { return (m_signedness); }

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

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

Referenced by Botan::square().

232  {
233  const size_t sw = sig_words();
234 
235  secure_vector<word> z(2*sw);
236  ws.resize(z.size());
237 
238  bigint_sqr(z.data(), z.size(),
239  data(), size(), sw,
240  ws.data(), ws.size());
241 
242  swap_reg(z);
244 
245  return (*this);
246  }
void swap_reg(secure_vector< word > &reg)
Definition: bigint.h:166
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:357
const word * data() const
Definition: bigint.h:623
size_t size() const
Definition: bigint.h:583
size_t sig_words() const
Definition: bigint.h:589
void set_sign(Sign sign)
Definition: bigint.h:566

◆ sub()

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

Definition at line 286 of file bigint.h.

287  {
288  return add(y, y_words, sign == Positive ? Negative : Positive);
289  }
Sign sign() const
Definition: bigint.h:542
BigInt & add(const word y[], size_t y_words, Sign sign)
Definition: big_ops2.cpp:15

◆ swap()

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

Swap this value with another

Parameters
otherBigInt to swap values with

Definition at line 160 of file bigint.h.

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

161  {
162  m_data.swap(other.m_data);
163  std::swap(m_signedness, other.m_signedness);
164  }

◆ swap_reg()

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

Definition at line 166 of file bigint.h.

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

167  {
168  m_data.swap(reg);
169  // sign left unchanged
170  }

◆ to_dec_string()

std::string Botan::BigInt::to_dec_string ( ) const

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

Definition at line 15 of file big_code.cpp.

References Botan::ct_divide_u8(), Botan::Charset::digit2char(), Positive, and set_sign().

16  {
17  BigInt copy = *this;
18  copy.set_sign(Positive);
19 
20  uint8_t remainder;
21  std::vector<uint8_t> digits;
22 
23  while(copy > 0)
24  {
25  ct_divide_u8(copy, 10, copy, remainder);
26  digits.push_back(remainder);
27  }
28 
29  std::string s;
30 
31  for(auto i = digits.rbegin(); i != digits.rend(); ++i)
32  {
33  s.push_back(Charset::digit2char(*i));
34  }
35 
36  if(s.empty())
37  s += "0";
38 
39  return s;
40  }
void ct_divide_u8(const BigInt &x, uint8_t y, BigInt &q_out, uint8_t &r_out)
Definition: divide.cpp:82
char digit2char(uint8_t b)
Definition: charset.cpp:253
BigInt()=default

◆ to_hex_string()

std::string Botan::BigInt::to_hex_string ( ) const

Convert this value to a hexadecimal string.

Definition at line 42 of file big_code.cpp.

References bits(), encode(), and Botan::hex_encode().

Referenced by botan_mp_to_hex().

43  {
44  const std::vector<uint8_t> bits = BigInt::encode(*this);
45  if(bits.empty())
46  return "00";
47  else
48  return hex_encode(bits);
49  }
void hex_encode(char output[], const uint8_t input[], size_t input_length, bool uppercase)
Definition: hex.cpp:14
size_t bits() const
Definition: bigint.cpp:281
static std::vector< uint8_t > encode(const BigInt &n)
Definition: bigint.h:751

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

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

Referenced by botan_mp_to_uint32().

230  {
231  if(is_negative())
232  throw Encoding_Error("BigInt::to_u32bit: Number is negative");
233  if(bits() > 32)
234  throw Encoding_Error("BigInt::to_u32bit: Number is too big to convert");
235 
236  uint32_t out = 0;
237  for(size_t i = 0; i != 4; ++i)
238  out = (out << 8) | byte_at(3-i);
239  return out;
240  }
bool is_negative() const
Definition: bigint.h:530
size_t bits() const
Definition: bigint.cpp:281
uint8_t byte_at(size_t n) const
Definition: bigint.h:500

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

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

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

272  {
273  const size_t words = sig_words();
274 
275  const word top_word = word_at(words - 1);
276  const size_t bits_used = high_bit(top_word);
277  CT::unpoison(bits_used);
278  return BOTAN_MP_WORD_BITS - bits_used;
279  }
word word_at(size_t n) const
Definition: bigint.h:511
size_t high_bit(T n)
Definition: bit_ops.h:55
size_t sig_words() const
Definition: bigint.h:589
void unpoison(const T *p, size_t n)
Definition: ct_utils.h:59

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

Referenced by clear_bit(), conditionally_set_bit(), ct_cond_assign(), Botan::divide(), Botan::is_prime(), Botan::low_zero_bits(), Botan::Montgomery_Params::Montgomery_Params(), mul(), Botan::operator%(), operator%=(), Botan::operator*(), Botan::operator/(), operator/=(), Botan::redc_p521(), and top_bits_free().

512  {
513  return m_data.get_word_at(n);
514  }

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