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?

If at all possible, never write your own crypto routines except for fun or learning. There's an appalling amount of non-obvious things you can get wrong. — David Thornley, Feb 24 '10 at 22:45
To calculate A^B mod C, there's no need to do the real power, use [modular exponentiation](https://en.wikipedia.org/wiki/Modular_exponentiation). There are lots of questions about this here: http://stackoverflow.com/questions/8496182/calculating-powa-b-mod-n?lq=1 http://stackoverflow.com/questions/8287144/modulus-power-of-big-numbers?lq=1 — phuclv, May 30 '14 at 04:29
http://stackoverflow.com/questions/2207006/modular-exponentiation-for-high-numbers-in-c?rq=1 — phuclv, May 30 '14 at 04:29
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. — Steve Jessop, Sep 23 '08 at 23:05

score 14 · Answer 1 · answered Sep 23 '08 at 23:03

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.

score 13 · Answer 2 · answered Sep 23 '08 at 22:43

13

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.

answered Sep 23 '08 at 22:43

TFKyle

856
6
12

6

64bit numbers are insignificant to the RSA security requirements. 1024bit is the minimum while 2048bit and 4096 are recommended. – Viet May 15 '10 at 07:37

score 3 · Answer 3 · answered Sep 23 '08 at 22:36

3

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.

answered Sep 23 '08 at 22:36

Paige Ruten

172,675
36
177
197

score 3 · Answer 4 · answered Sep 23 '08 at 22:38

3

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

answered Sep 23 '08 at 22:38

Greg Hewgill

951,095
183
1,149
1,285

score 3 · Answer 5 · answered Sep 23 '08 at 22:46

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.

score 3 · Answer 6 · answered Sep 23 '08 at 23:45

3

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.

answered Sep 23 '08 at 23:45

tfinniga

6,693
3
32
37

score 3 · Answer 7 · answered Feb 24 '10 at 22:10

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); 
      }
  }
}

score 3 · Answer 8 · answered Feb 24 '10 at 22:29

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.

score 2 · Answer 9 · answered Sep 24 '08 at 17:58

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.

score 1 · Answer 10 · edited May 23 '17 at 12:34

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

edited May 23 '17 at 12:34

Community

1
1

answered Sep 23 '08 at 22:36

Adam Pierce

33,531
22
69
89

score 1 · Answer 11 · answered Sep 23 '08 at 22:36

1

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.

answered Sep 23 '08 at 22:36

Scott Langham

58,735
39
131
204

David Ameller · Answer 12 · 2008-09-23T22:45:21.013

1

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.

edited Sep 23 '08 at 22:45

answered Sep 23 '08 at 22:38

David Ameller

1,774
3
18
25

C++ actually dates back to the early '80s, although you're right in that the current standard predates C99. – Captain Segfault May 18 '09 at 21:07
This is technically true, albeit somewhat irrelevant to the situation at hand. OTOH, the question specifically mentioned "long long", so I don't know where the downvote came from. +1 to counteract. PS @CaptainSegfault C++ was first standardized in '98, and the standard was based upon the ISO C standard of 1990 (i.e. C89). – Derrick Turk Feb 25 '10 at 13:19

adum · Answer 13 · 2012-07-03T19:06:35.037

1

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.

edited Jul 03 '12 at 19:06

answered Sep 24 '08 at 00:03

adum

2,890
3
25
30

score 0 · Answer 14 · answered Sep 23 '08 at 23:03

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.

score 0 · Answer 15 · answered May 18 '09 at 19:26

0

I used GMP when I wrote the RSA implementation.

answered May 18 '09 at 19:26

Vaibhav Bajpai

16,374
13
54
85

C++ handling very large integers

15 Answers15

Linked

Related