C++ handling very large integers

Question

Hey everyone,

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.

(stuff like: 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 im not sure exactly how big of an integer that can store

Thanks in advnace,

Tomek

Answer 1

A long int is typically 64 bits which would probably not be enough to handle an integer that large. You'll probably need a bigint library of some kind.

See also this question on Stack Overflow

Answer 2

To see the size of a long long try this:

#include <stdio.h>

int main(void) {
    printf("%d\n", sizeof(long long));

    return 0;
}

On my machine it returns 8 which means 8 bytes which can store 2^64 values.

Answer 3

Check out your compiler documentation. Some compilers have types defined such as __int64 that give you their size. Maybe you've got some of them available.

Answer 4

Just to note: __int64 and long long are non-standard extensions. Neither one is guaranteed to be supported by all C++ compilers. C++ is based on C89 (it came out in 98, so it couldn't be based on C99)

(C has support for 'long long' since C99)

By the way, I don't think that 64bit integers solve this problem.

Answer 5

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

Answer 6

I'd suggest using gmp, it can handle arbitrarily long ints and has decent C++ bindings.

afaik on current hardware/sofware long longs are 64bit, so unsigned can handle numbers up to (2**64)-1 == 18446744073709551615 which is quite a bit smaller than numbers you'd have to deal with with RSA.

Answer 7

For RSA you need a bignum library. The numbers are way too big to fit into a 64-bit long long. I once had a colleague at university who got an assignment to implement RSA including building his own bignum library.

As it happens, Python has a bignum library. Writing bignum handlers is small enough to fit into a computer science assignment, but still has enough gotchas to make it a non-trivial task. His solution was to use the Python library to generate test data to validate his bignum library.

You should be able to get other bignum libraries.

Alternatively, try implementing a prototype in Python and see if it's fast enough.

Answer 8

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.

Answer 9

Tomek, it sounds like you aren't linking to the BigInteger code correctly. I think you should resolve this problem rather than looking for a new library. I took a look at the source, and BigInteger::BigInteger(int) is most definitely defined. A brief glance indicates that the others are as well.

The link errors you're getting imply that you are either neglecting to compile the BigInteger source, or neglecting to include the resulting object files when you link. Please note that the BigInteger source uses the "cc" extension rather than "cpp", so make sure you are compiling these files as well.

Answer 10

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.

Answer 11

Well for example, I try to compile&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?

-Tomek

Answer 12

If you're not implementing RSA as a school assignment or something, then I'd suggest looking at the crypto++ library http://www.cryptopp.com

It's just so easy to implement crypto stuff badly.

Answer 13

I have had a lot of success using the LibTomCrypt library for my crypto needs. It's fast, lean, and portable. It can do your RSA for you, or just handle the math if you want.

Answer 14

Openssl also has a Bignum type you can use. I've used it and it works well. Easy to wrap in an oo language like C++ or objective-C, if you want.

https://www.openssl.org/docs/crypto/bn.html

Also, in case you didn't know, to find the answer to the equation of this form x^y % z, look up an algorithm called modular exponentiation. Most crypto or bignum libraries will have a function specifically for this computation.

Answer 15

I used GMP when I wrote the RSA implementation.

Answer 16

Here is my approach, it combines fast exponentation using squaring + modular exponentation which reduces the space required.

long long mod_exp (long long n, long long e, long long mod)
{
  if(e == 1)
  {
       return (n % mod);
  }
  else
  {
      if((e % 2) == 1)
      {
          long long temp = mod_exp(n, (e-1)/2, mod);
          return ((n * temp * temp) % mod);
      }
      else
      {
          long long temp = mod_exp(n, e/2, mod);
          return ((temp*temp) % mod); 
      }
  }
}

Answer 17

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.