Integer

From Crypto++ Wiki
Jump to navigation Jump to search
Integer
Documentation
#include <cryptopp/integer.h>

Crypto++ supplies a high performance Integer class. The class is used with nearly all public/private key cryptography, and can be used with general number theoretic operations. This class can represent positive and negative integers with absolute value less than [math]\displaystyle{ 256^{sizeof(word)^{256^{sizeof(int)}}} }[/math]. On a machine with 32-bit int, the value is [math]\displaystyle{ 256^{sizeof(word)^{4294967296}} }[/math].


Documentation for the Integer class is available at Integer Class Reference. The source files with annotated documentation are available online at integer.h and integer.cpp.

Also see the Integer Patch, which adds little-endian support and output base awareness to the Integer class.

Creating Integers

Integers can be constructed and assigned using strings, like 12345, 12345., 0xffffffff and ffffffffh; and from data values, like int and long. Example of doing so are provided below, along with various Integer constructors. 

// Construct an Integer from a base 10 string
Integer a("012345678");
Integer b("012345678.");

// Construct an Integer from a base 16 string
Integer c("0x01234567");
Integer d("01234567h");

// Construct an Integer from a base 8 string
Integer e("01234567o");

// Construct an Integer from a long
long f = 12345678;
Integer g(f);

Constructors

Integer()
  • Creates an integer initialized to 0.
Integer(signed long value)
  • Creates an integer initialized to value.
Integer(Sign s, lword value)
  • Creates an integer and initializes the integer to value. Since lword is unsigned, s is used for sign.
Integer(Sign s, word highWord, word lowWord)
  • Creates an integer and initializes the integer from highWord and lowWord. Since word is unsigned, s is used for sign.
Integer(const char *str)
  • Creates an integer and initializes the integer to str. See StringToInteger below.
Integer(const wchar_t *wstr)
  • Creates an integer and initializes the integer to wstr. See StringToInteger below.
Integer (const byte *encodedInteger, size_t byteCount, Signedness s=UNSIGNED)
  • Creates an integer and initializes the integer to the big-endian byte array encodedInteger.

Crypto++ 5.6.4

Crypto++ 5.6.4 added four overloads that allow you to parse little endian integers as described at Integer Patch. Little-endian support enables the Integer class to construct Integers from strings and byte arrays in little-endian format. Its useful for algorithms like Poly1305 and MS CAPI interop, where many parameters are provided in little-endian format. 

explicit Integer(const char *str, ByteOrder order = BIG_ENDIAN_ORDER)
  • Creates an integer and initializes the integer to str using the byte order specified by order. See StringToInteger below.
explicit Integer(const wchar_t *str, ByteOrder order = BIG_ENDIAN_ORDER)
  • Creates an integer and initializes the integer to wstr using the byte order specified by order. See StringToInteger below.
Integer(const byte *encodedInteger, size_t byteCount, Signedness s=UNSIGNED, ByteOrder o=BIG_ENDIAN_ORDER)
  • Creates an integer and initializes the integer from a byte array encodedInteger with the byte order specified by order.
Integer(BufferedTransformation &bt, size_t byteCount, Signedness s=UNSIGNED, ByteOrder o=BIG_ENDIAN_ORDER)
  • Creates an integer and initializes the integer from a BufferdTransformation bt with the byte count byteCount and order specified by order.

Operations

The Crypto++ Integer class is rich with operations. C++ allows operator overloading, so its relatively easy to write code that follows mathematical formulas.

In addition the header nbtheory.h provides number theoretic optimizations. a_times_b_mod_c and a_exp_b_mod_c are provided in <nbthoery.h> and avoid run-away memory usage for modular multiplication and exponentiation. 

#include <iostream>
#include <iomanip>

#include <integer.h>
#include <nbtheory.h>


int main(int argc, char* argv[])
{
    using namespace CryptoPP;

    Integer m("4294967295"), n("0x1000000000000000000000000000000"), j;
    j = 1999;

    std::cout << "n+m: " << std::hex << n + m << std::endl;
    std::cout << "n-m: " << std::hex << n - m << std::endl;
    std::cout << "n*m: " << std::hex << n * m << std::endl;
    std::cout << "n%m: " << std::hex << n % m << std::endl;

    std::cout << "(n*m)%j:" << std::hex << a_times_b_mod_c(n,m,j) << std::endl; 
    std::cout << "(n^m)%j:" << std::hex << a_exp_b_mod_c(n,m,j) << std::endl; 

    return 0;
}

Compile the program with the following. -DNDEBUG -g2 -O2 is used because that's how the library was built. -I/usr/include/cryptopp is used because that's where the Crypto++ headers are usually placed by a distribution. -L/usr/lib is used because that's where the Crypto++ libraries are usually placed by a distribution. -lcryptopp is used because that's the Crypto++ library. 

g++ -DNDEBUG -g2 -O2 -I/usr/include/cryptopp test.cpp -o test.exe -L/usr/lib -lcryptopp

Then, run the program: 

$ ./test.exe 
n+m: 10000000000000000000000ffffffffh
n-m: ffffffffffffffffffffff00000001h
n*m: ffffffff000000000000000000000000000000h
n%m: 1000000h
(n*m)%j:10ah
(n^m)%j:4feh

Mod Operations

The Operations section provided the simple, Integer-based way to use big integers. Crypto++ also provides a ModularArithmetic to provide operations tailored for finite fields. The header file of interest is modarith.h.

The sample program above using modular arithemetic operations would look as follows. 

#include "integer.h"
#include "modarith.h"

#include <iostream>
#include <iomanip>

int main(int argc, char* argv[])
{
  using namespace CryptoPP;

  Integer m("4294967295"), n("0x1000000000000000000000000000000"), j;
  j = 1999;

  ModularArithmetic ma(j);

  std::cout << "n+m mod j: " << ma.Add(n, m) << std::endl;
  std::cout << "n-m mod j: " << ma.Subtract(n, m) << std::endl;
  std::cout << "n*m mod j: " << ma.Multiply(n, m) << std::endl;
  std::cout << "n/m mod j: " << ma.Divide(n, m) << std::endl;
  std::cout << "n%m mod j: " << ma.Reduce(n, m) << std::endl;
  std::cout << "n^m mod j: " << ma.Exponentiate(n, m) << std::endl;

  return 0;
}

It appears to produce incorrect results for some of the operations: 

$ ./test.exe 
n+m mod j: 1329227995784915872903807064575309872.
n-m mod j: 1329227995784915872903807055985377281.
n*m mod j: 266.
n/m mod j: 599.
n%m mod j: 1329227995784915872903807055985377281.
n^m mod j: 1326.

The reason ModularArithmetic appears to produce incorrect results is the class is meant to be fast for specific problems, and it does not perform a full reduction using the Euclidean extended algorithm. Rather, it performs at most one subtraction. That means the accumulated value n to be reduced by the modulus p must be in the range [0, 2p-1).

Exponentiation

Exponentiation can consume massive amounts of memory if its not a modular exponentiation and the exponent is large. To perform a non-modular exponentiation, then use the following code: 

#include <integer.h>
#include <algebra.h>
...

Integer base = 10, exp = 20;
Integer x = EuclideanDomainOf<Integer>().Exponentiate(base, exp);

std::cout << "10^20: " << std::dec << x << std::endl;

It will produce the expected result of 10^20: 100000000000000000000.

Encode as Byte Array

Sometimes you need to encode an Integer as a byte array. The library will use the Encode function when it needs to convert an Integer to a byte array, like when DER encoding a value. The code below will perform the encoding.

While the code below shows use of a std::vector, you could also use another container class that provides contiguous memory like std::string. 

#include <iostream>
#include <vector>
#include "integer.h"
#include "osrng.h"

int main(int argc, char* argv[])
{
    using namespace CryptoPP;
    
    AutoSeededRandomPool prng;
    Integer n;
    
    n.Randomize(prng, 128);
    size_t len = n.MinEncodedSize(Integer::UNSIGNED);
    
    std::vector<byte> v(len);
    n.Encode((byte*)&v[0], v.size(), Integer::UNSIGNED);

    std::cout << "Iostream: " << std::hex << n << std::endl;
    std::cout << "  Vector: ";
    for(byte i : v) {
      std::cout << std::hex << std::setw(2) << std::setfill('0') << (i & 0xff);
    }
    std::cout << std::endl;

    return 0;
}

Compile the program with the following. 

$ g++ -g2 -O3 test.cxx ./libcryptopp.a -o test.exe

And run the program to show its output. Each run should produce a different result since a random integer is used. 

$ ./test.exe 
Iostream: b32bd756bde62ea5124552714147af6eh
  Vector: b32bd756bde62ea5124552714147af6e

$ ./test.exe 
Iostream: fcbf89617f7f1cf55c1016b2355152e9h
  Vector: fcbf89617f7f1cf55c1016b2355152e9

$ ./test.exe 
Iostream: dea61c1e9e91477a2d88a18478f724ch
  Vector: dea61c1e9e91477a2d88a18478f724c
Retrieved from "https://www.cryptopp.com/w/index.php?title=Integer&oldid=29490"