#include <bigint.h>

Classes
struct	DivideByZero
Public Types
enum	Base { Decimal = 10, Hexadecimal = 16, Binary = 256 }
enum	Sign { Negative = 0, Positive = 1 }
Public Member Functions
BigInt	abs () const
	BigInt ()
	BigInt (u64bit n)
	BigInt (const BigInt &other)
	BigInt (const std::string &str)
	BigInt (const byte buf[], size_t length, Base base=Binary)
	BigInt (RandomNumberGenerator &rng, size_t bits)
	BigInt (Sign sign, size_t n)
	BigInt (BigInt &&other)
void	binary_decode (const byte buf[], size_t length)
void	binary_decode (const secure_vector< byte > &buf)
void	binary_encode (byte buf[]) const
size_t	bits () const
byte	byte_at (size_t n) const
size_t	bytes () const
void	clear ()
void	clear_bit (size_t n)
s32bit	cmp (const BigInt &n, bool check_signs=true) const
const word *	data () const
size_t	encoded_size (Base base=Binary) const
void	flip_sign ()
bool	get_bit (size_t n) const
u32bit	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)
word *	mutable_data ()
bool	operator! () const
BigInt &	operator%= (const BigInt &y)
word	operator%= (word y)
BigInt &	operator*= (const BigInt &y)
BigInt &	operator++ ()
BigInt	operator++ (int)
BigInt &	operator+= (const BigInt &y)
BigInt	operator- () const
BigInt &	operator-- ()
BigInt	operator-- (int)
BigInt &	operator-= (const BigInt &y)
BigInt &	operator/= (const BigInt &y)
BigInt &	operator<<= (size_t shift)
BigInt &	operator= (BigInt &&other)
BigInt &	operator= (const BigInt &)
BigInt &	operator>>= (size_t shift)
void	randomize (RandomNumberGenerator &rng, size_t bitsize=0)
Sign	reverse_sign () const
void	set_bit (size_t n)
void	set_sign (Sign sign)
void	set_word_at (size_t i, word w)
size_t	sig_words () const
Sign	sign () const
size_t	size () const
void	swap (BigInt &other)
void	swap_reg (secure_vector< word > &reg)
u32bit	to_u32bit () const
word	word_at (size_t n) const
Static Public Member Functions
static BigInt	decode (const byte buf[], size_t length, Base base=Binary)
static BigInt	decode (const secure_vector< byte > &buf, Base base=Binary)
static BigInt	decode (const std::vector< byte > &buf, Base base=Binary)
static std::vector< byte >	encode (const BigInt &n, Base base=Binary)
static void	encode (byte buf[], const BigInt &n, Base base=Binary)
static secure_vector< byte >	encode_1363 (const BigInt &n, size_t bytes)
static secure_vector< byte >	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 23 of file bigint.h.

Member Enumeration Documentation

enum Botan::BigInt::Base

Base enumerator for encoding and decoding

Enumerator:

Decimal
Hexadecimal
Binary

Definition at line 29 of file bigint.h.

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

enum Botan::BigInt::Sign

Sign symbol definitions for positive and negative numbers

Enumerator:

Negative
Positive

Definition at line 34 of file bigint.h.

{ Negative = 0, Positive = 1 };

Constructor & Destructor Documentation

Botan::BigInt::BigInt ( ) [inline]

Create empty BigInt

Definition at line 45 of file bigint.h.

Referenced by random_integer().

{ m_signedness = Positive; }

Botan::BigInt::BigInt ( u64bit n )

Create BigInt from 64 bit integer

Parameters:

n	initial value of this BigInt

Definition at line 20 of file bigint.cpp.

References Botan::MP_WORD_BITS, and Botan::MP_WORD_MASK.

   {
   if(n == 0)
      return;

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

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

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

Copy Constructor

Parameters:

other the BigInt to copy

Definition at line 44 of file bigint.cpp.

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

Botan::BigInt::BigInt ( const std::string & str )

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

References 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(reinterpret_cast<const byte*>(str.data()) + markers,
                  str.length() - markers, base);

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

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

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

References decode().

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

Botan::BigInt::BigInt	(	RandomNumberGenerator &	rng,
		size_t	bits
	)

Create a random BigInt of the specified size

Parameters:

rng	random number generator
bits	size in bits

Definition at line 90 of file bigint.cpp.

References randomize().

   {
   randomize(rng, bits);
   }

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

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

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

Move constructor

Definition at line 93 of file bigint.h.

        {
        this->swap(other);
        }

Member Function Documentation

BigInt Botan::BigInt::abs ( ) const

Returns:: absolute (positive) value of this

Definition at line 249 of file bigint.cpp.

References Positive, set_sign(), and x.

Referenced by Botan::abs(), and Botan::operator*().

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

void Botan::BigInt::binary_decode	(	const byte	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 269 of file bigint.cpp.

References clear().

Referenced by decode(), Botan::generate_dsa_primes(), and randomize().

   {
   const size_t WORD_BYTES = sizeof(word);

   clear();
   m_reg.resize(round_up<size_t>((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];
   }

void Botan::BigInt::binary_decode ( const secure_vector< byte > & buf ) [inline]

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

Parameters:

buf	the array to load from

Definition at line 456 of file bigint.h.

        {
        binary_decode(&buf[0], buf.size());
        }

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

Store BigInt-value in a given byte array

Parameters:

buf	destination byte array for the integer value

Definition at line 259 of file bigint.cpp.

References byte_at(), and bytes().

Referenced by encode(), and Botan::GOST_3410_PublicKey::x509_subject_public_key().

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

size_t Botan::BigInt::bits ( ) const

Get the bit length of the integer

Returns:: bit length of the represented integer value

Definition at line 179 of file bigint.cpp.

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

Referenced by Botan::Blinder::Blinder(), Botan::TLS::Client_Key_Exchange::Client_Key_Exchange(), Botan::BER_Decoder::decode(), Botan::BER_Decoder::decode_constrained_integer(), Botan::DH_PrivateKey::DH_PrivateKey(), Botan::DL_Group::DL_Group(), Botan::DER_Encoder::encode(), encoded_size(), Botan::IF_Scheme_PublicKey::estimated_strength(), Botan::DL_Scheme_PublicKey::estimated_strength(), Botan::Fixed_Window_Exponentiator::execute(), Botan::generate_dsa_primes(), Botan::generate_rfc6979_nonce(), Botan::is_prime(), Botan::multi_exponentiate(), Botan::operator*(), operator/=(), Botan::operator>>(), random_integer(), Botan::random_prime(), Botan::RSA_PrivateKey::RSA_PrivateKey(), Botan::RW_PrivateKey::RW_PrivateKey(), Botan::Fixed_Window_Exponentiator::set_base(), Botan::Montgomery_Exponentiator::set_base(), Botan::Montgomery_Exponentiator::set_exponent(), 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 * MP_WORD_BITS + high_bit(word_at(full_words)));
   }

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

References Botan::get_byte().

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

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

size_t Botan::BigInt::bytes ( ) const [inline]

Give byte length of the integer

Returns:: byte length of the represented integer value

Definition at line 399 of file bigint.h.

Referenced by binary_encode(), Botan::EC_Group::DER_encode(), Botan::EC2OSP(), Botan::DER_Encoder::encode(), encode_1363(), encoded_size(), Botan::ECDSA_Signature::get_concatenation(), Botan::EC_PrivateKey::pkcs8_private_key(), Botan::srp6_client_agree(), Botan::SRP6_Server_Session::step1(), and Botan::GOST_3410_PublicKey::x509_subject_public_key().

{ return (bits() + 7) / 8; }

void Botan::BigInt::clear ( ) [inline]

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

Definition at line 213 of file bigint.h.

References Botan::zeroise().

Referenced by binary_decode(), Botan::CurveGFp_NIST::curve_mul(), Botan::CurveGFp_NIST::curve_sqr(), operator%=(), operator*=(), operator-=(), and randomize().

{ zeroise(m_reg); }

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

Clear bit at specified position

Parameters:

n	bit position to clear

Definition at line 168 of file bigint.cpp.

References Botan::MP_WORD_BITS, and size().

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

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

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

Referenced by Botan::divide(), Botan::operator!=(), 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());
   }

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

Referenced by cmp(), Botan::CurveGFp_NIST::curve_mul(), Botan::CurveGFp_NIST::curve_sqr(), Botan::Montgomery_Exponentiator::execute(), Botan::mul_add(), Botan::CurveGFp_Repr::normalize(), Botan::operator*(), operator*=(), Botan::operator+(), operator+=(), Botan::operator-(), operator-=(), Botan::operator<<(), Botan::operator>>(), Botan::Montgomery_Exponentiator::set_base(), and Botan::square().

{ return &m_reg[0]; }

BigInt Botan::BigInt::decode	(	const byte	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 98 of file big_code.cpp.

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

Referenced by BigInt(), Botan::TLS::Client_Key_Exchange::Client_Key_Exchange(), Botan::decode_concatenation(), Botan::CRL_Entry::encode_into(), Botan::generate_rfc6979_nonce(), Botan::OCSP::CertID::is_id_for(), and Botan::OS2ECP().

   {
   BigInt r;
   if(base == Binary)
      r.binary_decode(buf, length);
   else if(base == Hexadecimal)
      {
      secure_vector<byte> 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(reinterpret_cast<const char*>(&buf[1]),
                                     length - 1,
                                     false);
         }
      else
         binary = hex_decode_locked(reinterpret_cast<const char*>(buf),
                                    length, false);

      r.binary_decode(&binary[0], 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 byte 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;
   }

static BigInt Botan::BigInt::decode	(	const secure_vector< byte > &	buf,
		Base	base = `Binary`
	)		`[inline, static]`

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

References Botan::BER::decode().

        {
        return BigInt::decode(&buf[0], buf.size(), base);
        }

static BigInt Botan::BigInt::decode	(	const std::vector< byte > &	buf,
		Base	base = `Binary`
	)		`[inline, static]`

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

References Botan::BER::decode().

        {
        return BigInt::decode(&buf[0], buf.size(), base);
        }

std::vector< byte > 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::TLS::Client_Key_Exchange::Client_Key_Exchange(), encode_1363(), encode_locked(), Botan::operator<<(), and Botan::TLS::Server_Key_Exchange::Server_Key_Exchange().

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

void Botan::BigInt::encode	(	byte	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(), Decimal, Botan::Charset::digit2char(), Botan::divide(), encoded_size(), Botan::hex_encode(), Hexadecimal, is_zero(), n, Positive, set_sign(), and word_at().

   {
   if(base == Binary)
      {
      n.binary_encode(output);
      }
   else if(base == Hexadecimal)
      {
      secure_vector<byte> binary(n.encoded_size(Binary));
      n.binary_encode(&binary[0]);

      hex_encode(reinterpret_cast<char*>(output),
                 &binary[0], 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<byte>(remainder.word_at(0)));
         if(copy.is_zero())
            break;
         }
      }
   else
      throw Invalid_Argument("Unknown BigInt encoding method");
   }

secure_vector< byte > 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<byte>

Returns:: a secure_vector<byte> containing the encoded BigInt

Definition at line 82 of file big_code.cpp.

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

Referenced by Botan::PK_Verifier::check_signature(), Botan::EC_Group::DER_encode(), Botan::EC2OSP(), Botan::generate_rfc6979_nonce(), Botan::ECDSA_Signature::get_concatenation(), Botan::EC_PrivateKey::pkcs8_private_key(), Botan::DH_PublicKey::public_value(), Botan::srp6_client_agree(), and Botan::SRP6_Server_Session::step2().

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

   secure_vector<byte> output(bytes);
   encode(&output[leading_0s], n, Binary);
   return output;
   }

secure_vector< byte > 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<byte> output(n.encoded_size(base));
   encode(&output[0], n, base);
   if(base != Binary)
      for(size_t j = 0; j != output.size(); ++j)
         if(output[j] == 0)
            output[j] = '0';
   return output;
   }

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 193 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");
   }

void Botan::BigInt::flip_sign ( )

Flip the sign of this BigInt

Definition at line 221 of file bigint.cpp.

References reverse_sign(), and set_sign().

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

   {
   set_sign(reverse_sign());
   }

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

Referenced by Botan::EC2OSP(), Botan::multi_exponentiate(), and Botan::operator*().

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

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

References byte_at().

Referenced by Botan::Fixed_Window_Exponentiator::execute(), Botan::Montgomery_Exponentiator::execute(), and Botan::operator*().

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

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

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

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

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

Definition at line 419 of file bigint.h.

{ return m_reg; }

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

Definition at line 420 of file bigint.h.

{ return m_reg; }

void Botan::BigInt::grow_to ( size_t n ) [inline]

Increase internal register buffer to at least n words

Parameters:

n	new size of register

Definition at line 426 of file bigint.h.

Referenced by Botan::CurveGFp_NIST::curve_mul(), Botan::CurveGFp_NIST::curve_sqr(), Botan::divide(), Botan::Montgomery_Exponentiator::execute(), Botan::CurveGFp_Repr::normalize(), operator%=(), operator*=(), operator+=(), operator-=(), operator<<=(), and set_bit().

        {
        if(n > size())
           m_reg.resize(n + (8 - n % 8));
        }

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

Referenced by Botan::IF_Scheme_PublicKey::check_key(), Botan::IF_Scheme_PrivateKey::check_key(), Botan::IF_Scheme_PrivateKey::IF_Scheme_PrivateKey(), Botan::inverse_mod(), Botan::is_prime(), Botan::jacobi(), and Botan::Montgomery_Exponentiator::Montgomery_Exponentiator().

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

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

Referenced by cmp(), Botan::divide(), Botan::inverse_mod(), Botan::jacobi(), Botan::mul_add(), Botan::multi_exponentiate(), Botan::CurveGFp_Repr::normalize(), Botan::operator%(), Botan::operator*(), Botan::Modular_Reducer::reduce(), Botan::Power_Mod::set_base(), Botan::Power_Mod::set_exponent(), Botan::sub_mul(), and to_u32bit().

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

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

Referenced by Botan::gcd(), Botan::IF_Scheme_PrivateKey::IF_Scheme_PrivateKey(), Botan::inverse_mod(), and Botan::low_zero_bits().

{ return (!is_zero()); }

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

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

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

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

Referenced by cmp(), Botan::low_zero_bits(), Botan::Montgomery_Exponentiator::Montgomery_Exponentiator(), Botan::operator%(), and Botan::Modular_Reducer::reduce().

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

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

Referenced by Botan::CurveGFp_NIST::curve_mul(), Botan::CurveGFp_NIST::curve_sqr(), Botan::divide(), encode(), Botan::gcd(), Botan::inverse_mod(), Botan::jacobi(), Botan::mul_add(), Botan::operator%(), Botan::operator*(), operator>>=(), Botan::Power_Mod::set_base(), and set_sign().

        {
        const size_t sw = sig_words();

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

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

References Botan::clear_mem().

Referenced by 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())
           {
           clear_mem(&m_reg[top_word+1], size() - (top_word + 1));
           m_reg[top_word] &= mask;
           }
        }

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

Referenced by Botan::CurveGFp_NIST::curve_mul(), Botan::CurveGFp_NIST::curve_sqr(), Botan::divide(), Botan::Montgomery_Exponentiator::execute(), Botan::mul_add(), operator*=(), operator+=(), operator-=(), Botan::operator<<(), operator<<=(), Botan::operator>>(), operator>>=(), Botan::Montgomery_Exponentiator::set_base(), and Botan::square().

{ return &m_reg[0]; }

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

! operator

Returns:: true iff this is zero, otherwise false

Definition at line 207 of file bigint.h.

{ return (!is_nonzero()); }

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

Modulo operator

Parameters:

y	the modulus to reduce this by

Definition at line 145 of file big_ops2.cpp.

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

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

Modulo operator

Parameters:

y	the modulus (word) to reduce this by

Definition at line 153 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);
   }

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

*= operator

Parameters:

y	the BigInt to multiply with this

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

   {
   const size_t x_sw = sig_words(), 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 + 2);
      bigint_linmul3(mutable_data(), y.data(), y_sw, word_at(0));
      }
   else if(y_sw == 1 && x_sw)
      {
      grow_to(x_sw + 2);
      bigint_linmul2(mutable_data(), x_sw, y.word_at(0));
      }
   else
      {
      grow_to(size() + y.size());

      secure_vector<word> z(data(), data() + x_sw);
      secure_vector<word> workspace(size());

      bigint_mul(mutable_data(), size(), &workspace[0],
                 &z[0], z.size(), x_sw,
                 y.data(), y.size(), y_sw);
      }

   return (*this);
   }

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

Increment operator

Definition at line 180 of file bigint.h.

{ return (*this += 1); }

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

Postfix increment operator

Definition at line 190 of file bigint.h.

References x.

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

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

+= operator

Parameters:

y	the BigInt to add to this

Definition at line 18 of file big_ops2.cpp.

References Botan::bigint_add2(), Botan::bigint_cmp(), Botan::bigint_sub2(), Botan::bigint_sub3(), data(), grow_to(), mutable_data(), Positive, set_sign(), sig_words(), sign(), swap(), and Botan::zeroise().

   {
   const size_t x_sw = sig_words(), y_sw = y.sig_words();

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

   if(sign() == y.sign())
      bigint_add2(mutable_data(), reg_size - 1, y.data(), y_sw);
   else
      {
      s32bit relative_size = bigint_cmp(data(), x_sw, y.data(), y_sw);

      if(relative_size < 0)
         {
         secure_vector<word> z(reg_size - 1);
         bigint_sub3(&z[0], y.data(), reg_size - 1, data(), x_sw);
         std::swap(m_reg, z);
         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.data(), y_sw);
      }

   return (*this);
   }

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

Unary negation operator

Returns:: negative this

Definition at line 239 of file bigint.cpp.

References flip_sign(), and x.

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

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

Decrement operator

Definition at line 185 of file bigint.h.

{ return (*this -= 1); }

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

Postfix decrement operator

Definition at line 195 of file bigint.h.

References x.

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

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

-= operator

Parameters:

y	the BigInt to subtract from this

Definition at line 53 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(), Positive, reverse_sign(), set_sign(), sig_words(), and sign().

   {
   const size_t x_sw = sig_words(), y_sw = y.sig_words();

   s32bit relative_size = bigint_cmp(data(), x_sw, y.data(), 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.data(), y_sw);
      else
         bigint_add2(mutable_data(), reg_size - 1, y.data(), y_sw);

      set_sign(y.reverse_sign());
      }
   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.data(), y_sw);
      else
         bigint_add2(mutable_data(), reg_size - 1, y.data(), y_sw);
      }

   return (*this);
   }

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

/= operator

Parameters:

y	the BigInt to divide this by

Definition at line 133 of file big_ops2.cpp.

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

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

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

Left shift operator

Parameters:

shift the number of bits to shift this left by

Definition at line 187 of file big_ops2.cpp.

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

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

      grow_to(words + shift_words + (shift_bits ? 1 : 0));
      bigint_shl1(mutable_data(), words, shift_words, shift_bits);
      }

   return (*this);
   }

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

Move assignment

Definition at line 101 of file bigint.h.

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

        return (*this);
        }

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

Copy assignment

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

Right shift operator

Parameters:

shift the number of bits to shift this right by

Definition at line 205 of file big_ops2.cpp.

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

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

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

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

   return (*this);
   }

static BigInt Botan::BigInt::power_of_2 ( size_t n ) [inline, static]

Create a power of two

Parameters:

n	the power of two to create

Returns:: bigint representing 2^n

Definition at line 482 of file bigint.h.

References set_bit().

Referenced by Botan::Modular_Reducer::Modular_Reducer(), Botan::Montgomery_Exponentiator::Montgomery_Exponentiator(), Botan::Modular_Reducer::reduce(), and Botan::ressol().

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

BigInt Botan::BigInt::random_integer	(	RandomNumberGenerator &	rng,
		const BigInt &	min,
		const BigInt &	max
	)		`[static]`

Parameters:

rng	a random number generator
min	the minimum value
max	the maximum value

Returns:: random integer in [min,max)

Definition at line 37 of file big_rand.cpp.

References BigInt(), and bits().

Referenced by Botan::DSA_PrivateKey::DSA_PrivateKey(), Botan::EC_PrivateKey::EC_PrivateKey(), Botan::is_prime(), and Botan::NR_PrivateKey::NR_PrivateKey().

   {
   BigInt range = max - min;

   if(range <= 0)
      throw Invalid_Argument("random_integer: invalid min/max values");

   return (min + (BigInt(rng, range.bits() + 2) % range));
   }

void Botan::BigInt::randomize	(	RandomNumberGenerator &	rng,
		size_t	bitsize = `0`
	)

Fill BigInt with a random number with size of bitsize

Parameters:

rng	the random number generator to use
bitsize	number of bits the created random value should have

Definition at line 16 of file big_rand.cpp.

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

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

   {
   set_sign(Positive);

   if(bitsize == 0)
      clear();
   else
      {
      secure_vector<byte> array = rng.random_vec((bitsize + 7) / 8);

      if(bitsize % 8)
         array[0] &= 0xFF >> (8 - (bitsize % 8));
      array[0] |= 0x80 >> ((bitsize % 8) ? (8 - bitsize % 8) : 0);
      binary_decode(&array[0], array.size());
      }
   }

BigInt::Sign Botan::BigInt::reverse_sign ( ) const

Returns:: the opposite sign of the represented integer value

Definition at line 229 of file bigint.cpp.

References Negative, Positive, and sign().

Referenced by flip_sign(), Botan::operator-(), and operator-=().

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

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

Set bit at specified position

Parameters:

n	bit position to set

Definition at line 157 of file bigint.cpp.

References grow_to(), Botan::MP_WORD_BITS, and size().

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

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

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

Set sign of the integer

Parameters:

sign	new Sign to set

Definition at line 210 of file bigint.cpp.

References is_zero(), and Positive.

Referenced by abs(), BigInt(), Botan::divide(), encode(), flip_sign(), Botan::gcd(), operator%=(), operator*=(), operator+=(), operator-=(), operator>>=(), randomize(), and Botan::Modular_Reducer::reduce().

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

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

Definition at line 330 of file bigint.h.

        {
        grow_to(i + 1);
        m_reg[i] = w;
        }

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

References x.

Referenced by bits(), cmp(), Botan::CurveGFp_NIST::curve_mul(), Botan::CurveGFp_NIST::curve_sqr(), Botan::divide(), Botan::Montgomery_Exponentiator::execute(), Botan::Modular_Reducer::Modular_Reducer(), Botan::mul_add(), Botan::operator%(), operator%=(), Botan::operator*(), operator*=(), Botan::operator+(), operator+=(), Botan::operator-(), operator-=(), operator/=(), Botan::operator<<(), operator<<=(), Botan::operator>>(), operator>>=(), Botan::Montgomery_Exponentiator::set_base(), and Botan::square().

        {
        const word* x = &m_reg[0];
        size_t sig = m_reg.size();

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

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

Return the sign of the integer

Returns:: the sign of the integer

Definition at line 352 of file bigint.h.

Referenced by Botan::mul_add(), Botan::operator%(), operator%=(), Botan::operator*(), operator*=(), Botan::operator+(), operator+=(), Botan::operator-(), operator-=(), Botan::operator<<(), Botan::operator>>(), and reverse_sign().

{ return (m_signedness); }

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

Give size of internal register

Returns:: size of internal register in words

Definition at line 379 of file bigint.h.

Referenced by clear_bit(), Botan::CurveGFp_NIST::curve_mul(), Botan::CurveGFp_NIST::curve_sqr(), Botan::Montgomery_Exponentiator::execute(), Botan::low_zero_bits(), Botan::mul_add(), Botan::operator*(), operator*=(), Botan::rfc3394_keywrap(), Botan::Montgomery_Exponentiator::set_base(), set_bit(), and Botan::square().

{ return m_reg.size(); }

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

Swap this value with another

Parameters:

other BigInt to swap values with

Definition at line 118 of file bigint.h.

References swap().

Referenced by operator+=(), swap(), and Botan::PointGFp::swap().

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

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

Definition at line 124 of file bigint.h.

Referenced by Botan::CurveGFp_Repr::normalize().

        {
        m_reg.swap(reg);
        }

u32bit Botan::BigInt::to_u32bit ( ) const

Convert this value into a u32bit, if it is in the range [0 ... 2**32-1], or otherwise throw an exception.

Returns:: the value as a u32bit if conversion is possible

Definition at line 141 of file bigint.cpp.

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

   {
   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");

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

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

Referenced by bits(), Botan::divide(), encode(), Botan::is_prime(), Botan::low_zero_bits(), Botan::Montgomery_Exponentiator::Montgomery_Exponentiator(), Botan::operator%(), operator%=(), Botan::operator*(), operator*=(), and operator/=().

        { 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

Classes

Public Types

Public Member Functions

Static Public Member Functions

Detailed Description

Member Enumeration Documentation

Constructor & Destructor Documentation

Member Function Documentation