Botan::BigInt Class Reference

#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
BigInt &	add (const word y[], size_t y_words, Sign sign)
	BigInt ()=default
	BigInt (uint64_t n)
	BigInt (const BigInt &other)
	BigInt (const std::string &str)
	BigInt (const uint8_t buf[], size_t length)
	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	const_time_poison () const
void	const_time_unpoison () const
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)
bool	is_even () const
bool	is_negative () const
bool	is_nonzero () const
bool	is_odd () const
bool	is_positive () const
bool	is_zero () const
void	mask_bits (size_t n)
BigInt &	mod_add (const BigInt &y, const BigInt &mod, secure_vector< word > &ws)
BigInt &	mod_sub (const BigInt &y, const BigInt &mod, secure_vector< word > &ws)
BigInt &	mul (const BigInt &y, secure_vector< word > &ws)
word *	mutable_data ()
bool	operator! () const
BigInt &	operator%= (const BigInt &y)
word	operator%= (word y)
BigInt &	operator*= (const BigInt &y)
BigInt &	operator*= (word y)
BigInt &	operator++ ()
BigInt	operator++ (int)
BigInt &	operator+= (const BigInt &y)
BigInt &	operator+= (word y)
BigInt	operator- () const
BigInt &	operator-- ()
BigInt	operator-- (int)
BigInt &	operator-= (const BigInt &y)
BigInt &	operator-= (word y)
BigInt &	operator/= (const BigInt &y)
BigInt &	operator<<= (size_t shift)
BigInt &	operator= (BigInt &&other)
BigInt &	operator= (const BigInt &)=default
BigInt &	operator>>= (size_t shift)
void	randomize (RandomNumberGenerator &rng, size_t bitsize, bool set_high_bit=true)
void	reduce_below (const BigInt &mod, secure_vector< word > &ws)
BigInt &	rev_sub (const word y[], size_t y_size, 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
BigInt &	square (secure_vector< word > &ws)
BigInt &	sub (const word y[], size_t y_words, Sign sign)
void	swap (BigInt &other)
void	swap_reg (secure_vector< word > &reg)
uint32_t	to_u32bit () const
word	word_at (size_t n) const

Static Public Member Functions
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, Base base=Binary)
static BigInt	decode (const secure_vector< uint8_t > &buf, Base base=Binary)
static BigInt	decode (const std::vector< uint8_t > &buf, Base base=Binary)
static std::vector< uint8_t >	encode (const BigInt &n, Base base=Binary)
static void	encode (uint8_t buf[], const BigInt &n, Base base=Binary)
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, Base base=Binary)
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

enum Botan::BigInt::Base

Base enumerator for encoding and decoding

Enumerator
Decimal
Hexadecimal
Binary

Definition at line 31 of file bigint.h.

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

Sign

enum Botan::BigInt::Sign

Sign symbol definitions for positive and negative numbers

Enumerator
Negative
Positive

Definition at line 36 of file bigint.h.

{ Negative = 0, Positive = 1 };

Constructor & Destructor Documentation

BigInt() [1/11]

Botan::BigInt::BigInt ( )

default

Create empty BigInt

BigInt() [2/11]

Botan::BigInt::BigInt

(

uint64_t

n

)

Create BigInt from 64 bit integer

Parameters

n	initial value of this BigInt

Definition at line 24 of file bigint.cpp.

References Botan::MP_WORD_MASK.

   {
   if(n == 0)
      return;

   const size_t limbs_needed = sizeof(uint64_t) / sizeof(word);

   m_reg.resize(limbs_needed);
   for(size_t i = 0; i != limbs_needed; ++i)
      m_reg[i] = ((n >> (i*BOTAN_MP_WORD_BITS)) & MP_WORD_MASK);
   }

BigInt() [3/11]

Botan::BigInt::BigInt

(

const BigInt &

other

)

Copy Constructor

Parameters

other

the BigInt to copy

Definition at line 48 of file bigint.cpp.

   {
   m_reg = other.m_reg;
   m_signedness = other.m_signedness;
   }

BigInt() [4/11]

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

str	the string to parse for an integer value

Definition at line 57 of file bigint.cpp.

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

   {
   Base base = Decimal;
   size_t markers = 0;
   bool negative = false;

   if(str.length() > 0 && str[0] == '-')
      {
      markers += 1;
      negative = true;
      }

   if(str.length() > markers + 2 && str[markers    ] == '0' &&
                                    str[markers + 1] == 'x')
      {
      markers += 2;
      base = Hexadecimal;
      }

   *this = decode(cast_char_ptr_to_uint8(str.data()) + markers,
                  str.length() - markers, base);

   if(negative) set_sign(Negative);
   else         set_sign(Positive);
   }

BigInt() [5/11]

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

Create a BigInt from an integer in a byte array

Parameters

buf	the byte array holding the value
length	size of buf

Definition at line 83 of file bigint.cpp.

References binary_decode().

   {
   binary_decode(input, length);
   }

BigInt() [6/11]

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

Create a BigInt from an integer in a byte array

Parameters

buf	the byte array holding the value
length	size of buf
base	is the number base of the integer in buf

Definition at line 91 of file bigint.cpp.

References decode().

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

BigInt() [7/11]

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

buf	the byte array holding the value
length	size of buf
max_bits	if the resulting integer is more than max_bits, it will be shifted so it is at most max_bits in length.

Definition at line 96 of file bigint.cpp.

References bits(), and decode().

   {
   const size_t max_bytes = std::min(length, (max_bits + 7) / 8);
   *this = decode(buf, max_bytes);

   const size_t b = this->bits();
   if(b > max_bits)
      {
      *this >>= (b - max_bits);
      }
   }

BigInt() [8/11]

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

Create a BigInt from an array of words

Parameters

words	the words
length	number of words

Definition at line 16 of file bigint.cpp.

   {
   m_reg.assign(words, words + length);
   }

BigInt() [9/11]

Botan::BigInt::BigInt	(	RandomNumberGenerator &	rng,
		size_t	bits,
		bool	set_high_bit = true
	)

Create a random BigInt of the specified size.

Parameters

rng	random number generator
bits	size in bits
set_high_bit	if true, the highest bit is always set

See also

randomize

Definition at line 111 of file bigint.cpp.

References bits(), and randomize().

   {
   randomize(rng, bits, set_high_bit);
   }

BigInt() [10/11]

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

Create BigInt of specified size, all zeros

Parameters

sign	the sign
n	size of the internal register in words

Definition at line 39 of file bigint.cpp.

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

   {
   m_reg.resize(round_up(size, 8));
   m_signedness = s;
   }

BigInt() [11/11]

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

inline

Move constructor

Definition at line 125 of file bigint.h.

        {
        this->swap(other);
        }

Member Function Documentation

abs()

BigInt Botan::BigInt::abs

(

)

const

Returns

absolute (positive) value of this

Definition at line 295 of file bigint.cpp.

References Positive, and set_sign().

Referenced by Botan::abs().

   {
   BigInt x = (*this);
   x.set_sign(Positive);
   return x;
   }

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

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

   {
   const size_t x_sw = sig_words();

   if(sign() == y_sign)
      {
      const size_t reg_size = std::max(x_sw, y_sw) + 1;

      if(m_reg.size() < reg_size)
         grow_to(reg_size);

      bigint_add2(mutable_data(), reg_size - 1, y, y_sw);
      }
   else
      {
      const int32_t relative_size = bigint_cmp(data(), x_sw, y, y_sw);

      if(relative_size < 0)
         {
         const size_t reg_size = std::max(x_sw, y_sw);
         grow_to(reg_size);
         bigint_sub2_rev(mutable_data(), y, y_sw);
         set_sign(y_sign);
         }
      else if(relative_size == 0)
         {
         zeroise(m_reg);
         set_sign(Positive);
         }
      else if(relative_size > 0)
         {
         bigint_sub2(mutable_data(), x_sw, y, y_sw);
         }
      }

   return (*this);
   }

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

buf	byte array buffer containing the integer
length	size of buf

Definition at line 326 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().

   {
   const size_t WORD_BYTES = sizeof(word);

   clear();
   m_reg.resize(round_up((length / WORD_BYTES) + 1, 8));

   for(size_t i = 0; i != length / WORD_BYTES; ++i)
      {
      const size_t top = length - WORD_BYTES*i;
      for(size_t j = WORD_BYTES; j > 0; --j)
         m_reg[i] = (m_reg[i] << 8) | buf[top - j];
      }

   for(size_t i = 0; i != length % WORD_BYTES; ++i)
      m_reg[length / WORD_BYTES] = (m_reg[length / WORD_BYTES] << 8) | buf[i];
   }

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

buf	the array to load from

Definition at line 602 of file bigint.h.

        {
        binary_decode(buf.data(), buf.size());
        }

binary_encode()

void Botan::BigInt::binary_encode

(

uint8_t

buf[]

)

const

Store BigInt-value in a given byte array

Parameters

buf	destination byte array for the integer value

Definition at line 316 of file bigint.cpp.

References byte_at(), and bytes().

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

   {
   const size_t sig_bytes = bytes();
   for(size_t i = 0; i != sig_bytes; ++i)
      output[sig_bytes-i-1] = byte_at(i);
   }

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

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

Referenced by BigInt(), botan_mp_num_bits(), bytes(), Botan::ct_inverse_mod_odd_modulus(), 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_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::operator>>(), 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(), and to_u32bit().

   {
   const size_t words = sig_words();

   if(words == 0)
      return 0;

   const size_t full_words = words - 1;
   return (full_words * BOTAN_MP_WORD_BITS + high_bit(word_at(full_words)));
   }

byte_at()

uint8_t Botan::BigInt::byte_at ( size_t  n ) const

inline

Parameters

n	the offset to get a byte from

Returns

byte at offset n

Definition at line 429 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().

        {
        return get_byte(sizeof(word) - (n % sizeof(word)) - 1,
                        word_at(n / sizeof(word)));
        }

bytes()

size_t Botan::BigInt::bytes

(

)

const

Give byte length of the integer

Returns

byte length of the represented integer value

Definition at line 220 of file bigint.cpp.

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

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

   {
   return round_up(bits(), 8) / 8;
   }

clear()

void Botan::BigInt::clear ( )

inline

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

Definition at line 314 of file bigint.h.

References Botan::zeroise().

Referenced by binary_decode(), botan_mp_clear(), mul(), operator%=(), operator*=(), randomize(), and sub().

{ zeroise(m_reg); }

clear_bit()

void Botan::BigInt::clear_bit

(

size_t

n

)

Clear bit at specified position

Parameters

n	bit position to clear

Definition at line 212 of file bigint.cpp.

References size().

Referenced by botan_mp_clear_bit().

   {
   const size_t which = n / BOTAN_MP_WORD_BITS;
   const word mask = static_cast<word>(1) << (n % BOTAN_MP_WORD_BITS);
   if(which < size())
      m_reg[which] &= ~mask;
   }

cmp()

int32_t Botan::BigInt::cmp	(	const BigInt &	n,
		bool	check_signs = true
	)		const

Compare this to another BigInt

Parameters

n	the BigInt value to compare with
check_signs	include 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 131 of file bigint.cpp.

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

Referenced by botan_mp_cmp(), Botan::divide(), Botan::operator!=(), Botan::operator<(), Botan::operator<=(), Botan::operator>(), Botan::operator>=(), and Botan::Modular_Reducer::reduce().

   {
   if(check_signs)
      {
      if(other.is_positive() && this->is_negative())
         return -1;

      if(other.is_negative() && this->is_positive())
         return 1;

      if(other.is_negative() && this->is_negative())
         return (-bigint_cmp(this->data(), this->sig_words(),
                             other.data(), other.sig_words()));
      }

   return bigint_cmp(this->data(), this->sig_words(),
                     other.data(), other.sig_words());
   }

cmp_word()

int32_t Botan::BigInt::cmp_word

(

word

n

)

const

Compare this to an integer

Parameters

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

   {
   if(is_negative())
      return -1; // other is positive ...

   const size_t sw = this->sig_words();
   if(sw > 1)
      return 1; // must be larger since other is just one word ...

   return bigint_cmp(this->data(), sw, &other, 1);
   }

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

References BOTAN_ASSERT, Botan::clear_mem(), Botan::CT::is_equal(), Botan::CT::poison(), size(), Botan::CT::unpoison(), and word_at().

   {
   const size_t words = output.size();

   clear_mem(output.data(), output.size());

   CT::poison(&idx, sizeof(idx));

   for(size_t i = 0; i != vec.size(); ++i)
      {
      BOTAN_ASSERT(vec[i].size() >= words,
                   "Word size as expected in const_time_lookup");

      const word mask = CT::is_equal(i, idx);

      for(size_t w = 0; w != words; ++w)
         output[w] |= CT::select<word>(mask, vec[i].word_at(w), 0);
      }

   CT::unpoison(idx);
   CT::unpoison(output.data(), output.size());
   }

const_time_poison()

void Botan::BigInt::const_time_poison ( ) const

inline

Definition at line 623 of file bigint.h.

{}

const_time_unpoison()

void Botan::BigInt::const_time_unpoison ( ) const

inline

Definition at line 624 of file bigint.h.

{}

data()

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

inline

Return a const pointer to the register

Returns

a pointer to the start of the internal register

Definition at line 551 of file bigint.h.

Referenced by Botan::PointGFp::add(), add(), Botan::PointGFp::add_affine(), cmp(), cmp_word(), Botan::ct_inverse_mod_odd_modulus(), encode_words(), mod_sub(), Botan::Montgomery_Params::mul(), mul(), Botan::mul_add(), Botan::Montgomery_Params::mul_by(), Botan::operator*(), Botan::operator+(), operator+=(), Botan::operator-(), operator-=(), Botan::operator<<(), Botan::operator>>(), Botan::Montgomery_Params::redc(), Botan::redc_p521(), Botan::Modular_Reducer::reduce(), reduce_below(), rev_sub(), Botan::Montgomery_Params::sqr(), square(), Botan::Montgomery_Params::square_this(), and sub().

{ return m_reg.data(); }

decode() [1/3]

BigInt Botan::BigInt::decode ( const uint8_t  buf[], size_t  length, Base  base = Binary  )

static

Create a BigInt from an integer in a byte array

Parameters

buf	the binary value to load
length	size of buf
base	number-base of the integer in buf

Returns

BigInt representing the integer in the byte array

Definition at line 114 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().

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

   {
   BigInt r;
   if(base == Binary)
      r.binary_decode(buf, length);
   else if(base == Hexadecimal)
      {
      secure_vector<uint8_t> binary;

      if(length % 2)
         {
         // Handle lack of leading 0
         const char buf0_with_leading_0[2] =
            { '0', static_cast<char>(buf[0]) };

         binary = hex_decode_locked(buf0_with_leading_0, 2);

         binary += hex_decode_locked(cast_uint8_ptr_to_char(&buf[1]),
                                     length - 1,
                                     false);
         }
      else
         binary = hex_decode_locked(cast_uint8_ptr_to_char(buf),
                                    length, false);

      r.binary_decode(binary.data(), binary.size());
      }
   else if(base == Decimal)
      {
      for(size_t i = 0; i != length; ++i)
         {
         if(Charset::is_space(buf[i]))
            continue;

         if(!Charset::is_digit(buf[i]))
            throw Invalid_Argument("BigInt::decode: "
                                   "Invalid character in decimal input");

         const uint8_t x = Charset::char2digit(buf[i]);

         if(x >= 10)
            throw Invalid_Argument("BigInt: Invalid decimal string");

         r *= 10;
         r += x;
         }
      }
   else
      throw Invalid_Argument("Unknown BigInt decoding method");
   return r;
   }

decode() [2/3]

static BigInt Botan::BigInt::decode ( const secure_vector< uint8_t > &  buf, Base  base = Binary  )

inlinestatic

Create a BigInt from an integer in a byte array

Parameters

buf	the binary value to load
base	number-base of the integer in buf

Returns

BigInt representing the integer in the byte array

Definition at line 691 of file bigint.h.

References decode().

        {
        return BigInt::decode(buf.data(), buf.size(), base);
        }

decode() [3/3]

static BigInt Botan::BigInt::decode ( const std::vector< uint8_t > &  buf, Base  base = Binary  )

inlinestatic

Create a BigInt from an integer in a byte array

Parameters

buf	the binary value to load
base	number-base of the integer in buf

Returns

BigInt representing the integer in the byte array

Definition at line 703 of file bigint.h.

References decode().

        {
        return BigInt::decode(buf.data(), buf.size(), base);
        }

encode() [1/2]

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

static

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

Parameters

n	the BigInt to use as integer source
base	number-base of resulting byte array representation

Returns

secure_vector of bytes containing the integer with given base

Definition at line 54 of file big_code.cpp.

References Binary, and encoded_size().

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

   {
   std::vector<uint8_t> output(n.encoded_size(base));
   encode(output.data(), n, base);
   if(base != Binary)
      for(size_t j = 0; j != output.size(); ++j)
         if(output[j] == 0)
            output[j] = '0';
   return output;
   }

encode() [2/2]

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

static

Encode the integer value from a BigInt to a byte array

Parameters

buf	destination byte array for the encoded integer value with given base
n	the BigInt to use as integer source
base	number-base of resulting byte array representation

Definition at line 18 of file big_code.cpp.

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

   {
   if(base == Binary)
      {
      n.binary_encode(output);
      }
   else if(base == Hexadecimal)
      {
      secure_vector<uint8_t> binary(n.encoded_size(Binary));
      n.binary_encode(binary.data());

      hex_encode(cast_uint8_ptr_to_char(output),
                 binary.data(), binary.size());
      }
   else if(base == Decimal)
      {
      BigInt copy = n;
      BigInt remainder;
      copy.set_sign(Positive);
      const size_t output_size = n.encoded_size(Decimal);
      for(size_t j = 0; j != output_size; ++j)
         {
         divide(copy, 10, copy, remainder);
         output[output_size - 1 - j] =
            Charset::digit2char(static_cast<uint8_t>(remainder.word_at(0)));
         if(copy.is_zero())
            break;
         }
      }
   else
      throw Invalid_Argument("Unknown BigInt encoding method");
   }

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

n	the BigInt to encode
bytes	the length of the resulting secure_vector<uint8_t>

Returns

a secure_vector<uint8_t> containing the encoded BigInt

Definition at line 82 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().

   {
   secure_vector<uint8_t> output(bytes);
   BigInt::encode_1363(output.data(), output.size(), n);
   return output;
   }

encode_1363() [2/2]

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

static

Definition at line 90 of file big_code.cpp.

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

   {
   const size_t n_bytes = n.bytes();
   if(n_bytes > bytes)
      throw Encoding_Error("encode_1363: n is too large to encode properly");

   const size_t leading_0s = bytes - n_bytes;
   encode(&output[leading_0s], n, Binary);
   }

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

n1	the first BigInt to encode
n2	the second BigInt to encode
bytes	the 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 103 of file big_code.cpp.

References bytes(), and encode_1363().

   {
   secure_vector<uint8_t> output(2 * bytes);
   BigInt::encode_1363(output.data(), bytes, n1);
   BigInt::encode_1363(output.data() + bytes, bytes, n2);
   return output;
   }

encode_locked()

secure_vector< uint8_t > Botan::BigInt::encode_locked ( const BigInt &  n, Base  base = Binary  )

static

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

Parameters

n	the BigInt to use as integer source
base	number-base of resulting byte array representation

Returns

secure_vector of bytes containing the integer with given base

Definition at line 68 of file big_code.cpp.

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

   {
   secure_vector<uint8_t> output(n.encoded_size(base));
   encode(output.data(), n, base);
   if(base != Binary)
      for(size_t j = 0; j != output.size(); ++j)
         if(output[j] == 0)
            output[j] = '0';
   return output;
   }

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

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

   {
   const size_t words = sig_words();

   if(words > size)
      throw Encoding_Error("BigInt::encode_words value too large to encode");

   clear_mem(out, size);
   copy_mem(out, data(), words);
   }

encoded_size()

size_t Botan::BigInt::encoded_size

(

Base

base = Binary

)

const

Parameters

base	the base to measure the size for

Returns

size of this integer in base base

Definition at line 242 of file bigint.cpp.

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

Referenced by encode(), and encode_locked().

   {
   static const double LOG_2_BASE_10 = 0.30102999566;

   if(base == Binary)
      return bytes();
   else if(base == Hexadecimal)
      return 2*bytes();
   else if(base == Decimal)
      return static_cast<size_t>((bits() * LOG_2_BASE_10) + 1);
   else
      throw Invalid_Argument("Unknown base for BigInt encoding");
   }

flip_sign()

void Botan::BigInt::flip_sign ( )

inline

Flip the sign of this BigInt

Definition at line 487 of file bigint.h.

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

        {
        set_sign(reverse_sign());
        }

get_bit()

bool Botan::BigInt::get_bit ( size_t  n ) const

inline

Return bit value at specified position

Parameters

n	the bit offset to test

Returns

true, if the bit at position n is set, false otherwise

Definition at line 404 of file bigint.h.

Referenced by Botan::PointGFp::encode(), and Botan::operator*().

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

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

offset	the offset to start extracting
length	amount of bits to extract (starting at offset)

Returns

the integer extracted from the register starting at offset with specified length

Definition at line 164 of file bigint.cpp.

References byte_at(), and Botan::ASN1::to_string().

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

   {
   if(length > 32)
      throw Invalid_Argument("BigInt::get_substring: Substring size " + std::to_string(length) + " too big");

   uint64_t piece = 0;
   for(size_t i = 0; i != 8; ++i)
      {
      const uint8_t part = byte_at((offset / 8) + (7-i));
      piece = (piece << 8) | part;
      }

   const uint64_t mask = (static_cast<uint64_t>(1) << length) - 1;
   const size_t shift = (offset % 8);

   return static_cast<uint32_t>((piece >> shift) & mask);
   }

get_word_vector() [1/2]

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

inline

Definition at line 553 of file bigint.h.

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

{ return m_reg; }

get_word_vector() [2/2]

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

inline

Definition at line 554 of file bigint.h.

{ return m_reg; }

grow_to()

void Botan::BigInt::grow_to

(

size_t

n

)

Increase internal register buffer to at least n words

Parameters

n	new size of register

Definition at line 302 of file bigint.cpp.

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

Referenced by add(), Botan::ct_inverse_mod_odd_modulus(), Botan::divide(), mod_sub(), mul(), Botan::Montgomery_Params::mul_by(), operator%=(), operator*=(), operator<<=(), Botan::Montgomery_Params::redc(), reduce_below(), set_bit(), Botan::Montgomery_Params::square_this(), and sub().

   {
   if(n > size())
      {
      if(n <= m_reg.capacity())
         m_reg.resize(m_reg.capacity());
      else
         m_reg.resize(round_up(n, 8));
      }
   }

is_even()

bool Botan::BigInt::is_even ( ) const

inline

Test if the integer has an even value

Returns

true if the integer is even, false otherwise

Definition at line 337 of file bigint.h.

Referenced by Botan::almost_montgomery_inverse(), botan_mp_is_even(), Botan::RSA_PublicKey::check_key(), Botan::RSA_PrivateKey::check_key(), Botan::ct_inverse_mod_odd_modulus(), Botan::generate_rsa_prime(), Botan::inverse_euclid(), Botan::inverse_mod(), Botan::is_prime(), Botan::jacobi(), Botan::Montgomery_Params::Montgomery_Params(), Botan::power_mod(), and Botan::ressol().

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

is_negative()

bool Botan::BigInt::is_negative ( ) const

inline

Tests if the sign of the integer is negative

Returns

true, iff the integer has a negative sign

Definition at line 460 of file bigint.h.

Referenced by botan_mp_is_negative(), cmp(), cmp_word(), Botan::ct_inverse_mod_odd_modulus(), Botan::BER_Decoder::decode(), Botan::divide(), Botan::inverse_euclid(), Botan::inverse_mod(), Botan::jacobi(), mod_add(), mod_sub(), Botan::Montgomery_Params::Montgomery_Params(), Botan::monty_multi_exp(), Botan::PointGFp_Base_Point_Precompute::mul(), Botan::PointGFp_Var_Point_Precompute::mul(), Botan::mul_add(), Botan::mul_sub(), Botan::PointGFp_Multi_Point_Precompute::multi_exp(), Botan::operator%(), Botan::operator*(), Botan::Montgomery_Int::operator-(), Botan::power_mod(), random_integer(), Botan::random_prime(), Botan::Modular_Reducer::reduce(), reduce_below(), Botan::Power_Mod::set_base(), Botan::Power_Mod::set_exponent(), Botan::sub_mul(), and to_u32bit().

{ return (sign() == Negative); }

is_nonzero()

bool Botan::BigInt::is_nonzero ( ) const

inline

Test if the integer is not zero

Returns

true if the integer is non-zero, false otherwise

Definition at line 349 of file bigint.h.

References Botan::CT::is_zero().

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

{ return (!is_zero()); }

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

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

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

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

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

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

is_zero()

bool Botan::BigInt::is_zero ( ) const

inline

Test if the integer is zero

Returns

true if the integer is zero, false otherwise

Definition at line 355 of file bigint.h.

Referenced by Botan::PointGFp::add(), Botan::PointGFp::add_affine(), botan_mp_is_zero(), Botan::ct_inverse_mod_odd_modulus(), Botan::DH_PrivateKey::DH_PrivateKey(), Botan::divide(), Botan::ElGamal_PrivateKey::ElGamal_PrivateKey(), encode(), Botan::gcd(), Botan::inverse_euclid(), Botan::inverse_mod(), Botan::Montgomery_Int::is_zero(), Botan::jacobi(), Botan::mul_sub(), Botan::PointGFp::mult2(), Botan::PointGFp::mult2i(), Botan::operator%(), operator>>=(), Botan::DL_Group::PEM_for_named_group(), Botan::power_mod(), Botan::random_prime(), Botan::Power_Mod::set_base(), and Botan::DL_Group::verify_public_element().

        {
        const size_t sw = sig_words();

        for(size_t i = 0; i != sw; ++i)
           if(m_reg[i])
              return false;
        return true;
        }

mask_bits()

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

inline

Clear all but the lowest n bits

Parameters

n	amount of bits to keep

Definition at line 381 of file bigint.h.

References Botan::clear_mem().

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

        {
        if(n == 0) { clear(); return; }

        const size_t top_word = n / BOTAN_MP_WORD_BITS;
        const word mask = (static_cast<word>(1) << (n % BOTAN_MP_WORD_BITS)) - 1;

        if(top_word < size())
           {
           const size_t len = size() - (top_word + 1);
           if (len > 0)
              {
              clear_mem(&m_reg[top_word+1], len);
              }
           m_reg[top_word] &= mask;
           }
        }

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

y	the BigInt to add - assumed y >= 0 and y < mod
mod	the positive modulus
ws	a temp workspace

Definition at line 112 of file big_ops2.cpp.

References is_negative(), and reduce_below().

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

   {
   if(this->is_negative() || s.is_negative() || mod.is_negative())
      throw Invalid_Argument("BigInt::mod_add expects all arguments are positive");

   // TODO add optimized version of this
   *this += s;
   this->reduce_below(mod, ws);

   return (*this);
   }

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

y	the BigInt to subtract - assumed y >= 0 and y < mod
mod	the positive modulus
ws	a temp workspace

Definition at line 124 of file big_ops2.cpp.

References Botan::bigint_add2_nc(), Botan::bigint_cmp(), Botan::bigint_sub2(), Botan::bigint_sub3(), BOTAN_ASSERT_NOMSG, BOTAN_DEBUG_ASSERT, Botan::carry(), data(), grow_to(), is_negative(), mutable_data(), and sig_words().

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

   {
   if(this->is_negative() || s.is_negative() || mod.is_negative())
      throw Invalid_Argument("BigInt::mod_sub expects all arguments are positive");

   const size_t t_sw = sig_words();
   const size_t s_sw = s.sig_words();
   const size_t mod_sw = mod.sig_words();

   if(t_sw > mod_sw || s_sw > mod_sw)
      throw Invalid_Argument("BigInt::mod_sub args larger than modulus");

   BOTAN_DEBUG_ASSERT(*this < mod);
   BOTAN_DEBUG_ASSERT(s < mod);

   int32_t relative_size = bigint_cmp(data(), t_sw, s.data(), s_sw);

   if(relative_size >= 0)
      {
      // this >= s in which case just subtract
      bigint_sub2(mutable_data(), t_sw, s.data(), s_sw);
      }
   else
      {
      // Otherwise we must sub s and then add p (or add (p - s) as here)

      if(ws.size() < mod_sw)
         ws.resize(mod_sw);

      word borrow = bigint_sub3(ws.data(), mod.data(), mod_sw, s.data(), s_sw);
      BOTAN_ASSERT_NOMSG(borrow == 0);

      if(m_reg.size() < mod_sw)
         grow_to(mod_sw);

      word carry = bigint_add2_nc(mutable_data(), m_reg.size(), ws.data(), mod_sw);
      BOTAN_ASSERT_NOMSG(carry == 0);
      }

   return (*this);
   }

mul()

BigInt & Botan::BigInt::mul	(	const BigInt &	y,
		secure_vector< word > &	ws
	)

Multiply this with y

Parameters

y	the BigInt to multiply with this
ws	a temp workspace

Definition at line 210 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(), and word_at().

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

   {
   const size_t x_sw = sig_words();
   const size_t y_sw = y.sig_words();
   set_sign((sign() == y.sign()) ? Positive : Negative);

   if(x_sw == 0 || y_sw == 0)
      {
      clear();
      set_sign(Positive);
      }
   else if(x_sw == 1 && y_sw)
      {
      grow_to(y_sw + 1);
      bigint_linmul3(mutable_data(), y.data(), y_sw, word_at(0));
      }
   else if(y_sw == 1 && x_sw)
      {
      grow_to(x_sw + 1);
      bigint_linmul2(mutable_data(), x_sw, y.word_at(0));
      }
   else
      {
      const size_t new_size = x_sw + y_sw + 1;
      ws.resize(new_size);
      secure_vector<word> z_reg(new_size);

      bigint_mul(z_reg.data(), z_reg.size(),
                 data(), size(), x_sw,
                 y.data(), y.size(), y_sw,
                 ws.data(), ws.size());

      z_reg.swap(m_reg);
      }

   return (*this);
   }

mutable_data()

word* Botan::BigInt::mutable_data ( )

inline

Return a mutable pointer to the register

Returns

a pointer to the start of the internal register

Definition at line 545 of file bigint.h.

Referenced by add(), Botan::divide(), mod_sub(), Botan::Montgomery_Params::mul(), mul(), Botan::mul_add(), Botan::Montgomery_Params::mul_by(), operator*=(), Botan::operator<<(), operator<<=(), operator>>=(), Botan::Montgomery_Params::redc(), Botan::redc_p521(), Botan::Montgomery_Params::sqr(), Botan::Montgomery_Params::square_this(), and sub().

{ return m_reg.data(); }

operator!()

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

inline

! operator

Returns

true iff this is zero, otherwise false

Definition at line 257 of file bigint.h.

{ return (!is_nonzero()); }

operator%=() [1/2]

BigInt & Botan::BigInt::operator%=

(

const BigInt &

y

)

Modulo operator

Parameters

y	the modulus to reduce this by

Definition at line 297 of file big_ops2.cpp.

   {
   return (*this = (*this) % mod);
   }

operator%=() [2/2]

word Botan::BigInt::operator%=

(

word

y

)

Modulo operator

Parameters

y	the modulus (word) to reduce this by

Definition at line 305 of file big_ops2.cpp.

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

   {
   if(mod == 0)
      throw BigInt::DivideByZero();

   if(is_power_of_2(mod))
       {
       word result = (word_at(0) & (mod - 1));
       clear();
       grow_to(2);
       m_reg[0] = result;
       return result;
       }

   word remainder = 0;

   for(size_t j = sig_words(); j > 0; --j)
      remainder = bigint_modop(remainder, word_at(j-1), mod);
   clear();
   grow_to(2);

   if(remainder && sign() == BigInt::Negative)
      m_reg[0] = mod - remainder;
   else
      m_reg[0] = remainder;

   set_sign(BigInt::Positive);

   return word_at(0);
   }

operator*=() [1/2]

BigInt & Botan::BigInt::operator*=

(

const BigInt &

y

)

*= operator

Parameters

y	the BigInt to multiply with this

Definition at line 204 of file big_ops2.cpp.

References mul().

   {
   secure_vector<word> ws;
   return this->mul(y, ws);
   }

operator*=() [2/2]

BigInt & Botan::BigInt::operator*=

(

word

y

)

*= operator

Parameters

y	the word to multiply with this

Definition at line 265 of file big_ops2.cpp.

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

   {
   if(y == 0)
      {
      clear();
      set_sign(Positive);
      }

   const size_t x_sw = sig_words();

   if(size() < x_sw + 1)
      grow_to(x_sw + 1);
   bigint_linmul2(mutable_data(), x_sw, y);

   return (*this);
   }

operator++() [1/2]

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

inline

Increment operator

Definition at line 230 of file bigint.h.

{ return (*this += 1); }

operator++() [2/2]

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

inline

Postfix increment operator

Definition at line 240 of file bigint.h.

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

operator+=() [1/2]

BigInt & Botan::BigInt::operator+=

(

const BigInt &

y

)

+= operator

Parameters

y	the BigInt to add to this

Definition at line 53 of file big_ops2.cpp.

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

   {
   return add(y.data(), y.sig_words(), y.sign());
   }

operator+=() [2/2]

BigInt & Botan::BigInt::operator+=

(

word

y

)

+= operator

Parameters

y	the word to add to this

Definition at line 58 of file big_ops2.cpp.

References add(), and Positive.

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

operator-()

BigInt Botan::BigInt::operator-

(

)

const

Unary negation operator

Returns

negative this

Definition at line 259 of file bigint.cpp.

References flip_sign().

   {
   BigInt x = (*this);
   x.flip_sign();
   return x;
   }

operator--() [1/2]

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

inline

Decrement operator

Definition at line 235 of file bigint.h.

{ return (*this -= 1); }

operator--() [2/2]

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

inline

Postfix decrement operator

Definition at line 245 of file bigint.h.

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

operator-=() [1/2]

BigInt & Botan::BigInt::operator-=

(

const BigInt &

y

)

-= operator

Parameters

y	the BigInt to subtract from this

Definition at line 102 of file big_ops2.cpp.

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

   {
   return sub(y.data(), y.sig_words(), y.sign());
   }

operator-=() [2/2]

BigInt & Botan::BigInt::operator-=

(

word

y

)

-= operator

Parameters

y	the word to subtract from this

Definition at line 107 of file big_ops2.cpp.

References Positive, and sub().

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

operator/=()

BigInt & Botan::BigInt::operator/=

(

const BigInt &

y

)

/= operator

Parameters

y	the BigInt to divide this by

Definition at line 285 of file big_ops2.cpp.

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

   {
   if(y.sig_words() == 1 && is_power_of_2(y.word_at(0)))
      (*this) >>= (y.bits() - 1);
   else
      (*this) = (*this) / y;
   return (*this);
   }

operator<<=()

BigInt & Botan::BigInt::operator<<=

(

size_t

shift

)

Left shift operator

Parameters

shift

the number of bits to shift this left by

Definition at line 339 of file big_ops2.cpp.

References Botan::bigint_shl1(), grow_to(), mutable_data(), and sig_words().

   {
   if(shift)
      {
      const size_t shift_words = shift / BOTAN_MP_WORD_BITS,
                   shift_bits  = shift % BOTAN_MP_WORD_BITS,
                   words = sig_words();

      /*
      * FIXME - if shift_words == 0 && the top shift_bits of the top word
      * are zero then we know that no additional word is needed and can
      * skip the allocation.
      */
      const size_t needed_size = words + shift_words + (shift_bits ? 1 : 0);

      if(m_reg.size() < needed_size)
         grow_to(needed_size);

      bigint_shl1(mutable_data(), words, shift_words, shift_bits);
      }

   return (*this);
   }

operator=() [1/2]

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

inline

Move assignment

Definition at line 133 of file bigint.h.

        {
        if(this != &other)
           this->swap(other);

        return (*this);
        }

operator=() [2/2]

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

default

Copy assignment

operator>>=()

BigInt & Botan::BigInt::operator>>=

(

size_t

shift

)

Right shift operator

Parameters

shift

the number of bits to shift this right by

Definition at line 366 of file big_ops2.cpp.

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

   {
   if(shift)
      {
      const size_t shift_words = shift / BOTAN_MP_WORD_BITS,
                   shift_bits  = shift % BOTAN_MP_WORD_BITS;

      bigint_shr1(mutable_data(), sig_words(), shift_words, shift_bits);

      if(is_zero())
         set_sign(Positive);
      }

   return (*this);
   }

power_of_2()

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

inlinestatic

Create a power of two

Parameters

n	the power of two to create

Returns

bigint representing 2^n

Definition at line 642 of file bigint.h.

References set_bit().

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

        {
        BigInt b;
        b.set_bit(n);
        return b;
        }

random_integer()

BigInt Botan::BigInt::random_integer ( RandomNumberGenerator &  rng, const BigInt &  min, const BigInt &  max  )

static

Parameters

rng	a random number generator
min	the minimum value (must be non-negative)
max	the 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_prime(), Botan::EC_Group::random_scalar(), and Botan::PointGFp::randomize_repr().

   {
   if(min.is_negative() || max.is_negative() || max <= min)
      throw Invalid_Argument("BigInt::random_integer invalid range");

   BigInt r;

   const size_t bits = max.bits();

   do
      {
      r.randomize(rng, bits, false);
      }
   while(r < min || r >= max);

   return r;
   }

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

rng	the random number generator to use
bitsize	number of bits the created random value should have
set_high_bit	if 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().

   {
   set_sign(Positive);

   if(bitsize == 0)
      {
      clear();
      }
   else
      {
      secure_vector<uint8_t> array = rng.random_vec(round_up(bitsize, 8) / 8);

      // Always cut unwanted bits
      if(bitsize % 8)
         array[0] &= 0xFF >> (8 - (bitsize % 8));

      // Set the highest bit if wanted
      if (set_high_bit)
         array[0] |= 0x80 >> ((bitsize % 8) ? (8 - bitsize % 8) : 0);

      binary_decode(array);
      }
   }

reduce_below()

void Botan::BigInt::reduce_below	(	const BigInt &	mod,
		secure_vector< word > &	ws
	)

Return *this below 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 of modulo operator.

Definition at line 266 of file bigint.cpp.

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

Referenced by mod_add(), Botan::Montgomery_Int::mul_by_2(), Botan::Montgomery_Int::mul_by_3(), Botan::Montgomery_Int::mul_by_4(), Botan::Montgomery_Int::mul_by_8(), Botan::Montgomery_Int::operator+(), Botan::redc_p521(), and Botan::Modular_Reducer::reduce().

   {
   if(p.is_negative())
      throw Invalid_Argument("BigInt::reduce_below mod must be positive");

   const size_t p_words = p.sig_words();

   if(size() < p_words + 1)
      grow_to(p_words + 1);

   if(ws.size() < p_words + 1)
      ws.resize(p_words + 1);

   clear_mem(ws.data(), ws.size());

   for(;;)
      {
      word borrow = bigint_sub3(ws.data(), data(), p_words + 1, p.data(), p_words);

      if(borrow)
         break;

      m_reg.swap(ws);
      }
   }

rev_sub()

BigInt & Botan::BigInt::rev_sub	(	const word	y[],
		size_t	y_size,
		secure_vector< word > &	ws
	)

Set *this to y - *this

Parameters

y	the BigInt to subtract from as a sequence of words
y_size	length of y in words
ws	a temp workspace

Definition at line 166 of file big_ops2.cpp.

References Botan::bigint_cmp(), Botan::bigint_sub3(), Botan::clear_mem(), data(), flip_sign(), Positive, sig_words(), and sign().

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

   {
   /*
   *this = BigInt(y, y_sw) - *this;
   return *this;
   */
   if(this->sign() != BigInt::Positive)
      throw Invalid_State("BigInt::sub_rev requires this is positive");

   const size_t x_sw = this->sig_words();

   const int32_t relative_size = bigint_cmp(y, y_sw, this->data(), x_sw);

   ws.resize(std::max(y_sw, x_sw) + 1);
   clear_mem(ws.data(), ws.size());

   if(relative_size < 0)
      {
      bigint_sub3(ws.data(), this->data(), x_sw, y, y_sw);
      this->flip_sign();
      }
   else if(relative_size == 0)
      {
      ws.clear();
      }
   else if(relative_size > 0)
      {
      bigint_sub3(ws.data(), y, y_sw, this->data(), x_sw);
      }

   m_reg.swap(ws);

   return (*this);
   }

reverse_sign()

Sign Botan::BigInt::reverse_sign ( ) const

inline

Returns

the opposite sign of the represented integer value

Definition at line 477 of file bigint.h.

        {
        if(sign() == Positive)
           return Negative;
        return Positive;
        }

set_bit()

void Botan::BigInt::set_bit

(

size_t

n

)

Set bit at specified position

Parameters

n	bit position to set

Definition at line 201 of file bigint.cpp.

References grow_to(), and size().

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

   {
   const size_t which = n / BOTAN_MP_WORD_BITS;
   const word mask = static_cast<word>(1) << (n % BOTAN_MP_WORD_BITS);
   if(which >= size()) grow_to(which + 1);
   m_reg[which] |= mask;
   }

set_sign()

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

inline

Set sign of the integer

Parameters

sign	new Sign to set

Definition at line 496 of file bigint.h.

References Botan::CT::is_zero().

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

        {
        if(is_zero())
           m_signedness = Positive;
        else
           m_signedness = sign;
        }

set_word_at()

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

inline

Definition at line 443 of file bigint.h.

        {
        if(i >= m_reg.size())
           grow_to(i + 1);
        m_reg[i] = w;
        }

set_words()

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

inline

Definition at line 450 of file bigint.h.

References Botan::copy_mem().

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

        {
        m_reg.resize(len);
        copy_mem(mutable_data(), w, len);
        }

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

        {
        const size_t words = std::max(min_size, sig_words());
        m_reg.resize(words);
        }

sig_words()

size_t Botan::BigInt::sig_words ( ) const

inline

Return how many words we need to hold this value

Returns

significant words of the represented integer value

Definition at line 519 of file bigint.h.

Referenced by add(), bits(), cmp(), cmp_word(), Botan::ct_inverse_mod_odd_modulus(), Botan::CurveGFp_Repr::curve_mul(), Botan::CurveGFp_Repr::curve_sqr(), Botan::divide(), encode_words(), Botan::Montgomery_Int::fix_size(), mod_sub(), Botan::Modular_Reducer::Modular_Reducer(), Botan::Montgomery_Params::Montgomery_Params(), Botan::Montgomery_Params::mul(), mul(), Botan::mul_add(), Botan::Montgomery_Params::mul_by(), Botan::operator%(), operator%=(), Botan::operator*(), operator*=(), Botan::operator+(), operator+=(), Botan::operator-(), operator-=(), Botan::operator/(), operator/=(), Botan::operator<<(), operator<<=(), Botan::operator>>(), operator>>=(), Botan::redc_p521(), Botan::Modular_Reducer::reduce(), reduce_below(), rev_sub(), Botan::Montgomery_Params::sqr(), square(), Botan::Montgomery_Params::square_this(), and sub().

        {
        const word* x = m_reg.data();
        size_t sig = m_reg.size();

        while(sig && (x[sig-1] == 0))
           sig--;
        return sig;
        }

sign()

Sign Botan::BigInt::sign ( ) const

inline

Return the sign of the integer

Returns

the sign of the integer

Definition at line 472 of file bigint.h.

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

{ return (m_signedness); }

size()

size_t Botan::BigInt::size ( ) const

inline

Give size of internal register

Returns

size of internal register in words

Definition at line 513 of file bigint.h.

Referenced by Botan::PointGFp::add(), Botan::PointGFp::add_affine(), BigInt(), clear_bit(), const_time_lookup(), encode_words(), grow_to(), Botan::low_zero_bits(), Botan::Montgomery_Params::mul(), mul(), Botan::mul_add(), Botan::Montgomery_Params::mul_by(), Botan::operator*(), operator*=(), Botan::redc_p521(), Botan::Modular_Reducer::reduce(), reduce_below(), set_bit(), Botan::Montgomery_Params::sqr(), square(), and Botan::Montgomery_Params::square_this().

{ return m_reg.size(); }

square()

BigInt & Botan::BigInt::square

(

secure_vector< word > &

ws

)

Square value of *this

Parameters

ws	a temp workspace

Definition at line 248 of file big_ops2.cpp.

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

Referenced by Botan::square().

   {
   const size_t sw = sig_words();

   secure_vector<word> z(2*sw);
   ws.resize(z.size());

   bigint_sqr(z.data(), z.size(),
              data(), size(), sw,
              ws.data(), ws.size());

   swap_reg(z);
   set_sign(BigInt::Positive);

   return (*this);
   }

sub()

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

Definition at line 63 of file big_ops2.cpp.

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

Referenced by operator-=().

   {
   const size_t x_sw = sig_words();

   int32_t relative_size = bigint_cmp(data(), x_sw, y, y_sw);

   const size_t reg_size = std::max(x_sw, y_sw) + 1;
   grow_to(reg_size);

   if(relative_size < 0)
      {
      if(sign() == y_sign)
         bigint_sub2_rev(mutable_data(), y, y_sw);
      else
         bigint_add2(mutable_data(), reg_size - 1, y, y_sw);

      set_sign(y_sign == Positive ? Negative : Positive);
      }
   else if(relative_size == 0)
      {
      if(sign() == y_sign)
         {
         clear();
         set_sign(Positive);
         }
      else
         bigint_shl1(mutable_data(), x_sw, 0, 1);
      }
   else if(relative_size > 0)
      {
      if(sign() == y_sign)
         bigint_sub2(mutable_data(), x_sw, y, y_sw);
      else
         bigint_add2(mutable_data(), reg_size - 1, y, y_sw);
      }

   return (*this);
   }

swap()

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

inline

Swap this value with another

Parameters

other

BigInt to swap values with

Definition at line 150 of file bigint.h.

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

        {
        m_reg.swap(other.m_reg);
        std::swap(m_signedness, other.m_signedness);
        }

swap_reg()

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

inline

Definition at line 156 of file bigint.h.

Referenced by square().

        {
        m_reg.swap(reg);
        }

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

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

Referenced by botan_mp_to_uint32().

   {
   if(is_negative())
      throw Encoding_Error("BigInt::to_u32bit: Number is negative");
   if(bits() > 32)
      throw Encoding_Error("BigInt::to_u32bit: Number is too big to convert");

   uint32_t out = 0;
   for(size_t i = 0; i != 4; ++i)
      out = (out << 8) | byte_at(3-i);
   return out;
   }

word_at()

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

inline

Return the word at a specified position of the internal register

Parameters

n	position in the register

Returns

value at position n

Definition at line 440 of file bigint.h.

Referenced by bits(), const_time_lookup(), Botan::divide(), encode(), Botan::is_prime(), Botan::low_zero_bits(), Botan::Montgomery_Params::Montgomery_Params(), mul(), Botan::operator%(), operator%=(), Botan::operator*(), Botan::operator/(), operator/=(), and Botan::redc_p521().

        { return ((n < size()) ? m_reg[n] : 0); }

---

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

• src/lib/math/bigint/bigint.h
• src/lib/math/bigint/big_code.cpp
• src/lib/math/bigint/big_ops2.cpp
• src/lib/math/bigint/big_rand.cpp
• src/lib/math/bigint/bigint.cpp