C - RSA 加密系统解密问题(unsigned long long 不够大？)

Question

我正在做一项任务，必须构建 RSA 加密系统。我能够毫无问题地加密 key ，但是由于指数的结果太大，我在解密它时遇到了麻烦。我尝试过使用 unsigned long long int 但输出仍然为 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);
}

我应该补充一点，教授没有提到使用大数字库，所以我确信我们很可能不应该在这项作业中使用一个大数字库。

Answer 1

无符号 64 位整数的最大值为 18,446,744,073,709,551,615

但是，1394^2011 更接近于 1.296 x 10^6323。这比无符号 64 位整数的最大值大 7.02 x 10^6303 倍。

TL;DR:使用 BigInteger 库，一个非常大的库。

说实话，RSA 可以计算如此大的幂的主要原因是因为 RSA 在模数下运行，所以如果我们使用 Modular Exponentiation ，我们需要更少的计算能力来达到结果。通过将明文计算为指数然后在最后应用模数来计算结果在计算上是不可行的。