pow function and long int causing problems

Question

I am trying to impliment RSA encryption scheme. It goes something like this:

encrypted data = ((message)^e) % n and decrypted data = ((encrypted data)^d) % n

I tried to implement this in c. Here is the code :

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int main(){

    long int num = 3255859; 
    long int encrypt =(int)pow((double) num,3) % 33;
    printf("%ld\n",encrypt);

    return 0;

}

I compiled this using gcc -Werror -g -o encrypt encrypt.c -lm

This is the output I get = -2, which is obviously wrong. When i try this code for smaller numbers, I get the right result. For eg:

when I set num = 2, I get the right result which is 8

I know I am either type casting wrong or I am running out of boundaries somewhere. I do need to use this code to encrypt large numbers like the one in the code above.

Could you please point out where I am going wrong.

Thanks

EDIT:

Ok as per suggestion from @Micael Oliver here is the modified code:

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int main(){

    unsigned long long  num = 3255859; 

    long long encrypt =(long long)pow((double) num,3) % 33;

    printf("%llu\n",encrypt);

    long long decrypt =(long long)pow((double) encrypt,7) % 33;

    printf("%llu\n",decrypt);

    return 0;

}

here is the output of this code :

Notra:Desktop Sukhvir$ gcc -Werror -g -o encrypt encrypt.c -lm
Notra:Desktop Sukhvir$ ./encrypt
18446744073709551608
18446744073709551614

which is obviously wrong as the 2nd outpt should have been 3255859

Answer 1

You've got a bit of a mix of unsigned and signed numbers in your code - you should try to avoid this when possible. Also you're attempting to use %llu on a signed long long - you should use %lld in this case.

But there is a more subtle problem in play here. In this line:

long long encrypt =(long long)pow((double) num,3) % 33;

pow returns a double, which won't guarantee all the precision you're looking for. You're going to end up losing a few digits when you cast to long long. Unfortunately C doesn't provide a good alternative for computing exponentials, so you'll need to implement something yourself or use a library (some of the other answers have suggested some).

If you want to implement one yourself, a great article on fast exponentiation by squaring can be found on Wikipedia here: Exponentiation by squaring

They provide some pseudo-code that should be obvious for coding in C.

But lastly, in general your code is going to be limited by the size of long long, or whatever type you choose. Ultimately for large numbers you should use some other library, or find a better algorithm. In this case, you're computing a power and then taking a modulus - which is exactly what Modular Exponentation algorithms can accomplish without having to deal with these libraries. You can find a Wikipedia article here: Modular Exponentiation

Answer 2

one suggestion was to use another datatype like long long:

3255859^3 ==  34514116960466804779
ULLONG_MAX == 18446744073709551615  // this is the minimum guaranteed

So, unsigned long long may not work. In general changing datatypes has limits. Another more robust approach you can consider is to use GMP - free. gmp manual --

-- you can download gmp at this site as well.

code snippet:

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <gmp.h>

int main()
{
    mpz_t rop, base, exp, mod;
    mpz_init2(rop,128); 
    mpz_init2(base,128); 
    mpz_init2(exp,128); 
    mpz_init2(mod,128);
    mpz_set_ui(base, 3255859);
    mpz_set_ui(exp, 3);
    mpz_set_ui(mod, 33);
    mpz_powm_sec (rop, base, exp, mod);
    gmp_printf ("result %Zd\n", rop);    
    return 0;
}

Answer 3

As long as your numbers are at most half the size of the type you're working in, you can do something like this:

(((num * num) % 33) * num) % 33

In general, for anything practical for cryptographic purposes, you'll need much larger values and a computational framework to work with 1024+ bit numbers. For this you can use existing code (I would recommend libtommath from libtomcrypt, definitely not GMP) or write your own.