C - RSA 密码系统解密问题（unsigned long long 不够大？）

Question

我正在完成一项必须构建 RSA 密码系统的任务。我能够毫无问题地加密密码密钥，但是由于指数太大，我无法解密它。我试过使用 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，我们需要更少的计算能力来获得结果。通过将明文提高到指数然后在最后应用模数来计算结果在计算上是不可行的。

C - RSA 密码系统解密问题（unsigned long long 不够大？）

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

c

encryption

rsa

unsigned-long-long-int