Provided by: libbobcat-dev_2.20.01-1_amd64 bug

NAME

       FBB::BigInt - Arithmetic on Integers of Unlimited Size

SYNOPSIS

       #include <bobcat/bigint>
       Linking option: -lbobcat

DESCRIPTION

       This  class  is  defined  as  a  wrapper  class around the openSSL BN series of functions,
       offering members to perform arithmetic on integral values of unlimited sizes. Members  are
       offered  to  generate  primes  and to perform all kinds of common arithmetic operations on
       BigInt objects. Also, conversions to characters and standard  numerical  value  types  are
       offered.

       Below,  the  phrase  the object may also refer to the object’s value. The context in which
       this occurs will make clear that the object’s  value  rather  than  the  object  as-is  is
       referred to.

       Various  constructors  accept  BIGNUM  arguments.  Type  BIGNUM  is the type containing an
       integer of unlimited precision as defined by OpenSSL.

       Signs of BigInt are handled in a special way. Whether a BigInt is negative or positive  is
       determined  by  its sign-flag, and not by a sign bit as is the case with int typed values.
       Since BigInt values have unlimited precision shifting values  to  the  left  won’t  change
       their signs.

       Operators  return  either  a reference to the current (modified) object or return a BigInt
       object containing the computed  value.  The  rule  followed  here  was  to  implement  the
       operators  analogously  to  the  way  the operators work on int type values and variables.
       E.g., operator+()  returns  a  BigInt  value  whereas  operator+=()  returns  a  BigInt  &
       reference.

       All  members  modifying their objects return a reference to the current (modified) object.
       All members not modifying the current object return  a  BigInt  object.  If  both  members
       exists  performing the same functionality the name of the member returning a BigInt object
       ends in a c (const) (e.g., addMod and addModc.

       Almost all operators, members and constructors (except for the default constructor)  throw
       Errno exceptions on failure.

INHERITS FROM

       -

ENUMERATIONS

       Msb
       This (most significant bit) enumeration is used when generating a cryptographically strong
       random number. Its values are:

       o      MSB_UNKNOWN:
              The most significant bit may be 0 or 1.

       o      MSB_IS_ONE:
              The most significant bit is guaranteed to be 1.

       o      TOP_TWO_BITS_ONE:
              The two most significant bits are guaranteed to be 1, resulting in a product of two
              values each containing nBits having 2 * nBits bits.

       Lsb
       This  (least significant bit) enumeration is used when generating random numbers, ensuring
       that the resulting value is either odd or even.

       o      EVEN:
              The random value will be an even value;

       o      ODD:
              The random value will be an odd value.

CONSTRUCTORS

       o      BigInt():
              The default constructor initializes a BigInt value to 0.

       o      BigInt(BIGNUM const &value):
              This constructor initializes a BigInt from a BIGNUM.

       o      BigInt(BIGNUM const *value):
              This constructor initializes a BigInt from a pointer to a const BIGNUM.

       o      BigInt(Type value):
              This constructor is defined as a member template. Any type that  can  be  converted
              using  a  static  cast  to  an  unsigned  long  can  be  used  as  argument to this
              constructor. Promotion is allowed, so in many situations where BigInts are expected
              a plain numerical value can be used as well.

       The standard copy constructor is available.

MEMBER FUNCTIONS

       o      BigInt &addMod(BigInt const &rhs, BigInt const &mod) :
              Rhs is added (modulo mod) to the current object.

       o      BigInt addModc(BigInt const &rhs, BigInt const &mod) :
              The sum (modulo mod) of the current object and rhs is returned.

       o      BIGNUM const &bignum() const:
              A  reference  to  the  BIGNUM  value  maintained  by  the  current BigInt object is
              returned.

       o      char *bigEndian() const:
              The value represented by the current object is stored in a  series  of  char  typed
              values  in  big-endian  order.  If  a  value  consists  of  5  chars the eight most
              significant bits will be stored in the char having index value 0, the  eight  least
              significant  bits  will  be  stored  in  the char having index value 4. When needed
              simply swap char[i] with char[j] (i = 0 .. nBytes/2, j = nBytes-1 ..  nBytes/2)  to
              convert  to  little-endian  order.  The  return  value  consists  of  a  series  of
              sizeInBytes()  (see  below)  dynamically  allocated  char  values.  The  caller  of
              bigEndian  owns  the  allocated  memory and should eventually delete it again using
              delete[]. Note that the current object’s sign cannot be inferred  from  the  return
              value.

       o      BigInt &clearBit(size_t index):
              The current object’s bit at index position index is cleared.

       o      BigInt clearBit(size_t index) const:
              A copy of the current object having its bit at index position index cleared.

       o      BigInt &div(BigInt *remainder, BigInt const &rhs):
              The  current  object  is  divided  by  rhs. The division’s remainder is returned in
              *remainder.

       o      BigInt divc(BigInt *remainder, BigInt const &rhs) const:
              The quotient of the current object and rhs is returned. The division’s remainder is
              returned in *remainder.

       o      int compare(BigInt const &rsh) const:
              Using  signed  values, if the current object is smaller than rhs -1 is returned; if
              they are equal 0 is returned; if the  current  object  is  larger  than  ths  1  is
              returned (see also uCompare).

       o      BigInt &exp(BigInt const &exponent):
              The current object is raised to the power exponent.

       o      BigInt expc(BigInt const &exponent) const:
              The current object raised to the power exponent is returned.

       o      BigInt &expMod(BigInt const &exponent, BigInt const &mod):
              The current object is raised to the power exponent modulo mod.

       o      BigInt expModc(BigInt const &exponent, BigInt const &mod) const:
              The current object raised to the power exponent modulo mod is returned.

       o      BigInt &gcd(BigInt const &rhs):
              The  greatest common divisor (gcd) of the current object and rhs is assigned to the
              current  object.  To  compute  the  least  common  multiple  (lcm)  the   following
              relationship can be used:

                  lcm(a, b) = a * b / a.gcd(b)

       o      BigInt gcdc(BigInt const &rhs) const:
              The  greatest  common  divisor  (gcd) of the current object and rhs is returned. To
              compute the least common multiple (lcm) the following relationship can be used:

                  lcm(a, b) = a * b / a.gcd(b)

       o      bool hasBit(size_t index):
              True is returned if the bit at index position index has been set, false otherwise.

       o      BigInt &inverseMod(BigInt const &mod):
              The inverse of the current object modulo mod is assigned  to  the  current  object.
              This is the value ret for which the following expression holds true:

                      (*this * ret) % mod = 1

       o      BigInt inverseModc(BigInt const &mod) const:
              This  inverse of the current object modulo mod is returned.

       o      bool isNegative() const:
              Returns true if the current object contains a negative value.

       o      bool isOdd() const:
              Returns true if the current object is an odd value.

       o      bool isOne() const:
              Returns true if the current object equals one (1).

       o      BigInt &isqrt():
              The  current  object’s integer square root value is assigned to the current object.
              The integer square root of a value x is the biggest  integral  value  whose  square
              does  not  exceed  x.  E.g.,  isqrt(17)  ==  4. An Errno exception is thrown if the
              current object’s value is smaller than one.

       o      BigInt isqrtc() const:
              The integer square root of the current object is returned. An  Errno  exception  is
              thrown if the current object’s value is smaller than one.

       o      bool isZero() const:
              Returns true if the current object equals zero (0).

       o      BigInt &lshift():
              The  current  object’s  bits  are  shifted  one  bit to the left. The object’s sign
              remains unaltered.

       o      BigInt lshiftc():
              The current object’s bits shifted one bit to the left are  returned.  The  object’s
              sign will be equal to the current object’s sign.

       o      BigInt &lshift(size_t nBits):
              The  current object’s bits are shifted nBits to the left. The object’s sign remains
              unaltered.

       o      BigInt lshiftc(size_t nBits) const:
              The current object’s bits shifted nBits bit to the left are returned. The  object’s
              sign will be equal to the current object’s sign.

       o      BigInt &maskBits(size_t lowerNBits):
              The   current  object’s  lowerNBits  lower bits are kept, its higher order bits are
              cleared. The object’s sign is not affected.

       o      BigInt maskBitsc(size_t lowerNBits) const:
              A copy of the current object is returned having all but its lowerNBits  lower  bits
              cleared.  The  sign  of  the  returned object will be equal to the current object’s
              sign.

       o      BigInt &mulMod(BigInt const &rhs, BigInt const &mod):
              The current object is multiplied  (modulo mod) by rhs.

       o      BigInt mulModc(BigInt const &rhs, BigInt const &mod) const:
              The current object multiplied (modulo mod) by rhs is returned.

       o      BigInt &negate():
              The current object’s value is negated (i.e., the value changes its sign).

       o      BigInt negatec() const:
              The  negated value of the current object is returned.

       o      BigInt &rshift():
              The current object’s bits are shifted one bit  to  the  right.  The  object’s  sign
              remains unaltered.

       o      BigInt rshiftc():
              The  current  object’s bits shifted one bit to the right are returned. The object’s
              sign will be equal to the current object’s sign.

       o      BigInt &rshift(size_t nBits):
              The current object’s bits are shifted nBits to the right. The object’s sign remains
              unaltered.

       o      BigInt rshiftc(size_t nBits) const:
              The current object’s bits shifted nBits bit to the right are returned. The object’s
              sign will be equal to the current object’s sign.

       o      BigInt &setBit(size_t index):
              The bit at index position index is set.

       o      BigInt setBitc(size_t index) const:
              A copy of the current object is returned having its bit  at  index  position  index
              set.

       o      BigInt &setBit(size_t index, bool value):
              The bit at index position index is set to value.

       o      BigInt setBitc(size_t index, bool value) const:
              A copy of the current object is returned having its bit at index position index set
              to value.

       o      BigInt &setNegative(bool negative):
              The current object’s sign will be set to negative if  the  function’s  argument  is
              true, it will be set to positive if the function’s argument is false.

       o      BigInt setNegativec(bool negative) const:
              A  copy  of  the  current object is return having a negative sign if the function’s
              argument is true and a positive sign if the function’s argument is false.

       o      size_t size() const:
              The number of bytes required to store the current BIGNUM value is returned.

       o      size_t sizeInBits() const:
              The number of bits required to represent the current BIGNUM value is  returned.  If
              you  want  to  know  the key size of RSA, DH or DSA keys functions like RSA_size(),
              DH_size(), or DSA_size() should be used.

       o      BigInt &sqr():
              The current object’s value is squared.

       o      BigInt sqrc() const:
              The square of the current object is returned.

       o      BigInt &sqrMod(BigInt const &mod) const:
              The current object’s value is squared modulo mod.

       o      BigInt sqrModc(BigInt const &mod) const:
              The square (modulo mod) of the current object is returned.

       o      BigInt &subMod(BigInt const &rhs, BigInt const &mod):
              Rhs is subtracted modulo mod from the current object.

       o      BigInt subModc(BigInt const &rhs, BigInt const &mod) const:
              The difference (modulo mod) of the current object and rhs is returned.

       o      void swap(BigInt &other):
              The current object swaps its value with other.

       o      BigInt &tildeBits():
              All the bits in the bytes of the current object and the sign of the current  object
              are toggled.  So, after

                      Bigint b(5);
                      b.tildeBits();

              b contains the value -250. Also see the discussion with operator~() below.

       o      BigInt tildeBitsc() const:
              A copy of the current object whose bits are toggled is returned.

       o      BigInt &tildeInt():
              The  `tilde’  operation  is  performed on the current object using the standard int
              semantics. E.g., ~5 results in -6.  Also see the discussion with operator~() below.

       o      BigInt tildeIntc() const:
              A copy of the current object is returned to which the `tilde’  operation  has  been
              performed using the standard int semantics.

       o      unsigned long ulong() const:
              The absolute value stored in the current object is returned as an unsigned long. If
              it cannot be represented by an unsigned long it returns 0xffffffffL.

       o      int uCompare(BigInt const &rsh) const:
              Using absolute values, if the current object is smaller than rhs -1 is returned; if
              they  are  equal  0  is  returned;  if  the  current object is larger than ths 1 is
              returned (see also uCompare).

OVERLOADED OPERATORS

       Except for some operators all operators perform their  intuitive  operations.  Where  that
       isn’t  completely true an explanatory remark is provided. E.g., operator*() multiplies two
       BigInts, possibly promoting one of the operands; operator*=() multiplies the  lhs  by  the
       rhs BigInt, possibly promoting the rhs operand.

       Here are the available operators:

       Unary operators:

       o      BigInt &operator++():

       o      BigInt operator++(int):

       o      BigInt &operator--():

       o      BigInt operator--(int):

       o      BigInt operator-():

       o      int operator[](size_t idx) const:
              With BigInt objects it returns the bit-value of the object’s idxth bit as the value
              0 or 1.

       o      BigInt::Bit operator[](size_t idx):
              With non-const BigInt objects it returns  a  reference  to  the  bit-value  of  the
              object’s  idxth  bit.  When  used  as lvalue assigning a 0 or non-zero value to the
              operator’s return value will either clear or set the bit.  Likewise, the  following
              arithmetic  assignment  operators  may  be used: binary or (|=), binary and (&=) or
              binary xor (^=). When used as rvalue  the  value  of  the  object’s  idxth  bit  is
              returned  as  a  bool  value. When inseerted into a std::ostream the bit’s value is
              displayed as 0 or 1.

       o      BigInt operator~():
              This operator is not implemented as it cannot be implemented so that it matches the
              actions of this operator when applied to int type values.

              When  used  on  int  values  this  operator  toggles  all  the int’s bits. E.g., ~5
              represents -6, and ~-6 again equals five. The -6 is the result of the sign  bit  of
              int  values. The obvious implementation of BigInt::operator~() is to toggle all the
              value’s bits and to toggle its sign bit. For 5 this would result in -250: 5,  being
              101  (binary), fits in one byte, so ~5 becomes 11111010 (binary), which is 250. Its
              sign must be reversed as well, so it becomes -250.  This clearly differs  from  the
              value  represented  by the int constant ~5: when constructing BigInt(~5), the value
              -6 is obtained.

              It is possible to change the implementation. E.g., after

                      Bigint b(5);
                      b = ~b;

              ~b could be implemented so that it results in the value -6. But this too  leads  to
              unexpected  results.  While  5 & ~5 == 0, this would no longer hold true for BigInt
              objects: Assuming b contains 5  then  b  &  ~b  would  expand  to  (binary)  101  &
              (negative)110 which equals (binary) 100.

              Since either implementation produces unexpected results BigInt::operator~() was not
              implemented. Instead two members are offered: tildeBits(), toggling all the bits of
              all the BigInt bytes and toggling its sign (so

                      Bigint b(5);
                      b.tildeBits();

              changes  b’s  value into -250), and tildeInt() changing the object’s value into the
              value that would have been obtained if a BigInt was a mere int (so

                      Bigint b(5);
                      b.tildeInt();

              changes b’s value into -6).

       Binary operators:

       o      BigInt operator*(BigInt const &lhs, BigInt const &rhs):

       o      BigInt operator/(BigInt const &lhs, BigInt const &rhs):
              This operator returns the quotient of the lhs object divided by the rhs object. The
              remainder  is  lost  (The  member div performs the division and makes the remainder
              available as well).

       o      BigInt operator%(BigInt const &lhs, BigInt const &rhs):

       o      BigInt operator+(BigInt const &lhs, BigInt const &rhs):

       o      BigInt operator-(BigInt const &lhs, BigInt const &rhs):

       o      BigInt operator<<(BigInt const &lhs, size_t nBits):
              See also the lshift members. If lhs is positive,

       o      BigInt operator>>=(BigInt const &lhs, size_t nBits):
              See also the rshift members.

       o      BigInt operator&(BigInt const &lhs, BigInt const &rhs):
              This operator returns a BigInt value consisting of the  bit_and-ed  bits  and  sign
              flags  of  lhs  and  rhs  operands.  Consequently,  if one operand is positive, the
              resulting value will be positive.

       o      BigInt operator|(BigInt const &lhs, BigInt const &rhs):
              This operator returns a BigInt value consisting of  the  bit_or-ed  bits  and  sign
              flags  of  lhs  and  rhs operands. Consequently, if either operand is negative, the
              result will be negative.

       o      BigInt operator^(BigInt const &lhs, BigInt const &rhs):
              This operator returns a BigInt value consisting of the  bit_xor-ed  bits  and  sign
              flags  of  lhs  and rhs operands. Consequently, if exactly one operand is negative,
              the result will be negative.

       (Arithmetic) assignment operator(s):

       o      BigInt &operator=(BigInt const &rhs):

       o      BigInt &operator*=(BigInt const &rhs):

       o      BigInt &operator/=(BigInt const &rhs):
              This operator assigns the result of the (integer) division of  the  current  BigInt
              object  by ths to the current object. The remainder is lost. The member div divides
              and makes the remainder available as well.

       o      BigInt &operator%=(BigInt const &rhs):

       o      BigInt &operator+=(BigInt const &rhs):

       o      BigInt &operator-=(BigInt const &rhs):

       o      BigInt &operator<<=(size_t nBits):
              See also the lshift members.

       o      BigInt &operator>>=(size_t nBits):
              See also the rshift members.

       o      BigInt &operator&(BigInt const &rhs):
              This operator bit_ands the bits and sign flags of the current object  and  the  rhs
              operand.

       o      BigInt &operator|(BigInt const &rhs):
              This  operator  bit_ors  the  bits and sign flags of the current object and the rhs
              operand.

       o      BigInt &operator^(BigInt const &rhs):
              This operator bit_xors the bits and sign flags of the current object  and  the  rhs
              operand.

STATIC MEMBERS

       All  members  returning  a  BigInt  computed  from a set of arguments and not requiring an
       existing BigInt object are defined as static members.

       o      BigInt fromText(std::string text, int mode = 0):
              This member converts a textual representation  of  a  number  to  a  BigInt  value.
              Conversion  continues  until  the  end  of  text or until a character outside of an
              expected range is encountered.

              The expected range may be preset by  specifying  mode  as  ios::dec,  ios::oct,  or
              ios::hex  or  (the  default) the expected range is determined by fromText itself by
              inspecting the characters in text.

              By default if text contains hexadecimal characters then fromText assumes  that  the
              number  is  represented  as  a  hexadecimal  value (e.g., "abc" is converted to the
              (decimal) value 2748); if text starts with 0 and contains only  characters  in  the
              range  0  until (including) 7 then fromText assumes the number is represented as an
              octal value (e.g., "01234" is converted to the (decimal) value  668).  Otherwise  a
              decimal value is assumed.

              If  the  text  does  not represent a valid numerical value (of the given extraction
              mode) then a FBB::Errno exception is thrown (fromText: text does  not  represent  a
              BigInt value).

       o      BigInt rand(size_t size, Msb msb = MSB_IS_ONE, Lsb lsb = ODD):
              This  member  returns a cryptographically strong pseudo-random number of size bits.
              The most significant bit(s) can be controlled by msb (by default  MSB_IS_ONE),  the
              least  significant  bit  can  be controlled by lsb (by default ODD). Before calling
              this member the random number generator must have been seeded.

       o      BigInt randRange(BigInt const &max):
              This member returns a cryptographically strong pseudo-random number in the range  0
              <=  number  < max. Before calling this member the random number generator must have
              been seeded.

       o      BigInt setBigEndian(std::string const &bytes):
              The bytes.length() bytes of bytes are used to compute  a  BigInt  object  which  is
              returned  by  this function. The characters in bytes are interpreted as a series of
              bytes in big-endian order. See also the  member  function  bigEndian()  above.  The
              returned BigInt has a positive value.

       o      BigInt  prime(size_t nBits, BigInt const *mod = 0, BigInt const *rem = 0, PrimeType
              primeType = ANY):
              This member returns a prime number of bBits bits. If both mod and rem are non-zero,
              the  condition  prime % mod == rem.  (E.g., use prime % mod == 1 in order to suit a
              given generator). The parameter primeType can be ANY, (prime - 1) / 2  may  or  may
              not  be  a  prime.  If  it is SAFE then  (prime - 1) / 2 will be a (so-called safe)
              prime.

       o      BigInt pseudoRand(size_t size, Msb msb = MSB_IS_ONE, Lsb lsb = ODD):
              This member returns a potentially predictable pseudo-random number  of  size  bits.
              The  most  significant bit(s) can be controlled by msb (by default MSB_IS_ONE), the
              least significant bit can be controlled by lsb (by default ODD). It can be used for
              non-cryptographic purposes and for certain purposes in cryptographic protocols, but
              usually not for key generation.

       o      BigInt pseudoRandRange(BigInt const &max):
              This member returns a potentially predictable  pseudo-random number in the range  0
              <= number < max.

FREE FUNCTIONS IN THE FBB NAMESPACE

       o      std::ostream &operator<<(ostream &out, BigInt const &value):
              Inserts  value  into the provided ostream. If the hex manipulator has been inserted
              into the stream before inserting the BigInt value the value will be displayed as  a
              hexadecimal  value (without a leading 0x); if the oct manipulator has been inserted
              the value will be represented as an octal value (starting with a 0). The value will
              be  displayed  as  a  decimal value if the dec manipulator is active. If the BigInt
              value is negative its value will be preceded by a minus character.

       o      std::istream &operator>>(istream &in, BigInt &value):
              Extracts value from the provided istream. Depending on the currently set extraction
              mode  (dec,  oct,  or hex) the matching set of characters will be extracted from in
              and converted to a number which is stored in value. Extraction stops at EOF  or  at
              the  first  character  outside  of  the range of characters matching the extraction
              mode. if no numerical characters were extracted the stream’s failbit  is  set.  The
              extracted  value  may  be  preceded by a minus character, resulting in an extracted
              negative value.

EXAMPLE

       #include <iostream>
       #include <bobcat/bigint>

       using namespace std;
       using namespace FBB;

       int main(int argc, char **argv)
       {
           BigInt value(BigInt::prime(100));
           BigInt mod(BigInt::rand(50));
           BigInt inverse(value.inverseModc(mod));

           cout << ’(’ << value << " * " << inverse << ") % " << mod << " = " <<
                    (    value       *      inverse     ) %      mod << endl;
       }

FILES

       bobcat/bigint - defines the class interface

SEE ALSO

       bobcat(7), RAND_seed(3)

BUGS

       None Reported.

DISTRIBUTION FILES

       o      bobcat_2.20.01-x.dsc: detached signature;

       o      bobcat_2.20.01-x.tar.gz: source archive;

       o      bobcat_2.20.01-x_i386.changes: change log;

       o      libbobcat1_2.20.01-x_*.deb: debian package holding the libraries;

       o      libbobcat1-dev_2.20.01-x_*.deb: debian package holding the libraries,  headers  and
              manual pages;

       o      http://sourceforge.net/projects/bobcat: public archive location;

BOBCAT

       Bobcat is an acronym of `Brokken’s Own Base Classes And Templates’.

COPYRIGHT

       This  is  free  software,  distributed  under  the terms of the GNU General Public License
       (GPL).

AUTHOR

       Frank B. Brokken (f.b.brokken@rug.nl).