c++ - RSA 解密失败

Question

我正在尝试实现 RSA 加密方案，但虽然我的加密值似乎是正确的，但解密的值却不是。根据我得到的 p、q 等值，计算部分(IE，困难部分)似乎很好，并且消息似乎正在正确加密(以防万一我将加密部分包括为好吧)。请注意，我应该在没有任何库的情况下执行此操作(我已经使用 GMP 编写了它)，所以这就是我使用不切实际的小数字的原因。

int main()
{
    ...
    vector<uint64_t> encrypted = doEncrypt(e, n);
    doDecrypt(d, n, encrypted);
}
vector<uint64_t> doEncrypt(unsigned int e, unsigned int n)
{
    string message;
    vector<uint64_t> encrypted;
    cout << "Public key is <" << e << ", " << n << ">.\nPlease enter a message to encrypt: ";
    getline(cin, message);
    for (unsigned int i = 0; i < message.length(); i++)
        encrypted.push_back(encrypt(message[i], e, n));
    return encrypted;
}
uint64_t encrypt(char message, unsigned e, unsigned int n)
{
    int toencrypt = (int)message;
    cout << toencrypt << ' ';
    uint64_t result = pow64(toencrypt, e);
    return result%n;
}
void doDecrypt(unsigned int d, unsigned int n, vector<uint64_t> encrypted)
{
    cout << "Encrypted message is: ";
    for (unsigned int i = 0; i < encrypted.size(); i++)
    cout << encrypted[i] << ' ';
    cout << "\nDecrypted message is: ";
    char out;
    for (unsigned int i = 0; i < encrypted.size(); i++){
        decrypt(out, encrypted[i], d, n);
        cout << out << ' ';//This is only for diagnostics, I will
                       //take out the printing of the decrypted
                       //number and space later
    }
    cout << endl;
}

void decrypt(char& decrypted, uint64_t message, unsigned int d, unsigned int n)
{
    uint64_t decrypt = (pow64(message, d)%n);
    cout << decrypt;
    decrypted = (char)decrypt;
}

uint64_t pow64(uint64_t base, unsigned int ex)
{
    uint64_t back = 1;
    for (unsigned int i = 0; i < ex; i++)
        back = back * base;
    return back;
}

示例输出:

p = 23
q = 23
n = 529
phi_n = 484
e = 9
d = 269
公钥是<9, 529>。
请输入要加密的信息:dog
100 111 103 加密信息为:515 33 295
解密后的消息是:523 417▒ 364l

Answer 1

你的问题是 p == q，所以 n 是一个完全平方而不是两个素数的乘积，这意味着你对 phi(n) 的计算是错误的。 phi(p^2) == p * (p-1) 其中 p 是素数。因此，如果您将代码更改为使用 phi(n) == 506 和 d == 225，它应该可以工作。

或者选择一个不同的 p 和 q。

使用小质数测试代码时要担心的另一个陷阱——如果明文值是 p 或 q 的倍数，加密/解密将失败。当对 p 和 q 使用实数值(256 位或更多)时，这种情况极不可能发生，但对于如此小的值，可能会偶然发生。命中此问题的概率与对手随机猜测您的私有(private)因素的概率相同。

可能发生的第三个陷阱是，您选择的公共(public)指数 e 不能与 phi(n) 有任何共同因子，或者没有有效的 d 解码指数将存在。同样，这与“真正的”RSA key 无关，因为 (p-1)/2 和 (q-1)/2 应该是质数，所以只要 e 是奇数，没有有效解密 key 的可能性微乎其微。

编辑

您的代码存在一个问题，即您的 pow64 例程很容易溢出(515^269 超过 2000 位)。尝试使用:

uint64_t pow64(uint32_t base, uint32_t ex, uint32_t n)
{
    uint64_t back = 1;
    for (unsigned int i = 0; i < ex; i++)
        back = (back * base) % n;
    return back;
}

请注意，我将输入值限制为 uint32_t，因此中间乘法永远不会溢出 64 位。这也非常低效——你最好一次对基数进行平方并通过指数:

uint64_t pow64(uint32_t base, uint32_t ex, uint32_t n)
{
    uint64_t back = 1;
    for (uint64_t i = 1; i <= ex; i <<= 1) {
        if (i & ex)
            back = (back * base) % n;
        base = ((uint64_t)base * base) % n; }
    return back;
}