c++ - RSA 程序只能加密和解密特定范围内的数字

Question

如果我将样本输入作为 p=61,q=53，并且如果我为这个特定的素数集提供一个介于 1 和 21 之间的消息值，我的程序会成功地将消息加密和解密为正确的原始消息。但是，如果我将输入作为 p=61、q=53 并且消息值大于 21，则无法将消息解密回正确的原始消息。

而且不仅仅是这些特定的素数集。对于任何一对素数，只有一定范围的消息值才能正确加密和解​​密。那是为什么呢？谁能建议如何解决这个问题？

class RSA
{
    private:
    long int p,q;
    long int msg,cipherMsg,plainMsg;
    long int n,totient;
    long int  publicKey,privateKey;

    public:
    RSA();
    void ComputeKeys(long int p1,long int p2,long long int message);
    void EncryptMessage();
    void DecryptMessage();

};
RSA :: RSA()
{
    p=0;q=0;
    n=0;totient=0;
    publicKey=0;privateKey=0;
    msg=0;cipherMsg=0;plainMsg=0;
}

void RSA :: EncryptMessage()
{
    int y=1;
    cout<<"Encrypting Message....."<<endl;
    for(long int i=1;i<=publicKey;i++)
    {
        y=y*msg;
    }
    msg=y;
    cout<<"m^e:"<<msg<<endl;
    cipherMsg= msg%n;
    cout<<"Encryption Complete!"<<endl;
    cout<<"Cipher Message:"<<cipherMsg<<endl;
}

void RSA :: DecryptMessage()
{
    long int y= 1,tmp;
    cout<<"Decrypting Message...."<<endl;
    for(long int i=1;i<=privateKey;i++)
    {
        y=y*cipherMsg;
        tmp=y;
        y=fmod(y,n);
    }

    cout<<"c^d:"<<tmp<<endl;
    plainMsg=y;
    cout<<"Decryption Complete!"<<endl;
    cout<<"Original Message:"<<plainMsg<<endl;
}

int main()
{
    RSA obj;
    cout<<"\t------RSA Cryptography------"<<endl;
    obj.ComputeKeys(61,53,21);

    return 0;
}

(请注意，出于专有原因，我没有发布我的 ComputeKeys() 方法。但我相信我需要在此处进行修改。)

Answer 1

对我来说，它看起来像是整数溢出。现在，您正在计算 x^y，并且仅当您完成后，才对该结果进行模 m。

您通常希望利用这样一个事实，即您可以在沿途的每一步取模，以最小化避免溢出所需的大小。

模块化幂函数的代码看起来像这样:

template <class T>
T mul_mod(T a, T b, T m) { 
    if (m == 0) return a * b;

    T r = T();

    while (a > 0) {
        if (a & 1)
            if ((r += b) > m) r %= m;
        a >>= 1;
        if ((b <<= 1) > m) b %= m;
    }
    return r;
}

template <class T>
T pow_mod(T a, T n, T m) {
    T r = 1;

    while (n > 0) {
        if (n & 1)
            r = mul_mod(r, a, m);
        a = mul_mod(a, a, m);
        n >>= 1;
    }
    return r;
}

根据您使用的类型和值，这个可能仍然会溢出，但是对于给定的类型，它会为比天真的值多的值产生正确的结果版本。

另请注意，这会通过重复平方来求幂，这使得它在处理更大的数字时更加实用(基本上，它是 O(log N) 而不是 O(N)，N=模数)。

我在 another answer 中发布了一个更完整的实现.