0

I'm implementing RSA in C. I'm using "unsigned long long int" (Top limit: 18446744073709551615).

The problems come when I have to calculate thing like 4294967296 ^ 2. It should be 18446744073709551616, but I get 0 (overflow). I mean, I need to calculate things that result is over the top limit.

I've tried using float, double, long double, but the results are incorrect.

Example: 

4294967000.0 * 4294967000.0 the result is 18446741874686296064.0
but it should be 18446741531089000000
user1211
  • 1,507
  • 1
  • 18
  • 27
Alan
  • 1
  • 1
  • 2
  • 2
    If you need multiple-precision arithmetic (and you do), you need to write or obtain a multiple-precision library. There are various ones available — [GMP](https://gmplib.org/) for example, and in the [OpenSSL](https://openssl.org/) libraries. Or you can consult Knuth and write your own. – Jonathan Leffler Aug 06 '17 at 02:12
  • 2
    It is quite simple to implement a basic big integer library, see for example https://github.com/libtom/libtommath which has some excellent documentation. Search for `tommath.pdf` if you want the documentation only or cannot build it from source. It has a couple of fast modular functions in it that useful for encryption (because they were written for encryption). Shameless plug: an extended version including more optimizations for multiplication, fast divisions and a lot more is here: https://github.com/czurnieden/libtommath – deamentiaemundi Aug 06 '17 at 02:30
  • 1
    Looks to be duplicate of [this](https://stackoverflow.com/questions/2252896/how-to-store-a-very-long-integer-value-in-a-c-program-for-an-exam-98474737475?rq=1) – Milind Deore Aug 06 '17 at 03:09

3 Answers3

1

Openssl example:

#include <stdio.h>
#include <openssl/bn.h>
/* compile with -lcrypto */
int main ()
{
 char p_sa[] = "4294967296";
 char p_sb[] = "4294967296";
 BN_CTX *c = BN_CTX_new();
 BIGNUM *pa = BN_new();
 BIGNUM *pb = BN_new();
 BN_dec2bn(&pa, p_sa);
 BN_dec2bn(&pb, p_sb);
 BN_mul (pa,pb, pa,c);
 char * number_str = BN_bn2hex(pa);
 printf("%s\n", number_str);
 OPENSSL_free(number_str);
 BN_free(pa);
 BN_free(pb);
 BN_CTX_free(c);
 return 0;
}
0

"implementing RSA" + "I have to calculate thing like 4294967296 ^ 2" is contradictory. To implement RSA, that calculation is not needed. The algorithm does not need wider than 64-bit integers.

I've tried using float, double, long double, but the results are incorrect.

4294967000.0 * 4294967000.0 the result is 18446741874686296064.0

Use unsigned long long math. Typical double has only 53 bits of precision, yet this calculation needs 60+ bits for a precise product.

int main(void) {
  unsigned long x = 4294967000;
  printf("%lu * %lu the result is %lu\n", x,x,x*x);  // overflow
  printf("%lu * %lu the result is %llu\n", x,x,(unsigned long long) (x*x)); // overflow
  printf("%lu * %lu the result is %llu\n", x,x,(unsigned long long)x*x);// good 64-bit math
  return 0;
}

Output

4294967000 * 4294967000 the result is 87616
4294967000 * 4294967000 the result is 87616
4294967000 * 4294967000 the result is 18446741531089000000
chux - Reinstate Monica
  • 143,097
  • 13
  • 135
  • 256
0

4294967296 is this:

> witch 4294967296 
witch (c) 1981-2017 Alf Lacis  Build: 20200823.144838

Param ________Hex_______ _______Uns.Dec______
1     0x0000000100000000           4294967296

As you can see, it is already using the bottom bit of byte 5 (01).

If you square this number, it will try to set the bottom bit of byte 9, but there are only 8 bytes in a 64-bit unsigned integer, so the answer, 0, is what the processor believes to be correct. And that's why the value of UINT64_MAX (stdint.h) is 18446744073709551615, not 18446744073709551616.

18446744073709551615 is this in hex:

>witch 18446744073709551615
witch (c) 1981-2017 Alf Lacis  Build: 20200823.144838

Param ________Hex_______ _______Uns.Dec______
1     0xffffffffffffffff 18446744073709551615
Alfredo
  • 3
  • 3