C语言RSA解密异常：无法获取正确明文求助

问题背景 #

假设你已知我的RSA公钥，模数n = 16076635963，公钥指数e = 456233，且截获了用该公钥加密的密文5395334961，请解密该消息。
注：消息采用ASCII编码。

你遇到的乱码问题由两个原因导致：私钥d计算错误，以及字节输出顺序颠倒。

参数错误分析 #

你给出的私钥d=3693459617不满足RSA核心条件e*d ≡1 mod φ(n)（其中φ(n)=(p-1)(q-1)=123340*130342=16076382280）。通过扩展欧几里得算法计算，正确的私钥d应为10382922663。

代码逻辑问题 #

你的解密函数从最低位字节开始输出，而ASCII字符串遵循高位字节在前的顺序，导致输出的明文是反向的。

修正后的代码 #

#include <stdio.h>

unsigned long long mod_exp(unsigned long long base, unsigned long long exponent, unsigned long long modulus) {
    unsigned long long result = 1;
    while (exponent > 0) {
        if (exponent & 1) {
            result = (result * base) % modulus;
        }
        base = (base * base) % modulus;
        exponent >>= 1;
    }
    return result;
}

void decrypt_message(unsigned long long encrypted_message, unsigned long long private_key, unsigned long long modulus) {
    unsigned long long decrypted_message = mod_exp(encrypted_message, private_key, modulus);

    printf("Decrypted Message: ");
    // 先收集所有字节到数组
    unsigned char bytes[8];
    int byte_count = 0;
    while (decrypted_message > 0) {
        bytes[byte_count++] = decrypted_message & 0xFF;
        decrypted_message >>= 8;
    }
    // 反向输出字节，还原正确的ASCII顺序
    for (int i = byte_count - 1; i >= 0; i--) {
        printf("%c", bytes[i]);
    }
    printf("\n");
}

int main() {
    unsigned long long modulus = 16076635963;
    unsigned long long private_key = 10382922663; // 修正后的私钥
    unsigned long long encrypted_message = 5395334961;

    decrypt_message(encrypted_message, private_key, modulus);

    return 0;
}

运行结果 #

修正后运行代码，将输出正确的明文：Helo

内容的提问来源于stack exchange，提问作者user3587527