c++ - C++ 中的 RSA 加密

Question

我想使用其 ASCII 值将字符加密（RSA）为整数。例如。'a' 被加密为 48。

对于加密：c=pow(m,e)%n其中 c 是密文，m 是明文，(e,n) 是公钥。

如果 pow(m,e) 很大，比如 67^7，则它不适合int或long。但是如果我使用double，我不能将它与模数 % 运算符一起使用。所以我使用for循环编写了这个加密函数：

int encrypt(int m, int e, int n)
{
    int res=m, i;
    for(i=0; i<e-1;i++)
        res=(res*res)%n;
    return res;
}

它适用于 67^7mod11，即 67，但后来我知道它实际上并不正确。我哪里出错了？

score 5 · Accepted Answer

你的循环

for(i=0; i<e-1;i++)
    res=(res*res)%n;

平方e-1乘以模数n，这意味着它计算m^(2^(e-1))模数n。要使用简单算法计算m^e模数n，请使用

for(i = 0; i < e-1; ++i)
    res = (res*m) % n;

反而。

对于指数较大时稍快的算法，您可以通过重复平方来使用取幂：

res = 1;
while (e > 0) {
    if (e % 2 != 0) {
        res = (m*res) % n;
    }
    m = (m*m) % n;
    e /= 2;
}
return res;

score 0 · Accepted Answer

通常在使用加密参数时，您使用“big int”而不是 int。正是因为这个原因。

这里有一些建议： Bigint (bigbit) library

2 回答 2