RSA Decryption Failure

Question

I'm trying to implement the RSA encryption scheme, but while my encrypted values seem to be correct the decrypted ones are not. Based on the values of p, q, etc that I am getting it seems that the calculation part (IE, the hard part) is fine, and the message seems to be encrypting correctly (just in case I'm including the encryption part as well though). Note that I am supposed to do this without any libraries (I've already written it using GMP), so that's why I'm using impractically small numbers.

int main()
{
    ...
    vector<uint64_t> encrypted = doEncrypt(e, n);
    doDecrypt(d, n, encrypted);
}
vector<uint64_t> doEncrypt(unsigned int e, unsigned int n)
{
    string message;
    vector<uint64_t> encrypted;
    cout << "Public key is <" << e << ", " << n << ">.\nPlease enter a message to encrypt: ";
    getline(cin, message);
    for (unsigned int i = 0; i < message.length(); i++)
        encrypted.push_back(encrypt(message[i], e, n));
    return encrypted;
}
uint64_t encrypt(char message, unsigned e, unsigned int n)
{
    int toencrypt = (int)message;
    cout << toencrypt << ' ';
    uint64_t result = pow64(toencrypt, e);
    return result%n;
}
void doDecrypt(unsigned int d, unsigned int n, vector<uint64_t> encrypted)
{
    cout << "Encrypted message is: ";
    for (unsigned int i = 0; i < encrypted.size(); i++)
    cout << encrypted[i] << ' ';
    cout << "\nDecrypted message is: ";
    char out;
    for (unsigned int i = 0; i < encrypted.size(); i++){
        decrypt(out, encrypted[i], d, n);
        cout << out << ' ';//This is only for diagnostics, I will
                       //take out the printing of the decrypted
                       //number and space later
    }
    cout << endl;
}

void decrypt(char& decrypted, uint64_t message, unsigned int d, unsigned int n)
{
    uint64_t decrypt = (pow64(message, d)%n);
    cout << decrypt;
    decrypted = (char)decrypt;
}

uint64_t pow64(uint64_t base, unsigned int ex)
{
    uint64_t back = 1;
    for (unsigned int i = 0; i < ex; i++)
        back = back * base;
    return back;
}

Example output:

p = 23
q = 23
n = 529
phi_n = 484
e = 9
d = 269
Public key is <9, 529>.
Please enter a message to encrypt: dog
100 111 103 Encrypted message is: 515 33 295
Decrypted message is: 523 417▒ 364l

Answer 1

Your problem is that p == q, so n is a perfect square rather than a product of two primes, which means your calculation of phi(n) is wrong. phi(p^2) == p * (p-1) where p is a prime. So If you change your code to use phi(n) == 506 and d == 225, it should work.

Or chose a different p and q.

Another pitfall to worry about when testing your code with small primes -- encryption/decryption will fail if your plaintext value is a multiple of p or q. This is exceedingly unlikely to happen when using real values (256 bits or more) for p and q, but can happen by accident with such small values. The probability of hitting this problem is the same as the probability of an adversary randomly guessing your private factors.

A third pitfall that can occur is that the public exponent e you choose must not have any factors in common with phi(n), or no valid d decoding exponent will exist. Again, this is not a concern with 'real' RSA keys, as (p-1)/2 and (q-1)/2 should be prime, so as long as e is odd, the chance of not having a valid decryption key is vanishingly small.

edit

A problem with your code, is that your pow64 routine will overflow easily (515^269 is over 2000 bits). Try using:

uint64_t pow64(uint32_t base, uint32_t ex, uint32_t n)
{
    uint64_t back = 1;
    for (unsigned int i = 0; i < ex; i++)
        back = (back * base) % n;
    return back;
}

Note that I'm restricting the input values to uint32_t, so the intermediate multiplication will never overflow 64 bits. This also very inefficent -- you're much better off squaring the base and going through the exponent one bit at a time:

uint64_t pow64(uint32_t base, uint32_t ex, uint32_t n)
{
    uint64_t back = 1;
    for (uint64_t i = 1; i <= ex; i <<= 1) {
        if (i & ex)
            back = (back * base) % n;
        base = ((uint64_t)base * base) % n; }
    return back;
}