Is there a reason this is wrong?

Solution 1:

The decrypt (and encrypt) function is broken in that it (a) is exceeding platform representation of int, and (b) is unnecessarily using pow to do it in the first place.

In your trivial example you should be utilizing a technique called modulo chaining . The crux of this is the following.

(a * b) % n == ((a % n) * (b % n)) % n

In your case, you're performing simple exponentiation. That means, for example a^2 % n would be:

(a * a) % n = ((a % n) * (a % n)) % n

Similarly, a^3 % n is:

(a * a * a) % n = (((a % n) * (a % n)) % n) * (a % n)) % n

Using modulo chaining allows you to compute what would otherwise be very large product computation mod some N, so long as no product term pair exceeds your platform representation (and it doesn't in your case).

A trivial version of integer pow that does this is below:

int int_pow_mod(int c, int d, int n)
{
    int res = 1;

    // may as well only do this once
    c %= n;

    // now loop.
    for (int i=0; i<d; ++i)
        res = (res * c) % n;

    return res;
}

Understand, this is no silver bullet. You can easily contrive a c that still produces a product exceeding INT_MAX, but in your case, that won't happen due to your choices of starting material. A general solution will employ this with a big-number library that allows exceeding platform int representation. Regardless, doing that should deliver what you seek, as shown below:

#include <iostream>
using namespace std;

unsigned int gcd(unsigned int a, unsigned int b)
{
    if (a == 0)
        return b;
    return gcd(b % a, a);
}

int phi(unsigned int n)
{
    unsigned int result = 1;
    for (unsigned int i = 2; i < n; i++)
        if (gcd(i, n) == 1)
            result++;
    return result;
}

int gen_priv_n(int p1, int p2)
{
    int n = phi(p1) * phi(p2);
    return n;
}

int gen_pub_n(int p1, int p2)
{
    int n = (p1 * p2);
    return n;
}

int gen_priv_key(int n, int e)
{
    int x = (phi(e) * n + 1) / e;
    return x;
}

int int_pow_mod(int c, int d, int n)
{
    int res = 1;

    // may as well only do this once
    c %= n;

    // now loop.
    for (int i=0; i<d; ++i)
        res = (res * c) % n;

    return res;
}

int encrypt(int n, int e, int data)
{
    int crypt_data = int_pow_mod(data, e, n);
    return crypt_data;
}


int decrypt(int c, int d, int n)
{
    int data = int_pow_mod(c, d, n);
    return data;
}

int main()
{
    int ph1 = 53;
    int ph2 = 59;
    int e = 3;
    int message = 89;

    int pub_n = gen_pub_n(ph1, ph2);
    cout << "PUBN " << pub_n << "\n";
    int priv_n = gen_priv_n(ph1, ph2);
    cout << "PRIVN " << priv_n << "\n";
    int d = gen_priv_key(gen_priv_n(ph1, ph2), e);
    cout << "PRIVKEY " << d << "\n";
    int c = encrypt(pub_n, e, message);
    cout << "ENCRYPTED " << c << "\n";
    int data = decrypt(c, d, pub_n);
    cout << "MESSAGE " << data;
}

Output

PUBN 3127
PRIVN 3016
PRIVKEY 2011
ENCRYPTED 1394
MESSAGE 89