Search code examples
c++encryptionkeyrsamodulo

RSA encryption breakes when M^e mod(N) = 0 (C++). How to fix?


Currently trying to implement RSA encryption in c++ and running into an issue with the encrypted message.

If we take p = 2, q = 7 then N = 14 and phi = 6. e is forced to be 5 and d can be a variety of numbers but lets take the first applicable from the list d = 11. Now suppose the asccii message to encrypt is "b".

b in asccii is 98 and if we encrypt this with e = 5, N = 14 then 98^5 mod(14) = 0 the resulting encrypted message is 0. Now if we try to decrypt with d = 11 or any d for that matter, 0^d mod14 = 0 gives that the original message was 0 or NULL which is not true.

How can this be solved so that any message can be encrypted and decrypted without loss of characters for which M^5 mod14 is 0?

In the code we get the already encrypted data and turn it into a vector of asccii values:

#define ull unsigned long long int

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

Then decrypt is called

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);
    }
}

But I dont think the issue lies with the code but with the mathematics as shown when M^e mod(N) = 0


Solution

  • As commented by @President James K. Polk,

    With RSA the plaintext must be less than the modulus. And don't use p=2, use only odd primes.