RSA加密遇M^e mod(N)=0失效问题的修复方案咨询（C++）

当选取p=2、q=7时，计算得N=14，φ=6，公钥e=5，私钥d=11。加密ASCII码为98的字符"b"时，98^5 mod(14)结果为0，解密0^11 mod14仍为0，无法还原原消息。相关代码片段如下：

#define ull unsigned long long int

void dataToAscii() {
    asciiVec = {};
    for (wchar_t c: dataString) {
        asciiVec.push_back((ull) c);
    }
}

void decrypt(){
    std::vector<ull> decrypted;
    for (int i=0;i<= this->asciiVec.size()-1;i++) {
        decrypted.push_back(modPow((ull)this->asciiVec.at(i), (ull)privateKey.at(0), (ull)privateKey.at(1)));
    }
    deAsciiVec = decrypted;
    deAscciiToData();
}

void deAscciiToData() {
    deDataString = "";
    for (ull el:deAsciiVec) {
        deDataString.push_back((wchar_t) el);
    }
}

问题根源并非代码实现，而是M^e mod(N)=0时的数学逻辑问题，请问如何解决该问题以实现任意消息的正常加解密？

解决方案 #

1. 严格遵循RSA密钥生成规范 #

RSA的核心前提是消息M必须与N互质，同时密钥生成阶段需满足：

• p和q必须是足够大的素数（实际场景中至少1024位，绝对不能用2这类极小素数）
• e需满足1 < e < φ(N)且gcd(e, φ(N))=1

你的案例中N=14，消息98和14的最大公约数是14（不互质），导致M是N的倍数，加密后必然为0，无法还原。这属于违反RSA基本前提的情况，解决方式是：
更换符合规范的密钥对，比如选p=11、q=13，此时N=143，φ=120，选e=7，计算得d=103，此时98和143互质，加密98^7 mod143的结果解密后可正常还原98。

2. 对消息进行预处理 #

如果必须支持与N不互质的消息，可采用两种标准处理方式：

• 分块处理：将消息拆分为小于N且与N互质的小块，比如N=14时，消息块最大取13，同时排除2、7等与14不互质的数值。
• 添加填充：使用PKCS#1 v1.5或OAEP这类标准填充方案，这是实际RSA实现的通用做法，既解决了消息与N不互质的问题，还能提升加密安全性。

3. 代码层面补充校验逻辑 #

可以在加密前添加互质性校验，提前拦截不符合要求的消息：

bool isCoprime(ull a, ull b) {
    while(b != 0) {
        ull temp = b;
        b = a % b;
        a = temp;
    }
    return a == 1;
}

void encrypt() {
    // 加密前检查每个消息块是否与N互质（privateKey.at(1)对应N）
    for (ull m : asciiVec) {
        if (!isCoprime(m, privateKey.at(1))) {
            throw std::invalid_argument("消息块与N不互质，无法直接加密，请先做预处理");
        }
    }
    // 执行后续加密逻辑
}

内容的提问来源于stack exchange，提问作者Mori