C++ handling very large integers


Question

I am using the RSA Algorithm for encryption/decryption, and in order to decrypt the files you have to deal with some pretty big values. More specifically, things like

P = C^d % n
  = 62^65 % 133

Now that is really the only calculations that ill be doing. I have tried using Matt McCutchen's BigInteger Library, but I am getting a lot of compiler errors during linking, such as:

encryption.o(.text+0x187):encryption.cpp: undefined reference to `BigInteger::BigInteger(int)'

encryption.o(.text+0x302):encryption.cpp: undefined reference to `operator<<(std::ostream&, BigInteger const&)'

encryption.o(.text$_ZNK10BigIntegermlERKS_[BigInteger::operator*(BigInteger const&) const]+0x63):encryption.cpp: undefined reference to `BigInteger::multiply(BigInteger const&, BigInteger const&)'

So I was wondering what would be the best way to go about handling the really big integers that come out of the RSA Algorithm.

I heard that a possibility would be to declare your variables as a double long, so...

long long decryptedCharacter;

but I'm not sure exactly how big of an integer that can store.


Well for example, I try to compile and run the following program using dev C++:

#include iostream

#include "bigint\BigIntegerLibrary.hh"

using namespace std;

int main()
{
    BigInteger a = 65536;
    cout << (a * a * a * a * a * a * a * a);
    return 0;
}

then I get those errors.

Derek, I thought that by including the BigIntegerLibrary.hh file, that the compiler would go through and compile all the necessary files that it will use.

How should I try and compile the program above in order to resolve the linking errors?

1
20
11/1/2011 2:40:52 PM

Meta-answer:

If you're using a library for the bigint arithmetic, then ask yourself why you aren't using a library for the whole RSA implementation.

For example, http://www.gnu.org/software/gnu-crypto/ contains an RSA implementation. It has the same license as GMP.

However, they do not have the same license as http://mattmccutchen.net/bigint/, which appears to me to have been placed into the public domain in the US.

23
9/23/2008 11:05:55 PM

Licensed under: CC-BY-SA with attribution
Not affiliated with: Stack Overflow
Icon