C++ handling very large integers

Asked 2008-09-23T22:32:27.737

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?

Edit Report

3 Answers

I would try out the GMP library - it is robust, well tested, and commonly used for this type of code.

answered 2008-09-23T22:38:58.610

There is more to secure RSA implementation than just big numbers. A simple RSA implementation tends to leak private information through side channels, especially timing (in simple words: computation time depends on the processed data, which allows an attacker to recover some, possibly all, of the private key bits). Good RSA implementations implement countermeasures.

Also, beyond the modular exponentiation, there is the whole padding business, which is not conceptually hard, but, as all I/O and parsing code, has room for subtle bugs. The easiest code to write is the code which has already been written by somebody else.

Another point is that once you have your RSA code up and running, you may begin to envision extensions and other situations, e.g. "what if the private key I want to use is not in RAM but in a smartcard ?". Some existing RSA implementations are actually API which can handle that. In the Microsoft world, you want to lookup CryptoAPI, which is integrated in Windows. You may also want to look at NSS, which is what the Firefox browser uses for SSL.

To sum up: you can build up a RSA-compliant implementation from big integers, but this is more difficult to do correctly than what it usually seems, so my advice is to use an existing RSA implementation.

answered 2010-02-24T22:29:06.823

The fact, that you have a problem using some biginteger library doesn't mean, that it's a bad approach.

Using long long is definitely a bad approach.

As others said already using a biginteger library is probably a good approach, but You have to post more detail on haw you use mentioned library for us to be able to help You resolve those errors.

answered 2008-09-23T23:03:03.840

C++ handling very large integers

3 Answers

Your Answer