时间戳

首页 > 解决方案 > RSA 解密产生错误结果

c++ - RSA 解密产生错误结果

问题描述

我正在尝试实施 RSA 加密，每当实施解密部分时，我都会得到错误的答案。

加密之前的所有内容都给了我正确的值：n 是 187，phi 是 160，e 是 3，私钥 d 是 107，密文 c 是 183。然后，我首先计算 c^d（这给了我 -9223372036854775808 ) 然后对该结果执行 mod(n) 以获得 -162（假定解密）。

我认为错误出现在 c^d 部分，但我无法确定出了什么问题。任何帮助，将不胜感激。

int main()
{
    long p = 11;
    long q = 17;
    long n = p * q;

    double phi = (p-1) * (q-1);
    int e = 3;

    while(e < phi) {
        if(GCD(e, phi) == 1) break; //GCD is a function that returns the GCD
        else e++;
    }

    int k = 2;
    // private key computation
    double d = (1+(k*phi))/e;

    double msg = 72;

    long c = pow(msg, e);
    // c mod(n)
    c %= n;

    long decr = pow(c, d); 
    decr %= n;

    return 0;
}

标签： c++encryptionrsa

解决方案

您可以使用以下代码来计算模数（O(n)复杂度）

//Compute a^b mod n
int powermod(int a, int b, int n) {
    int result = 1;
    for (int i=1;i<=b;++i) {
       result *= (a%n);
       result %= n;
    }
    return result%n;
}

您可以以类似于计算指数模的方式修改快速功率。它使用以下公式

a^b mod n = (a mod n)^b mod n

推荐阅读