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但后来我才知道它实际上并不正确.我哪里出错了？

Answer 1

你的循环

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

square e-1times modulo 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;