C - RSA Cryptosystem Decryption Issue (unsigned long long not big enough?)

Question

I'm working on an assignment where I have to build an RSA Cryptosystem. I was able to encrypt the cipher key no problem however I'm having trouble decrypting it due to the result of the exponent being so large. I've tried using unsigned long long int but I'm still getting an output of 0.

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

//Unsigned long long int power function
unsigned long long getPower(unsigned long long int base, int exponent){
    unsigned long long result = 1;
    int count = 0;

    while(count != exponent){
        result *= base;
        count++;
    }

    return result;
}

int decryptFile(int cipherInt, int n, int d){
    int plainInt;
    unsigned long long int cipherIntLong = cipherInt;
    unsigned long long int power = getPower(cipherIntLong, d);

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

    return (int) plainInt;
}

int main(){
    decryptFile(1394, 3127, 2011);
}

I should add that the professor made no mention of using a big number library so I'm sure we are most likely not supposed to use one for this assignment.

Answer 1

The maximum value of an unsigned 64-bit integer is 18,446,744,073,709,551,615

However, 1394^2011 is more around 1.296 x 10^6323. That is 7.02 x 10^6303 times larger than the maximum value of an unsigned 64-bit integer.

TL;DR: Use a BigInteger library, a really big one.

Seriously though, the main reason RSA can compute such large powers is because RSA operates under a modulus, so if we use Modular Exponentiation, we require far less computational power to reach the result. Calculating the result by raising the plaintext to the exponent and then applying the modulus at the end isn't computationally feasible.